# inclusion & exclusion help

#### jvignacio

Hey guys, im really struggling with this topic. If someone could show me step by step how to do this specific question id really appreciated it.

Question:
Use inclusion-exclusion to find the number of solutions in the non-negative integers to

$$\displaystyle X_1 + X_2 +$$ .... $$\displaystyle + X_6 = 45$$ with the conditions $$\displaystyle X_j > 4$$, $$\displaystyle j = 1,2,3.$$

I have no idea how to start or go about doing this problem. Any help would be much appreciated.

#### sid_178

Number of ways of distributing n identical items among r persons such that anyone can get any number of items is : n+r-1Cr-1 .

Now,in X1 + X2 +X3 +X4 +X5 +X6 =45 We have to distribute 45 1s into six entities namely X1 ,X2..... . {1s being identical to each other}
Answer should have been : (45+6-1)C(6-1)=50C5 .

But we are given condition that X1,X2,X3>=5

Therefore 15 1s have already been distributed among X1,X2,X3 .So from remaining 30 1s we start distibuting among X1,X2..using above formula ..

30+6-1C6-1 = 35C5

Hope This helps .

#### jvignacio

Number of ways of distributing n identical items among r persons such that anyone can get any number of items is : n+r-1Cr-1 .

Now,in X1 + X2 +X3 +X4 +X5 +X6 =45 We have to distribute 45 1s into six entities namely X1 ,X2..... . {1s being identical to each other}
Answer should have been : (45+6-1)C(6-1)=50C5 .
hey sorry, first question.. i thought it was n+r-1 C r ? NOT n+r-1 C r-1 ?

#### jvignacio

Number of ways of distributing n identical items among r persons such that anyone can get any number of items is : n+r-1Cr-1 .

Now,in X1 + X2 +X3 +X4 +X5 +X6 =45 We have to distribute 45 1s into six entities namely X1 ,X2..... . {1s being identical to each other}
Answer should have been : (45+6-1)C(6-1)=50C5 .

But we are given condition that X1,X2,X3>=5
Sorry where did the >=5 come from? unless you meant 4 ?

#### Plato

MHF Helper
To answer your first question. The number of ways to put I identical items into D different cells is $$\displaystyle \binom{I+D-1}{I}=\binom{I+D-1}{D-1}$$.

Next question. Because $$\displaystyle X_1$$ in an integer if $$\displaystyle X_1{\color{blue}>}4$$ then it is necessary that $$\displaystyle X_1{\color{blue}\ge}5$$.

#### jvignacio

Hi Plato, sorry i still dont understand why
Because $$\displaystyle X_1$$ in an integer if $$\displaystyle X_1{\color{blue}>}4$$ then it is necessary that $$\displaystyle X_1{\color{blue}\ge}5$$.

#### sid_178

Hi jvignacio,

Since values of variables X1,X2,...can only take values as integers (in our case non negative integers you can also say X1,x2,..are whole numbers)
So if value of a particular variable is greater than 4 ,it has to be greater than equal to 5 .
Like X1,X2,X3>4 and since X1,X2,X3 are whole numbers Therefore X1,X2,X3>=5.

#### jvignacio

Hi jvignacio,

Since values of variables X1,X2,...can only take values as integers (in our case non negative integers you can also say X1,x2,..are whole numbers)
So if value of a particular variable is greater than 4 ,it has to be greater than equal to 5 .
Like X1,X2,X3>4 and since X1,X2,X3 are whole numbers Therefore X1,X2,X3>=5.
Ok so for instance, another question

Question:
Use inclusion-exclusion to find the number of solutions in the non-negative integers to

$$\displaystyle X_1 + X_2 +$$ .... $$\displaystyle + X_6 = 45$$ with the conditions $$\displaystyle X_j < 6$$, $$\displaystyle j = 1,2,3,4.$$

We distribute N identical items into R persons so $$\displaystyle \binom{N+R-1}{R-1}$$ = $$\displaystyle \binom{45+6-1}{6-1}$$ = $$\displaystyle \binom{50}{5}$$ but we are given a condition, $$\displaystyle X_1,X_2,X_3,X_4 \leq 5$$, so 20 1's are been distributed $$\displaystyle X_1,X_2,X_3,X_4$$ so the remaining 25 will be distributed to $$\displaystyle X_1,X_2$$.... Therefore answer = $$\displaystyle \binom{25+6-1}{6-1}$$ = $$\displaystyle \binom{30}{5}$$.

Is this correct? thanks

#### Plato

MHF Helper
Question:
Use inclusion-exclusion to find the number of solutions in the non-negative integers to $$\displaystyle X_1 + X_2 +$$ .... $$\displaystyle + X_6 = 45$$ with the conditions $$\displaystyle X_j < 6$$, $$\displaystyle j = 1,2,3,4.$$
.... Therefore answer = $$\displaystyle \binom{25+6-1}{6-1}$$ =$$\displaystyle \binom{30}{5}$$.
Is this correct? thanks
No, that is not correct. And that is not even the bad news.
Your title of this thread is inclusion-exclusion and that is what is called for in this case.
Here is the answer $$\displaystyle \sum\limits_{k = 0}^4 {\left( { - 1} \right)^k \binom{4}{k}\binom{50-6k}{5}}$$.

To see this, we find the number of ways at least one of $$\displaystyle X_j,~j=1,2,3,4$$ is at least six.
That is using inclusion/exclusion. Then we take that number from the total.

#### jvignacio

No, that is not correct. And that is not even the bad news.
Your title of this thread is inclusion-exclusion and that is what is called for in this case.
Here is the answer $$\displaystyle \sum\limits_{k = 0}^4 {\left( { - 1} \right)^k \binom{4}{k}\binom{50-6k}{5}}$$.

To see this, we find the number of ways at least one of $$\displaystyle X_j,~j=1,2,3,4$$ is at least six.
That is using inclusion/exclusion. Then we take that number from the total.
okay now Im really confused because I did that last question exactly like the first question.