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'm having a lot of trouble understanding the logic in my Combinatorics class. I've got this question for an assignment:

How many solutions are there to $x_1 + x_2 + x_3 + x_4 = 19$, $x_i \geq 0$ for $1\leq i\leq4$?

I don't think the Principle of Inclusion / Exclusion needs to be applied here. As far as I know, the answer is $\binom{4+19-1}{19} = \binom{22}{19}$. However, I don't understand why this choose with repetition formula is used.

I'm further confused with the second part of the question: How many solutions are there to $x_1 + x_2 + x_3 + x_4 = 19$, $0 \leq x_i < 8$ for $1 \leq i \leq 4$?

An example in the textbook shows that the Principle of Inclusion and Exclusion must be used at this point. My understanding is that we consider four cases, $c_1, c_2, c_3, c_4$, which respectively represent the cases where $x_1, x_2, x_3, x_4$ each are greater than 7. Then, the answer to the problem is the total number of solutions to $x_1 + x_2 + x_3 + x_4$ minus $S_1$ (the number of cases where one of the $x$ values is greater than 7) plus $S_2$ (the number of cases where two of the $x$ values are greater than 7) minus $S_3$ (the number..three of the $x$ values are greater than 7).

If someone could please confirm my understanding of the application of PIE, and provide some inside as to WHY were using the choose repetition formula to solve these problems (I only know the choose formula as picking 4 people from 12 to form a committee, etc)

Cheers!!

share|improve this question
4  
You’re right that incl.-excl. is not needed for the first problem, and you’re right about how to use it for the second. There’s a fairly decent explanation of the formula that should be used here; try to make sense of that first, and see if you still have questions. –  Brian M. Scott Oct 13 '12 at 22:41
add comment

1 Answer

up vote 0 down vote accepted

You could use generating functions to understand it a bit better or just apply the formula of $\binom{n+k-1}{k -1}$ like you did. Here is a link to a free pdf file that deals with combinatroics http://people.math.gatech.edu/~trotter/keller-wtt-book/keller-wtt-book.pdf. You should read section 2.5 on page 32.

share|improve this answer
    
Subtracting 1 from the subscripts? How can that affect the sum? What do you mean, "generating functions for 0, 1, 2, and 3"? –  Gerry Myerson Oct 14 '12 at 4:29
    
There is no need to substract $1$, since $i$ is only for the values of $x_i$. He could have used $x,y,z,w$ instead. His variables are already greater or equal than $0$ –  Jean-Sébastien Oct 14 '12 at 4:40
    
I meant since we subtract 1 from our constraints we must subtract it in our equation of $x_1+x_2+x_3+x_4=19$ as well. So subtract 1 from $x_1, ..x_4$ which will give us $x_1+x_2+x_3+x_4=15$. Is not that correct? –  diimension Oct 14 '12 at 4:41
    
also, although I love generating function, and you should keep the answer, givent what is written in the question, I don't think @somekindarakus knows about these yet –  Jean-Sébastien Oct 14 '12 at 4:41
    
@diimension read my comment if not done, the first one –  Jean-Sébastien Oct 14 '12 at 4:42
show 5 more comments

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.