Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By Plato
  • 1 Post By SlipEternal

Math Help - Inclusion-Exclusion principle

  1. #1
    Junior Member
    Joined
    Aug 2013
    From
    hcm
    Posts
    27

    Inclusion-Exclusion principle

    Hi everyone, I don't know how to apply Inclusion-Exclusion principle to find the number of distributions of five red balls and five blue balls into three distinct boxes, with no empty boxes.
    Can anyone help me with this problem? I will be thankful.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,708
    Thanks
    1638
    Awards
    1

    Re: Inclusion-Exclusion principle

    Quote Originally Posted by math88 View Post
    Hi everyone, I don't know how to apply Inclusion-Exclusion principle to find the number of distributions of five red balls and five blue balls into three distinct boxes, with no empty boxes.
    Using inclusion/exclusion to find at least one of the boxes is empty.
    Let the boxes be $A,~B,~\&~C$ and $\|X\|$ is the number of ways for box $X$ is empty.

    So we have $\|A\|+\|B\|+\|C\|-\|A\& B\|-\|A\& C\|-\|B\& C\|$
    Subtract that number from the total.
    Thanks from math88
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2013
    From
    hcm
    Posts
    27

    Re: Inclusion-Exclusion principle

    the number of distributions of five red balls and five blue balls into three distinct boxes is 3^10
    |A|=|B|=|C| = 2^10 is the number of ways for missing box A (or B, or C )
    |A&B|=|A&C| = |B&C| = 1^10 is the number of ways for missing 2 boxes.
    |A&B&C|=0 is the number of ways for missing 3 boxes.
    => The number of ways for missing at least one box is |A U B U C| =|A|+|B|+|C|-|A&B|-|A&C|-|B&C|+|A&B&C|=2^10+2^10+2^10-1-1-1+0=3069
    => the answer is 3^10-3069= 55980

    Is that right?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,900
    Thanks
    763

    Re: Inclusion-Exclusion principle

    First, distribute the red balls. Consider sequences of the form RRRRR|| (seven characters, however many R's appear to the left of the first | is the number of red balls in the first box, the number of R's between the first and the second | is the number of red balls in the second box, and the number of R's after the second | is the number of red balls in the last box). This obviously counts the number of ways to distribute the red balls. Multiply that by the number of ways to distribute the blue balls (it will be the same).. Since you are just choosing the positions of the R's in the sequence (and the remaining two positions will be |'s), it is \binom{7}{5} ways to distribute the red balls and the same for the blue. That gives a total of 21^2 total ways to distribute all 10 balls. Next, count the number of ways that box 1 is empty. That is the number of sequences that begin with a |. So, if the | is fixed, there are \binom{6}{5}=6 ways to distribute the red balls times \binom{6}{5}=6 ways to distribute the blue balls.

    Next, count the number of ways that box #2 is empty. That means the two pipes have to be next to each other. You can treat them as a single character ||. Hence, again, there are 6 ways for each the red and blue balls. Finally, if box 3 is empty, it means that the | was at the end of the sequence. Again, there are 6\cdot 6 = 36 ways that can happen.

    Next, check the number of ways to have two boxes empty. If box 1 and 2 are empty, it means the sequence starts with ||. If boxes 1 and 3 are empty, it means the sequence starts with | and ends with |. And if boxes 2 and 3 are empty, it means the sequence ends with ||. In each case, there is only one way to order the R's and B's.
    So, |A\cup B \cup C| = |A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B \cap C| = 36+36+36-1-1-1+0 = 35\cdot 3 = 105

    SO, the total number of ways to distribute the ten balls leaving no box empty is 21^2-105 = 336
    Thanks from math88
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. inclusion and exclusion principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 9th 2013, 01:27 PM
  2. Inclusion Exclusion Principle?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 12th 2012, 02:45 PM
  3. Inclusion Exclusion Principle Help!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 28th 2011, 02:43 AM
  4. Inclusion - Exclusion Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 15th 2011, 06:52 AM
  5. Principle of Inclusion of Exclusion
    Posted in the Statistics Forum
    Replies: 2
    Last Post: December 10th 2008, 12:15 PM

Search Tags


/mathhelpforum @mathhelpforum