In how many ways can $3$ girls and $5$ boys be placed in three distinct cars that each hold at most three children?

Question

There are $3$ cars of different makes available to transport $3$ girls and $5$ boys on a field trip. Each car can hold up to $3$ children. Find the number of ways in which they can be accommodated, if the internal arrangement of children inside the car is considered to be immaterial.

I considered three cases:

1. $3$ G in car 1, $3$ B in car 2, and $2$ B in car 3.This can be done in $\binom{3}{3}\binom{5}{3}\binom{2}{2}3!=60$ ways;

2. $2$ G, $1$ B in car 1; $1$ G, $2$ B in car 2; and $2$ B in car 3. This can be done in $\binom{3}{2}\binom{5}{1}\binom{1}{1}\binom{4}{2}\binom{2}{2}3!=540$ ways;

3. $1$ G, $2$ B in car 1; $1$ G, $2$ B in car 2; and $1$ G, $1$ B in car 3. This can be done in $\binom{3}{1}\binom{5}{2}\binom{2}{1}\binom{3}{2}\binom{1}{1}\binom{1}{1}\frac{3!}{2!}=540$ ways.

The total number of ways thus equals $540+540+60=1140,$ but the answer given is $1680$. Where did I go wrong?

Answer 1

There is no need to distinguish between boys and girls. Since there are $8$ children for nine seats available in the three cars I suggest a $9^{\rm th}$ child that will withdraw at the last moment.

There are ${9\choose3}$ ways to choose the $3$ children for the first car, then ${6\choose3}$ ways to choose the three children for the second car, and the remaining $3$ children will be put in the third car. It follows that there are $${9\cdot8\cdot7\cdot6\cdot5\cdot 4\over(3!)^2}=1680$$ ways to accommodate the children.

Answer 2

Christian Blatter has provided an elegant solution. The argument below shows you the two cases you omitted and a different way of counting the cases you handled.

The number $3$ can be partitioned into three parts as follows: \begin{align*} 3 & = 3 + 0 + 0\\ & = 2 + 1 + 0\\ & = 1 + 1 + 1 \end{align*} The number $5$ can be partitioned into three parts not larger than $3$ as follows: \begin{align*} 5 & = 3 + 2 + 0\\ & = 3 + 1 + 1\\ & = 2 + 2 + 1 \end{align*}

With that in mind, we consider cases:

Case 1: Three girls in one car, three boys in another car, and the remaining two boys in the remaining car.

Since the cars are different, there are $\binom{3}{1}$ ways to select the car for the three girls and one way to place all three girls in that car, $\binom{2}{1}$ ways to select which of the remaining cars will receive three boys, and $\binom{5}{3}$ ways to select which three boys are placed in that car. The remaining two boys must be placed in the remaining car. Hence, there are $$\binom{3}{1}\binom{2}{1}\binom{5}{3} = 60$$ such distributions as you found.

Case 2: Three boys in one car, one boy in each of the other cars, with two girls being placed in one of the cars with one boy and the other girl being placed in the other car with one boy.

There are $\binom{3}{1}$ ways to select the car which will receive three boys and $\binom{5}{3}$ ways to select the boys who will be placed in that car. There are $2!$ ways to place one boy in each of the two remaining cars. There are $\binom{2}{1}$ ways to select which of the cars with one boy will receive two girls and $\binom{3}{2}$ ways to select which two of the girls will be placed in that car. The remaining girl must be placed in the other car with one boy. Hence, there are $$\binom{3}{1}\binom{5}{3}2!\binom{2}{1}\binom{3}{2} = 360$$ such distributions. You omitted this case.

Case 3: Two girls and one boy are placed in one car, one girl and two boys are placed in another car, and the remaining two boys are placed in the remaining car.

There are $\binom{3}{1}$ ways of selecting the car that receives two girls and $\binom{3}{2}$ ways to select which two of the girls that car receives. There are $\binom{2}{1}$ ways to select which of the remaining cars receives the remaining girl and one way to place her there. There are $\binom{5}{1}$ ways to select the boy who is placed in the same car as the two girls and $\binom{4}{2}$ ways to select the boys who are placed in the same car as the single girl. The remaining two boys must be placed in the empty car. There are $$\binom{3}{1}\binom{3}{2}\binom{2}{1}\binom{5}{1}\binom{4}{2} = 540$$ such distributions, which you counted correctly.

Case 4: Two girls are placed in one car, two boys and a girl are placed in a different car, and three boys are placed in the remaining car.

There are $\binom{3}{1}$ ways to select the car that receives two girls and $\binom{3}{2}$ ways to select which two of the three girls that car receives. There are $\binom{2}{1}$ ways to select which of the remaining cars receives one girl and one way to place her there. There are $\binom{5}{2}$ ways to select which two boys are placed in the car with the single girl. The remaining boys must be placed in the remaining car. There are $$\binom{3}{1}\binom{3}{2}\binom{2}{1}\binom{5}{2} = 180$$ such distributions. You omitted this case.

Case 5: One girl is placed in each of the three cars, with two boys placed in each of two cars, and the remaining boy placed in the other car.

There are $3!$ ways to place one girl in each of the three cars. There are $\binom{3}{1}$ ways to select the car which receives one boy and $\binom{5}{1}$ ways to select that boy. There are $\binom{4}{2}$ ways to select which two boys will be placed in the same as the older of the two girls who does not yet have a boy in her car. The remaining two boys must be placed in the remaining car. There are $$3!\binom{3}{1}\binom{5}{1}\binom{4}{2} = 540$$ such distributions. You counted this case correctly.

Total: Since these cases are mutually exclusive and exhaustive, the answer is found by adding up the cases.