# How to give a combinatorial proof for this forumula

I need to give a combinatorial argument that $$S(n,m) = \sum_{i =0} ^{n-1} {n -1 \choose i} S(i,m-1)$$

Where $S(n,m)$ is the Stirling numbers of the second kind.

Here is my attempt.

Well first thing to know here is that $S(n,m)$ is the number of ways to distribute $n$ distinct among $m$ non empty identical containers.

So If by somehow I managed to show that the right hand side of the above equation mean the same thing then I am done right !

Now for $0 \leq i \leq n-1$, let $i$ count the number of distinct objects that we actually distribute (The number of objects that got distributed from $n-1$ objects). This number of distinct objects can be chosen in ${n-1 \choose i}$ ways, Now the number of ways that we can distribute those $i$ objects among $m-1$ non empty identical container is ${n-1 \choose i} S(i,m-1)$.

But if we kept doing that we will get $S(n-1,m-1)$ and not $S(n,m)$.

I feel like I am missing something here, and something is wrong with my reasoning. How do I proceed with this proof or re correct it.

Say that the objects being distributed are the integers $1,2,\ldots,n$. Let $i$ be the number of objects that are not in the same container as $n$. Then $0\le i\le n-1$, there are $\binom{n-1}i$ ways to choose those $i$ objects, and there are $S(i,m-1)$ ways to distribute them amongst the remaining $m-1$ containers.
• ahaa, and so in total there are ${n-1 \choose i} S(i,m-1)$ ways to distribute those $i$ objects (that are not in the same container as n)) among $m-1$ identical containers. And here we have $m-1$ because we are not counting the container that $n$ is inside it right? But I have a question. Fixing this $n$ and doing this for all other $n-1$ objects will be the same as $S(n,m)$ ? is that correct ? thanks – alkabary Oct 6 '15 at 17:48
• @alkabary: Yes, you’re understanding correctly. Remember, the containers are identical, so it doesn’t matter which one $n$ is in; it’s identified only by the fact that $n$ is in it. That’s why we can fix it. – Brian M. Scott Oct 6 '15 at 17:53