7

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?

Community
  • 1
Dominic Farolino
  • 501

1 Answers1

4

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$$

2'5 9'2
  • 54,717
  • Can you please extend it for $r$ choices of colours? – MathIsNice1729 Dec 29 '15 at 07:46
  • I feel like there is an error in your last paragraph. We don't want to subtract it JUST once from the total, $4^n$, we want to subtract it ALL but once from the total, so that were only counting it one time and one time only. So we leave that one case with the $4^n$ and subtract the rest that are counted multiple times – Dominic Farolino Dec 29 '15 at 07:50
  • @DomFarolino I don't follow you. The count $4^n$ includes the one instance where everything is colored $A$. The $-\binom{4}{3}\cdot3^n$ subtracts three colorings where everything is colored $A$. The $+\binom{4}{2}\cdot2^n$ adds back three colorings where everything is colored $A$. Finally, $-\binom{4}{1}\cdot1^n$ subtracts one coloring where everything is colored $A$. The net is that no all-$A$ colorings are counted. We have subtracted a net of one all-$A$ coloring from the one that was included with the $4^n$ count. – 2'5 9'2 Dec 29 '15 at 07:55
  • I expanded the wording, in case that helps. – 2'5 9'2 Dec 29 '15 at 08:08
  • @alex.jordan Ok so I understand that each solution using exactly 3 colors has been subtracted once...each solution using exactly two colors have been subtracted twice, as shows my table in the question that has the repeated $2^n$ sets stricken out. Then you say each set using exactly 1 color has been subtracted once. This is where I lose you. I see each one being subtracted 3 times from each of the unique $2^n$ sets, when we only need to subtract them once. So to make up for this, we need to add back two of each color, that we over-counted. – Dominic Farolino Dec 29 '15 at 17:55
  • @alex.jordan Similarly to how in my table in the question, we added back the stricken out duplicate $2^n$ sets, we have to add back the stricken out $1^n$ sets that were overcounted...exactly 8 of the 12 single color ($1^n$) sets formed from the unique $2^n$ sets are not unique so we must add them back...This is my rationale if that makes any sense – Dominic Farolino Dec 29 '15 at 17:57
  • With $n=4$, $\binom{4}{4}4^4$ counts ${\color{blue}{AAAA},AAAB,\ldots,ABCD,\ldots,DDDD}$. Note the one instance of $\color{blue}{AAAA}$. – 2'5 9'2 Dec 29 '15 at 18:19
  • Then $-\binom{4}{3}3^4$ counts ${\color{blue}{AAAA},AAAB,\ldots,ABCC,\ldots,CCCC}\sqcup{\color{blue}{AAAA}, AAAB\ldots,ABDD,\ldots,DDDD}\sqcup{\color{blue}{AAAA},AAAC,\ldots,ACDD,\ldots,DDDD}\sqcup{BBBB,BBBC,\ldots,BCDD,\ldots,DDDD}$. Note the three instances of $\color{blue}{AAAA}$. – 2'5 9'2 Dec 29 '15 at 18:19
  • Then $+\binom{4}{2}2^4$ counts ${\color{blue}{AAAA},AAAB,\ldots,BBBB}\sqcup{\color{blue}{AAAA},AAAC,\ldots,CCCC}\sqcup{\color{blue}{AAAA},AAAD,\ldots,DDDD}\sqcup{BBBB,BBBC,\ldots,CCCC}\sqcup{BBBB,BBBD,\ldots,DDDD}\sqcup{CCCC,CCCD,\ldots,DDDD}$. Note the three instances of $\color{blue}{AAAA}$. – 2'5 9'2 Dec 29 '15 at 18:19
  • Lastly, $-\binom{4}{1}1^4$ counts ${\color{blue}{AAAA}}\sqcup{BBBB}\sqcup{CCCC}\sqcup{DDDD}$. All together, $1-3+3-1=0$. This is all the effort I can make trying to explain it differently. I'm sorry if this isn't enough, but if you still don't see it, at least convince yourself that your approach is not working because it fails to give $24$ for $n=4$. – 2'5 9'2 Dec 29 '15 at 18:19
  • @alex.jordan . I appreciate it thanks a lot. I think that makes sense. I was seeing the $4^n$ as overcounting each single color set by 8, not just counting it once. I re-layed out my thought process for the n=3 problem in the question, which incidentally yields the right answer but seemingly by mistake. My original thought process was wrong. Thanks so much – Dominic Farolino Dec 29 '15 at 18:29
  • Cool. If you haven't already, read up on the link to the inclusion-exclusion principle. It makes this kind of thing easy in the future. – 2'5 9'2 Dec 29 '15 at 18:30