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