Liczba wypełnień prostokąta

[Marrous]

Witam użytkowników forum.

Proszę o pomoc w zadaniu z matematyki dyskretnej:

"Niech \(\displaystyle{ a_{n}}\) oznacza liczbę pokryć prostokąta \(\displaystyle{ 3 \times 2n}\) prostokątami \(\displaystyle{ 1 \times 2}\). Znajdź \(\displaystyle{ \lim_{n \to \infty}(a_{n})^{1/n}}\).

WSKAZÓWKA: Znajdź układ zależności rekurencyjnych i wyprowadź z niego równanie na \(\displaystyle{ a_{n}}\)."

Siedzę nad zadaniem już dobrą godzinkę i co chwila coś się sypie.

Myślę, że dobrą odpowiedzią będzie samo równanie rekurencyjne, dalej rozwiąże je za pomocą funkcji tworzących, a obliczenie tej granicy będzie proste.

Co "ustaliłem" :

\(\displaystyle{ a_{0}=1}\)
\(\displaystyle{ a_{1}=3}\)
\(\displaystyle{ a_{2}=11}\) : \(\displaystyle{ 9}\) z racji tego, że prostokąt \(\displaystyle{ 3 \times 4}\) można podzielić na dwie części, czyli wychodzi \(\displaystyle{ a_{1} \cdot a_{1} = 9}\) + dodatkowe dwa, w których dwie poziome kreski leżą na środku.
\(\displaystyle{ a_{3} = 39}\)

Już z miejsca widać, że przodującą potęgą w zwartym wzorze na \(\displaystyle{ a_{n}}\) jest \(\displaystyle{ 3^{n}}\), więc odpowiedź to prawdopodobnie \(\displaystyle{ 3}\).

[kropka+]

\(\displaystyle{ a _{0}=0, \ a _{3}>39}\). Tych poziomych prostokątów w drugim wierszu może być 1,2 lub 3. Gdy jest 1 lub 2, to można je przesuwać od lewej do prawej, a pozostałe moduły zmieniają się na 3 sposoby każdy.

[Qń]

Wzór rekurencyjny to:
\(\displaystyle{ a_n=a_{n-1}+2\sum_{k=0}^{n-1}a_k}\)
Szkicowe wyjaśnienie (dłuższe byłoby zbyt pracochłonne bez rysunków): \(\displaystyle{ a_{n-1}}\) to układy, które w pierwszym prostokącie \(\displaystyle{ 2\times 3}\) mają trzy poziome klocki. Następnie zaczynamy zliczać układy, które "zaczynają się" od "litery L", to znaczy jednego poziomego i jednego pionowego klocka. Dwójka bierze się stąd, że ta elka może stać normalnie lub "na głowie". A dalej to: układów w którym pierwsze wolne miejsce wypełniamy klockiem pionowym jest \(\displaystyle{ a_{n-1}}\). W pozostałych układach na pierwsze wolne miejsca kładziemy klocki poziome. I teraz znów: układów w których na pierwsze wolne miejsce kładziemy klocek pionowy jest \(\displaystyle{ a_{n-2}}\) itd.

Łatwo powyższy wzór można przekształcić do:
\(\displaystyle{ a_n=4a_{n-1}-a_{n-2}}\)
a w tej postaci już łatwo rozwiązać rekurencję np. używając równania charakterystycznego. Pierwiastki niestety nieładne, ale sama granica to jak się zdaje będzie \(\displaystyle{ 2+\sqrt{3}}\).

Q.

[Marrous]

Dziękuję za odpowiedź.

Trochę nie rozumiem pierwszego wzoru rekurencyjnego z sumą
\(\displaystyle{ a_n=a_{n-1}+2\sum_{k=0}^{n-1}a_k}\)
oraz jego przekształcenia

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

Natomiast szkicowe wyjaśnienie tak. Wcześniej pomyślałem trochę nad zadaniem i doszedłem do wzoru (w inny sposób)

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

Według sposobu myślenia z "L-kami" rozrysowałem to sobie na kartce.



I też doszedłem do tego samego wzoru. Czy jednak 2x się mylę?

[Qń]

W każdym kroku w szkicu mamy do wyboru - albo w wolne miejsce kładziemy klocek pionowy i zabawa się kończy, albo też kładziemy w wolne miejsca trzy klocki poziome i zabawa przenosi się o poziom niżej. Za każdym razem da się przejść poziom niżej, stąd suma musi być do \(\displaystyle{ i=0}\).

A samo przekształcenie jest już proste - wystarczy napisać pierwotny wzór dla \(\displaystyle{ n}\) oraz dla \(\displaystyle{ n-1}\) i odjąć stronami.

Q.