3

We have 14 indistinguishable pencils and we want to hand out all of the pencils to 6 people and we want everyone to get at least one pencil. However, we do not want person 6 to get more than 3 pencils. How many different ways could this be done?

Is the answer $\binom{10}{6}$ correct?

Reserve 1 pencil per person and reserve 3 pencils to person 6. So we now have 6 pencils left that we need to pass out to 5 people (since person 6 can no longer receive a pencil). So the problem is the same as asking how many ways can pass out 6 pencils to 5 people? Or am I looking at this wrong?

Seumas Frew
  • 135
  • Close. Person six can have no more than three pencils, but may have one, two or three from what I can see in the problem description. These are disjoint, of course, so you can do casework for each scenario and proceed as you have. – Alex Wertheim May 01 '15 at 02:34
  • @AlexWertheim So would this be correct? (13 choose 8) + (11 choose 7) + (10 choose 6) – Seumas Frew May 01 '15 at 02:43
  • That's the right idea, but your 'stars and bars' computation doesn't seem to be quite right. Unless I've made a mistake, you should be getting (12 choose 8) + (11 choose 7) + (10 choose 6). (Perhaps the 13 was a typo?) – Alex Wertheim May 01 '15 at 02:46

2 Answers2

2

You are only counting the cases when person $6$ gets exactly three pencils.

Solution:

First give out one person to each (Let's get this over this as soon as possible as it is necessary).

We now have to give out $8$ pencils ,among $6$ people so that person $6$ gets $0,1$ or $2$ pencils. Each of these three cases can be easily solved by the Stars and Bars method

Community
  • 1
Asinomás
  • 105,651
0

Here is an alternative method using the Inclusion-Exclusion Principle.

If we hand out $14$ pencils to six people so that each person gets at least $1$ in such a way that person $6$ gets at most $3$ pencils, then we need to find the number of solutions of the equation $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 14 \tag{1}$$ in the positive integers subject to the restriction that $x_6 \leq 3$.

As you observed, we can first give each person one pencil to reduce the problem to distributing eight pencils to six people so that person $6$ gets no more than $2$ additional pencils. Let $y_k = x_k - 1$ for $1 \leq k \leq 6$. Then \begin{align*} x_1 + x_2 + x_3 + x_4 + x_5 + x_6 & = 14\\ y_1 + 1 + y_2 + 1 + y_3 + 1 + y_4 + 1 + y_5 + 1 + y_6 + 1 & = 14\\ y_1 + y_2 + y_3 + y_4 + y_5 + y_6 & = 8 \tag{2} \end{align*} where equation 2 is an equation in the nonnegative integers subject to the restriction that $y_6 \leq 2$. Moreover, equation 2 has the same number of solutions has equation 1.

If we do not restrict the value of $y_6$, then the number of solutions to equation 2 is the number of ways we can insert five addition signs in a row of eight ones, which is $$\binom{8 + 5}{5} = \binom{13}{5}$$
However, we must eliminate those solutions in which $y_6 \geq 3$. Suppose $y_6 \geq 3$. Then $z_6 = y_6 - 3 \geq 0$. Then the number of solutions we must eliminate is the number of solutions in the nonnegative integers of the equation \begin{align*} y_1 + y_2 + y_3 + y_4 + y_5 + z_6 + 3 & = 8\\ y_1 + y_2 + y_3 + y_4 + y_5 + z_6 & = 5 \tag{3} \end{align*} Since equation 3 has $$\binom{5 + 5}{5} = \binom{10}{5}$$ solutions in the nonnegative integers, the number of ways $14$ pencils can be distributed to six people so that each person receives at least one pencil and person $6$ receives no more than three pencils is $$\binom{13}{5} - \binom{10}{5}$$

As you can check, this is equivalent to the answer that Gamamal obtained by considering the cases $y_6 = 0$, $y_6 = 1$, and $y_6 = 2$ separately, that is, $$\binom{13}{5} - \binom{10}{5} = \binom{12}{8} + \binom{11}{7} + \binom{10}{6} = 1035$$

N. F. Taussig
  • 76,571