Results 1 to 12 of 12

Math Help - inclusion & exclusion help

  1. #1
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517

    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

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

    I have no idea how to start or go about doing this problem. Any help would be much appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Sep 2008
    Posts
    14
    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 .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Quote Originally Posted by sid_178 View Post
    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 ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Quote Originally Posted by sid_178 View Post
    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 ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,824
    Thanks
    1717
    Awards
    1
    To answer your first question. The number of ways to put I identical items into D different cells is \binom{I+D-1}{I}=\binom{I+D-1}{D-1}.

    Next question. Because X_1 in an integer if X_1{\color{blue}>}4 then it is necessary that X_1{\color{blue}\ge}5.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Hi Plato, sorry i still dont understand why
    Quote Originally Posted by Plato View Post
    Because X_1 in an integer if X_1{\color{blue}>}4 then it is necessary that X_1{\color{blue}\ge}5.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Sep 2008
    Posts
    14
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Quote Originally Posted by sid_178 View Post
    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

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

    My Answer:

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

    Is this correct? thanks
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,824
    Thanks
    1717
    Awards
    1
    Quote Originally Posted by jvignacio View Post
    Question:
    Use inclusion-exclusion to find the number of solutions in the non-negative integers to X_1 + X_2 + ....  + X_6 = 45 with the conditions X_j < 6, j = 1,2,3,4.
    .... Therefore answer = \binom{25+6-1}{6-1} = \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 \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 X_j,~j=1,2,3,4 is at least six.
    That is using inclusion/exclusion. Then we take that number from the total.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Quote Originally Posted by Plato View Post
    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 \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 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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,824
    Thanks
    1717
    Awards
    1
    Quote Originally Posted by jvignacio View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inclusion Exclusion
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 9th 2011, 10:38 AM
  2. Inclusion/Exclusion
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 19th 2011, 03:49 AM
  3. Inclusion/Exclusion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 3rd 2009, 08:46 AM
  4. Inclusion-exclusion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 28th 2009, 02:45 AM
  5. inclusion/exclusion
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 18th 2008, 10:31 PM

Search Tags


/mathhelpforum @mathhelpforum