Benjamin Hackl

House(s) of Cards

When I sat at our family dinner on Saturday, I watched my cousin build a house of cards from coasters. At one point he said to me: “I want to build a reeeally tall house of cards. One with like 100 levels! Do you think we could collect enough coasters from the tables around here?”. The question got me interested, and so I decided to do some counting.

In particular, we want to find out how many cards $a_n$ are required to build a simple house of cards of height $n$. The associated counting sequence is $\def\N{\mathbb{N}}(a_n)_{n\in \N_0}$. The following figure illustrates what I mean by simple house of cards.

Simple houses of cards (of height 3 and 2, respectively) Obviously, we have $a_0 = 0$, $a_1 = 2$, as well as $a_2 = 7$. This is our (combinatorial) starting point. In fact, there are several approaches for tackling this problem that can be found all over the internet. Here, I want to discuss two approaches: a direct approach as well as an approach that is a bit closer to what I do in my Master’s thesis (i.e. involving recursion and generating functions).

Direct Approach

This approach relies on the following observation: in the highest level of a simple house of cards of height $n$, there is exactly one pair of cards. On the second-highest level, there are two such pairs, on the third-highest there are three such pairs – and on the ground level, there have to be $n$ such pairs. Additionally, apart from the pairs on the ground floor, every pair needs an additional card to stand on. This means, the number of cards required to build a house of cards of height $n$ is given by

$$a_n = 1 \cdot 3 + 2\cdot 3 + 3\cdot 3 + \cdots + (n-1)\cdot 3 + n\cdot 2 = \sum_{j=1}^{n-1} 3 j + 2 n = 3\cdot\sum_{j=1}^{n-1} j + 2 n.$$

Using Gauß’ famous summation formula $\sum_{j=1}^r j = \frac{1}{2} r (r+1)$, this can be written as

$$a_n = 3\cdot \sum_{j=1}^{n-1} j + 2 n = \frac{3}{2} (n-1) n + 2\cdot n = \frac{1}{2} n (3n+1).$$

This means that in order to build a house of cards of height $n$, we need $a_n = \frac{1}{2} n (3n+1)$ cards! Observe that this number grows quadratically; we have $a_n \sim \frac{3}{2} n^2$ for $n\to\infty$. And to come back to my cousin’s question: in order to build a house of cards with 100 levels, we would need $a_{100} = \frac{1}{2}\cdot 100\cdot (3\cdot 100 + 1) = 50\cdot 301 = 15050$ – which, unfortunately, makes it rather difficult build such a large house in a restaurant while waiting for some meal.

Now, let us turn to the recursive approach.

Recursive Approach

Basically, this approach is based on the question how many cards are needed in order to add an additional level to a given house of cards of height $n$. Basically, we need $n$ times three cards (one pair of cards and one card that comes on top of that), and two extra cards (for the new “summit”). This means that we have the recurrence relation

$$a_{n+1} = a_n + 3n + 2. \tag{$\star$}$$

One method to solve such an equation is by using generating functions. Define the ordinary generating function $A(z)$ as the formal power series $A(z) := \sum_{n\geq 0} a_n z^n$. Next, take a recurrence relation like $(\star)$, multiply it by $z^n$, and sum over $n\geq 0$. This implies

$$\sum_{n\geq 0} a_{n+1} z^n = \sum_{n\geq 0} a_n z^n + \sum_{n\geq 0} 3n\cdot z^n + \sum_{n\geq 0} 2 z^n.$$

At this point, we use some well-known tricks in order to simplify these sums. Because of $a_0 = 0$, we have $\sum_{n\geq 0} a_{n+1} z^n = \frac{1}{z} (A(z) - a_0) = \frac{1}{z} A(z)$. The second sum is exactly $A(z)$. The fourth sum is, by definition of the geometric series, $\frac{2}{1 - z}$. And by looking at the derivative of $\frac{1}{1 - z}$, we find that $\sum_{n\geq 0} n z^{n-1} = \frac{1}{(1 - z)^2}$. Multiplying this by $z$ yields $\sum_{n\geq 0} 3n\cdot z^n = \frac{3z}{(1-z)^2}$. Overall, we obtain the functional equation

$$\frac{1}{z} A(z) = A(z) + \frac{3z}{(1-z)^2} + \frac{2}{1-z},$$

or, equivalently,

$$A(z) = \frac{3z^2}{(1-z)^3} + \frac{2z}{(1-z)^2}.$$

This representation already tells us, that the growth of the sequence $(a_n)_{n\in \N_0}$ is at most polynomial. This is because the generating function only has a singularity at $z = 1$. Furthermore, as the pole has order $3$, we know that the growth is quadratic (this follows from Singularity Analysis). Additionally, by using some more of the framework of Singularity Analysis, we can also get the main contribution, $a_n \sim \frac{3}{2} n^2$. This is because of the formula

$$[z^n] (1-z)^{-\alpha} \sim \frac{n^{\alpha - 1}}{\Gamma(\alpha)},$$

$\Gamma(3) = 2! = 2$, as well as the factor $3$ in the partial fraction decomposition from above.

Nevertheless, we want to have exact results. These can be obtained by using a binomial series in order to extract the coefficients; we have

$$(1-z)^{-3} = \sum_{n\geq 0} (-1)^n {-3 \choose n} z^n,\quad \text{ and }\quad (1-z)^{-2} = \sum_{n\geq 0} (-1)^n {-2 \choose n} z^n.$$

From using the definition of the generalized binomial coefficient, it is easy to show that $[z^{n-2}] (1-z)^{-3} = \frac{1}{2} n (n-1)$, and $[z^{n-1}] (1-z)^{-2} = n$. Combining this with the partial fraction decomposition for $A(z)$, we find

$$a_n = [z^n] A(z) = \frac{3}{2} n (n-1) + 2n = \frac{1}{2} n (3n+1),$$

which is the same result as from the direct approach.

So, to summarize our results: there are $a_n = \frac{1}{2} n (3n+1)$ cards required in order to build a simple house of cards of height $n$. Furthermore, although the direct approach seems a lot easier, it also requires a more detailed observation of the given problem structure – whereas the observation required for the recursive approach is rather straightforward (at least from my very subjective point of view). In any case, this is a nice illustration for the recursive approach where a recurrence relation is solved by means of generating functions.