Why does the exponential generating function approach fail here?

Question

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?

Answer 1

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.

Answer 2

You shouldn't be using exponential generating functions at all. The blocks and the units in the blocks all come in an order so there's nothing to permute; the GFs to use are ordinary. Specifically, the ordinary generating function is

$$A(x) = \sum_{n \ge 0} a_n x^n = \frac{1}{1 - 2x - x^2 - x^3} = \sum_{k \ge 1} (2x + x^2 + x^3)^k$$

where the term $(2x + x^2 + x^3)^k$ describes towers with exactly $k$ blocks.

The EGF you've written down describes how to count ways to partition a set into four (distinguishable) disjoint subsets, the third of which must have even cardinality and the fourth of which must have cardinality divisible by $3$. This is a very different problem.