wyznaczenie zaleznosci rekurencyjnej

[danielek12201220]

na ile sposobow mozna zapelnic szachownice \(\displaystyle{ 2\times n}\) jesli mamy do dyspozycji biale , czerwone i zielone klocki o wymiarze \(\displaystyle{ 2\times 1}\) ktore mozna ukladac pionowo i poziomo oraz klocki czarne \(\displaystyle{ 2\times 2}\) , wszystkie w nieograniczonej ilosci? prosze ulozyc zaleznosc rekurencyjna i ja uzasadnic .

MOJA IDEA:

mamy szachownice o dlugosci \(\displaystyle{ 2}\) i szerokosci \(\displaystyle{ n}\). Bierzemy klocek bialy. mozemy go ulozyc pionowo ( zostanie \(\displaystyle{ n-1}\) miejsc do wypelnienia) lub mozemy dac \(\displaystyle{ 2}\) klocki poziomo ( wtedy zostanie \(\displaystyle{ n-2}\) miejsc do wypelnienia). A wiec mamy \(\displaystyle{ U_n =U_{n-1} + U_{n-2}}\) Tak samo robimy z klockami o kolorach czerwonych i zielonych. A wiec sumujac lacznie te wszystkie przypadki to bedzie zaleznosc:
\(\displaystyle{ U_n = 3U_{n-1} + 3U_{n-2}}\) . Ale mamy jeszcze klocki w kolorze czarnym \(\displaystyle{ 2\times 2}\) i je zawsze tak samo sie wklada ( kwadrat nie zmienia polozenia pionowo czy poziomo) a wiec zostanie \(\displaystyle{ n-2}\) miejsc po wlozeniu czarnego klocka.

Czyli : \(\displaystyle{ U_n = 3U_{n-1} + 4U_{n-2}}\)

oraz \(\displaystyle{ U_1 = 3, U_2=7}\)

Czy moglby ktos sprawdzic ?

[Jarosz23]

Nie jest poprawnie. Nawet dla \(\displaystyle{ U_{2}}\) nie masz \(\displaystyle{ 7}\) możliwości. Nie permutujesz w żaden sposób kolorów klocków. Po za tym nie permutujesz również możliwości.

Zobacz, że poziomo możesz ułożyć klocki na \(\displaystyle{ {3 \choose 1} {2 \choose 1}}\). Pionowo zaś na \(\displaystyle{ {3 \choose 1} {2 \choose 1}}\) i do tego dodajesz klocek czarny. Zostaw na razie kolory i rozrysuj sobie pierwsze 5 możliwości. Możesz oznaczyć klocki poprzez \(\displaystyle{ a,b,c}\) , bo tylko one będą permutować ze sobą.(\(\displaystyle{ a}\)-dwa klocki poziomo,\(\displaystyle{ b}\)-kwadrat,\(\displaystyle{ c}\)-pojedynczy klocek.