28
$\begingroup$

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

Example of a

Formula

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.

Question

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.

$\endgroup$
9
  • $\begingroup$ Connected... and interesting as well, this document in French $\endgroup$
    – Jean Marie
    May 5, 2020 at 6:08
  • $\begingroup$ An old MathsSE question interesting for its references $\endgroup$
    – Jean Marie
    May 5, 2020 at 6:19
  • $\begingroup$ @JMP, I included the tag statistical-mechanics because the original 1988 paper was a statistical mechanics paper. $\endgroup$ May 5, 2020 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, 2020 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$ May 5, 2020 at 20:14

1 Answer 1

16
$\begingroup$

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}

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .