There are $85$ different candies and $30$ children in a kindergarden.How many ways are there to distribute $85$ different candies to $30$ children if :
a-)Each children has at least $1$ candy
b-)Each children has at least $2$ candies
$\color{blue}{SOLUTION:}$
$\color{green}{a-)}$ Fisrt assume that all of children are indistinguishable , and distribute candies such that $S(85,30)$ where $\color{blue}{S}$ is Stirling number of second kind.
After dividing these $85$ candies into $30$ pieces , we can give them to $30$ children in $30!$ different ways.
$\color{red}{\therefore}$ $30! \times S(85,30) $
$\color{green}{b-)}$ In this part , I thought that i should firstly give $2$ candies to each of $30$ children by $C(85,60) \times \frac{60!}{(2!)^{30}}$ different ways.
Now , I have $25$ different candies to disperse $30$ children , but i know that i can distribute these candies to at most $25$ children and at least $1$ child.
So , i will choose $25$ children from $30$ children by $C(30,25)$ ways.
Because of the fact that i can give these candies any of $25$ children , i thought that i can do it by $\sum_{i=1}^{25}P(25,i) \times \sum_{i=1}^{25}S(25,i) $ where $S$ is stirling number of second kind.
So , answer is $C(85,60) \times \frac{60!}{(2!)^{30}} \times C(30,25) \times \sum_{i=1}^{25}(P(25,i) \times S(25,i)) $
Are my solutions correct , if not , can you share your knowledge with me. Thanks for all contributions ..
NOTE: This question is inspired from : In how many ways can $50$ sweets be distributed to $30$ children so that each child receives at least one sweet?
NOTE 2 = As you know , children are distinguishable, as well.
$\color{red}{EDIT}$: This edit contains my new solution for part $\color{blue}{b}$
$C(85,2) \times C(83,2) \times … \times C(27,2)$ = $\frac{85!}{25!\times2^{30}}$
So, $\frac{85!}{25!\times2^{30}} \times \sum_{i=1}^{25}(P(25,i) \times S(25,i)) $
Best Answer
I would not assume that the children are indistinguishable: in problems of this kind people are by default assumed to be distinguishable, and there is nothing in the statement of the problem that would override this default. The normal interpretation of this problem is that the children are distinguishable. Whether the candies are distinguishable does need to be stated, as is done here; in most problems of this type at an elementary level they are taken to be indistinguishable, and for completeness I’ll go through that first and then return to other interpretations.
Under the this interpretation (a) is a bog standard stars and bars problem, equivalent to asking for the number of solutions in positive integers to the equation $x_1+x_2+\ldots+x_{30}=85$: here $x_k$ is the number of candies received by the $k$-th child. The answer is $\binom{85-1}{30-1}=\binom{84}{29}$. Under the same interpretation (b) is only a little harder: we first give each child one candy, leaving us with $85-30=55$ to distribute, and then apply the stars and bars approach to determine in how many ways we can give each child at least one of these $55$ candies. The answer to that is $\binom{55-1}{30-1}=\binom{54}{29}$. And that’s all there is to it.
If we make the very implausible assumption that the children are indistinguishable and make the candies distinguishable, then (a) essentially asks for the number of partitions of $[85]$ into $30$ (non-empty) parts. That is exactly what ${85\brace 30}$, the Stirling number of the second kind, counts. Since we are assuming that the children are indistinguishable, we’re done: it doesn’t matter how the parts are permuted. Your figure of ${85\brace 30}30!$ would be correct if both the candies and the children were distinguishable: we first distribute the $85$ candies into $30$ identical boxes, which we can do in ${85\brace 30}$ ways, and then we assign the boxes to the $30$ children, which we can do in $30!$ ways. (Note that once the candies have been distributed to the boxes, the boxes are no longer identical: they can be individually identified by their contents.)
Part (b) is a much harder problem under either of these interpretations. Your calculation is incorrect for either interpretation in which the candies are distinguishable. It appears that your idea is to pick $60$ of the candies and then divide them into $30$ pairs, one pair for each child, after which you will distribute the remaining $25$ candies. There are indeed $\binom{85}{60}$ ways to pick $60$ of the candies, and the number of ways to divide them into pairs is $\frac{60!}{2^{30}\cdot 30!}$ (see this answer for details). If the children are indistiguishable, your idea would stop here with $\binom{85}{60}\frac{60!}{2^{30}\cdot 30!}$. If the children are distinguishable, you would then multiply this by $30!$ to get the number of different ways to distribute the pairs to the children, which would give you your $\binom{85}{60}\frac{60!}{2^{30}}$.
However, neither of these would be correct, because both overcount rather badly. Consider a distribution in which some child gets candies $A,B$, and $C$. This distribution is counted once when we consider $A$ and $B$ to be the initial pair of candies received by this child, once again when we consider $A$ and $C$ to be that initial pair, and a third time when we consider $B$ and $C$ to be that initial pair. We’ve already counted it $3$ times and every child who gets more than $2$ candies will cause further overcounting. And unfortunately there is no simple way to compensate for this overcounting no matter how you deal with the remaining $25$ candies.
The only remaining possibility is that the candies and children are both indistinguishable. In that case we want $p_{30}(85)$, the number of partitions of $85$ indistinguishable objects into $30$ parts, and there is no nice formula for that. Under this interpretation (b) turns out to be another problem of the same kind. To partition $85$ into $30$ parts, each of size at least $2$, we can partition $55$ into $30$ non-empty parts and then add $1$ to each part, and the number of ways to partition $55$ into $30$ non-empty parts is $p_{30}(55)$.