# Combinatorics counting, inclusion exclusion problem

Santa Claus has five toy airplanes of each of n plane models. How many ways are there to put one airplane in each of $r$ ($r \geq n$) identical stockings such that all models of planes are used?

-
Trick Question: Santa Claus does not have a model in ZFC – gary Nov 11 '11 at 5:20
Welcome to MathSE. I see that this is your first question. So I wanted to let you know a few things about MathSE. We like to know the sources of questions. We also like to know what you've tried on a problem or what your thoughts are, so that the answer does not re-invent the wheel or go over stuff you already know. These sort of pleasantries usually result in more and better answers. Thank you! – Arturo Magidin Nov 11 '11 at 5:21
+1 for the funny context... lol – Patrick Da Silva Nov 11 '11 at 5:29
First, put one each of the $n$ plane models into stockings; that leaves $r-n$ stockings to be filled, with $4$ planes of each of $n$ types to be placed with no restrictions. – Arturo Magidin Nov 11 '11 at 6:13
To show Im a complete egghead, I will correct my joke: ZFC$\cup${Santa Claus} has no model. – gary Nov 11 '11 at 8:15

If the stockings are truly indistinguishable, we’re simply counting the integer solutions of the equation $x_1+x_2+\dots+x_n=r$ that satisfy the inequalities $1\le x_i\le 5$ for $i=1,\dots n$: $x_i$ is the number of planes of model $i$ that go into stockings.
Without the upper bounds on the $x_i$’s there are $\binom{r-1}{n-1}$ solutions. The number of these that exceed the limit on a fixed $x_i$ is $\binom{r-6}{n-1}$. In fact, for any $S\subseteq [n]$ the number of integer solutions that exceed the limit on every $x_i$ with $i\in S$ is $\binom{r-1-5|S|}{n-1}$. There are $\binom{n}k$ subsets of $[n]$ of size $k$, so by the inclusion-exclusion principle the number of acceptable solutions $-$ those exceeding none of the upper bounds $-$ is $$\sum_{k=0}^n(-1)^k\sum_{\substack{S\subseteq[n]\\|S|=k}}\binom{r-1-5k}{n-1}=\sum_{k=0}^n(-1)^k\binom{n}k\binom{r-1-5k}{n-1}\;.$$