One of the most surprising combinatorial formulas I know of counts the number of LEGO towers built from $n$ "$1 \times 2$" blocks subject to four rules:

  1. The bricks lie in a single plane.
  2. Each brick is offset by 1 stud (as in a brick wall).
  3. The bottom layer is contiguous.
  4. Each brick has at least one brick below it (apart from the bottom layer).


Example of a


On page 26 of Miklós Bóna's Handbook of Enumerative Combinatorics, the author states the combinatorial formula (!!):

Remarkably there are $3^{n-1}$ domino towers consisting of $n$ bricks. Equally remarkably, no simple bijection is known.

The formula was first proven in 1988 by Gouyou-Beauchamps and Viennot.


While writing up a short essay on this fact, I became interested in what happens when you relax some of the rules.

In particular, for the small values I checked on the computer, removing the second rule ("Each brick is offset by 1 stud") appears to result in $4^{n-1}$ towers with $n$ bricks.

I imagine this result exists in the literature, and I was hoping MSE could help me find it. If it hasn't been written down anywhere, I was hoping for insight for how to adapt Bóna's proof into this new setting.

  • $\begingroup$ Connected... and interesting as well, this document in French $\endgroup$ – Jean Marie May 5 '20 at 6:08
  • $\begingroup$ An old MathsSE question interesting for its references $\endgroup$ – Jean Marie May 5 '20 at 6:19
  • $\begingroup$ @JMP, I included the tag statistical-mechanics because the original 1988 paper was a statistical mechanics paper. $\endgroup$ – Peter Kagey May 5 '20 at 6:21
  • $\begingroup$ @PeterKagey; I read the tag info : math.stackexchange.com/tags/statistical-mechanics/info, and it doesn't seem to match, but good call! $\endgroup$ – JMP May 5 '20 at 6:52
  • 1
    $\begingroup$ @AntonioHernandezMaquivar, Here's the Ruby code that I used, but it might not be especially clear since it wasn't designed for external consumption. $\endgroup$ – Peter Kagey May 5 '20 at 20:14

Your result $4^{n-1}$ is correct. Bóna's proof goes through with a single modification. In the last step that counts the half-pyramids, there is one more option: A bottom brick with a half-pyramid on it whose bottom brick is directly on top of the bottom brick.

Instead of $H\cong(H\times\bullet\times H)+(\bullet\times H)+\bullet$ we get $H\cong(H\times\bullet\times H)+(\bullet\times H)+(\bullet\times H)+\bullet$, thus $H=xH^2+2xH+x$, and then

\begin{eqnarray} P &=& \frac H{(1-H)^2} \\ &=& \frac H{-2H + (1+H^2)} \\ &=& \frac H{-2H + H\frac{1-2x}x} \\ &=& \frac x{1-4x}\;. \end{eqnarray}


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.