Trillions of Toy Towers

Question: Mira the baby architect has a tapering post and some rings. If placed alone, each ring will “find its height” and rest there. If a ring with a higher rest height is placed before one with a lower rest height, the higher one will cut the bottom of the post off from ring placement. How many different ways are there to stack a ring tower?

(FiveThirtyEight)

Solution

This solution has two phases:

1. Getting the structure of the problem
2. Solving the resulting recurrence relation

We’ll get at the structure of the problem in two passes.

Structure

First some notation. If there are $m$ available heights, and $n$ remaining rings, then we say we have an $S(m,n)$ problem. As we’ll see soon, there’s no need to track the identities of the remaining rings.

Imagine we start with the bare post and $5$ rings. As there are $5$ rings and $5$ open heights, we’ll call this the $(5,5)$ stacking problem, or $S(5,5).$

If we drop ring $5$ first, then it will settle to the bottom and we’ll have $4$ rings with $4$ open slots, e.g., $S(4,4).$ We could also stop there, so the total number of cases where ring $5$ is placed first is $S(4,4) + 1.$ We could also drop ring $4$ first, which would settle at its height, and leave us to figure out how to place the $4$ remaining rings at the $3$ remaining heights. Or we could choose to stop there. These contribute $S(3,4) + 1.$ Carrying on, we’d get $S(2,4) + 1$ if we placed ring $3$ first, and $S(1,4)+1$ if we place ring $2$ first. Finally, we have to add $1$ for the case where we skip straight to placing ring $1$ first.

Altogether, this becomes

Or, collecting terms:

This process spawned $S(4,4)$ which is the same kind of problem as the original, just with one less ring and one less height. But it also spawned $S(3,4)$ and $S(2,4),$ and $S(1,4)$ which are new.

We can deal with $S(1,4)$ first. This is the problem of picking $1$ out of $4$ rings to put at $1$ open height. The answer is $4$ and, in general, we can say $S(1,n)=n.$

With $S(3,4),$ two of the four remaining rings can be chosen to sit at height $3$. We’ll then have an $S(2,3)$ problem as well as the option to call it quits and place no further rings. Since we have two choices of which ring to place at height $3$, our choice is arbitrary and both contribute the same number of cases: $2\cdot\left(S(2,3) + 1\right)$. We could also place ring $2$ first which would give us the choice between a $S(1,3)$ problem, or calling it quits.

Diagram of the recursive cases for the $S(3,4)$ problem. The case where we skip straight to placing ring $1$ is not drawn.

In all,

Similarly, the $S(2,4)$ problem give us $3$ choices of ring that could sit at height $2$. After that, we have a $S(1,3)$ problem. We also have the option to stop where we are, so

These cases contain the general logic: if we don’t place the rings in order then we’ll have extras, giving $n-m+1$ equivalent choices if we want to place a ring at the next available position (height $m$). Otherwise we have a unique choice at the other remaining positions. In all cases, we get a new subproblem with with $(n-1)$ total rings:

Note that it isn’t possible to have more remaining heights than remaining rings, so we take the convention $S(m,n) = 0$ when $m > n.$ Also, our decision to explicitly add $1$ when we “call it quits” implies that $S(0,n)=0.$ We could adopt another convention, but we don’t.

Recursion relation

What I will now relay is the happy endng of the story. Sometime later, I will give a glimpse into the darkness — a tragic episode where I stayed staring into a generating-function-shaped mirage, only to give up all hope of a solution. After a cajoling by Goh Pi Han, I was inspired to give the recurrence one last try. With no further ado, I present the resolution.

At first glance, the recurrence is no joke. It descends levels in two indices, there’s the $n$, and there’s the $(n-m)$ on $S(m-1,n-1),$ and there’s the sum. You just don’t see these every day (maybe you do, but I don’t).

After calculating some of the $S(m,n)$ by hand, we observed that $S(1,3)=3$ and $S(2,3)=7$ are separated by $4,$ $S(3,4)=21$ and $S(2,4)=13$ are separated by $8,$ and $S(4,5)=64$ and $S(3,5)=48$ are separated by $16$. If this generalizes, then we’d have

At this point I wasn’t expecting much, but it seemed like a small piece that might be provable. Using the recurrence relation,

So, the difference between the $(m=n-1)$ and $(m=n-2)$ coefficients with $n$ rings is replaced with twice the difference between the corresponding coefficients in the $n-1$ ring problem. Following this down, we get

Small miracle, or sneak preview? What about $S(n-2,n) - S(n-3,n)$? Applying the same approach yields

which recurses $n-3$ times down to $3^{n-3}\cdot\left(S(1,3) - S(0,3)\right) = 3^{n-2}.$

Telescope

And thus, the rest flowed down like a waterfall. Carrying on in this way can get all the pairwise differences so that

But these are not mere amusements. Nay, the sum of these differences telescopes to the $S(n,n)$ coefficient itself. Adding them up, like a zipper pulled tight in the dead of winter, the number of ways there are for Mira to stack her $n$ rings filters down to:

Magical!

For the case at hand, $S(5,5) = 1^5 + 2^4 + 3^3 + 4^2 + 5^1 = 65.$

Program

We can confirm this divine form by evaluating the recursion on the computer. Setting up the recursive function with memoization in Mathematica, we have

stack[1, n_] := n;
stack[m_, n_] := 
 stack[m, n] = 
  n 
  + (n - m) stack[m - 1, n - 1] 
  + Sum[stack[i, n - 1], {i, 1, m - 1}];

The first few $S(n,n)$ are

The recursion with memoization is quite fast, dispensing with the $100$ ring case in $\approx 170\text{ ms}.$ Plotting the analytical result and the computation up to $N=1000$, we get

Pretty good.