inclusion-exclusion principle question

**jmedsy** · February 7th 2010, 06:58 PM

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

**Plato** · February 8th 2010, 06:39 AM

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.

Thread: inclusion-exclusion principle question

LinkBack

Thread Tools

Display

inclusion-exclusion principle question

Similar Math Help Forum Discussions

Inclusion Exclusion Principle Help!

inclusion exclusion principle help!

Inclusion - Exclusion Principle

math question - inclusion exclusion principle

Principle of Inclusion of Exclusion

Search Tags