# Coloring of an $1\times n$ board using 4 colors?

How can I find the number of ways to color an $1\times n$ board using the colors red, blue, green and orange if:

# of red squares is even

# of green squares is even

We did the tilings of a $1\times n$ board using squares and dominos in class, but I'm not sure how to do the coloring with more than two options

Thanks for any help!

-

Let $\mathrm{Even}(n)$ be the number of colorings of the $1\times n$ board in which the number of red and of green squares is each even. Let $\mathrm{Odd}(n)$ be the number of colorings of the $1\times n$ board in which the number of red and green squares is each odd.

For $n\geq 2$, color the initial $1\times (n-2)$ board any which way; there are $4^{n-2}$ ways of doing it. Now, if the number of red tiles and the number of green tiles are both even (which happens in $\mathrm{Even}(n-2)$ of the colorings), then we can complete the coloring by either coloring both remaining tiles green, both red, or each of them either blue or orange. This gives six different colorings with the same "base" coloring on the initial $1\times (n-2)$ board.

If the number of red tiles and the number of green tiles are both odd (which happens in $\mathrm{Odd}(n-2)$ of the colorings), then we must color the remaining two tiles one red and one green, in some order. That's two different colorings with the same "base" coloring.

If one of the number of red tiles and of green tiles is even and the other is odd (which occurs in $4^{n-2} - (\mathrm{Odd}(n-2)+\mathrm{Even}(n-2))$ of the colorings), then one of the two remaining tiles must be the deficient color, and the other tile can be either blue or orange. That gives 4 possible completions (select which tile is either blue or orange, select the color).

A similar computation holds for $\mathrm{Odd}(n)$, since we are trying to preserve parity.

So we have the recursion \begin{align*} \mathrm{Even}(n) &= 6\mathrm{Even}(n-2) + 2\mathrm{Odd}(n-2) + 4\bigl(4^{n-2}-\mathrm{Odd}(n-2)-\mathrm{Even}(n-2)\bigr)\\ &= 4^{n-1} + 2\mathrm{Even}(n-2) - 2\mathrm{Odd}(n-2)\\ &= 4^{n-1} + 2\Bigl(\mathrm{Even}(n-2) - \mathrm{Odd}(n-2)\Bigr).\\ \mathrm{Odd}(n) &= 6\mathrm{Odd}(n-2) + 2\mathrm{Even}(n-2) + 4\bigl(4^{n-2}-\mathrm{Odd}(n-2) - \mathrm{Even}(n-2)\bigr)\\ &= 4^{n-1} + 2\Bigl(\mathrm{Odd}(n-2) - \mathrm{Even}(n-2)\Bigr). \end{align*}

Thus, we have: $$\mathrm{Even}(n) - \mathrm{Odd}(n) = 4\Bigl(\mathrm{Even}(n-2)-\mathrm{Odd}(n-2)\Bigr).$$

We also have $\mathrm{Odd}(0) = 0$, $\mathrm{Even}(0)=1$; and $\mathrm{Odd}(1)=0$ and $\mathrm{Even}(1)=2$.

From this, it should be easy to get a formula for $\mathrm{Even}(k) - \mathrm{Odd}(k)$, and from there a formula for $\mathrm{Even}(n)$ for all $n\geq 1$.

-
$\mathcal{O}(n)$ can be confused with the asymptotic notation... –  Aryabhata Apr 25 '11 at 20:16
@Moron. Thanks; I'll replace with "Odd" and "even", then. –  Arturo Magidin Apr 25 '11 at 20:56
Having gone to all that effort, is there a reason you do not say $\mathrm{Even}(k) - \mathrm{Odd}(k) = 2^k$ ? –  Henry Apr 25 '11 at 21:10
@Henry: I actually had it all the way down to the formula for $\mathrm{Even}(n)$ (same as user9325, as it happens), and then decided to let a few nontrivial parts of the problem for the OP to do on her own. Maybe it was silly (or foolish). –  Arturo Magidin Apr 25 '11 at 21:13

Let us first count the colorings that contain at least one of the colors red and orange, and at least one of the colors blue and green.

Now by switching the first color that is red or orange, we see that there are just as much colorings with $k$ blue-green tiles and even red tiles as there are colorings with $k$ blue-green tiles and odd red tiles.

Now, by switching the first blue-green tile, we see that there are as many colorings with even red and even green tiles as there are of the three other varieties.

Therefore we have $\frac 14 \cdot (4^n-2^n-2^n)$ where the second factor counts all coloring minus the colorings that only use red-orange and those that only use blue-green.

Now, among the colorings that only use red-orange or only blue-green, the same argument gives that we want to count exactly half of them which gives $\frac 12 \cdot (2^n +2^n)$

Result: $4^{n-1}+2^{n-1}$

-

I just want to point out that exponential generating functions serve as a good approach here. Let $g(x)$ be the exponential generating function of the sequence $h_0, h_1, h_2,\ldots$, where $h_n$ is the number of acceptable colorings of a $1\times n$ board. So $h_n$ is the coefficient of $x^n$ in $g(x)$.

Then $$g(x)=\left(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots\right)^2\left(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}\cdots\right)^2$$ where the first squared term comes from the fact that red and green tiles must occurs in even numbers, so we only consider even powers, and the second squared term comes from the fact that orange and blue tiles can occur in any number.

The first series is just the even terms of the series for $e^x$, so bisecting the series into its even terms, one sees $g(x)$ simplifies to \begin{align*} g(x) &= \left(\frac{e^x+e^{-x}}{2}\right)^2\cdot(e^x)^2 \\ &= \frac{1}{4}(e^{2x}+2+e^{-2x})\cdot(e^{2x})\\ &= \frac{1}{4}(e^{4x}+2e^{2x}+1)\\ &= \frac{1}{4}+\frac{1}{4}\left(\sum_{n\geq 0}\frac{(4x)^n}{n!}+2\sum_{n\geq 0}\frac{(2x)^n}{n!}\right)\\ &= \frac{1}{4}+\frac{1}{4}\left(\sum_{n\geq 0}\frac{(4^n+2\cdot 2^n)x^n}{n!}\right) \end{align*} Since there is a $\frac{1}{4}$ hanging out outside the sum, we calculate $h_0=\frac{1}{4}+\frac{1}{4}(3)=1$. Then for the coefficient of nonconstant terms, we see $$h_n=\frac{1}{4}(4^n+2\cdot 2^n)=4^{n-1}+2^{n-1}$$ as noted in user9325's answer.

-