0
$\begingroup$

We want to determine the number of ways that 10 distinct pieces of candy can be placed into 2 identical bags with each bag getting at least 1 piece.
As we know the answer is $S(10,2)$, where $S$ stands for Stirling number of the second kind.
I thought that we can start by choosing two candies out 10 to put each one in a bag, so we will have that each bag is nonempty. Then, the remaining 8 candies will either be put in a single bag or put in the two bags (meaning each bag gets at least one candy out of 8) and that can be done in $S(8,2)$ ways. And finally, I get $S(10,2)= \binom {10}{2} \left( S(8,1) + S(8,2) \right) $.
I know that the result I get is wrong, because from the tables of the Stirling numbers $S(10,2)$ is $511$. But the reasoning seems to me correct!!! Where is the problem with my reasoning?

Improve this question
$\endgroup$
1
$\begingroup$

Suppose there are 4 candies and 2 bags. let the candies be $1,2,3,4.$ Choose $2$ perhaps $\color{red}1,2.$ Then you place them in different bags and then you distribute the $2$ other candies as $\{3,4\}$ in one bag or $\{3\},\{4\}$ in two different bags. So one of the partitions created on this process is $\{\color{red}{1},3\},\{\color{red}{2},4\}.$

Notice that you could have chosen $\color{red}{3,4}$ instead of $1,2$ and so here also you will end up with $\{1,\color{red}{3}\},\{2,\color{red}{4}\}.$ In consequence, you are overcounting partitions. You are giving them a color!

Improve this answer
$\endgroup$
  • $\begingroup$ yeah that was really helpful, thank you $\endgroup$ – Math 512 Apr 1 '20 at 20:50
  • $\begingroup$ it would be interesting if I could find a way to subtract the overcounted cases, I will try that $\endgroup$ – Math 512 Apr 1 '20 at 20:52
  • $\begingroup$ Take a look at Jeea's answer(+1) for the way to not overcount. You are welcome! $\endgroup$ – Phicar Apr 1 '20 at 21:14
1
$\begingroup$

Stirling number $S(n,k)$ is concerned with number of different groupings of $n$ entities into $k$ groups.

  1. Suppose that you have $n-1$ items and $k$ groups, then new nth element has to be added to one of the existing $k$ groups, so this will generate some of the required partitions. How many partitions can there be of this kind, well we can choose one out of $k$ groups, so $k \times S(n-1, k)$

  2. Another case can be when you have $n-1$ items and $k-1$ groups, then if we create a group in itself for nth added element, then this will generate partitions different from first case. So this is $S(n-1, k-1)$

Overall recurrence relation comes as

$$S(n, k) = kS(n-1, k) + S(n-1,k-1)$$

Phicar has already pointed out a mistake in your example

Improve this answer
$\endgroup$
  • $\begingroup$ thank you so much $\endgroup$ – Math 512 Apr 1 '20 at 20:56

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.