Why would Inclusion-Exclusion be used here?

Question

I'm trying to do some discrete mathematics work and I am told I need to use Inclusion-exclusion, but I really don't see why the exclusion would be needed?

The question:

What is the number of ways to color $n$ objects with 3 colors if every color must be used at least once?

If we let each color represent a circle on a venn diagram, we would come up with this something like this:

Let's say the green circle is $A$, the blue circle is $B$ and the red circle is $C$.

If we used inclusion-exclusion, $|A \cup B \cup C| = |A| + |B| + |C| = |A \cap B| - |A \cap C| - |B \cap C| + |A \cap C \cap C|$

Why would you exclude $|A \cap B| - |A \cap C| - |B \cap C|$? That would be getting rid of yellow, purple, and baby blue. Is there something I'm missing?

I would say there are 7 possible colors per object, therefore, the number of ways to color n objects with 3 colors would be $n^7$.

Answer 1

We can make a table of the number of ways to color:

Using color $1$ only: $1$ way to color.

Using color $2$ only: $1$ way to color.

Using color $3$ only: $1$ way to color.

Using colors $1$ and $2$ (so each color appears at least once): $2^n-2$ ways to color

Using colors $1$ and $3$ (so each color appears at least once): $2^n-2$ ways to color

Using colors $2$ and $3$ (so each color appears at least once): $2^n-2$ ways to color

Using colors $1,2$ and $3$ (so each color appears at least once): $3^n-3\cdot2^n+6-3=3^n-3\cdot2^n+3$

Answer 2

Why would you exclude |A∩B|−|A∩C|−|B∩C| ? That would be getting rid of yellow, purple, and baby blue. Is there something I'm missing?

They are not the rounded-triangle areas, they are the areas of the lenticular shapes.

That is, they are the $()$ where two circles overlap.

So if you take the area of all three circles, subtract the areas where two circles overlap, add back the area where three circles overlap, how many of each distinct coloured section do you measure?

• Circle A: Green, Cyan, White, Yellow
• Circle B: Blue, Cyan, White, Purple
• Circle C: Red, Purple, White, Yellow.
• Lens $A \cap B$: Cyan, White
• Lens $B\cap C$: Purple, White
• Lens $A\cap C$: White, Yellow
• Central $A\cap B\cap C$: White.

But this is not what the question was asking; though the principle is similar.

---

I would say there are 7 possible colors per object, therefore, the number of ways to color n objects with 3 colors would be $n^7$ .

No.   The question means each object can be painted one of three colours, and each colour must be used to paint at least one object.

The ways to paint $n$ objects with at most $3$ colours is $3^n$.   But that's at most three colours.   We want to use exactly three colours.

So you have to count ways to paint the objects using at most three colours, exclude ways that use at most two colours, and include ways that use only one colour.

$$3^n - \binom{3}{2} 2^n + \binom{3}{1} = 3^n - 3\cdot 2^n + 3$$

Answer 3

$$\left|\,A\cup B\cup C\,\right|=\color{#C00000}{\left|\,A\,\right|+\left|\,B\,\right|+\left|\,C\,\right|}\color{#00A000}{-\left|\,A\cap B\,\right|-\left|\,B\cap C\,\right|-\left|\,A\cap C\,\right|}\color{#0000F0}{+\left|\,A\cap B\cap C\,\right|}$$ Count the number of times that something that is in only one of $A$, $B$, or $C$ is counted: $$ 1=\color{#C00000}{1}\color{#00A000}{-0}\color{#0000F0}{+0} $$ Count the number of times that something that is in exactly two of $A$, $B$, and $C$ is counted: $$ 1=\color{#C00000}{2}\color{#00A000}{-1}\color{#0000F0}{+0} $$ Count the number of times that something that is in all three of $A$, $B$, and $C$ is counted: $$ 1=\color{#C00000}{3}\color{#00A000}{-3}\color{#0000F0}{+1} $$

---

To apply this to your coloring, note that in $\left|\,A\,\right|+\left|\,B\,\right|+\left|\,C\,\right|$ we have colored (or counted) each of $\left|\,A\cap B\,\right|$, $\left|\,B\cap C\,\right|$, and $\left|\,A\cap C\,\right|$ twice, so we need to remove one of each of those. However, in removing all three of $\left|\,A\cap B\,\right|$, $\left|\,B\cap C\,\right|$, and $\left|\,A\cap C\,\right|$, we've removed $\left|\,A\cap B\cap C\,\right|$ three times from the initial three times it was added in $\left|\,A\,\right|+\left|\,B\,\right|+\left|\,C\,\right|$, so we need to color (or count) it again.

Answer 4

It is not made clear whether the objects to be painted are distinct (like houses) or should be considered identical, like balls. The answers in the two cases are different. We study only the case where the objects are distinct.

Remember the side condition that each colour must be used at least once.

Suppose we forget about that condition. Assume say that there are $10$ distinct objects to be painted.

If there were no condition about using each colour at least once, the answer would be simple. For every one of the $10$ objects, there are $3$ colour choices, for a total of $3^{10}$.

Let the colours be blue, red, and white. Some of the $3^{10}$ choices mentioned above are bad choices. For example, some of these choices do not use the colour blue.

How many choices do not use blue? Then we are using a $2$-colour palette. So $2^{10}$ choices do not use blue. Similarly, $2^{10}$ choices do not use red, and $2^{10}$ choices do not use white.

So is the number of bad choices equal to $3\cdot 2^{10}$? Not quite. Each of the $2^{10}$ choices includes $2$ choices in which only one colour is used. So each one colour choice has been counted by $3\cdot 2^{10}$ twice. So there are in fact only $3\cdot 2^{10}-3$ bad choices.

Thus the total number of valid choices is $3^{10}-3\cdot 2^{10}+3$. It is useful to write this as $\binom{3}{3}3^{10}-\binom{3}{2}2^{10}+\binom{3}{1}1^{10}$.