How many ways are there to distribute $85$ different candies to $30$ children if each children has at least $2$ candies

Question

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

Answer 1

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

Answer 2

Under the assumption that the candies are distinguishable, I would attack part (a) of the question as follows: [note that part (b)] is much more difficult].

Using Inclusion-Exclusion

$$\sum_{k=0}^{29} (-1)^k \binom{30}{k} f(k).$$

Here, $f(k)$ represents the number of ways that at least $k$ children got no candy. Note that $f(30)$ must equal $0$, since all $(85)$ candies must be distributed. Therefore, it is impossible that all $(30)$ children got no candy.

Constructing $f(k)$ takes some analysis.

$f(0)$ represents that the $(85)$ candies were distributed unconstrained, so $f(0) = (30)^{(85)}.$

$f(1)$ represents that 1 child was selected to get no candy, and there may have been other children who also got no candy. Therefore $f(1) = (29)^{(85)}$.

From this, it is clear that for $k \in \{2,3,\cdots,29\},$
$f(k) = (30-k)^{(85)}.$

This completes part (a).

---

For part (b), my first thought was to somehow piggyback off of the answer to part (a). No joy trying that. Further, it is clear that part (b) will also require Inclusion-Exclusion. So the answer to part (b) will be

$$\sum_{k=0}^{29} (-1)^k \binom{30}{k} g(k).$$

Here, for $k \in \{0, 1, \cdots, 29\}, ~g(k)~$ represents having exactly $k$ children pre-selected, having each of the $k$ children get either no candy or 1 candy, and having the remaining candy distributed among the $(30-k)$ people.

Again, clearly, $g(0)$, which represents totally unconstrained distribution, equals $(30)^{(85)}.$

For $g(1)$, assume that Person-1 has been chosen to receive either $(0)$ or $(1)$ candy. As in part (a), the number of ways that Person-1 can receive no candy is $(30 - 1)^{(85)}.$

For enumerating the number of ways that Person-1 can receive exactly $(1)$ candy:

There are $\binom{85}{1} = 85$ ways of choosing which candy Person 1 gets.

Then, there are $(29)^{84}$ ways of distributing the remaining candies in unconstrained fashion, among the other $(29)$ people.

Therefore,

$$g(1) = \left[(30 - 1)^{(85)}\right] + \left[\binom{85}{1} \times (29)^{84}\right].$$

Now consider $g(2)$.

For $r \in \{0,1,2\}$, let $(r)$ represent that of the $(2)$ people, exactly $(r)$ of them got no candy, and the remaining $(2-r)$ people got exactly 1 candy each.

Then $g(2) = \sum_{r=0}^2 h(r).$

Here, if $(r)$ people got no candy, and $(2-r)$ people got 1 candy each, then the $(2)$ people consumed $(2-r)$ candies, and $[85 - (2-r)]$ candies were left to be distributed among the $(30-2)$ people, in an unconstrained fashion.

There are $\binom{2}{r}$ ways of selecting the $r$ people who got no candy.

Then, there are $\frac{85!}{[85 - (2-r)]!}$ ways of distributing $(1)$ candy each to the $(2-r)$ people.

Then, there are $(30-2)^{[85 - (2-r)]}$ ways of distributing the remaining candy to the remaining people.

Therefore, focusing on $g(2)$, you have that

$$h(r) = \binom{2}{r} \times \frac{85!}{[85 - (2-r)]!} \times (30-2)^{[85 - (2-r)]}.$$

Therefore,

$$g(2) = \sum_{r=0}^2 h(r).$$

Fortunately, the method chosen to compute $g(2)$ generalizes nicely for $k \in \{3,4, \cdots, 29\}.$

That is,

$$g(k) = \sum_{r=0}^k \binom{k}{r} \times \frac{85!}{[85 - (k-r)]!} \times (30-k)^{[85 - (k-r)]}.$$

This completes part (b).

Answer 3

As you have already solved part (a) on your own, I will focus on part (b). Given any method you go for, it would require some serious computation. So my suggestion will be to use exponential generating function as that is easiest to set up and easier to compute online too. In fact WolframAlpha Basic will not even compute result for this question using P.I.E given large numbers. But it will return a result using generating function.

If candies are different and a child can receive no candy or any number of candies subject to number of candies there are, its generating function can be written as expansion of $e^x$ and if there are $n$ candies in total, we can restrict it to $n+1$ terms as $ \displaystyle \sum \limits_{k=0}^n \frac{x^k}{k!}$.

Now if a child must have at least one candy, we need to take out zero term from the generating function. So it is given by $ \displaystyle \sum \limits_{k=1}^n \frac{x^k}{k!}$.

So if there are $m$ children and all of them must have at least one candy each ($n \geq m$) then the generating function can be written as,

$ \displaystyle \bigg(\sum \limits_{k=1}^n \frac{x^k}{k!} \bigg)^m$.

Let's now go ahead and set up generating function for this question given each child must have at least $2$ candies, there are $85$ candies and there are $30$ children -

$ \displaystyle \bigg(\sum \limits_{k=2}^{85} \frac{x^k}{k!} \bigg)^{30}$.

But we note that as each child gets at least two candies, no child can get more than $27$ candies. So we can simplify it as,

$ \displaystyle \bigg(\sum \limits_{k=2}^{27} \frac{x^k}{k!} \bigg)^{30}$

So to find number of ways to distribute with given constraint, we need coefficient of $ \displaystyle \frac{x^{85}}{85!}$ or we find coefficient of term $ \displaystyle x^{85}$ and multiply the result by $85!$. Here is what you can plug into WolframAlpha to get the result.

coefficient $[(\sum \limits_{k=2}^{27} \frac{x^k}{k!})^{30}, x, 85] \times 85!$