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.

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?

share|improve this question
    
You may want to look at math.stackexchange.com/questions/11468/…. –  user17762 Jun 22 '11 at 3:00
    
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"? –  Arturo Magidin Jun 22 '11 at 3:15

4 Answers 4

up vote 2 down vote accepted

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.

share|improve this answer
    
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. –  BrotherJack Jun 23 '11 at 20:07

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.$$

share|improve this answer

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.

share|improve this answer
    
+1 for setting me on the right path. Thanks Gerry! –  BrotherJack Jun 23 '11 at 20:08

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!

share|improve this answer
    
This should be the approach that must be followed :) –  AnkitSablok Jul 21 at 14:54

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.