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).

  • 2
    $\begingroup$ Not much of a "chessboard" if it's $1 \times n$, and three colours as well. $\endgroup$ – Robert Israel Jul 23 '12 at 7:23
  • $\begingroup$ Yea i know, the book I'm using refers to these boards as x by n chessboards a lot of times. $\endgroup$ – Andariel Jul 23 '12 at 7:26
  • $\begingroup$ Your (2) overcounts: for $n=5$ it counts RRRRB three times, once for each of the last three red squares. $\endgroup$ – Brian M. Scott Jul 23 '12 at 7:27
  • $\begingroup$ @BrianM.Scott Can you tell me the right expression for (2)? $\endgroup$ – Andariel Jul 23 '12 at 7:35

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}\;.$$


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


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.

  • $\begingroup$ 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) . $\endgroup$ – Andariel Jul 23 '12 at 8:11

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

  • $\begingroup$ Ok. Thank 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. $\endgroup$ – Andariel Jul 23 '12 at 7:53

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.