Prove the set partition identity via double counting argument

Question

$${{n}\brace l+m}\dbinom{l+m}{l}=\sum_{k \in \mathbb{Z}}{{k}\brace l}{{n-k}\brace m}\dbinom{n}{k}$$

LHS: gives the ways ways to partition $[n]$ into $l+m$ blocks with $l$ blocks (lets say) underlined.

RHS: lets choose the first $k$ elements and select $l$ elements from it. Then select $m$ elements from the remaining $n-k$ elements. This gives us the partitions. I'm confused about how $\dbinom{n}{k}$ will give the underlined partitions since $k$ can be greater than $l$

Answer 1

I think you've misstated the RHS slightly. Let's break it down:

• Choose the first $k$ elements: $\binom{n}{k}$
• Partition them into $l$ blocks: ${{k}\brace l}$
• Partition the remaining $n-k$ elements into $m$ blocks: ${{n-k}\brace m}$

Does that clear it up?

Answer 2

The reader may be interested in seeing a solution using EGFs. With the Stirling numbers enforcing the range we may write for the RHS

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

Now observe that we may extend $k$ beyond $n$ to infinity because there is no contribution to the coefficient extractor $[w^n]$ when $k\gt n.$ We find

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