Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
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) . –  Andariel Jul 23 '12 at 8:11
add comment

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

share|improve this answer
    
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. –  Andariel Jul 23 '12 at 7:53
add comment

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 ({3x}^n/n!+{x^n}/n!). Hence, a_n=(1/2)(3^n+1).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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