Coloring the 1 x n field

Question

I have a field of 1 x n size. I need to color it using: red, orange, green, blue. Also, I can color red only even amount of blocks, and orange only odd amount of blocks.

Finally I need to find a generating function describing how many combinations of different colors I can use.

How can I do it?

Answer 1

If order doesn’t matter, you’re looking at partitions of $n$ into four parts labelled red, orange, green, and blue, where any of the parts except the orange part can be empty, the red part must be even, and the orange part must be odd. Look at the coefficient of $x^n$ in the product

$$\begin{align*} &\underbrace{(1+x^2+x^4+\ldots)}_{\text{red}}\underbrace{(x+x^3+x^5+\ldots)}_{\text{orange}}\underbrace{(1+x+x^2+\ldots)}_{\text{green}}\underbrace{(1+x+x^2+\ldots)}_{\text{blue}}=\\\\ &\left(\sum_{n\ge 0}x^{2n}\right)\left(\sum_{n\ge 0}x^{2n+1}\right)\left(\sum_{n\ge 0}x^n\right)\left(\sum_{n\ge 0}x^n\right)\;. \end{align*}$$

All of these summations have simple generating functions.

Answer 2

Brian M. Scott's answer gets ugly when asking for explicit coefficients...

You are classifying sequences into (subindex is length):

• Even red, even orange ($a_n$, with $a_0 = 1$)
• Even red, odd orange ($b_n$, with $b_0 = 0$)
• Odd red, even orange ($c_n$, with $c_0 = 0$)
• Odd red, odd orange ($d_n$, with $d_0 = 0$)

You can set up recurrences, by noting that to get the $a_{n + 1}$ even/even secuences you can start with the $a_n$ even/even and add green or blue ($2 a_n$ ways) or start with even/odd and add orange ($b_n$ ways) or odd/even and add red ($c_n$ ways). Completing this: $$ \begin{align*} a_{n + 1} &= 2 a_n + b_n + c_n \\ b_{n + 1} &= a_n + 2 b_n + d_n \\ c_{n + 1} &= a_n + 2 c_n + d_n \\ d_{n + 1} &= b_n + c_n + 2 d_n \end{align*} $$ Define generating functions $A(z) = \sum_{n \ge 0} a_n z^n$ and so on; multiply the recurrences by $z^n$ and add over $n \ge 0$ to get: $$ \begin{align*} \frac{A(z) - a_0}{z} &= 2 A(z) + B(z) + C(z) \\ \frac{B(z) - b_0}{z} &= A(z) + 2 B(z) + D(z) \\ \frac{C(z) - c_0}{z} &= A(z) + 2 C(z) + D(z) \\ \frac{D(z) - d_0}{z} &= B(z) + C(z) + 2 D(z) \end{align*} $$ Solve this linear system of equations for $B(z)$: $$ B(z) = \frac{z}{1 - 4 z} = \frac{1}{4} \cdot \frac{1}{1 - 4 z} - \frac{1}{4} $$ You can read the coefficients from the geometric series (the $[n = 0]$ is Iverson's bracket, $1$ if $n = 0$ and 0 otherwise): $$ b_n = 4^{n - 1} - \frac{1}{4} [n = 0] $$ I.e, $b_n = \langle 0, 1, 4, 16, \ldots \rangle$