2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – alkabary Oct 6 '15 at 17:48
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 6 '15 at 17:53
  • $\begingroup$ Yes, Thank you sooo much ! :) $\endgroup$ – alkabary Oct 6 '15 at 17:55
  • $\begingroup$ @alkabary: You’re welcome! $\endgroup$ – Brian M. Scott Oct 6 '15 at 17:55

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.