Stirling numbers of the second kind

Stirling numbers of the second kind, or Stirling partition numbers, are the number of ways to partition a set of n objects into k non-empty subsets. They are closely related to Bell numbers, and may be derived from them.

Stirling numbers of the second kind obey the recurrence relation:

   S2(n, 0) and S2(0, k) = 0 # for n, k > 0
   S2(n, n) = 1
   S2(n + 1, k) = k * S2(n, k) + S2(n, k - 1)

Task

• Write a routine (function, procedure, whatever) to find Sterling numbers of the second kind. There are several methods to generate Sterling numbers of the second kind. 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 Stirling numbers of the second kind, S2(n, k), up to S2(12, 12). it is optional to show the row / column for n == 0 and k == 0. It is optional to show places where S2(n, k) == 0 (when k > n).

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

See also

• Wikipedia - Stirling numbers of the second kind
• OEIS:A008277 - Stirling numbers of the second kind

Related Tasks

• Stirling numbers of the first kind
• Bell numbers
• Lah numbers

Factor

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

<lang factor>USING: combinators.short-circuit formatting io kernel math math.extras prettyprint sequences ; RENAME: stirling math.extras => (stirling) IN: rosetta-code.stirling-second

! Tweak Factor's in-built stirling function for k=0

stirling ( n k -- m )

   2dup { [ = not ] [ nip zero? ] } 2&&
   [ 2drop 0 ] [ (stirling) ] if ;

"Stirling numbers of the second kind: n k stirling:" print "n\\k" write 13 dup [ "%8d" printf ] each-integer nl

<iota> [

   dup dup "%-2d " printf [0,b] [
       stirling "%8d" printf
   ] with each nl

] each nl

"Maximum value from the 100 _ stirling row:" print 100 <iota> [ 100 swap stirling ] map supremum .</lang>

Output:

Stirling numbers of the second kind: n k stirling:
n\k       0       1       2       3       4       5       6       7       8       9      10      11      12
0         1
1         0       1
2         0       1       1
3         0       1       3       1
4         0       1       7       6       1
5         0       1      15      25      10       1
6         0       1      31      90      65      15       1
7         0       1      63     301     350     140      21       1
8         0       1     127     966    1701    1050     266      28       1
9         0       1     255    3025    7770    6951    2646     462      36       1
10        0       1     511    9330   34105   42525   22827    5880     750      45       1
11        0       1    1023   28501  145750  246730  179487   63987   11880    1155      55       1
12        0       1    2047   86526  611501 1379400 1323652  627396  159027   22275    1705      66       1

Maximum value from the 100 _ stirling row:
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674

Perl 6

Works with: Rakudo version 2019.07.1

<lang perl6>sub Stirling2 (Int \n, Int \k) {

   ((1,), { (0, |@^last) »+« (|(@^last »*« @^last.keys), 0) } … *)[n;k]

}

my $upto = 12;

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

put 'Stirling numbers of the second kind: S2(n, k):'; put 'n\k', (0..$upto)».fmt: "%{$mx}d";

for 0..$upto -> $row {

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

}

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

Output:

Stirling numbers of the second kind: S2(n, k):
n\k      0       1       2       3       4       5       6       7       8       9      10      11      12
0        1
1        0       1
2        0       1       1
3        0       1       3       1
4        0       1       7       6       1
5        0       1      15      25      10       1
6        0       1      31      90      65      15       1
7        0       1      63     301     350     140      21       1
8        0       1     127     966    1701    1050     266      28       1
9        0       1     255    3025    7770    6951    2646     462      36       1
10       0       1     511    9330   34105   42525   22827    5880     750      45       1
11       0       1    1023   28501  145750  246730  179487   63987   11880    1155      55       1
12       0       1    2047   86526  611501 1379400 1323652  627396  159027   22275    1705      66       1

Maximum value from the S2(100, *) row:
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674