3
$\begingroup$

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?

$\endgroup$
9
  • 1
    $\begingroup$ Do you need to use each colour at least once? For red, assuming the answer to the previous question is false, is $0$ an even number for you? $\endgroup$
    – Ian Coley
    May 14 '13 at 17:07
  • $\begingroup$ Even for red and odd for orange is the only requirement, so I guess I don't need to use each color at least once. $\endgroup$
    – khernik
    May 14 '13 at 17:09
  • $\begingroup$ Does order matter? You'ved asked for the number of combinations of different colours, but do you properly mean permutations? Or are you looking at the number of ways to pick $n$ blocks within these four colours? $\endgroup$
    – Ian Coley
    May 14 '13 at 17:10
  • $\begingroup$ The order doesn't matter. $\endgroup$
    – khernik
    May 14 '13 at 17:12
  • $\begingroup$ And yes, as you've said - I'm looking at the number of ways to pick n blocks withing these colors. $\endgroup$
    – khernik
    May 14 '13 at 17:13
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

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.