Show that $$S(n,k) = \sum_{m = k-1}^{n-1} {n-1 \choose m} S(m,k-1) $$

-I was having trouble with this proof in class and my professor suggested to look at it as another proof of the following theorem which states:

-For all $n\ge1$ $$B(n) = \sum_{k=0}^{n-1} {n-1 \choose k} B(k) $$ -Unfortunately I still do not understand how to solve this proof, I do see the similarities in structure although I am brand new to Stirling numbers and am unsure of how this would affect the proof. Any help is appreciated.


It may interest the reader to see how this can be done using generating functions.

Fixing the parameter $k$ we seek to show that $${n\brace k} = \sum_{m=0}^{n-1} {n-1\choose m} {m\brace k-1}.$$

Here we have extended the summation back to zero because the second Stirling number produces zero for those extra values.

Recall the species for set partitions $$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$ which yields the generating function $$G(z, u) = \exp(u(\exp(z)-1)).$$

It follows that the EGF of the LHS is $$\frac{(\exp(z)-1)^k}{k!}.$$

Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that $$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ i.e. the product of the two generating functions is the exponential generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

In the present case we have $A(z)=\exp(z)$ and $$B(z) = \frac{(\exp(z)-1)^{k-1}}{(k-1)!}.$$

Therefore on the RHS we are extracting the coefficient $$(n-1)! [z^{n-1}] \exp(z) \frac{(\exp(z)-1)^{k-1}}{(k-1)!}.$$

Integrating we see that this is $$n! [z^n] \frac{(\exp(z)-1)^{k}}{k!},$$

the same as the LHS as claimed.


$S(n,k)$ is the number of partitions of the set $[n]=\{1,\ldots,n\}$ into exactly $k$ non-empty parts. Suppose that $\mathscr{P}$ is such a partition; then there must be a $P\in\mathscr{P}$ that contains the number $n$.

  • The other $k-1$ parts must contain at least $k-1$ and at most $n-1$ elements of $[n]$; why?

Let $m=|[n]\setminus P|$, the number of elements of $[n]$ that are not in the same part of $\mathscr{P}$ as $n$.

  • Show that there are $\binom{n-1}m$ ways to choose the elements that are not in the same piece as $n$.
  • Show that there are $S(m,k-1)$ ways to divide them into exactly $k-1$ non-empty parts.

Now combine the pieces to get the desired identity.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.