3
$\begingroup$

So I have a question about a practice problem employing combination in which the repetition of elements is allowed, here it is:

Determine the number of non-negative integer solutions to the equation $a + b + c + d + e = 70$.

So this seems straightforward enough to me. I see 70 possible elements with 5 combinations, so $n=70$ and $r=5$. So employing the formula $C(n + r - 1, r) = C(n + r - 1, n - 1)$, I reach the following:

$C(70 + 5 - 1, 70 - 1) = C(74,69) = \frac{74!}{69!(74-69)!} = \frac{74 \cdot 73 \cdot 72 \cdot 71\cdot 70}{5!} = 1.6108764 \cdot 10^{7}$

However, here is the answer supplied:

This is a combinations with repetition question without any special circumstances. There are 5 distinct objects and we are choosing exactly 70 of them. The number of ways to do this is C(70+5-1, 5-1) = C(74,4) = C(74, 70). (Grading: Recognizing combinations with repetition is worth 3 pts. Stating both 70 and 5 (or 4 depending on how they conceive of the problem) is worth 1 pt each. Applying the formula correctly is worth 5 pts

Could someone explain to me what I am doing wrong?

$\endgroup$
2
  • $\begingroup$ You may want to look at math.stackexchange.com/questions/11468/…. $\endgroup$
    – user17762
    Jun 22, 2011 at 3:00
  • $\begingroup$ One way to see it's 5 objects and 70 choices is: you have 70 balls; place them in 5 buckets, one labeled $a$, one labeled $b$, one labeled $c$, and labeled $d$, one labeled $e$. When you are done, $a$ is the number of balls in bucket $a$, $b$ is the number of balls in bucket $b$, etc. You have 5 possibilities for each ball, and you have to make the choices 70 times. How do you try to interpret "70 elements, five combinations"? $\endgroup$ Jun 22, 2011 at 3:15

4 Answers 4

4
$\begingroup$

Others have told you how to do it right, or have pointed to sites that tell you how to do it right. But I think the first thing is to be convinced you've done it wrong, and the easiest way to do that is to look at a much simpler example, say, $a+b=1$. Your reasoning gives 1 element with 2 combinations, so $n=1$ and $r=2$, so $C(2,2)=1$. But this is manifestly wrong, since there are 2 solutions, $a=1$, $b=0$, and $a=0$, $b=1$. Once you see why it's wrong, you're on your way to doing it right.

$\endgroup$
0
2
$\begingroup$

Please wee the Wikipedia article on Stars and Bars.

Questions very similar to this one have been asked on StackExchange a number of times, so a search will reveal quite a few detailed answers. But the Wikipedia article is longer than any of these answers, and very detailed.

$\endgroup$
1
  • $\begingroup$ Thanks User6312! I had seen a professor use this before, but he wasn't very clear on what he was doing at the time (or I was too slow to get it, or both!). This page was very helpful. $\endgroup$ Jun 23, 2011 at 20:07
2
$\begingroup$

When you say it is obviously $C(70,5)$ what did you see?

I think a good way yo do a problem like this is to imagine that you have 70 balls on a line that you want to divide in 5 groups. To do that, you have to place 4 markers in between the balls to divide it in 5 groups. If you didn't allow groups of size 0 you would obviously get $C(69,4)$ solutions.

But since you want non-negative solutions, you have to do something a bit more subtle: say that you take a solution to your problem and add 1 to each of $a,b,c,d$ and $e$, then you get a strictly positive solution to $a+b+c+d+e=75$ (and you should convince yourself that a positive solution to this equation yields a non-negative solution to your original problem). But clearly, for our discussion in the previous paragraph, there are $C(74,4)$ solutions to that problem!

$\endgroup$
1
  • $\begingroup$ This should be the approach that must be followed :) $\endgroup$ Jul 21, 2014 at 14:54
0
$\begingroup$

This problem belongs to "$k$-combination with repetitions" problems. The general formula is like this: $X_1+X_2+X_3+X_4+\cdots+X_n=r$. Can you see the problem in your answer? According to this, $r=70$ and $n=5$ so the combination should be $$C(n+k-1,n-1) = C(74,4) = C(n+k-1,r) = C(74,70) = 1,150,626.$$

$\endgroup$

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.