Lah numbers

Lah numbers, sometimes referred to as Stirling numbers of the third kind, are coefficients of polynomial expansions expressing rising factorials in terms of falling factorials.

Unsigned Lah numbers count the number of ways a set of n elements can be partitioned into k non-empty linearly ordered subsets.

Lah numbers are closely related to Stirling numbers of the first & second kinds, and may be derived from them.

Lah numbers obey the identities and relations:

   L(n, 0), L(0, k) = 0 # for n, k > 0
   L(n, n) = 1
   L(n, 1) = n!
   L(n, k) = ( n! *(n - 1)!) / k! * (k - 1)! ) / (n - k)! # For unsigned Lah numbers
     or
   L(n, k) = (-1)**n * ( n! *(n - 1)!) / k! * (k - 1)! ) / (n - k)! # For signed Lah numbers

Task

• Write a routine (function, procedure, whatever) to find unsigned Lah numbers. There are several methods to generate unsigned Lah numbers. You are free to choose the most appropriate for your language. If your language has a built-in, or easily, publicly available library implementation, it is acceptable to use that.

• Using the routine, generate and show here, on this page, a table (or triangle) showing the unsigned Lah numbers, L(n, k), up to L(12, 12). it is optional to show the row / column for n == 0 and k == 0. It is optional to show places where L(n, k) == 0 (when k > n).

• If your language supports large integers, find and show here, on this page, the maximum value of L(n, k) where n == 100.

See also

• Wikipedia - Lah number
• OEIS:A105278 - Unsigned Lah numbers
• OEIS:A008297 - Signed Lah numbers

Related Tasks

• Stirling numbers of the first kind
• Bell numbers

Factor

Works with: Factor version 0.99 development version 2019-07-10

<lang factor>USING: combinators combinators.short-circuit formatting infix io kernel locals math math.factorials math.ranges prettyprint sequences ; IN: rosetta-code.lah-numbers

! Yes, Factor can do infix arithmetic with local variables! ! This is a good use case for it.

INFIX:: (lah) ( n k -- m )

   ( factorial(n) * factorial(n-1) ) /
   ( factorial(k) * factorial(k-1) ) / factorial(n-k) ;

lah ( n k -- m )

   {
       { [ k 1 = ] [ n factorial ] }
       { [ k n = ] [ 1 ] }
       { [ k n > ] [ 0 ] }
       { [ k 1 < n 1 < or ] [ 0 ] }
       [ n k (lah) ]
   } cond ;

"Unsigned Lah numbers: n k lah:" print "n\\k" write 13 dup [ "%11d" printf ] each-integer nl

<iota> [

   dup dup "%-2d " printf [0,b] [
       lah "%11d" printf
   ] with each nl

] each nl

"Maximum value from the 100 _ lah row:" print 100 [0,b] [ 100 swap lah ] map supremum .</lang>

Output:

Unsigned Lah numbers: n k lah:
n\k          0          1          2          3          4          5          6          7          8          9         10         11         12
0            1
1            0          1
2            0          2          1
3            0          6          6          1
4            0         24         36         12          1
5            0        120        240        120         20          1
6            0        720       1800       1200        300         30          1
7            0       5040      15120      12600       4200        630         42          1
8            0      40320     141120     141120      58800      11760       1176         56          1
9            0     362880    1451520    1693440     846720     211680      28224       2016         72          1
10           0    3628800   16329600   21772800   12700800    3810240     635040      60480       3240         90          1
11           0   39916800  199584000  299376000  199584000   69854400   13970880    1663200     118800       4950        110          1
12           0  479001600 2634508800 4390848000 3293136000 1317254400  307359360   43908480    3920400     217800       7260        132          1

Maximum value from the 100 _ lah row:
44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000

Perl 6

Works with: Rakudo version 2019.07.1

<lang perl6>constant @factorial = 1, |[\*] 1..*;

sub Lah (Int \n, Int \k) {

   return @factorial[n] if k == 1;
   return 1 if k == n;
   return 0 if k > n;
   return 0 if k < 1 or n < 1;
   (@factorial[n] * @factorial[n - 1]) / (@factorial[k] * @factorial[k - 1]) / @factorial[n - k]

}

my $upto = 12;

my $mx = (1..$upto).map( { Lah($upto, $_) } ).max.chars;

put 'Unsigned Lah numbers: L(n, k):'; put 'n\k', (0..$upto)».fmt: "%{$mx}d";

for 0..$upto -> $row {

   $row.fmt('%-3d').print;
   put (0..$row).map( { Lah($row, $_) } )».fmt: "%{$mx}d";

}

say "\nMaximum value from the L(100, *) row:"; say (^100).map( { Lah 100, $_ } ).max;</lang>

Output:

Unsigned Lah numbers:  L(n, k):
n\k         0          1          2          3          4          5          6          7          8          9         10         11         12
0           1
1           0          1
2           0          2          1
3           0          6          6          1
4           0         24         36         12          1
5           0        120        240        120         20          1
6           0        720       1800       1200        300         30          1
7           0       5040      15120      12600       4200        630         42          1
8           0      40320     141120     141120      58800      11760       1176         56          1
9           0     362880    1451520    1693440     846720     211680      28224       2016         72          1
10          0    3628800   16329600   21772800   12700800    3810240     635040      60480       3240         90          1
11          0   39916800  199584000  299376000  199584000   69854400   13970880    1663200     118800       4950        110          1
12          0  479001600 2634508800 4390848000 3293136000 1317254400  307359360   43908480    3920400     217800       7260        132          1

Maximum value from the L(100, *) row:
44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000