Inclusion exclusion principle questions i tried(doing it correct?)

120 Views Asked by At

$x_1+x_2+x_3\le10$

how many natural numbers solve this problem if

$1\le x_1 \\ 2\le x_2 \\3\le x_3$

What i did: i created $y_1,y_2 , y_3$ so $\\ y_1=x_1-1 \\y_2=x_2-2\\ y_3=x_3 -3$ and then added $y_4$ so it will be $=$ instead of $\le$

and got:

$y_1 +y_2 +y_3 +y_4 =4$

is it the correct way? thank you!

1

There are 1 best solutions below

0
On BEST ANSWER

The key aspect that we need to consider is how to construct this problem. Imagine a graph of 30 dots, arranged in 10 rows and 3 columns. As I go up a column $i$, I add more integers to $x_i$, and as I move right from a column $i$ to $i+1$, I stop adding integers to $x_i$ and I start adding integers to $x_{i+1}$. The key idea is, how many ways can I get to row $10$, column $3$ with the given constraints? These give limits to how long a given column up-path will be. Initially, the number of ways to get to row 10, column 3 unconstrained should be $\binom{10+3}{3}$ ways. Now remove the ways I can get there when $x_1 < 1, x_2 < 2, \vee x_2 < 3.$ This is the "exclusionary" step.