Question: Let $a_{n}$ count the number of different ways to build a tower $n$ units high using red 1-unit blocks, red 2-unit blocks, blue 1-unit blocks, and blue 3-unit blocks. Find $a_{n}$ for $n \geq 1$.
So I have found a recurrence relation for this, namely $a_{n} = 2a_{n-1} + a_{n-2} + a_{n-3}$.
But I have also modelled this using exponential generating functions given by $g(x) = \left( 1 + x + \frac{x^{2}}{2!}+ \dots \right)^{2}(1 + \frac{x^{2}}{2!} + \frac{x^{4}}{4!} + \dots)(1 + \frac{x^{3}}{3!} + \frac{x^{6}}{6!} + \dots )$
When I compute the coefficient of $\frac{x^3}{3!}$, they agree with those given by my recurrence relation, up until $a_{3}$, where it gives $a_{3} = 15$ (although it should be 13). Is there some reason why my generating function would not model the above relation?
When you have two exponential generating functions $\displaystyle f(x) = \sum_{n=0}^\infty a_n \frac{x^n}{n!}$ and $\displaystyle g(x) = \sum_{n=0}^\infty b_n\frac{x^n}{n!}$, their product $\displaystyle f(x)g(x) = \sum_{n=0}^\infty c_n\frac{x^n}{n!}$ has $\displaystyle c_n = \sum_{k=0}^n \binom{n}{k}a_kb_{n-k}$.
The problem is that each two-unit block is just that: a two-unit block. If I want an $n$-unit-tall tower containing $k$ two-unit blocks and $n-2k$ one-unit blocks (no colors at the moment), there are only $n-k$ total blocks and thus $\displaystyle \binom{n-k}{k}$ ways to arrange them, not $\displaystyle \binom{n}{k}$ ways as would be computed in the product of generating functions.