# Inclusion-Exclusion Principle.

Determine the number of solutions of the equation $x_1+x_2+x_3+x_4+x_5=14$ in positive integers $x_1$, $x_2$, $x_3$, $x_4$, and $x_5$ not exceeding $5$.

I know I need to introduce a new variable, $y$, but then when I do that I get a negative...

$y_1=x_1-5$

$y_2=x_2-5$

$y_3=x_3-5$

$y_4=x_4-5$

$y_5=x_5-5$

my new equation would be $y_1+y_2+y_3+y_4+y_5=-11$

## 2 Answers

Consider $$x_1+x_2+x_3+x_4+x_5=14.$$ We must find all solutions where $1\leq x_i\leq 5$ for each $i\in\{1,2,3,4,5\}$. Make the substitution $y_i=x_i-1$ for each $i$. This gives us $$y_1+y_2+y_3+y_4+y_5=9$$ where $0\leq y_i\leq4$ for each $i$. Let $S$ be the set of all non-negative integral solutions of the above equation. So, $|S|={9+5-1\choose 9}={13\choose 9}=715$. Let $P_i$ be the property that $y_i\geq5$ for each $i$. Let $A_i$ denote the subset of $S$ consisting of the solutions satisfying property $P_i$. Making the substitution $z_1=y_1-5$, $z_2=y_2$, $z_3=y_3$, $z_4=y_4$, and $z_5=y_5$ we obtain the equation $z_1+z_2+z_3+z_4+z_5=4$. The number of solutions in $A_1$ is the same as the number of non-negative integral solutions to the above equation. Thus ${4+5-1\choose 4}={8\choose 4}=70$. We make the same substitution for each $y_i$ to find the number of solutions in $A_i$. So, $|A_i|'s=5{8\choose 4}=350$. The intersections of the $A_i$'s is empty. Thus the number of non-negative integral solutions in positive integers $x_1$, $x_2$, $x_3$, $x_4$, and $x_5$ not exceeding $5$ is $715-350=365$.

the number of non-negtive integer solutions to X1+X2+......XK=N is equal to the no of way of placing n identical balls into k balled boxes? Can you see that?

the no of solutions is n+k-1Ck (where C is for combinations)

Now you need to consider the constraints, note your y's defined above are either 0 or negative (we dont want this), so instead its

(5-X1)+(5-X2)+(5-X3)+(5-X4)+(5-X5)=25-14, which boils down to Y1+Y2+Y3+Y4+Y5=11, here Yi's are non-negative

You should be able to get the answer from here :)