# A question about the Inclusion-Exclusion principle

Grandma has 8 grandchildren, and 4 different types of popsicles:

• 6 Vanilla popsicles
• 6 Strawberry popsicles
• 5 Banana popsicles
• 3 Chokolate popsicles

This morning, all of her grandchildren came together and asked for one popsicle each (every grandchild asked for a particular flavor). What is the total number of different sets of requests that Grandma can fulfill?

I think this is related to the Inclusion-Exclusion principle because it was taught in the same class. Can you help me solve it?

I did reach the following sum, but I imagine the question's author had something simpler in mind...

$E(0) = W(0)-W(1) = 3^8 - 4\cdot C(8,8)-4\cdot 3\cdot C(7, 8)-2\cdot C(6, 8)\cdot 3^2-C(5, 8)\cdot 3^3 - C(4, 8)\cdot 3^4$

-

## 1 Answer

I don't quite understand how you arrived at your result, so I'll try to sketch my solution. As you tagged the question as homework, there are no computations - just the idea.

There are at first $4$ possibilities to consider, depending how many chocolate popsicles the kids want: $0,1,2$ or $3$. Say $A(i)$ is the number of requests that have $i$ chocolate popsicles chosen. Let $T$ be the desired total. Then clearly:

$$T = A(0) + A(1) + A(2) + A(3)$$

as the possibilities are mutually exclusive and exhaustive.

• $A(3)$ is easy: $3$ kids picked chocolate, and the remaining $5$ are choosing amongst the other three flavours. Note that they can all choose the same flavour.

• $A(2)$ is just as easy: you have $6$ kids left to consider. Assume first that there are $6$ banana popsicles as well. Count all possible choices, then discount the one case when all six kids pick the banana popsicle.

• $A(1)$ and $A(0)$: this would be hard to compute as directly as the previous two. Try it this way: counting $A(1)$ is equivalent to the problem:

Grandma has 7 grandchildren, and 3 different types of popsicles:

- 6 Vanilla popsicles
- 6 Strawberry popsicles
- 5 Banana popsicles


This morning, all of her grandchildren came together and asked for one popsicle each (every grandchild asked for a particular flavor). What is the total number of different sets of requests that Grandma can fulfill?

Which is just the original problem minus one child and the chocolate popsicles. You approach it as above. Let $B(i)$ be the number of requests where $i$ banana popsicles are picked.

Then you have:

$$A(1) = B(0) + B(1) + B(2) + B(3) + B(4) + B(5)$$

All these $B(i)$ are now easy to compute. A similar calculation works for $A(0)$.

-