# Number of ways to stack LEGO bricks

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 # 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.

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}$$