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