\problemdata      
        {counting-3} % latex-friendly label for the prob.
        {Counting} % The topic(s) of the problem content.
        {Radhika Nagpal} % Source (if known)
        {S02 PS8} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).




\begin{problem}
A possible algorithm for checking if an arbitrary labelled graph is
3-colorable is to enumerate all possible 3 color assignments for the
nodes of the graph and then test each color assignment to see if it is
a valid coloring. We are going to count the maximum number of color
assignments that this algorithm may have to test (in other words, what
is the worst case behavior of this approach).

Let $G$ be a $n$ node graph with vertices labelled $v_1$ through
$v_n$. Let the set of colors $C=\{R,G,B\}$. A \emph{color assignment} 
is a function from the set of labelled nodes $G$ to the set of colors
$C$; a \emph{valid} coloring is one where no two adjacent nodes in $G$ 
have the same color, however we will not be concerned much with
validity in this problem.
\begin{problemparts}

\problempart 
How many different ways can you assign colors from $C$ to
the nodes of $G$? (Note that colors are not interchangable.)

\solution{
This is exactly the number of functions from an $n$-element set (the
nodes of $G$) to a $3$-element set (the colors). We know there
are~$3^n$ such functions.
}

\problempart 
There are much easier ways to check if a graph can be colored with one
color or two colors. Therefore we are really only interested in color
assignments that use \emph{exactly}~3 colors. How many ways can we
color the nodes of $G$, so that all three colors in $C$ are used?

\solution{
Let $A_i$ be the set of all colorings that use \emph{exactly}~$i$
colors, for $i=1,2,3$, so that we are after $|A_3|$. Clearly, $A_1$,
$A_2$, $A_3$ are disjoint, so  
$$
|A_1 \cup A_2\cup A_3| = |A_1| + |A_2| + |A_3|,
$$
and they cover the entire set of 3-colorings of $G$, so 
$$
|A_1 \cup A_2\cup A_3| = 3^n,
$$
by the previous part. Hence, to calculate $|A_3|$, we combine these
two equations to get 
\begin{equation}\label{eq:a}
|A_3| = 3^n - |A_2| - |A_1|,
\end{equation}
so that it suffices to calculate $|A_2|$, $|A_1|$. 

The number $|A_1|$ of colorings that use exactly one color is easily
seen to be
\begin{equation}
|A_1| = 3,
\end{equation}
because, once we pick one of the~3 colors, the numbering is fully
specified. 

To find the number $|A_2|$ of colorings that use exactly two colors,
we first observe that 
$$
A_2 = A_{RG} \cup A_{GB} \cup A_{BR},
$$
where $A_{RG}$ is the set of colorings that use \emph{both} red
\emph{and} green; and similarly for $A_{GB}$, $A_{BR}$. Easily, these
three sets are disjoint and all have the same size. So  
\begin{equation}
|A_2| = |A_{RG}| + |A_{GB}| + |A_{BR}| = 3|A_{RG}|,
\end{equation}
and we need to find $|A_{RG}|$ only. 

Now, we know that the total number of colorings that use red and green
(but maybe not both of them) is $2^n$. Among these colorings only two
fail to use both colors: the ``all-red'' coloring and the
``all-green'' one. So, 
\begin{equation}\label{eq:d}
|A_{RG}| = 2^n - 2.
\end{equation}

Combining~\eqref{eq:a}--\eqref{eq:d}, we get 
$$
|A_3| = 3^n - 3(2^n-2) - 3 = 3^n - 3\cdot 2^n + 3.
$$
}

\problempart 
For a graph with three nodes we can see that the number of color
assignments with exactly 3 colors are just the number of possible
permutations of $R$, $G$, $B$, which is $3!$. Verify that your formula
in part~(b) gives the right answer for a 3-node graph. 

\solution{
$3^3 - 3\cdot 2^3 + 3 = 27 -24 +3 = 6 = 3!$.

Note that the formula $3! \binom{n}{3} 3^{n-3}$ (suggested by several
tables this morning as the correct solution to part~(b)) returns the
correct value for $n=3$,
$$
3! \binom{3}{3} 3^{3-3} = 6\cdot 1\cdot 1 = 6,
$$
but tragically fails for other values, e.g., $n=4$,
$$
3! \binom{4}{3} 3^{4-3} = 6\cdot 4\cdot 3 = 72 \neq 
36 = 3^4 - 3\cdot 2^4 + 3.
$$
So, \emph{always test your formula on special cases, but never trust
your special tests}.
}

\problempart 
Even so, many of the assignments are redundant. For
example for a four node graph the color assignment $RGBB$ is
essentially the same as $RBGG$, because if one fails the other will 
also. In general, any two colorings are equivalent if one assignment
can be achieved from the other just by swapping color names. If we
remove these redundant color assignments, how much can we improve our
number from part~(b)?

\solution{
Consider the binary relation on $A_3$ that relates a coloring $c$ to
another coloring $c'$ iff $c'$ can be obtained from $c$ via a
permutation of the colors. One can easily check this is
an equivalence relation, that breaks $A_3$ into equivalence classes of
$3!=6$ members each. (To see why $6$ is the size of an equivalence
class: if you pick any coloring $c$ from the class and apply to it all
$3!=6$ possible permutations of the 3~colors, you are certain to
derive all members of the class exactly once.) 

Clearly, we want to count the number of these equivalence classes. But
since the classes are disjoint, cover the entire $A_3$, and all have
size~6, their number must be 
$$
\frac{|A_3|}{6} = \frac{3^n - 3\cdot 2^n + 3}{6}.
$$
}
\end{problemparts}
\end{problem}

