3

This is homework, please only provide hints!

I have a question: Given a 1-by-n board, let $a_{n}$ denote the number of ways to color the board with red, blue, white and green where that the number of red squares is even, and the number of white squares is odd.

So, I've started off by setting up different cases, I believe my cases do not overlap, so they each stand as a strong case on their own (independent of one another).

case 1: you have a board with an odd number of white, and odd red. Then, for an n-1 board, you can end the board with 1 red square.

case 2: even white, even red. You can end an n-1 board with 1 white.

case 3: even white, odd red. You can end an n-2 board with 1 white and 1 red square.

So, with all these cases, I've come up with: $$ a_{n} = 2a_{n-1} + a_{n-2} $$

I'm kind of just making that equation up, I'm not really sure how to form an equation from this problem, which is why I'm posting. Any hints would be appreciated.

EDIT: I realized I left the title to "Systems of... ". We are currently studying this, so I feel that may be related to this problem, and thus, my answer would be incorrect, obviously. That may not be the case though!

intervade
  • 441

2 Answers2

5

I'm not sure from your wording, but it sounds like you're thinking of smaller boards (of size less than $n$) and deciding how you can extend them to bigger boards (of size $n$). This often leads to confusion; in this case, for example, you forgot that you can extend an even-red,odd-white board by either a green or a blue square.

In my opinion, it's better to first think about a general big board (of size $n$) and enumerate the ways you can reduce it to smaller boards. Then we don't have to guess what the right set of smaller boards is - our argument just gives it to us, and we count what we get.

Let's set up some clumsy but easy-to-remember notation. All of these refer to $1\times n$ boards with squares that are blue, green, red, or white: \begin{align*} R^eW^e(n) &= \#\text{boards with even number of red squares and even number of white squares} \\ R^eW^o(n) &= \#\text{boards with even number of red squares and odd number of white squares} \\ R^oW^e(n) &= \#\text{boards with odd number of red squares and even number of white squares} \\ R^oW^o(n) &= \#\text{boards with odd number of red squares and odd number of white squares} \\ \end{align*} Now, given a $1\times n$ board of any fixed type - say one counted by $R^eW^e(n)$ - what happens when you chop off the last square? How can $R^eW^e(n)$ be counted by counting all possible resulting $1\times(n-1)$ boards with the above categorization?

Finally, whatever system of recurrence relations you get, remember that they have to include initial values. And also remember that you can check your recurrence relations by hand for small values of $n$ - this is valuable insurance against a mistake.

Greg Martin
  • 78,820
  • So, with this methodology, whats the point of counting $R^eW^e$, $R^oW^o$ and $R^oW^e$. They are not legal colorings, so why take them into count? The only legal coloring for the board is $R^eW^o$, so are we subtracting the other sets off? – intervade Feb 17 '13 at 22:55
  • They aren't legal colorings (in the sense of what you are looking for in the end), but they can all appear in the pieces you'd get by breaking a solved board. – vonbrand Feb 17 '13 at 23:52
  • My guess as to why this problem occurs in a section called "systems of recurrence relations" is because you need all of these quantities, related by mutual recurrence relations, in order to solve your problem. – Greg Martin Feb 18 '13 at 03:56
3

This is a permutation problem so it can be solved using exponential generating functions. \begin{align} \mathop{blue}, \mathop{green} &= 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \ldots + \frac{x^n}{n!} + \ldots \\ &= e^x \\ \mathop{red} &= 1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \ldots \\ &= \frac{e^x + e^{-x}}{2} \\ \mathop{white} &= x + \frac{x^3}{3!} + \frac{x^5}{5!} + \ldots \\ &= \frac{e^x - e^{-x}}{2} \end{align} so $$ \mathop{blue} \cdot \mathop{green} \cdot \mathop{red} \cdot \mathop{white} = e^{2x} \cdot \frac{e^x + e^{-x}}{2} \cdot \frac{e^x - e^{-x}}{2} = \frac{e^{4x}-1}{2} $$ Now: $$ \frac{e^{4x}-1}{2} = - \frac{1}{2} + \frac{1}{2} \sum_{n \ge 0} \frac{4^n x^n}{n!} $$ so $$h_n = \begin{cases} \displaystyle -\frac{1}{2} + \frac{4^0}{2} = 0 & \text{if \(n = 0\)} \\ \\ \displaystyle \frac{4^n}{2} & \text{if \(n > 0\)} \end{cases} $$ and there you have it! :)

Solving problems with restrictions like these are always easier to do with generating functions.

vonbrand
  • 27,812
Elias Nygren
  • 31