In how many ways can $6$ different candies be divided between three children

combinatoricsdiscrete mathematics

I am the freshman in Computer Science at university, and currently struggling with some tasks from the Combinatorics part of the Discrete Math class. Any help would be appreciated.

In how many ways can $6$ different candies be divided between three children?

My vision of solving this problem:

  1. For every candy there is $3$ children to give it to $\implies 3^6$ possible ways of candy distribution

OR

  1. Each child can get from $0$ to $6$ candies:
    $\implies 7$ possible distributions $\implies 7^3$ possible ways of candy distribution between the $3$ children?

But I feel like I am missing something which leads to the duality of my solutions. (Probably that the candies are different?) And I don't understand how to count that in.

Best Answer

Your first solution is correct. There are three possible recipients for each of the six candies, so there are $3^6$ possible distributions of the candies.

If you wish to consider how many candies each child receives, you need to consider cases based on partitions of $6$ into at most three parts. \begin{align*} 6 & = 6\\ & = 5 + 1\\ & = 4 + 2\\ & = 4 + 1 + 1\\ & = 3 + 3\\ & = 3 + 2 + 1\\ & = 2 + 2 + 2 \end{align*}

One child receives six candies: There are three ways to select the recipient of all six candies.

One child receives five candies and another child receives one candy: There are three ways to select the child who will receive five candies, $\binom{6}{5}$ ways to select which five of the six candies that child receives, and two ways to choose the child who receives the remaining candy. Hence, there are $$\binom{3}{1}\binom{6}{5}\binom{2}{1}$$ such distributions.

One child receives four candies and another child receives two candies: There are three ways to select the child who will receive four candies, $\binom{6}{4}$ ways to select which four of the six candies that child receives, and two ways to choose the child who receives the remaining two candies. Hence, there are $$\binom{3}{1}\binom{6}{4}\binom{2}{1}$$ such distributions.

One child receives four candies and each of the other children receive one candy each: There are three ways to select the child who will receive four candies, $\binom{6}{4}$ ways to select which four of the six candies that child receives, and two ways to choose which of the remaining two candies the younger of the two remaining children receives. The other child must receive the remaining candy. Hence, there are $$\binom{3}{1}\binom{6}{4}\binom{2}{1}$$ such distributions.

Two children each receive three candies: There are $\binom{3}{2}$ ways to select which two children receive three candies each and $\binom{6}{3}$ ways to select which three of the six candies the younger of the two selected children will receive. The other selected child must receive the three remaining candies. Hence, there are $$\binom{3}{2}\binom{6}{3}$$ such distributions.

One child receives three candies, a second child receives two candies, and the third child receives one candy: There are three ways to select the child who will receive three candies, $\binom{6}{3}$ ways to select which three candies that child will receive, two ways to decide which of the remaining children will receive two candies, and $\binom{3}{2}$ ways to select which two of the remaining three candies that child will receive. The remaining child must receive the remaining candy. Hence, there are $$\binom{3}{1}\binom{6}{3}\binom{2}{1}\binom{3}{2}$$ such distributions.

Each of the three children receives two candies: There are $\binom{6}{2}$ ways to select which two candies are received by the youngest child and $\binom{4}{2}$ ways to select which two of the remaining four candies are received by the next youngest child. The oldest child must receive the two remaining candies. Hence, there are $$\binom{6}{2}\binom{4}{2}$$ such distributions.

Total: Since the above cases are mutually exclusive and exhaustive, the number of ways of distributing six different candies to three children is $$\binom{3}{1} + \binom{3}{1}\binom{6}{5}\binom{2}{1} + \binom{3}{1}\binom{6}{4}\binom{2}{1} + \binom{3}{1}\binom{6}{4}\binom{2}{1} + \binom{3}{2}\binom{6}{3} + \binom{3}{1}\binom{6}{3}\binom{2}{1}\binom{3}{2} + \binom{6}{2}\binom{4}{2} = 3^6$$