# inclusion-exclusion principle question

• Feb 7th 2010, 07:58 PM
jmedsy
inclusion-exclusion principle question
Determine how many integer solutions there are to a+b+c+d=19 if

0<=a<=5,
0<=b<=6,
3<=c<=7,
3<=d<=8
• Feb 8th 2010, 07:39 AM
Plato
Quote:

Originally Posted by jmedsy
Determine how many integer solutions there are to a+b+c+d=19 if 0<=a<=5, 0<=b<=6, 3<=c<=7, 3<=d<=8

This is an extremely tedious problem to do with inclusion/exclusion!
It is easy to do with generating functions.

I will start you off with inclusion/exclusion.
The number of ways for condition a to happen is $\binom{22}{3}-\binom{16}{3}$.

The number of ways for conditions c to happen is $\binom{19}{3}-\binom{14}{3}$.

The number of ways for conditions a & c to happen together is $\binom{19}{3}-\binom{8}{3}$.

Now to finish you have to figure for each of the other conditions in all possible combinations.

With generating functions we expand $\left( {\sum\limits_{k = 0}^5 {x^k } } \right)\left( {\sum\limits_{k = 0}^6 {x^k } } \right)\left( {\sum\limits_{k = 3}^7 {x^k } } \right)\left( {\sum\limits_{k = 3}^8 {x^k } } \right)$.
The coefficient of $x^{19}$ will be the answer.