Counting LEGO towers

A Lego counting problem, from Soren Eilers, via Vlorbik on Math Ed.

The question: what is the number of ways to make a tower of height six out of two-by-four LEGO® blocks? There are 102,981,504 ways; this is pretty straightforward, once you take the relevant symmetries into account. But apparently this has been confused with the problem of how many ways there are to make any sort of configuration out of six blocks; Eilers and his collaborator Mikkel Abrahamsen claim this number is 915,103,765, by what sounds like a brute-force program. The most common height for such a tower is 4; almost half the towers have this height.

How are the heights of towers containing n blocks distributed? I don't have much faith that this problem could be answered; it reminds me of the problem of counting self-avoiding walks. Let's say you live on the integer lattice, and you go for a walk, going north, south, east, or west at each step. There are clearly 4ⁿ walks of length n. But in how many of these walks do you never come back to a point you've previously visited? Nobody knows. There are various classes of self-avoiding walks that are restricted in certain ways, which can be counted; for example, it's not hard to count walks that only go to the north or east, or even walks that only go to the north, east, or west. (Such a walk has the following structure: go north. Then go east or west a bunch of times. Then go north. Then go east or west a bunch of times. And so on.) It wouldn't even be that hard to determine the average number of times that a NEW-walk chosen uniformly at random from all those of length n takes a northbound step; if I remember correctly it's on the order of n^1/2. But counting all self-avoiding walks? Nobody knows. It's known that if f(n) is the number of self-avoiding walks of length n, then f(n)^1/n has a limit as n goes to infinity; this limit is the self-avoiding walk connective constant in two dimensions, which is somewhere between 2.62 and 2.68.

It's not hard to show it must be between 2.41 and 3, if it exists:

• Let g(n) be the number of self-avoiding walks of length n which only make steps to the north, east, or west. Then g(n)^1/n approaches 1+√2 as n goes to infinity. This can be shown by encoding the walks as words in the three-letter alphabet {N, E, W} and counting the number of words which don't include the subwords EW or WE;


• Let h(n) be the number of walks of length n which don't include the sequences NS, SN, EW, or WE. The number of these is 4 × 3^n-1; the first step can be anything you like, and each following step can be anything except the opposite of the previous step. So h(n)^1/n approaches 3.

But the walks counted by g(n) are all self-avoiding, and self-avoiding walks are a subset of those counted by h(n). So g(n) ≤ f(n) ≤ h(n), which is enough. I believe that at least some of the results which tighten up the connective constant were derived in the same way, by finding classes of walks which contain or are contained by the self-avoiding class.

(The thoughts on self-avoiding random walks are basically coming from a talk on prudent self-avoiding walks by Mireille Bousquet-Melou that I heard a couple weeks ago; I was hoping her slides would be online, since there were some nice pictures, but they aren't.)

The LEGO®-tower-counting problem is similar. In the case where the tower goes straight up, we don't have to worry about the different blocks colliding with each other, so it's something like the "easier" problems above. But if we allow more than one block on each level, we have to take into account the "physics" of the problem, namely that only one block can be in any given piece of space. The LEGO® problem is actually more closely related to counting polyominoes; if you look through the list of Bousquet-Melou's papers, you'll see she's done a lot of work on that sort of problem as well.