Stirling numbers. Combinatorial proof.

Question

Please, help!

What is the combinatorial proof of the following identity about signless Stirling numbers of the first kind, $c(n,k)$.

$$\binom {i+j}{j} c(n,i+j) = \sum\limits_{k=0}^{n} \binom nk c(k,i) c(n-k, j)$$

Answer 1

The number $c(n,k)=\genfrac[]0{}nk$ counts the permutations of an $n$-set which have $k$ cycles.

Both sides of your equation now count the ways to colour $n$ points red or blue, and defining a colour-preserving permutation that has $i$ cycles on the red points and $j$ cycles on the blue points. The right hand side describes the number of choices when done in that order, choosing some $k$-subset of red points with $0\leq k\leq n$, and then separately choosing a permutation of the red points with $i$ cycles and a permutation with $j$ cycles of blue points. The left hand side counts the number of choices when first choosing a permutation with $i+j$ cycles, and then selecting an $i$-subset of those $i+j$ cycles whose elements are to be coloured red.