3
$\begingroup$

So the question asks me to find the number of ways H[n] to color a 1 by n chessboard with 3 colors - red, blue and white such that the number of red squares is even and number of blue squares is at least one. I am doing it in this way -

1.If the first square is white then the remaining n-1 squares can be colored in H[n-1] ways.

2.If the first square is red then another red will be needed in the n-1 remaining squares and the rest n-2 can be colored in H[n-2] ways. (i.e (n-1)*H[n-2])

3.And now is the problem with blue. If I put blue in the first square and say that the rest n-1 squares can be colored in H[n-1] ways that will be wrong as I already have a blue and may not need any more(while H[n-1] requires one blue at least). I thought of adding H'[n-1] to H[n] = H[n-1] + (n-1)*H[n-2] which gives H[n] = H[n-1] + (n-1)*H[n-2] + H'[n-1] where H'[n] is the number of ways to fill n squares with no blue squares(so H'[n] = (n-1)*H'[n-2] + H'[n-1]). So now I'm kind of really confused how to solve such an equation ->

H[n] = H[n-1] + (n-1)*H[n-2] + H'[n-1]. (I am specifically asked not to use exponential generating function to solve problem).

  • 0
    @BrianM.Scott Can you tell me the right expression for (2)?2012-07-23

4 Answers 4

2

I wouldn’t actually use a recurrence to solve this problem. Let $c_n$ be the number of ways of coloring the $1\times n$ board with an even number of red cells, and let $b_n$ be the number of these that have no blue cells. Then $h_n=c_n-b_n$, where $h_n$ is the number of colorings with an even number of red cells and at least one blue cell, $c_n=\sum_k\binom{n}{2k}2^{n-2k}\;,$ and $b_n=\sum_k\binom{n}{2k}\;.$

Then

$\begin{align*} c_{n+1}&=\sum_k\binom{n+1}{2k}2^{n+1-2k}\\ &=\sum_k\left(\binom{n}{2k}+\binom{n}{2k-1}\right)2^{n+1-2k}\\ &=2c_n+\sum_k\binom{n}{2k-1}2^{n-(2k-1)}\\ &=2c_n+\sum_k\binom{n}k2^{n-k}-\sum_k\binom{n}{2k}2^{n-2k}\\ &=2c_n+\sum_k\binom{n}k1^k2^{n-k}-c_n\\ &=c_n+3^n \end{align*}$

Clearly $c_0=1$, so

$c_n=1+\sum_{k=0}^{n-1}3^k\;,$

which is easy to evaluate in closed form. And $b_n$ is just the number of subsets of $\{1,\dots,n\}$ of even cardinality, so it’s also easy to evaluate in closed form.

However, if you want a recurrence, you can probably get one without too much trouble by working backwards from this solution.

  • 0
    Thanks a lot for this solution. I agree this problem is really more suited for calculating without resorting to recurrences.(can't upvote anyone as I need more reputation, but anyways, thanks) .2012-07-23
1

Hint: Let $X(n)$ be the number of ways without requiring at least one blue square, and $Y(n)$ the number of ways with no blue squares. Then $H(n) = X(n) - Y(n)$.

  • 0
    Ok. Th$a$nk you, I get it. But now I'm in another problem as the resulting equations contain variable coefficients, which I have asked in another question. Thanks again.2012-07-23
0

This problem can be found in Principle and Techniques in Combinatorics Exercise 5 #31. The only difference is that each square is colored by a color... We use the exponential generating function to solve this problem...For a color red (since the number of square is even) we have $\frac{e^x+e^{-x}}2$ and for the other color we have $e^{2x}$. Thus, we have $\frac{e^{3x}+e^x}2$ which give us $(1/2)\sum (\frac{3x^n}{n!}+\frac{x^n}{n!})$. Hence, $a_n=(1/2)(3^n+1)$.