$$\sum_{j= m}^{n-r} \binom{j}n {j \brace m} {n-j\brace r} = \binom{m} {m+r} {n\brace m+r}$$
I am trying to proof some identies from concrete mathmatics page 265. But i cant get nowhere. No clues where to start, I have found a proof involving Euler's Formula for Stirling Number. The Books gives them: Like here there are not event a hint how to show it. update: Well there is a clue in other book: both sides counting pair $(P_1,P_2)$ with $P_1 (k+r)$ partitions of $\{1,\ldots,n\}$ $P_2$ subfamily of $k$-blocks of $P_1,\ldots$ what ever this means
This combinatorial Identity represents a bicolouring of a partition \begin{eqnarray*} \color{red}{(r_{1,1} \cdots ) (r_{2,1} \cdots )\cdots (r_{m,1}\cdots) } \color{blue}{(b_{1,1} \cdots ) (b_{2,1} \cdots )\cdots (b_{r,1}\cdots) } \end{eqnarray*} where the red partiton is of $k$ elemnets into $m$ blocks & the blue partition of $n-k$ elements into $r$ blocks.
Partition $[n]$ into $k+r$ blocks then colour $k$ of the blocks red and $n-k$ of them blue.
Choose $n-j$ elements from $[n]$, colour them red and partition them into $m$ blocks. Now colour the other $j$ elements blue and partition them into $r$ blocks. Thus \begin{eqnarray*} {{n}\brace r+m}\dbinom{r+m}{m}=\sum_{j =m}^{n-r}{{j}\brace r}{{n-j}\brace m}\dbinom{n}{j}. \end{eqnarray*}