Color combination problem

Question

How many different ways are there to color the objects $a_1 , a_2 , ... , a_n$ ($n > 3$) using 3 colors if every color must be used at least once?

I thought it was $3^n - 6$ to account for the 6 cases that you have to disregard (all the same color, all two colors).

score 1 · Accepted Answer · edited Apr 18 '21 at 05:47

There are two interpretations: (i) The $n$ objects are distinct and (ii) They are identical.

(i) Let the colours be $A,B,C$. A colouring can be viewed as a function from the set $\{a_1,a_2,\dots,a_n\}$ to the set $\{A,B,C\}$. There are $3^n$ such functions.

However, some ,do not use all the colours: There are $2^n$ that do not use $A$, $2^n$ that do not use $B$, and $2^n$ that do not use $C$.

However, $2^n+2^n+2^n$ does not count correctly the forbidden colourings. For in the first $2^n$, the colourings that use neither $A$ nor $B$ are counted. They are also counted in the second $2^n$. The colourings that use neither $A$ nor $C$ are counted in the first $2^n$ and the third. And the colourings that use neither $B$ nor $C$ are also double-counted. So the number of forbidden colourings is $3\cdot 2^n$ minus the number of monochromatic colourings, which is $3$. There are $3\cdot 2^n-3$ forbidden colourings.

Thus the number of colourings in which every colour is used at least once is $3^n -3\cdot 2^n+3$.

(ii) Line up the $n$ identical objects. There are $n-1$ "gaps" between consecutive objects. Choose $2$ of these gaps to put a separator into, colour everything up to the first separator $A$, colour the objects between the two separators $B$, and the rest $C$. There are just as many allowed colourings of the identical objects as there are ways to insert separators. There are $\binom{n-1}{2}$ such ways.

Remark: The calculation for distinct objects used the Principle of Inclusion/Exclusion. The calculation for identical objects used the technique of Stars and Bars.

It is $3^n-(3\cdot 2^n-3)$, which "simplifies" to $3^n-3\cdot 2^n+3$. — André Nicolas, Feb 18 '14 at 07:11
why is the number of forbidden colors $3 \cdot 2^n - 3 $instead of + 3? — user127778, Feb 18 '14 at 07:16
The sum $2^n+2^n+2^n$ double-counts the colourings that omit $A$ and $B$, in other words the one colouring that only uses $C$. There is also double-counting of the colouring that uses only $B$, and of the one that uses only $A$. so we must subtract $3$ from $3\cdot 2^n$. — André Nicolas, Feb 18 '14 at 07:22
It is $3^3-3\cdot 2^3+3$. which is $6$, the number of permutations of a $3$-element set. — André Nicolas, Feb 18 '14 at 07:25

Justin Case · Answer 2 · 2014-02-18T07:48:34.740

A colouring can be seen as a $n$-lettered string created from the three letters $r$, $g$, $b$ (red, green, blue) containing at least one $r$, one $g$ and and one $b$. The correspondent exponential generating function is thus

$$f(x)=\left(x^1+\frac{1}{2!} x^2 + \frac{1}{3!} x^3 + \ldots \right)^3 $$

and so the answer to this problem is the coefficient of $\frac{x^n}{n!}$ in $f(x)$ (why?). Now,

$$f(x)=(e^x-1)^3=3e^x-3e^{2x}+e^{3x}+1,$$

making the answer more or less evident; $3-3(2^n)+3^n=3^n-3(2^n)+3$.

Color combination problem

2 Answers2

Linked