I have seen, and solved the following problem:
How many ways to color n objects with 3 colors $\{A, B, C\}$, if all colors must be used at least once.
$\require{enclose}$
The answer is as follows:
$$3^n-{{3}\choose{2}}\cdot2^n + {{3}\choose{1}}\cdot1^n$$
Because the number of forbidden colorings is:
$${{3}\choose{2}}\cdot2^n – {{3}\choose{1}}\cdot1^n$$
The overall answer then reduces to:
$$3^n – 3\cdot2^n + 3$$
The solution comes to me as follows. There are $3\cdot2^n$ configurations that are illegal because they only use $2$ colors. Of these, some are counted more than once so let's take a closer look:
$$2^n\,\{B, C\}\qquad\qquad2^n\,\{A, C\}\qquad\qquad2^n\,\{A, B\}\qquad\qquad$$
All the formations you can make with EXACTLY two colors are unique and counted only once. How about all the formations you can make with EXACTLY one color? Well that answer is obviously ${{3}\choose{1}}$ but let's see how many times we have overcounted by subtracting $3\cdot2^n$. Just like we broke up $3^n$ into our $3\cdot2^n$ formations with two colors, let's break up each $2^n$ into $2$ single color $1^n$ formations and see if we have any repeats!
$$2^n\,\{B, C\}\qquad\qquad2^n\,\{A, C\}\qquad\qquad2^n\,\{A, B\}\qquad\qquad$$
\begin{array}{cc}
\text{Each of the $2^n$ can make 2 single color sets so we will have repeats:}\\
\hline
\end{array}
$$1^n\,\{B\}\qquad\qquad\qquad1^n\,\{A\}\qquad\qquad\qquad\enclose{updiagonalstrike}{1^n\,\{A\}}$$
$$1^n\,\{C\}\qquad\qquad\qquad\enclose{updiagonalstrike}{1^n\,\{C\}}\qquad\qquad\qquad\enclose{updiagonalstrike}{1^n\,\{B\}}$$
You can see that there are obviously only ${{3}\choose{1}}$ unique illegal single color formations, however we've accounted for each one twice by subtracting $3\cdot2^n$ from $3^n$ so we must add back the ones we overcounted. This is why we add back a ${{3}\choose{1}}$. If we overcounted each unique single color formation by 100, I believe we would add back 100 to the final answer so we could be left with only the unique single color formations that are illegal.
I was working on the following problem:
How many ways to color n objects with 4 colors $\{A, B, C, D\}$, if all colors must be used at least once.
Following the same logic in this post's answer, the following process makes sense to me:
Total number of ways to color N objects with any colors would be $4^n$. Of the $4^n$, there are:
$$3^n\,\text{that use only}\,\{B, C, D\},\;3^n\,\text{that use only}\,\{A, C, D\},\;3^n\,\text{that use only}\,\{A, B, C\}$$
This givs us ${{4}\choose{3}}\cdot3^n$ invalid options. However this over-counts several invalid options several times. Let's take a closer look.
$$3^n\, \{B, C, D\}\qquad3^n\, \{A, C, D\}\qquad3^n\, \{A, B, D\}\qquad3^n\, \{A, B, C\}$$
\begin{array}{cc}
\text{Which breaks down to the following (${{4}\choose{2}}$duplicates crossed out):}\\
\hline
\end{array}
$$2^n\,\{B, C\}\qquad\qquad2^n\,\{A, C\}\qquad\qquad2^n\,\{A, B\}\qquad\qquad\enclose{updiagonalstrike}{2^n\,\{A, B\}}$$
$$2^n\,\{B, D\}\qquad\qquad2^n\,\{A, D\}\qquad\qquad\enclose{updiagonalstrike}{2^n\,\{A, D\}}\qquad\qquad\enclose{updiagonalstrike}{2^n\,\{A, C\}}$$
$$2^n\,\{C, D\}\qquad\qquad\enclose{updiagonalstrike}{2^n\,\{C, D\}}\qquad\qquad\enclose{updiagonalstrike}{2^n\,\{B, D\}}\qquad\qquad\enclose{updiagonalstrike}{2^n\,\{B, C\}}$$
\begin{array}{cc}
\text{Which breaks down to the following:}\\
\hline
\end{array}
$$2^n\,\{B, C\}\quad2^n\,\{B, D\}\quad2^n\,\{C, D\}\quad2^n\,\{A, C\}\quad2^n\,\{A, D\}\quad2^n\,\{A, B\}$$
\begin{array}{cc}
\text{Since all $2^n$ are unique, the only sets that we count many times here are the one with one letter}\\
\hline
\end{array}
$$1^n\,\{B\}\qquad\enclose{updiagonalstrike}{1^n\,\{B\}}\qquad\enclose{updiagonalstrike}{1^n\,\{C\}}\qquad1^n\,\{A\}\qquad\enclose{updiagonalstrike}{1^n\,\{A\}}\qquad\enclose{updiagonalstrike}{1^n\,\{A\}}$$
$$1^n\,\{C\}\qquad1^n\,\{D\}\qquad\enclose{updiagonalstrike}{1^n\,\{D\}}\qquad\enclose{updiagonalstrike}{1^n\,\{C\}}\qquad\enclose{updiagonalstrike}{1^n\,\{D\}}\qquad\enclose{updiagonalstrike}{1^n\,\{B\}}$$
We obviously know that there are going to be only 4 unique countings of 1 letter sets since there are only 4 colors, so the other 8 were counted many times, just like the other 6 sets of $2^n$
To me, this makes the answer:
$$4^n – {{4}\choose{3}}\cdot3^n + {{4}\choose{2}}\cdot2^n + 8\cdot1^n$$
I am slightly suspicious as it doesn't follow the pattern that would make ${{4}\choose{1}}\cdot1^n$ be the last term, however walking through the logic it is clear to me that just as we counted 6 of the $2^n$ sets twice, we are counting, the monochromatic sets 8 extra times than necessary, so we need to give them back so I believe my first solution is correct? Could someone verify my logic here?
Best Answer
Consider $$4^n-\binom{4}{3}\cdot3^n+\binom{4}{2}2^n-\binom{4}{1}1^n$$
Any coloring that uses exactly 3 colors is subtracted from the $4^n$ total colorings once in the $-\binom{4}{3}\cdot3^n$ term. That coloring only appears in one of the $\binom{4}{3}$ collections of colorings, and it is only one of that collection's $3^n$ colorings.
Any coloring that uses exactly 2 colors (for example, an $\{A,B\}$-coloring) is subtracted from the $4^n$ total colorings twice in the $-\binom{4}{3}\cdot3^n$ term (as one of the $\{A,B,C\}$-colorings and as one of the $\{A,B,D\}$-colorings), then added back once in the $+\binom{4}{2}2^n$ term (as one of the $\{A,B\}$-colorings). The net effect is to subtract it once from the $4^n$ total.
Any coloring that uses exactly 1 color (for example, the all-$A$ coloring) is subtracted from the $4^n$ total colorings three times in the $-\binom{4}{3}\cdot3^n$ term (as one of the $\{A,B,C\}$-colorings, as one of the $\{A,B,D\}$-colorings, and as one of the $\{A,C,D\}$-colorings), then added back three times in the $+\binom{4}{2}2^n$ term (as one of the $\{A,B\}$-colorings, as one of the $\{A,C\}$-colorings, and as one of the $\{A,D\}$-colorings), and then subtracted again once in the $-\binom{4}{1}1^n$ term (as the $\{A\}$-coloring). The net effect is to subtract it once from the $4^n$ total.
This is all an example of the inclusion-exclusion principle.
Written as $$\binom{4}{4}4^n-\binom{4}{3}\cdot3^n+\binom{4}{2}2^n-\binom{4}{1}1^n+\binom{4}{0}\cdot0^n$$ you can directly verify that this gives correct results for $n=0,1,2,3,4$.
For $r$ colors, the same logic gives the formula $$\sum_{k=0}^r\binom{r}{r-k}(-1)^k(r-k)^n$$ which is equivalent (by reindexing $k\mapsto r-k$) to $$\sum_{k=0}^r\binom{r}{k}(-1)^{r-k}k^n$$