kostki domina w pudełeczku

[dabros]

na ile sposobów można umieścić kostki domina 2x1 w pudełku 3xN, jeżeli mamy ich nieskończony zapas tak, aby pudełko było całkowicie zapełnione (oczywiście kostki nie mogą na siebie zachodzić)

[Xitami]

\(\displaystyle{ 3^{N\over 2}}\)

[dabros]

a możesz napisać, jak do tego doszedłeś?

[Qń]

\(\displaystyle{ 3^{N\over 2}}\)

Nie zgadza się już dla \(\displaystyle{ N=4}\), łatwo zauważyć zresztą których możliwości nie zliczyłeś.

Mi wyszło tak:
Niech \(\displaystyle{ a_k}\) będzie liczbą sposobów zapełnienia kostkami domina planszy o wymiarach \(\displaystyle{ 3 2k}\). Ciąg ten można przedstawić następująco:

1) Rekurencja.
\(\displaystyle{ a_0 = 1 \\
a_1 = 3 \\
a_n=a_{n-1} + 2\sum_{k=0}^{n-1} a_k}\)
Zastrzegam, że bez ołówka i kartki papieru nie podejmuję się objaśniać skąd ta kombinatoryczna interpretacja.

2) Prostsza rekurencja.
\(\displaystyle{ a_0 = 1 \\
a_1 = 3 \\
a_n=4a_{n-1}-a_{n-2}}}\)
To zaś wzięło się z prostych przekształceń poprzedniej postaci. Być może da się od razu tę nową postać zależności wywnioskować kombinatorycznie, ja jednak nie mam pomysłu jak.

3) Postać zwarta.
\(\displaystyle{ a_n= \frac{3-\sqrt{3}}{6} ft( 2- \sqrt{3} \right)^n + \frac{3+\sqrt{3}}{6} ft( 2 + \sqrt{3} \right)^n}\)

Pozdrawiam.
Qń.

[piobury]

Rozważmy pokrycie szachownicy o wymiarach \(\displaystyle{ 3 \times n}\). Niech \(\displaystyle{ a_n}\) oznacza ilość takich pokryć. Wtedy \(\displaystyle{ a_0=1, a_1=0, a_2=3, a_3=0.}\)

\(\displaystyle{ a_0=1, a_1=0}\) oraz \(\displaystyle{ a_3=0}\) są oczywiste. Na Rysunku 1 przedstawiono ilość pokryć dla \(\displaystyle{ n=2}\).

Zauważmy, że pokrywając dwie pierwsze kolumny szachownicy na jeden z trzech powyższych sposobów otrzymujemy problem pokrycia szachownicy o wymiarach \(\displaystyle{ 3 \times (n-2)}\). Możemy jednak ułożyć trzy pierwsze klocki w inny sposób niż na rysunku, tak aby nie zamykały układu \(\displaystyle{ 3 \times 2}\). W przypadku układu pierwszego z Rysunku 1, po położeniu dwóch poziomych klocków, trzeci zawsze zamknie układ. W przypadku drugim i trzecim tak być nie musi. Przypadki te są symetryczne, więc opiszę jeden z nich (środkowy) (Rysunek 2). Połóżmy poziomy klocek oraz ten pionowy, który jest w pierwszej kolumnie (1) i (2). Dołożenie obok klocka pionowego zamyka układ. Kładziemy więc klocek poziomy (3). Wtedy mamy jedną możliwość na położenie kolejnego poziomego (4) oraz jeszcze kolejnego poziomego (5). Teraz dołożenie klocka pionowego (6) zamyka układ i otrzymujemy szachownicę \(\displaystyle{ 3 \times (n-4).}\)

Możemy jednak nie zamykać układu i położyć klocek (6) poziomo (Rysunek 3). Wtedy kolejne musimy położyć poziomo (7), (8) i powtarzamy tę procedurę, aż skończy nam się szachownica.

Otrzymujemy zatem następującą rekurencję liniową:

\(\displaystyle{ a_n=3a_{n-2}+2a_{n-4}+2a_{n-6}+2a_{n-8}+\ldots}\)

Dla dowolnego \(\displaystyle{ n}\) będzie ciężko wyznaczyć pierwiastki wielomianu charakterystycznego. Zauważmy jednak, że skoro rekurencja jest spełniona dla dowolnego \(\displaystyle{ n,}\) więc też dla \(\displaystyle{ n-2, (n\geqslant2)}\). Wstawmy więc do powyższej rekurencji \(\displaystyle{ n-2}\) zamiast \(\displaystyle{ n}\). Otrzymujemy:

\(\displaystyle{ a_{n-2}=3a_{n-4}+2a_{n-6}+2a_{n-8}+2a_{n-10}+\ldots}\)

Odejmując te dwie rekurencje stronami otrzymujemy:

\(\displaystyle{ a_{n}-a_{n-2}=3a_{n-2}+2a_{n-4}-3a_{n-4}}\)

co jest równoważne:

\(\displaystyle{ a_{n}=4a_{n-2}-a_{n-4}}\)

Możemy zauważyć, że dla \(\displaystyle{ n}\) nieparzystych \(\displaystyle{ a_n=0}\).
Niech zatem \(\displaystyle{ b_n:=a_{2n}}\). Wtedy mamy \(\displaystyle{ b_0=1, b_1=3}\). Otrzymujemy rekurencję:

\(\displaystyle{ b_n=4b_{n-1}-b_{n-2}}\)

Jej wielomian charakterystyczny to: \(\displaystyle{ x^2-4x+1}\). Zatem pierwiastkami tego wielomianu są: \(\displaystyle{ 2+\sqrt{3}, 2-\sqrt{3}}\). Zatem:

\(\displaystyle{ b_n=A\cdot (2+\sqrt{3})^n+B\cdot (2-\sqrt{3})^n}\)

z warunkami początkowymi \(\displaystyle{ b_0=1, b_1=3}\).

\(\displaystyle{ \left\{\begin{array}{l}
A+B=1\\
A(2+\sqrt{3})+B(2-\sqrt{3})=3
\end{array}\right.}\)

Stąd otrzymujemy:

\(\displaystyle{ A=\dfrac{3+\sqrt{3}}{6}, \qquad B=\dfrac{3-\sqrt{3}}{6}}\)

Ostatecznie:

\(\displaystyle{ a_{2n}=b_n=\dfrac{(3+\sqrt{3})(2+\sqrt{3})^n+(3-\sqrt{3})(2-\sqrt{3})^n}{6}}\)