Combinatorics Inclusion - Exclusion Principle

307 Views Asked by At

Find the number of integer solutions to $x_1 + x_2 + x_3 + x_4 = 25$ with $ 1 \leq x_1 \leq 6, 2 \leq x_2 \leq 8, 0 \leq x_3 \leq 8, 5 \leq x_4 \leq 9.$

Firstly, I defined $y_i = x_i - lower bound$ so for example $y_1 = x_1 - 1$ This gives $y_1 + y_2 + y_3 + y_4 = 17$ with $$0 \leq y_1 \leq 5, 0 \leq y_2 \leq 6, 0 \leq y_3 \leq 8, 0 \leq y_4 \leq 4$$ Next I applied Inclusion-Exclusion Principle;

Total number of ways = $17+3 \choose 3$

Number of ways with just $y_i$ breaking upper bound;

$y_1;$$11+3 \choose 3$

$y_2;$ $10+3 \choose 3$

$y_3;$ $8+3 \choose 3$

$y_4;$ $12+3 \choose 3$

Similarly I calculated the number of ways with $y_i$ and $y_j$ breaking upper bound at the same time. And since there is no way in which 3 of them break their upper bounds simultaneously I was left with ;

$${20 \choose 3} - {14 \choose 3} - {13 \choose 3} - {11 \choose 3} - {15 \choose 3} + {7\choose 3} + {5 \choose 3} + { 9 \choose 3} + {4 \choose 3} + {8 \choose 3} + {6 \choose 3} $$

as my final answer.

Is this solution correct and is there a nicer way of solving it/ any insights about this type of problem?

Note, this problem is from 'An Introduction to Combinatorics and Graph Theory'

1

There are 1 best solutions below

0
On

As noted in the comments, your solution is correct. The approach is described in Balls In Bins With Limited Capacity.

To solve the problem using generating functions, write $x+x^2+\cdots+x^6=x\frac{1-x^6}{1-x}$ for $x_1$, $x^2+x^3+\cdots+x^8=x^2\frac{1-x^7}{1-x}$ for $x_2$, $1+x+\cdots+x^8=\frac{1-x^9}{1-x}$ for $x_3$ and $x^5+x^6+\cdots+x^9=x^5\frac{1-x^5}{1-x}$ for $x_4$. The product is

$$ x^8\frac{\left(1-x^6\right)\left(1-x^7\right)\left(1-x^9\right)\left(1-x^5\right)}{(1-x)^4}\;, $$

and the number of solutions to $x_1+x_2+x_3+x_4=25$ is the coefficient of $x^{25}$ in this generating function. With the expansion

$$ \frac1{(1-x)^4}=\sum_{k=0}^\infty\binom{k+3}3x^k\;, $$

you can see how multiplying out the numerator and matching each resulting term with the missing powers of $x$ from the denominator yields exactly the alternating inclusion–exclusion sum of binomial coefficients that you calculated.