Prove the set partition identity via double counting argument $${{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$
 A: 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?
A: 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}.$$
A: This combinatorial identity represents a bicolouring of a partition
\begin{eqnarray*}
\color{red}{(r_{1,1} \cdots ) (r_{2,1} \cdots )\cdots (r_{l,1}\cdots) } \color{blue}{(b_{1,1} \cdots ) (b_{2,1} \cdots )\cdots (b_{m,1}\cdots) }
\end{eqnarray*}
where the red part is of $k$ elements into $l$ blocks & the blue part of $n-k$ elements into $m$ blocks.
Partition $[n]$ into $l+m$ blocks then colour $l$ of the blocks red and $m$ of them blue.
Choose $k$ elements from $[n]$, colour them red and partition them into $l$ blocks. Now colour the other $n-k$ elements blue and partition them into $m$ blocks. Thus
\begin{eqnarray*}
{{n}\brace l+m}\dbinom{l+m}{l}=\sum_{k \in \mathbb{Z}}{{k}\brace l}{{n-k}\brace m}\dbinom{n}{k}.
\end{eqnarray*}
