Show that $S(n ,k)$...

Question

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.

Answer 1

$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.

Answer 2

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.