Domino - rekurencja rekursja: Cześć. Zwracam się do was z prośbą związanego z zadaniem z rekurencją. Brzmi ono tak: "Odcinek o długości n pokrywany jest kośćmi domina o długości 2 w sześciu kolorach i o długości 1 w jednym kolorze. Oblicz, na ile różnych sposobów można pokryć odcinek tymi kośćmi." Nie chodzi mi o to żeby rozwiązać w całości to zadanie tylko o wypisanie warunków początkowych(a₁ i a₂). Wiem że a₁ = 1, natomiast a₂ = 7. Ponieważ wszystkich tych podwójnych kolorów mam 6 ale muszę doliczyć też ten pojedynczy. Więc jest 6 kolorów podwójnych + 1 pojedynczy z tymże ten pojedynczy to jest 1² bo jego mogę ustawić na dwa sposoby. 6 + 1² = 6 + 1 = 7. Czy tak?

. : A czy te pojedyncze na pewna są w innym kolorze niż te podwójne?

. : Jeżeli przyjmiemy ze jest to inny kolor (lub rozróżniamy czy są to dwa pojedyncze klocki czy jeden dłuższy) to takie będą początkowe, chociaż ja bym zaczął od a₀ = 0 i a₁ = 1, ale to już bez różnicy większej jest.

kerajs: ''rekursja: (...) Wiem że a1 = 1, natomiast a2 = 7. Ponieważ wszystkich tych podwójnych kolorów mam 6 ale muszę doliczyć też ten pojedynczy. Więc jest 6 kolorów podwójnych + 1 pojedynczy z tymże ten pojedynczy to jest 12 bo jego mogę ustawić na dwa sposoby. 6 + 12 = 6 + 1 = 7. Czy tak?'' Nie. Ciąg o długości 2 możesz uzyskać układając jeden z sześciu kamieni o długości 2 lub układając dwa kamienie o długości 1. Stąd 7 możliwych ustawień. Ogólnie, ciąg o długości n możesz uzyskać dokładając jeden z sześciu kolorowych kamieni o długości 2 do ciągu o długości n−2 lub dokładając kamień o długości 1 do ciągów o długości n−1.

	1
A stąd równanie rekurencyjne: an=6an−2+an−1 i wzór ogólny an=		(3*(3)n+2*(−2)n)
	5

.

Cała : Zapomniałem dodać że są one różnego koloru. Dziękuję za zwrócenie uwagi.

Cała : kerajs czy można wykorzystać tu wariacje z powtórzeniami?

rekursja : Przepraszam, ale zaszła pomyłka w nicku.

rekursja : Czy żeby wyliczyć a₂ to mogę użyć wariacji z powtórzeniami. W₁ ² = 1² = 1. I ostateczny wynik a₂ = 6 + 1 = 7

wredulus_pospolitus: ale po kiego grzyba stosować wariację z powtórzeniami ?

rekursja: Nauczyciel podał mi takie rozwiązanie. Dlatego się pytam?

wredulus_pospolitus: Takie znaczy jakie

kerajs: Może takie:

	i! (n−2i)!
an=∑i=0 [n/2]		*6i
	(n−i)!

rekursja : Takie że żeby policzyć a2 trzeba zastosować wariacje z powtórzeniami W₁² = 1² = 1

wredulus_pospolitus: heee

kerajs: To może pokaż rozwiązanie nauczyciela. Chętnie poznam nieznaną mi metodę rozwiązywania równań rekurencyjnych.

rekursja : Chciałbym zapytać tak jeszcze z innej beczki. Bo chciałbym zmienić nieco treść tego zadania a dokładniej to tu "Odcinek o długości n pokrywany jest kośćmi domina o długości 2 w sześciu kolorach i o długości 3 w dwóch kolorach. Jakby wtedy wyglądało a1 i a2 ?

. : a₁ = 0 (brak domin długości 1) a₂ = 6 a₃ = 3 Dodatkowo − czy kolory domin długości 2 i 3 są inne czy mogą się powtarzać?

. : Poprawka − a₃ = 2

rekursja : Inne. Cały czas innego koloru

rekursja: "kerajs: Ciąg o długości 2 możesz uzyskać układając jeden z sześciu kamieni o długości 2 lub układając dwa kamienie o długości 1. Stąd 7 możliwych ustawień." Dwa kamienie o długości 1 ale ustawione obok siebie?

rekursja: Bo to mam podobne zadanko: "Odcinek o długości n pokrywany jest kośćmi domina o długości 2 w 4 kolorach i o długości 1 w 3 kolorach. Oblicz, na ile różnych sposobów można pokryć odcinek tymi kośćmi." Warunki początkowe a₁ = 3 − bo 3 kolory o długości 1 i a₂ = 4 − bo 4 kolory o długości 2 plus jeszcze 9 bo dobieram sobie albo 1 o długości 2 albo 2 pojedyncze o długości 1? W efekcie mam a₁ = 3 i a₂ = 4 + 9 = 13. Czy dobrze? Pytam tylko formalnie bo mam to zrobione tylko upewnić w rozwiązaniu się chciałem. Dzięki

jc: a₀ = 1, a₁ = 1, a_n+1 = a_n + 7 a_n−1 a₂ = 1 + 7 = 8, a₃ = 8 + 7 = 15, a₄ = 15 + 7*8 = 71

jc: rekursja, ok ... pozostałe w 6 kolorach .. a₀ = 1, a₁ = 1, a_n+1 = a_n + 6 a_n−1 a₂ = 1 + 6 = 7, a₃ = 7 + 6 = 13, a₄ = 13 + 6*7 = 55 −−− drugie zadanie podobnie a₀=1, a₁=3, a_n+1=3a_n+4a_n−1 a₂ = 3*3+4=13, a₃=3*13+4*3=51

rekursja: jc: a możesz wytłumaczyć dlaczego tak?

rekursja: już nie trzeba. Przeanalizowałem sobie wszystko dokładnie na spokojnie. Już wszystko jasne. Dziękuje