Number of possible n-towers

Question

This question is inspired by Q5 from the 2018 MAT, but it is not the same.

An $n$-brick is defined as a rectangle with height $1$ and width $n$. A $1$-tower is defined as a $1$-brick.
An $n$-tower for $n$ greater than or equal to two is an $n$-brick atop which any number of towers are stacked. The $n$-bricks directly above the first one should sum to $n$ (so if you had a $4$-tower, you could put a $3$-brick and a $1$-brick on it, or two $2$-bricks on it. The $3$-brick would then have either three $1$-bricks on it, or one $2$-brick and one $1$-brick; whereas the $2$-brick would always have two $1$-bricks).  Below is a picture of a $4$-tower

If $s_n$ is the number of n-towers, can you write $s_n$ in terms of $s_k$ where $k<n$?

Brian M. Scott · Answer

Your $n$-towers are Schröder trees in disguise — plane trees with $n$ leaves, all of whose internal nodes have at least two children. Each brick is a node, each $1$-brick is a leaf, and each $k$-brick for $kge 2$ is an internal node. These are enumerated by the Schröder-Hipparchus numbers, also known as little Schröder or super-Catalan numbers; OEIS A001003 has a lot of information and references. It also has two fairly nice recurrences. One is similar to the familiar Catalan recurrence:
$$s_{n+1}=-s_n+2sum_{k=1}^ns_ks_{n+1-k}$$
For instance,
$$begin{align*}
s_5&=-s_4+2sum_{k=1}^4s_ks_{5-k}\
&=-11+2(1cdot11+1cdot3+3cdot1+11cdot1)\
&=45;.
end{align*}$$
The other is second-order:
$$ns_n=3(2n-3)s_{n-1}-(n-3)s_{n-2}$$
E.g., $5s_5=24s_4-2s_3=21cdot11-2cdot3=225$, so $s_5=frac{225}5=45$. Foata and Zeilberger have a nice combinatorial proof of this recurrence here [PDF].

Number of possible n-towers

One Answer

Add your own answers!

Ask a Question