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


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


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.