1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ But my answer to a) was $\binom{24}{15}$. I also don't understand why you would a another 10 bar to your line, as we only have a total of 15 bars available. $\endgroup$ – NoBackingDown Dec 9 '14 at 10:28
  • $\begingroup$ @Dominik Dear Friend. $ \begin{pmatrix}24 \\9 \end{pmatrix} $is equal to $ \begin{pmatrix}24 \\15 \end{pmatrix} $. And I add 10 another bars because in my partition, every child is given at least 1 chocolate bars which is different to settings in a). So I add 10 bars to line and subtract 1 bars for every child. I just give you an example. In one partition with 25 bars, Child 1 gets 2 bars and Child 2 gets 1 bars. So in real distribution, I give Child 1 $(2-1)$ bars and Child 2 $(1-1)$ bars. So that minimum number that each child can get can be reduced to 0 $\endgroup$ – NalRa Dec 9 '14 at 10:44
  • $\begingroup$ Okay, I got it. $\endgroup$ – NoBackingDown Dec 9 '14 at 10:58
  • $\begingroup$ any idea about c) and d) ? $\endgroup$ – NoBackingDown Dec 9 '14 at 11:32
0
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.