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

2. ## Re: Inclusion-Exclusion principle

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

3. ## 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?

4. ## 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$