Número de formas de apilar ladrillos LEGO

Question

Una de las fórmulas combinatorias más sorprendentes que conozco cuenta el número de torres de LEGO construidas a partir de $n$ " $1 \times 2$ ", que están sujetos a cuatro reglas:

1. Los ladrillos se encuentran en un solo plano.
2. Cada ladrillo está desplazado por 1 montante (como en una pared de ladrillos).
3. La capa inferior es contigua.
4. Cada ladrillo tiene al menos un ladrillo por debajo (aparte de la capa inferior).

Ejemplo

Fórmula

En la página 26 de Miklós Bóna Manual de Combinatoria Enumerativa el autor indica la fórmula combinatoria (!!):

Notablemente hay $3^{n-1}$ torres de dominó compuestas por $n$ ladrillos. De manera igualmente notable, no se conoce ninguna biyección simple.

La fórmula fue probada por primera vez en 1988 por Gouyou-Beauchamps y Viennot .

Pregunta

Mientras escribía un breve ensayo sobre este hecho, me interesé por lo que ocurre cuando se relajan algunas de las reglas.

En concreto, para los valores pequeños que he comprobado en el ordenador, la eliminación de la segunda regla ("Cada ladrillo se desplaza 1 tachuela") parece dar como resultado $4^{n-1}$ torres con $n$ ladrillos.

Imagino que este resultado existe en la literatura, y esperaba que MSE me ayudara a encontrarlo. Si no se ha escrito en ningún sitio, esperaba saber cómo adaptar la prueba de Bóna a este nuevo escenario.

Answer 1

Su resultado $4^{n-1}$ es correcto. La prueba de Bóna se cumple con una sola modificación. En el último paso que cuenta las medias pirámides, hay una opción más: Un ladrillo inferior con una media pirámide sobre él cuyo ladrillo inferior está directamente sobre el ladrillo inferior.

En lugar de $H\cong(H\times\bullet\times H)+(\bullet\times H)+\bullet$ obtenemos $H\cong(H\times\bullet\times H)+(\bullet\times H)+(\bullet\times H)+\bullet$ Por lo tanto $H=xH^2+2xH+x$ y luego

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