Generation of Stirling Numbers of the Second Kind by Polynomials

Kenneth Levasseur
Mathematical Sciences
UMass Lowell
Kenneth_Levasseur@uml.edu

Although the Stirling numbers of both kinds are built into Mathematica, it's fun to generate them yourself!   What are the Stirling numbers of the second kind?

Excerpt from MathWorld

Eric W. Weisstein
October 10, 2005

http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html.

©2005 Wolfram Research, Inc.

The number of ways of partitioning a set of n elements into m nonempty sets is the Stirling Number of the Second Kind, (Subscript[𝒮, n]^((m))). For example, the set {1, 2, 3} can be partitioned into three subsets in one way,  into two subsets in three ways, and and into one subset in one way, so 
	{(Subscript[𝒮, 3]^(("1"))),(Subscript[𝒮, 3]^(("2"))),(Subscript[𝒮, 3]^(("3")))}= {1, 3,  1}

Exercises

0

Observe that for all n,   (Subscript[𝒮, n]^((n)))=1  and (Subscript[𝒮, n]^((1)))=1

1

Prove that if 1 < k < n, then  (Subscript[𝒮, n]^((k))) =(Subscript[k 𝒮, n - 1]^((k)))+ (Subscript[𝒮, n - 1]^((k - 1)))

2

Prove that if (Subscript[s, n])(x) = (∑_(k = 1)^n)(Subscript[𝒮, n]^((k))) (x^(k - 1)), then   (Subscript[s, n])(x)  =  
        x (Subscript[s, n - 1])(
              x)  +  (d/(d x)) (  x (Subscript[s, n - 1])(
                  x) )

Generation of Stirling Numbers of the Second Kind

Definition of (Subscript[s, n]) using the recursion in exercise 2.

s[1, x] = 1;
s[n_, x_] := s[n, x] = 
        Expand[x s[n - 1, x] +  D[x s[n - 1, x], x]]

s[3, x]

s[6, x]

Verificaton that the these polynomials really generate the Stirling numbers of the 2nd kind for n = 10, in case you don't believe the proof of exercise 2.

Table[StirlingS2[10, k], {k, 1, 10}] == 
      CoefficientList[s[10, x], x]

Stirling's 2nd Triangle:

Map[CoefficientList[s[#, x], x] &, Range[1, 12]] // 
      TableForm

The number of partitions of  an n-element set ( see  Bell numbers:  http://www.research.att.com/~njas/sequences/A000110)

Table[{n, s[n, x]}, {n, 1, 12}] /. {x -> 1}