46.5 Stirling2

Stirling2( n, k )

Stirling2 returns the Stirling number of the second kind S_2(n,k) of the integers n and k. Stirling numbers of the second kind are defined by S_2(0,0) = 1, S_2(n,0) = S_2(0,k) = 0 if n, k <> 0 and the recurrence S_2(n,k) = k S_2(n-1,k) + S_2(n-1,k-1).

S_2(n,k) is the number of ways to partition a set of n elements into k pairwise disjoint nonempty subsets (see PartitionsSet). Stirling numbers of the second kind appear as coefficients in the expansion of x^n = sum_{k=0}^{n}{S_2(n,k) k! {x choose k}}. Note the similarity to n! {x choose n} = sum_{k=0}^{n}{S_1(n,k) x^k} (see Stirling1). Also the definition of S_2 implies S_2(n,k) = S_1(-k,-n) if n,k<0. There are many formulae relating Stirling numbers of the second kind to Stirling numbers of the first kind, Bell numbers, and Binomial numbers.

    gap> List( [0..4], k->Stirling2( 4, k ) );
    [ 0, 1, 7, 6, 1 ]    # Knuth calls this the trademark of $S_2$
    gap> List( [0..6], n->List( [0..6], k->Stirling2( n, k ) ) );;
    gap> PrintArray( last );
    [ [   1,   0,   0,   0,   0,   0,   0 ],    # Note the similarity with
      [   0,   1,   0,   0,   0,   0,   0 ],    # Pascal\'s triangle for
      [   0,   1,   1,   0,   0,   0,   0 ],    # the Binomial numbers
      [   0,   1,   3,   1,   0,   0,   0 ],
      [   0,   1,   7,   6,   1,   0,   0 ],
      [   0,   1,  15,  25,  10,   1,   0 ],
      [   0,   1,  31,  90,  65,  15,   1 ] ]
    gap> Stirling2( 50, 10 );
    26154716515862881292012777396577993781727011 

Previous Up Top Next
Index

GAP 3.4.4
April 1997