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}