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

Related Tasks

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