Stirling numbers of the second kind

Summary.

The Stirling numbers of the second kind,

$$S(n,k)=\left\{\genfrac{}{}{0pt}{}{n}{k}\right\},k,n\in \mathbb{N},1\le k\le n,$$

are a doublyindexed sequence of natural numbers, enjoying a wealth of interestingcombinatorial properties. There exist several logically equivalentcharacterizations, but the starting point of the present entry willbe the following definition:

The Stirling number $S(n,k)$ is the number of ways to partition a setof $n$ objects into $k$ groups.

For example, $S(4,2)=7$ because there are seven ways to partition 4objects — call them a, b, c, d — into two groups, namely:

$$(a)(bcd),(b)(acd),(c)(abd),(d)(abc),(ab)(cd),(ac)(bd),(ad)(bc)$$

Four additional characterizations will be discussed in this entry:

• a recurrence relation

• a generating function related to the falling factorial

• differential operators

• a double-index generating function

Each of these will be discussed below, and shown to be equivalent.

A recurrence relation.

The Stirling numbers of the second kind can be characterized in terms ofthe following recurrence relation:

subject to thefollowing initial conditions:

$$S(n,n)=S(n,1)=1.$$

Let us now show that the recurrence formulafollows from the enumerative definition. Evidently, there is only oneway to partition $n$ objects into $1$ group (everything is in thatgroup), and only one way to partition $n$ objects into $n$ groups(every object is a group all by itself). Proceeding recursively, adivision of $n$ objects $a_1,\mathrm{\dots },a_{n-1},a_n$ into $k$ groupscan be achieved by only one of two basic maneuvers:

• We could partition the first $n-1$ objects into $k$ groups, andthen add object $a_n$ into one of those groups. There are $kS(n-1,k)$ ways to do this.

• We could partition the first $n-1$ objects into $k-1$ groups andthen add object $a_n$ as a new, 1 element group. This gives anadditional$S(n-1,k-1)$ ways to create the desired partition.

The recursive point of view, therefore explains the connection betweenthe recurrence formula, and the original definition.

Using the recurrence formula we can easily obtain a table of theinitial Stirling numbers:

Falling Factorials.

Consider the vector space of polynomials in indeterminate $x$. Themost obvious basis of this infinite-dimensional vector space is thesequence of monomial powers: $x^n,n\in \mathbb{N}.$ However, thesequence of falling factorials:

$$x^{\underset{¯}{n}}=x(x-1)(x-2)\mathrm{\dots }(x-n+1),n\in \mathbb{N}$$

is also a basis, and hence can beused to generate the monomial basis. Indeed, the Stirling numbers ofthe second kind can be characterized as the coefficients involvedin the corresponding change of basis matrix, i.e.

$$x^n=\sum _{k=1}^{n}S(n,k)x^{\underset{¯}{k}}.$$

So, for example,

$$x^4=x+7x(x-1)+6x(x-1)(x-2)+x(x-1)(x-2)(x-3).$$

Arguing inductively, let us prove that this characterization followsfrom the recurrence relation. Evidently the formula is true for$n=1$. Suppose then that the formula is true for a given $n$. Wehave

$$x{x}^{\underset{¯}{k}}=x^{\underset{¯}{k+1}}+k{x}^{\underset{¯}{k}},$$

and hence using the recurrence relation we deduce that

$x^{n+1}$$={\displaystyle \sum _{k=1}^n}S(n,k)x{x}^{\underset{¯}{k}}$

$={\displaystyle \sum _{k=1}^n}\left(kS(n,k)x^{\underset{¯}{k}}+S(n,k+1)\right)x^{\underset{¯}{k+1}}$

$={\displaystyle \sum _{k=1}^{n+1}}S(n,k)x^{\underset{¯}{k}}$

Differential operators.

Let $D_x$ denote the ordinary derivative, applied to polynomials inindeterminate $x$, and let $T_x$ denote the differential operator$x{D}_x$. We have the following characterization of the Stirlingnumbers of the second kind in terms of these two operators:

$${(T_x)}^n=\sum _{k=1}^{n}S(n,k)x^k{(D_x)}^k,$$

where anexponentiated differential operator denotes the operator composed withitself the indicated number of times. Let us show that this followsfrom the recurrence relation. The proof is once again, inductive.Suppose that the characterization is true for a given $n$. We have

$$T_x(x^k{(D_x)}^k)=k{x}^k{(D_x)}^k+x^{k+1}{(D_x)}^{k+1},$$

and hence using the recurrence relation we deduce that

${(T_x)}^{n+1}$$=x{D}_x\left({\displaystyle \sum _{k=1}^n}S(n,k)x^k{(D_x)}^k\right)$

$={\displaystyle \sum _{k=1}^n}S(n,k)\left(k{x}^k{(D_x)}^k+x^{k+1}{(D_x)}^{k+1}\right)$

$={\displaystyle \sum _{k=1}^{n+1}}S(n+1,k)x^k{(D_x)}^k$

Double index generating function.

One can also characterize the Stirling numbers of the second kind interms of the following generating function:

$$e^{x(e^t-1)}=\sum _{n=1}^{\mathrm{\infty }}\sum _{k=1}^{n}S(n,k)x^k\frac{t^n}{n!}.$$

Let us now prove this. Note that the differential equation

$$\frac{d\xi }{dt}=\xi ,$$

admits the general solution

$$\xi =e^{t}x.$$

It follows that for any polynomial $p(\xi )$ we have

$${\exp (t{T}_{\xi })[p(\xi )]|}_{\xi =x}={\sum _{n=0}^{\mathrm{\infty }}\frac{t^n}{n!}{(T_{\xi })}^n[p(\xi )]|}_{\xi =x}=p(e^{t}x).$$

The proof is simple: just take $D_t$ of both sides. To be moreexplicit,

$$D_t\left[p(e^{t}x)\right]=p^{\prime }(e^{t}x)e^{t}x={T_{\xi }[p(\xi )]|}_{\xi =x{e}^t},$$

and that is exactly equal to $D_t$ of the left-hand side. Since thisrelation holds for all polynomials, it also holds for all formal powerseries. In particular if we apply the above relation to $e^{\xi }$,use the result of the preceding section, and note that

$$D_{\xi }[e^{\xi }]=e^{\xi },$$

we obtain

$e^{x{e}^t}$$={{\displaystyle \sum _{n=1}^{\mathrm{\infty }}}{\displaystyle \frac{t^n}{n!}}{(T_{\xi })}^n[e^{\xi }]|}_{\xi =x}$

$={{\displaystyle \sum _{n=1}^{\mathrm{\infty }}}{\displaystyle \sum _{k=1}^n}S(n,k){\displaystyle \frac{t^n}{n!}}{\xi }^k{(D_{\xi })}^k[e^{\xi }]|}_{\xi =x}$

$=e^x{\displaystyle \sum _{n=1}^{\mathrm{\infty }}}{\displaystyle \sum _{k=1}^n}S(n,k)x^k{\displaystyle \frac{t^n}{n!}}$

Dividing both sides by $e^x$ we obtain the desired generatingfunction. Q.E.D.