3
$\begingroup$

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!!

  • 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](http://en.wikipedia.org/wiki/Stars_and_bars_%28probability%29); try to make sense of that first, and see if you still have questions.2012-10-13

1 Answers 1

1

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.

  • 0
    Subtracting 1 from the subscripts? How can that affect the sum? What do you mean, "generating functions for 0, 1, 2, and 3"?2012-10-14
  • 0
    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$2012-10-14
  • 0
    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?2012-10-14
  • 0
    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 yet2012-10-14
  • 0
    @diimension read my comment if not done, the first one2012-10-14
  • 0
    Ah man, I was hoping to have given my first official answer here on SE. I make a better effort to understand the question next time. Hopefully my answer doesn't cause too much trouble.2012-10-14
  • 0
    Ah I see my mistake I didn't read it carefully I will make an edit to my answer! Thank you @Jean-Sebastien !2012-10-14
  • 0
    No trouble caused. Generating functions are the next section and I actually tried to tackle the problem like that at first but couldn't figure out how to get the coefficient of $x^{19}$ in $(1 + x + x^2 + x^3 + .. + x^{19})^4$ (did I go about that right?)2012-10-14
  • 0
    Yup, that is right but generating functions isn't ideal for this particular problem because there isn't any constraints. If there were constraints then generating functions will work out perfectly. By constraints I mean, $x_1 < 3 , x_2 > 2$, etc. Here is a test bank you can use for reference. http://people.math.gatech.edu/~trotter/math-3012-Fa11/test10-1-solutions.pdf look at problem 3.2012-10-14
  • 0
    To find the coefficient of $x^{19}$ you will have to use the multinomial theorem.2012-10-15