Combinatorics question involving distributing DISTINCT candies to DISTINCT children

combinationscombinatorics

Suppose you want to distribute 15 DISTINCT candies to 5 DISTINCT children: A, B, C, D and E.

a) In how many ways can this be done (no restrictions)?

b) In how many ways can this be done if each kid gets at least one candy?

c) In how many ways can this be done if each kid gets exactly 3 candies?

d) In how many ways can this be done if A and B collectively get at most four candies?

e) In how many ways can this be done if exactly two kids get nothing?

\

My attempts:

\
\

a) Since we can assign the children to the candies there are $5^{15}$ ways to do this with no restrictions.

b) I am very confused on this one…I would assume we would use the exclusion inclusion principle but I'm not sure exactly how to. First, I took the total number of ways to do this problem with no restrictions –> $5^{15}$ ways. Then I would subtract the bad cases, in which there are $5×4^{15}$ cases because if we take the case in which A has nothing then there are $4^{15}$ ways to distribute the rest of the kids to the candies and this stands for if B has nothing if C, if D and if E has nothing (so 5 times the $4^{15}$). I'm just unsure on how to figure out how much we overcounted by since there are essentially 5 circles in the venn diagrams… Can someone walk me through this one?

c) I picked three candies for the first kid, three candies for the second all the way to the 5th kid. So there are ${15\choose 3}{12\choose 3}{9\choose 3}{6\choose 3}{3\choose 3}$ ways to do this.

d) Let's give A and B 4 candies. First we need to choose the four candies for A and B so there are ${15\choose 4}$ ways to do this. Then we must assign the rest of the candies. Since there are 3 remaining children we can assign 3 kids to the remaining 11 candies in $3^11$ ways. So for this case there are ${15\choose 4}x3^{11}$ ways. You would continue this for the remaining cases in which A and B get 3 collectively, 2 collectively, 1 collectively and 0 collectively. So there would be ${15\choose 4}$x$3^{11}$ + ${15\choose 3}$x$3^{12}$ + ${15\choose 2}$x$3^{13}$ + ${15\choose 1}$x$3^{14}$ + ${15\choose 0}$x$3^{15}$ ways in total.

e) I'm not sure…

\
\

Overall I'm really not sure about b, d and e, but if you could check a and c as well I would appreciate it! Thanks!

Best Answer

(b) To distribute 15 candies to five children there are $5^{15}$ ways. To distribute the same candies to only four children, you have to choose which child will definitely not get any candy, which is $\binom51$ ways, and then actually distribute ($4^{15}$ ways). We continue down this line: distributing to three children is pre-omitting two children in $\binom52$ ways and distributing in $3^{15}$ ways, etc.

Thus the final total is the number of ways to distribute to five children, minus the ways to distribute to four, plus the ways to distribute to three, minus the ways to distribute to two, plus the ways to distribute to one: $$5^{15}-5\cdot4^{15}+10\cdot3^{15}-10\cdot2^{15}+5\cdot1^{15}$$

(d) Suppose A, B get exactly four candies. There are $\binom{15}4$ ways to choose the candies that go to them, $2^4$ ways to distribute that special selection and $3^{11}$ ways to distribute the other 11 candies to C, D, E.

Repeat for A, B receiving 3, 2, 1, 0 candies and add up: $$\binom{15}42^43^{11}+\binom{15}32^33^{12}+\binom{15}22^23^{13}+\binom{15}12^13^{14}+\binom{15}02^03^{15}$$

(e) First you choose which two children get nothing, which is $\binom52$ ways. The other three children must get at least one candy, so we can carry the argument in the answer to (b) over (include giving to three, exclude giving to two, include giving to one): $$\binom52\left(3^{15}-3\cdot2^{15}+3\cdot1^{15}\right)$$

Lastly, (a) and (c) are correct. In particular, (c) can be derived in a simpler way: have the children receive their candies in a queue, three at a time ($15!$ ways), then divide by $6^5$ for the $3!$ ways each child can permute their sweets without affecting their selection, thus $\frac{15!}{6^5}$ ways.