Number of possible ways to distribute 15 chocolate bars among 10 children

Question

(Introduction to Probability, Blitzstein and Nwang, p. 39)

There are 15 chocolate bars and 10 children. In how many ways can the chocolate bars be distributed to the children, in each of the following scenarios?

(a) The chocolate bars are fungible (interchangeable).

(b) The chocolate bars are fungible, and each child must receive at least one. Hint: First give each child a chocolate bar, and then decide what to do with the rest.

(c) The chocolate bars are not fungible (it matters which particular bar goes where).

(d) The chocolate bars are not fungible, and each child must receive at least one. Hint: The strategy suggested in (b) does not apply. Instead, consider randomly giving the chocolate bars to the children, and apply inclusion-exclusion.

My solutions:

a) I'm imagining for each chocolate bar to randomly sample from the children with replacement, with order not mattering. This would yield $\binom{10+15-1}{15}$ possibilities.

b) Now I first choose one chocolate bar for each child, and then I do the same as in a) with the remaining 5 bar, so I get $\binom{15}{10} \binom{10+5-1}{5}$ possibilities.

EDIT I'm ignoring here that the bars are exchangeable, so it should be only $\binom{10+5-1}{5}$. Or said differently, there is only one way to give a bar to each child.

c) I think this is sampling with replacement where order matters, so $10^{15}$ possible sequences.

d)

\begin{align} \Omega &:= \lbrace s|s \text{ is a 15 digit number with digits form [1-10]}\rbrace \\ A_i &:=\lbrace s \in \Omega | s \text{ contains at least (one or more) i's} \rbrace \\ \neg A_i &= \Omega \setminus A_i \\ |\Omega| &= 10^{15} \\ |\neg A_i| &= 9^{15} \\ |\neg A_i \cap \neg A_j| &= 8^{15} \\ \text{etc.} \end{align}

\begin{equation} \text{Possibilities that each childs gets at least one bar} = \sum_{i=0}^{i=10} \binom{10}{i} (10-i)^{15} (-1)^i \end{equation}

Are those results correct? I'm not quite sure about a) and b), since I think the number of possibilities in b) should be less than in a).

Answer 1

I have a different view of your question. I will focus on question b). Firstly, we put all the chocolate bars in a line. Because all the bars are interchangeable, there is only one way to line them up(it's $15!$ ways if bars are different from each other). Just like this: $$ 0\;0 \;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0 $$ Then we can cut 9 lines to divide the bars line into 10 parts and give the first part to first child, second part to second child and so on. Here is one example for partition: $$ 0\;|0 \;|0\;0\;|0\;|0\;|0\;|0\;0\;0\;|0\;0\;|0\;0\;|0 $$ One advantage of this partition is that we can guarantee that each students will receive at least one chocolate.

We are looking for 9 places to cut and (15-1) places are available. So the total number of partitions is $ \begin{pmatrix}14 \\9 \end{pmatrix} $.

This solution can be also applied to question a). But we need to add another 10 bars in the line, and subtract 1 bars for each child. The number of partitions in this setting is $ \begin{pmatrix}24 \\9 \end{pmatrix} $ which is the same as your answer.

Answer 2

A comment on your b) answer. (Due to it being indistinguishable chocolate bars) Look at it from the aspect of not having any excess first, so you only have the amount of candy bars as children. So to give each child a candy bar will equal out to 1 possible way or (10 choose 10), then choose what to do with the rest.

${10 \choose 10}* {10 + 5 - 1 \choose 5} = 2002$

or

${14 \choose 5}= 2002$

Answer 3

For part c) yes you have a set of 15 that involves all possible combinations. so each child has 15 possibilities of getting assigned candy hence $10^{15}$ is correct. yes part d) is correct.