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 Stirling numbers of the second kind. There are several methods to generate Stirling 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


BEGIN
    # show some Stirling numbers of the second kind                          #
 
    # specify the precision of LONG LONG INT, somewhat under 160 digits are  #
    # needed for Stirling numbers of the second kind with n, k = 100         #
    PR precision 160 PR
    MODE SINT = LONG LONG INT;
 
    # returns a triangular matrix of Stirling numbers up to max n, max n #
    PROC make s2 = ( INT max n )REF[,]SINT:
    BEGIN
        REF[,]SINT s2 := HEAP[ 0 : max n, 0 : max n ]SINT;
        FOR n FROM 0 TO max n DO FOR k FROM 0 TO max n DO s2[ n, k ] := 0 OD OD;
        FOR n FROM 0 TO max n DO s2[ n, n ] := 1 OD;
        FOR n FROM 0 TO max n - 1 DO
            FOR k FROM 1 TO n DO
                s2[ n + 1, k ] := k * s2[ n, k ] + s2[ n, k - 1 ]
            OD
        OD;
        s2
    END # make s2 # ;
    # task requirements:                                                     #
    # print Stirling numbers up to n, k = 12                                 #
    BEGIN
        INT max stirling = 12;
        REF[,]SINT s2 = make s2( max stirling );
        print( ( "Stirling numbers of the second kind:", newline ) );
        print( ( " k" ) );
        FOR k FROM 0 TO max stirling DO print( ( whole( k, -10 ) ) ) OD;
        print( ( newline, " n", newline ) );
        FOR n FROM 0 TO max stirling DO
            print( ( whole( n, -2 ) ) );
            FOR k FROM 0 TO n DO
                print( ( whole( s2[ n, k ], -10 ) ) )
            OD;
            print( ( newline ) )
        OD
    END;
    # find the maximum Stirling number with n = 100                          #
    BEGIN
        INT max stirling = 100;
        REF[,]SINT s2 = make s2( max stirling );
        SINT max 100 := 0;
        FOR k FROM 0 TO max stirling DO
            IF s2[ max stirling, k ] > max 100 THEN max 100 := s2[ max stirling, k ] FI
        OD;
        print( ( "Maximum Stirling number of the second kind with n = 100:", newline ) );
        print( ( whole( max 100, 0 ), newline ) )
    END
END