# Prove that Stirling numbers satisfy the identity $\sum_{m} \binom {n}{m}S(m,k)S(n-m,l)= \binom{k + l}{l}S(n,k + l)$

$$\sum_{m} \binom {n}{m}S(m,k)S(n-m,l)= \binom{k + l}{l}S(n,k + l)$$. How do I give a combinatorial proof of this identity?

My attempt:

LHS: choose m elements out of $$n$$ total elements then partition $$m$$ into $$k$$ and the rest into $$l$$.

RHS: partition n elements into $$k + l$$ boxes, then from the boxes choose $$l$$ elements to be special.

## 1 Answer

If you are interested in an algebraic proof, it can be done as follows. Goal is

$$\sum_{m=k}^{n-l} {n\choose m} {m\brace k} {n-m\brace l} = {k+l\choose l} {n\brace k+l}.$$

The LHS is

$$\sum_{m=k}^{n-l} {n\choose m} m! [z^m] \frac{(\exp(z)-1)^k}{k!} (n-m)! [w^{n-m}] \frac{(\exp(w)-1)^l}{l!}.$$

This is

$$n! [w^n] \frac{(\exp(w)-1)^l}{l!} \sum_{m=k}^{n-l} w^m [z^m] \frac{(\exp(z)-1)^k}{k!}.$$

Now we may extend $$m$$ beyond $$n-l$$ to infinity because if $$m\gt n-l$$ the least power of $$w$$ that appears is $$l+m \gt n$$ (this is due to $$\exp(z)-1 = z + \cdots$$) which does not contribute to the coefficient extractor $$[w^n]$$ in front. We obtain

$$n! [w^n] \frac{(\exp(w)-1)^l}{l!} \sum_{m\ge k} w^m [z^m] \frac{(\exp(z)-1)^k}{k!}.$$

Note that $$(\exp(z)-1)^k$$ starts at $$z^k,$$ so the remaining sum copies the term in $$z$$ to a term in $$w$$ and we find

$$n! [w^n] \frac{(\exp(w)-1)^l}{l!} \frac{(\exp(w)-1)^k}{k!} \\ = n! [w^n] {k+l\choose l} \frac{(\exp(w)-1)^{k+l}}{(k+l)!} \\ = {k+l\choose l} {n\brace k+l}.$$

This concludes the proof. What we have used here is a so-called annihilated coefficient extractor (ACE).