Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
Trick Question: Santa Claus does not have a model in ZFC –  gary Nov 11 '11 at 5:20
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 - if it's homework, please add the [homework] tag. People will still help, so don't worry. 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  
+1 for the funny context... lol –  Patrick Da Silva Nov 11 '11 at 5:29
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. –  Arturo Magidin Nov 11 '11 at 6:13
1  
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

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.