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)$


(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.

  • $\begingroup$ It looks like you meant to say $i$ red and $j$ blue boxes. $\endgroup$ – N. F. Taussig Dec 20 '19 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.