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}\).
Liczba wypełnień prostokąta
- kropka+
- Użytkownik
- Posty: 4389
- Rejestracja: 16 wrz 2010, o 14:54
- Płeć: Kobieta
- Lokalizacja: Łódź
- Podziękował: 1 raz
- Pomógł: 787 razy
Liczba wypełnień prostokąta
\(\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.
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Liczba wypełnień prostokąta
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.
\(\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.
-
- Użytkownik
- Posty: 4
- Rejestracja: 7 wrz 2014, o 14:27
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
Liczba wypełnień prostokąta
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ę?
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ę?
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Liczba wypełnień prostokąta
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.
A samo przekształcenie jest już proste - wystarczy napisać pierwotny wzór dla \(\displaystyle{ n}\) oraz dla \(\displaystyle{ n-1}\) i odjąć stronami.
Q.