$8$ Cars in $3$ Trailers

Motivation When we see such combinatorics question with a maximum number of items being placed into a box, we usually think of using the maximum, or $max$ idea as shown below:

Note The $3$ trailers are identical.

If the $max$ of the number of cars in the trailers is $3$ , we will have only $1$ case to consider:

• $(3,3,2)$ - referring to $3$ cars in $2$ trailers and $2$ cars in the remaining trailer.

The number of ways to arrange the $8$ cars in this order is simply: $\dbinom{8}{2} \cdot \dfrac{\binom{6}{3}}{2}= 280$ . We choose $2$ cars out of $8$ to put into $1$ trailer, then we simply choose $3$ out of the remaining $6$ cars, then divide by $2$ because choosing $3$ cars $c_1,c_2,c_3$ to put into one trailer is the same as choosing $c_1,c_2,c_3$ to put into the other trailer.

If the $max$ is $4$ , there are $2$ cases to consider:

• $(4,3,1)$ : Number of ways to arrange $= \dbinom{8}{4} \cdot \dbinom{4}{3} = 280$

• $(4,2,2)$ : Number of ways to arrange $\dbinom{8}{4} \cdot \dfrac{\binom{4}{2}}{2}= 210$ .

Therefore, the total number of ways is $280 +280+210 = \boxed{770}$ . We are done. :)

This is equivalent to the number of $8$ letter words consisting of $A,B,C$ where each letter appears between $1$ and $4$ times - by writing down to which trailer each car goes, and then dividing by $3!$ , since the trailers are identical.

We will do it using exponential generating functions: for each letter, $f_X(x)=x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}$ - for $X=A,B,C$ . So the generating function is $f(x)=f_A(x)\cdot f_B(x)\cdot f_C(x)=\left(x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}\right)^3$ And we are looking for the coefficient of $\frac{x^8}{8!}$ , which is $4620$ - by direct computation while remembering that we only need $x^8$ .

So, the number of $8$ letter words as described above is $4620$ , and so the answer will be $4620/3!=\boxed{770}$

1) ${8 \choose 4}*{4\choose 3}*{1 \choose 1} = 280$ (4 3 1)
2) ${8 \choose 4}*{4\choose 2}*{2 \choose 2} = 420$ (4 2 2)
3) ${8 \choose 3}*{5 \choose 3}*{2\choose 2} = 560$ (3 3 2)

Total number of ways $= (1) + \frac{ (2) +(3)} {2} = \boxed{770}$ .