Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Discrete mathematics, continuous mathematics and probability / 2 / d

For one colour, the box occupancies form a weak composition of $k$ into $n$ nonnegative parts. For $n\ge 1$, stars and bars gives $\left(\genfrac{}{}{0ex}{}{k+n-1}{n-1}\right)$ choices. The three colours' occupancies can be selected independently, so the number isBoxes are labelled, while equal-colour balls contribute only occupancy counts; no extra factorial for permuting such balls is appropriate.

There are $6^3=216$ unrestricted placements, since one colour has $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ occupancy vectors. For any specified empty box, the two remaining boxes admit $3^3=27$ placements. For any specified pair of empty boxes, the one remaining box admits one placement. All three boxes cannot be empty.

The inclusion-exclusion principle therefore givesThe empty-box events are not disjoint events, so subtracting their counts without restoring their pairwise overlaps would be incorrect.