Na ile sposobów można wypełnić prostokąt o wymiarach 2 na 2n kostkami domino o w Karmel: Na ile sposobów można wypełnić prostokąt o wymiarach 2 na 2n kostkami domino o wymiarach 2 na 1?. Znajdź zależność rekurencyjną a_n.

Maciess: A tych kostek domino to ile mamy?

znak : Zapewne dowolna ilość kostek, kwestia tego, że kostki można obracać i zamiast 2x1 robi się 1x2

Maciess: Pytam, bo nigdy nie bawiłem się domino. (choć widziałem!) A google mówią o zestawie 28 kostek więc w nieskonczoność ich nie poukładamy. I rozróżnianie kostek. WIęc nie wiem jak zadanie ugryźć

wredulus_pospolitus: wzór rekurencyjny: a₀ = 1 a_n = 2*a_n−1 jak do niego dojść. prostokąt o wymiarach 2 x 2(n−1) można ułożyć na 'ileś tam sposobów' (nie wiemy na ile), powiedzmy, że na y sposobów. to na ile sposobów można ułożyć prostokąt o wymiarach 2 x 2n na y* (ilość sposobów ułożenia dokładanego kwadratu 2 x 2 który można ułożyć na dwa sposoby). stąd 2*y = 2a_n−1

wredulus_pospolitus: natomiast jeżeli przyjmiemy, że kostki domina są ROZRÓŻNIALNE (a ilość każdego klocka jest nieskończona) to musimy to jeszcze musimy pomnożyć przez x² gdzie 'x' oznacza ilość rozróżnialnych klocków domina (których jest 7+6+5+4+3+2+1 = 28) więc będziemy mieli: a₀ = 1 a_n = 2*28²*a_n−1

Maciess: a₀ to na pewno 1?

znak : a₀ = 0 moim zdaniem, bo nie ma prostokąta o wymiarach 2x0, w końcu długość boku musi być większa od 0

Blee: Na ile sposobów można zbudować prostokąt o wymiarach 2x0... Na 1 (brak prostokąta) Albo jak nie chcecie to zaczynajcie od a₁ czyli kwadratu 2x2 który można utworzyć na 2*28² sposobów (jeżeli klocki domina są rozroznialne)

kerajs: Moim zdaniem wzór rekurencyjny to: a_n=a_n+1+a_n+2

kerajs: O sorry. Miało być: a_n=a_n−1+a_n−2

Blee: Kerajs − − − Zauważ co napisales/−as: Czyli a₅ = a₆ + a₇

wredulus_pospolitus: masz częściową rację ... zapomniałem o 'dodatkowym' układzie Więc winno być: a₁ = 2*28² a₂ = (2*28²)² + 28⁴ a_n = 2*28²*a_n−1 + 28⁴*a_n−2

wredulus_pospolitus: przy założeniu rozróżnialności klocków domina ... jeżeli klocki są jednakowe ... to wywalamy 28² i 28⁴

kerajs: Jeżeli kamienie domina są rozróżnialne i się nie powtarzają, to wynik z rekurencji wystarczy pomnożyć przez silnię z ich liczby

wredulus_pospolitus: Ale czemu kamienie mają się nie powtarzać Jeżeli nie mogą się powtarzać to mamy także górną granicę wymiaru prostokąta.

wredulus_pospolitus: Oki ... uznajmy, że mamy dokładnie 28 różnych klocków. Wtedy: a₁ = 2*28*27 a₂ = 2²*28*27*26*25 + 28*27*26*25 a_n = 2*a_n−1*(28 − 2(n−1))*(28 − 2(n−1) −1) + + a_n−2*(28 − 2(n−1))*(28 − 2(n−2) −1)*(28 − 2(n−2) −2)*(28 − 2(n−2) −3) a_n = 0 dla n ≥ 15

kerajs: Czekałem na reakcję autora, lecz ten najwyraźniej nie jest zainteresowany tematem, mimo zamieszczania nowych. Mimo to dopiszę: 1) Sądzę, że w zadaniu należy znaleźć liczbę wypełnień prostokąta 2x2n prostokątami 2x1. Przyjmując. iż a_n to ilość wypełnień prostokąta 2xn, to wzór rekurencyjny jest taki, jaki napisałem powyżej. a_n uzyskuje się przez dodanie pionowej płytki do a_n−1 lub dwóch poziomych (i leżących na sobie) płytek poziomych do a_n−2. Wzór ogólny (z kilkoma pierwiastkami z 5) można łatwo wyliczyć przyjmując warunki początkowe: a₁=1, a₂=2. 2) Autor zadania nieszczęśliwie użył słowa domino. Przyjmując założenie wredulusa (o wybieraniu dowolnego kamienia klasycznego 28 elementowego domina) wzór z 1) trzeba pomnożyć przez 28ⁿ. (Zupełnie niepotrzebnie wtrąciłem wersję o różnych kamieniach, lecz to wymaga definicji nowego domina więc utrudnia rozwiązanie. Wycofuję się z tego) A co wtedy z obracaniem wybranych kamieni, bo przecież 🀺 i 🁀 to dwa różne ustawienia? Nie wystarczy wyniku pomnożyć przez 2ⁿ gdyż dla czwartej części kamieni klasycznego domina obrót nie wpływa na ustawienie. Zadanie robi się niebanalne i dla mnie zdecydowanie za trudne.

Pytający: Kerajs 1) Lepiej inaczej oznaczyć ten ciąg, gdyż w treści zadania też występuje a_n, ale w innym znaczeniu ("a_n z treści" = "Twoje a_2n"). 2) Aby rozróżniać obroty wystarczy policzyć dla 7 + 21 * 2 = 49 różnych kamieni (zamiast dla 7 + 21 = 28).

kerajs: @ Pytający Ad 1) Założyłem, że a_n z treści zadania jest takie samo jak to, które zdefiniowałem w poprzednim poscie. Gdyby indeksy były wyłącznie parzyste, to nie ma szans na zależność rekurencyjną którą wskazałem, ani na zliczanie takich ustawień jak w grafice powyżej. Ad 2) W kilku ostatnich tematach nadepnąłem wredulusowi na odcisk i miałem nadzieję iż poprawię mu humor jeśli to on wskaże to rozwiązanie. Ech, kiepski jestem w takich gierkach. Przepraszam.

wredulus_pospolitus: @kerajs, autor ma 'w dupie' bo teraz siedzi i powtarza grafy. Kombinatorykę (a może analizę) już zostawił za sobą i go to nie interesuje. Nie nadepnąłeś mi na odcisk. Nie mam monopolu na 'mam rację' i nie mam problemu by się przyznać do tego, że błędnie coś pisałem. Mało tego − cieszę się, gdy ktoś wskaże mi mój błąd. (1) To jest błędna interpretacja ciągu a_n Ciąg {a_n} ma podawać ilość prostokątów o wymiarach 2 x 2n, tak więc a₅ ma podać liczbę takich prostokątów o wymiarach 2 x 10, a nie 2 x 5. Mało tego − nas nie interesują prostokąty o wymiarach 2 x (2n−1). Dlatego Twoja pierwotna rekurencja niestety jest błędna bo nie prezentuje tego ciągu o który pytają w treści zadania (a nawet jeśli to a_n = a_n−1 + 2*a_n−2 przy założeniu że elementy są nierozróżnialne. (2) Masz rację − dochodzą jeszcze obroty samego elementu domina. Heh. Jednak zapewne (patrząc na ostateczną postać wzoru rekurencyjnego) okaże się, że w zadaniu chodziło o nierozróżnialne klocki o wymiarze 2x1. Jednak tego nigdy się nie dowiemy, bo (jak już wcześniej napisałem) autor wątku ma to gdzieś i siedzi teraz w teorii grafów i postara się to 'ogarnąć' do egzaminu poprawkowego (zapewne matematyka dyskretna).

kerajs: ''(1) To jest błędna interpretacja ciągu an Ciąg {an} ma podawać ilość prostokątów o wymiarach 2 x 2n, tak więc a5 ma podać liczbę takich prostokątów o wymiarach 2 x 10, a nie 2 x 5. Mało tego − nas nie interesują prostokąty o wymiarach 2 x (2n−1).'' a) Ciąg {a_n} nie został zdefiniowany w zadaniu. b) Powyżej podałem swoją definicję {a_n}. c) Nie widzę problemu, aby przy innej interpretacji ktoś nazwał mój a_n jako b_n, a potem przyjął iż a_n=b_2n. Ciekawe jak wtedy będzie wyglądała zależność rekurencyjna? d) Obawiam się iż prostokąty o wymiarach 2x(2n−1) muszą nas interesować, gdyż bez nich nie da się wyliczyć: ''Na ile sposobów można WYPEŁNIĆ prostokąt o wymiarach 2 na 2n '' ''a nawet jeśli to an = an−1 + 2*an−2 przy założeniu że elementy są nierozróżnialne.'' Niewątpliwie a₁=1 i a₂=2. Twoim zdaniem a₃=2+2*1=4 ? Łatwo to sprawdzić wykonując cztery rysunki podziału prostokąta 2x3. I co, udało się?