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

$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$
    – Brian M. Scott
    Commented Oct 13, 2012 at 22:41

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ Subtracting 1 from the subscripts? How can that affect the sum? What do you mean, "generating functions for 0, 1, 2, and 3"? $\endgroup$
    – Gerry Myerson
    Commented Oct 14, 2012 at 4:29
  • $\begingroup$ 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$ $\endgroup$
    – Jean-Sébastien
    Commented Oct 14, 2012 at 4:40
  • $\begingroup$ 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? $\endgroup$
    – diimension
    Commented Oct 14, 2012 at 4:41
  • $\begingroup$ 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 $\endgroup$
    – Jean-Sébastien
    Commented Oct 14, 2012 at 4:41
  • $\begingroup$ @diimension read my comment if not done, the first one $\endgroup$
    – Jean-Sébastien
    Commented Oct 14, 2012 at 4:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .