4
$\begingroup$

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?

  • 1
    To show Im a complete egghead, I will correct my joke: ZFC$ \cup${Santa Claus} has no model.2011-11-11

1 Answers 1

2

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}\;.$