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?

  • 4
    Trick Question: Santa Claus does not have a model in ZFC2011-11-11
  • 6
    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!2011-11-11
  • 2
    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.2011-11-11
  • 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}\;.$$