# Stirling numbers of the second kind formulae

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?

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!

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

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