2
$\begingroup$

How many ways are there to distribute three different pens and nineteen identical pencils to five people, if no person gets more than two pens, and such that everyone gets at least one pen or pencil?

Attempt 1:

There's C(14 + 5 - 1, 5-1) = C(18, 4) = 3060 ways to distribute 19 pencils to 5 students if each receives at least one pencil.

Do I multiply this result with the result of finding how many ways to distribute the pens? I think I may have misinterpreted the question because the part about everyone getting at least one pen or pencil really confuses me.

Attempt 2:

Case 1: One student gets 2 pens. Choosing the 2 pens is C(3, 2) = 3. Then, 3*5 because there are 5 possible students who can get 2 pens. Now there's only 1 pen to distribute and there's 4 ways of doing that. Next, we have to take away 3 pencils leaving us with 16 pencils to distribute to 5 students.

Let x = pen and y = pencil

2x|x|y|y|y

So there's C(20, 4) = 4845 ways of distributing the pencils. The total for case 1 is 3*5*4*4845 (not sure if we multiply or add the 4845)

Case 2: 3 students receive 1 pen. 3! = 6 ways of distributing the pens. Now we distribute 17 pencils, so C(21, 4) = 5985. The total for case 2 is 6*5985

The overall total is the sum of the two cases, so 326610.

$\endgroup$
  • $\begingroup$ Is it given that all of the pens and pencils must be used? If not, the question is quite different. $\endgroup$ – Noble Mushtak Jan 25 '16 at 23:23
  • $\begingroup$ I'm pretty sure that all pens and pencils are supposed to be used. $\endgroup$ – helpme Jan 25 '16 at 23:28
  • $\begingroup$ OK. Since it seems that one person can have a pen, but not a pencil, I think that the best way to do this problem is to not account for pens and pencils, find the number of ways to distribute them, and then use combinations to find how the number of ways is changed by the fact that we need to account for pens and pencils. $\endgroup$ – Noble Mushtak Jan 25 '16 at 23:31
  • $\begingroup$ Hmmm, I don't know if it reads as one person with a pen cannot have a pencil. $\endgroup$ – helpme Jan 25 '16 at 23:47
  • $\begingroup$ No, but there are cases where we need to account for people having pens but not pencils which somewhat complicates things. This will make more sense if you read my solution below. $\endgroup$ – Noble Mushtak Jan 25 '16 at 23:49
2
$\begingroup$

We distribute the pens first.

There are two cases:

  1. The three pens are distributed to three people of the five people.

This can be done in $5 \cdot 4 \cdot 3$ ways since there are five ways of choosing the recipient of the first pen, four ways of choosing the recipient of the second pen, and three ways of choosing the recipient of the third pen.

That leaves two people who have not received a pen. Since each person receives at least one pen or pencil, we give each of those two people one of the $19$ identical pencils. There are now $17$ identical pencils to distribute to $5$ people. Let $x_k$ be the number of remaining pencils distributed to the $k$th person. Then $$x_1 + x_2 + x_3 + x_4 + x_5 = 17 \tag{1}$$ This is an equation in the non-negative integers. The number of solutions of equation 1 is the number of ways four addition signs can be inserted into a row of $17$ ones, which is $$\binom{17 + 4}{4} = \binom{21}{4}$$ since we must choose which four of the $21$ symbols (four addition signs and seventeen ones) will be addition signs. In this case, the number of ways of distributing three different pens and $19$ identical pencils to five people so that each person receives at least one pen or pencil is $$5 \cdot 4 \cdot 3 \cdot \binom{21}{4}$$

  1. The three pens are distributed to two of the five people.

There are five ways of selecting one person to receive two of the three pens. There are $\binom{3}{2}$ ways of selecting which two of the three pens that person receives. There are four ways of selecting the person who receives the third pen. Hence, the number of ways of distributing the pens to two of the five people is $$5 \cdot \binom{3}{2} \cdot 4$$

That leaves three people who have not received a pen. Since each person receives at least one pen or pencil, we give each of those three people one of the $19$ identical pencils. That leaves $16$ pencils to distribute to $5$ people. Let $x_k$ be the number of pencils distributed to the $k$th person. Then $$x_1 + x_2 + x_3 + x_4 + x_5 = 16 \tag{2}$$ Equation 2 is an equation in the non-negative integers with $$\binom{16 + 4}{4} = \binom{20}{4}$$ solutions. In this case, the number of ways of distributing the pens and pencils to the five people so that each person receives at least one pen or pencil is $$5 \cdot \binom{3}{2} \cdot 4 \cdot \binom{20}{4}$$

In total, the number of ways of distributing three different pens and five identical pencils to five people so that no person receives more than two pens and so that each person receives at least one pen or pencil is $$5 \cdot 4 \cdot 3 \cdot \binom{21}{4} + 5 \cdot \binom{3}{2} \cdot 4 \cdot \binom{20}{4} = 60\left[\binom{21}{4} + \binom{20}{4}\right]$$

$\endgroup$
  • $\begingroup$ @user84413 Thanks for the compliment. $\endgroup$ – N. F. Taussig Jan 26 '16 at 0:57
0
$\begingroup$

I am going to split this problem into three parts:

  1. Find the number of ways we can distribute $3$ pens and $19$ pencils to $5$ people so that each person has either one pen or one pencil.
  2. Find the number of ways we can distribute $3$ pens and $19$ pencils to $5$ people so that each person has either one pen or one pencil and one person has all $3$ pens.
  3. Subtract the former by the latter to get our answer where no one has more than $2$ pens.

Part 1:

First, let's forget about pens and pencils. We have $22$ writing utensils in all and we need to distribute them to $5$ different people. By stars and bars, there are ${22-1 \choose 5-1}=5985$ ways to distribute these writing utensils.

Now, let's account for pens and pencils. There are $22!$ different possible ways we can order the pens and pencils so different people get different writing utensils. However, if we switch two pencils, then nothing will change, so we need to divide this by $19!$. Thus, we get $\frac{22!}{19!}=9240$ as the number of different ways we can order the pens and pencils. If we multiply this by the number of ways to distribute $22$ writing utensils, we get $9240*5985=55301400$, which is our answer for Part 1.

Part 2:

There are two cases for this part: The case where everyone has at least one pencil (Case 1) or the case where everyone except one person has pencils and the one person without pencils has all of the pens (Case 2). Our answer for Part 2 will be the sum of the answers for these cases.

Case 1: The number of ways to give $5$ people $19$ pencils so that every person has at least one pencil is, as you said, $3060$. We need to multiply this by the number of ways we can distribute all of the pens. Since one person must have all of the pens and there are $5$ people, there are $5$ ways to distribute all of the pens. Therefore, our answer to Part 2 is simply the product of these two numbers, or $3060*5=15300$.

Case 2: If all but one person has pencils, then we need to distribute $19$ pencils to $4$ people. By stars and bars, this is ${19-1 \choose 4-1}=816$. Now, we need to distribute all of the pens to the last person. There is only one way to do this. However, since there are $5$ people, there are $5$ different ways to choose this last person, so we need to multiply the number of ways we can distribute the pencils by $5$. This gives us $816*5=4080$.

By adding our answers from both cases, we find that our answer to Part 2 is $15300+4080=19380$.

Part 3:

By subtracting our answer from Part 1 by our answer from Part 2, we get $55301400-19380=55282020$, which is the number of ways $3$ pens and $19$ pencils can be distributed to $5$ people so that each person has either one pen or one pencil and no person has more than $2$ pens. Thus, we have solved the problem.

$\endgroup$
  • $\begingroup$ The 3 pens are actually different from one another. Does that change anything? I think part 1 should be 9240*5985 if that is the case. Not sure if it will change anything in part 2. $\endgroup$ – helpme Jan 26 '16 at 0:06
  • $\begingroup$ @helpme You're right, if the $3$ pens are different, then Part 1 becomes $9240*5985$ and nothing changes for Part 2. I've edited the answer accordingly. $\endgroup$ – Noble Mushtak Jan 26 '16 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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