# Thread: inclusion & exclusion help

1. ## inclusion & exclusion help

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.

2. 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 .

3. Originally Posted by 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 .
hey sorry, first question.. i thought it was n+r-1 C r ? NOT n+r-1 C r-1 ?

4. Originally Posted by 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
Sorry where did the >=5 come from? unless you meant 4 ?

5. 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$.

6. Hi Plato, sorry i still dont understand why Originally Posted by Plato 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$.

7. 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.

8. Originally Posted by 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.
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.$

My Answer:

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

9. Originally Posted by jvignacio 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.

10. Originally Posted by Plato 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. 11. Originally Posted by jvignacio I did that last question exactly like the first question.
Why would you do that?
The two questions are completely different.
If they are different, why would you do them the same way?
You do see that they are entirely different. Don't you?

12. Originally Posted by Plato Why would you do that?
The two questions are completely different.
If they are different, why would you do them the same way?
You do see that they are entirely different. Don't you?
Yes I see they are different but its the concept of inclusion & exclusion that I dont understand. If I understood the concept the I would approach the questions differently. #### Search Tags

exclusion, inclusion 