inclusion & exclusion help

Oct 2007
517
6
Santiago
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.
 
Sep 2008
14
0
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 .
 
Oct 2007
517
6
Santiago
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 ?
 
Oct 2007
517
6
Santiago
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
Aug 2006
22,455
8,631
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\).
 
Oct 2007
517
6
Santiago
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\).
 
Sep 2008
14
0
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.
 
Oct 2007
517
6
Santiago
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
 

Plato

MHF Helper
Aug 2006
22,455
8,631
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.
 
Oct 2007
517
6
Santiago
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. :(