Combinatorics – Using Inclusion/Exclusion to Solve $x_1+x_2+x_3=15$ with Constraints

combinatoricsinclusion-exclusion

I want to solve for:

Number of integers solutions to the equation $x_1+x_2+x_3=15$ with $x_1,x_2\leq 5$ and $x_3\leq 7$ for non negative integers $x_1,x_2,x_3$

How can this be done using the principle of inclusion/exclusion?

Best Answer

If $N$ denotes the total number of ways $x_1+x_2+x_3 =15$ without any restrictions (of course, non-negative integers) and $M$ is the number of ways with desired constraints, then $$ M = N - \left(N_{x_1>5} + N_{x_2>5} + N_{x_3>7}\right) + \left(N_{x_1>5\ and\ x_2>5} + N_{x_1>5\ and\ x_3>7} + N_{x_2>5\ and\ x_3>7}\right) - N_{x_1>5\ and\ x_2>5\ and\ x_3>7} $$ where the $N$ with a subscript denotes the number of ways with the constraints in the subscript.

We have $$N_{x_1>5} = N_{x_2>5} = {11\choose 2},\ N_{x_3>7} = {9\choose2},$$ $$N_{x_1>5\ and\ x_2>5} = {5\choose 2},\ N_{x_1>5\ and\ x_3>7} = N_{x_2>5\ and\ x_3>7} = {3\choose 2},$$ and $$N_{x_1>5\ and\ x_2>5\ and\ x_3>7} = 0.$$

And the total number of ways without any constraint is ${17\choose 2}$. So, $$ M = {17\choose 2} - \left( 2{11\choose 2} + {9\choose2}\right) + \left({5\choose 2} + 2{3\choose 2}\right) = 6. $$