# Combinatorial Proof of $\binom{i+j}{j}S(n, i+j) = \sum_{k=0}^{n}\binom{n}{k}S(k,i)S(n-k,j)$

I would like to prove the following statements:

$\binom{i+j}{j}S(n, i+j) = \sum_{k=0}^{n}\binom{n}{k}S(k,i)S(n-k,j)$

combinatorially.

(where $\;S(i,j),\;i,j\in \Bbb Z\;$ denotes the Stirling number of the second kind, put labelled $j$ entities into $i$ unlabeled classifications)

I looked over related Wikipedia pages and checked over some recurrence identities of Stirling numbers of the second kind, however, there's no recurrences that decompose $S$ into two different $S$s.

Moreover, I need to understand combinatoric understanding behind this identity which is the final goal of mine.

Any advice where to start from? (maybe Pascal's triangle?)

HINT: Show that this is the number of ways to put $n$ labelled objects into $i$ red boxes and $j$ blue boxes. For the full combinatorial argument, hover below:
We can count these in two ways: first, just put $n$ objects into $i + j$ uncolored boxes, and then choose which boxes will be colored blue. This corresponds to $S(n,i+j)\cdot\binom{i+j}{j}$ The second way is to start with $i$ and $j$ red boxes, and let $k$ be the number put into red boxes. So we have to sum over $k$, choose which $k$ elements go in red boxes, and then put the $k$ elements in the $i$ red boxes and $n-k$ elements in the $j$ blue boxes. This is the right hand side.
• It looks like you meant to say $i$ red and $j$ blue boxes. – N. F. Taussig Dec 20 '19 at 11:57