1
$\begingroup$

There are 2 questions that are very similar and I have the same answer to both but I don't think that's correct. Can you help me see the difference between the 2 questions.

  1. We have 14 indistinguishable pencils and we want to hand out all of the pencils to 6 people (but we do not care if some of the people get no pencils.) How many different ways could this be done?

    My answer: 19 choose 14

  2. 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. How many different ways could this be done?

    My answer: again 19 choose 14

Am I right or wrong or both? I'm confident one answer is 19 choose 14 but I'm not sure which. As you can see I'm a bit confused.

$\endgroup$
  • $\begingroup$ The first is correct. Can you give reasons for this answer? - if so I think you will see why the second one is wrong, and how to fix it. $\endgroup$ – David May 1 '15 at 2:13
  • $\begingroup$ By using 5 dividers for the 6 people (think of the 6 people as "types"), putting the 14 pencils in the first section or divider and then counting the remaining sections/dividers which would be 5, so 14+5=19 $\endgroup$ – Seumas Frew May 1 '15 at 2:14
  • $\begingroup$ @David Since each person would have 1 pencil, would it essentially be like handing out 8 pencils to the 6 people? If so, that would be 13 choose 8. $\endgroup$ – Seumas Frew May 1 '15 at 2:16
  • $\begingroup$ Yes that's correct. $\endgroup$ – David May 1 '15 at 2:17
2
$\begingroup$

Problem 1 is correct with the answer being $\binom{19}{14}$. Problem 2 is wrong and the correct answer is $\binom{13}{8}$. You reserve 1 pencil to each of the 6 people leaving you with 8 pencils left to pass out. The problem can be looked at as being how many different ways can we pass out 8 pencils to 6 people, and that would be $\binom{13}{8}$.

$\endgroup$
  • $\begingroup$ I helped a little with the formatting. Please take a look at the edit I made... should help in the future. Also, see: math.stackexchange.com/help/notation for additional reference. $\endgroup$ – TravisJ May 1 '15 at 2:48
  • $\begingroup$ @TravisJ I tried formatting them to look like what you did by this {19 \choose 14} but it didn't work. $\endgroup$ – Seumas Frew May 1 '15 at 2:57
  • $\begingroup$ @TravisJ Nevermind, I see what you did. $ \binom {19}{14}$ $\endgroup$ – Seumas Frew May 1 '15 at 2:59
1
$\begingroup$

I think the second question is easier and should be asked first. Put the pencils in a row and there are $13$ spaces between them. You need to select $5$ of these spaces to stop giving pencils to a given person and start giving them to the next, so there are ${13 \choose 5}={13 \choose 8}$ ways to do this.
six.
The first then comes from adding $1$ to the number given to each person. You now have $20$ pencils to distribute to $6$ people, each of whom must get at least one. The same logic says the answer is $19 \choose 5$, which happens to equal $19 \choose 14$

$\endgroup$
  • $\begingroup$ The first question results in an equation of the form $x_1 + x_2 + \cdots + x_k = n$ with solutions in the nonnegative integers. The number of solutions is the number of ways we can insert $k - 1$ addition symbols in a row of $n$ ones, which is $\binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n}$. The second equation results in an equation of the same form with solutions in the positive integers. The number of solutions is the number of ways we can fill $k - 1$ of the $n - 1$ spaces between the $n$ ones with addition signs, which is $\binom{n - 1}{k - 1}$, as you clearly recognized. $\endgroup$ – N. F. Taussig May 1 '15 at 8:30

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.