Thread: 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

.... with the conditions ,

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

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 .

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 ?

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 ?

To answer your first question. The number of ways to put I identical items into D different cells is .

Next question. Because in an integer if then it is necessary that .

Hi Plato, sorry i still dont understand why

Originally Posted by Plato

Because in an integer if then it is necessary that .

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.

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

.... with the conditions ,

My Answer:

We distribute N identical items into R persons so = = but we are given a condition, , so 20 1's are been distributed so the remaining 25 will be distributed to .... Therefore answer = = .

Is this correct? thanks

Originally Posted by jvignacio

Question:
Use inclusion-exclusion to find the number of solutions in the non-negative integers to .... with the conditions ,
.... Therefore answer = = .
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 .

To see this, we find the number of ways at least one of is at least six.
That is using inclusion/exclusion. Then we take that number from the total.

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 .

To see this, we find the number of ways at least one of 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.

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?

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.