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?


2 Answers 2


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.


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.


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.