kombinatoryka Klaudiss: Niech an oznacza liczbę sposobów, na które możemy ułożyć wieżę wysokości n cm z klocków, jeśli mamy do dyspozycji klocki białe i czarne o wysokości 1 cm oraz klocki czerwone, zielone i żółte o wysokości 2 cm. Znajdź zależność rekurencyjną dla an, wylicz trzy pierwsze wyrazy oraz znajdź jawny wzór na ogólny wyraz tego ciągu. Coś rzeźbiłam z liczb bella, coś rzeźbiłam na metodę prób i błędów, coś mam, ale nie mogę dokończyć. Proszę o pomoc .

.: Jeśli stałaś sie juz rzeżbiarką to masz fach dla mnie to zwykłe kombinacje z powtóżrzeniami

Pytający: Ach, artyści. Zależność rekurencyjna jest prosta: a₀=1 // brak klocków a₁=2 // biały/czarny a_n=2a_n−1+3a_n−2 dla n≥2 // (a_n−1+biały/czarny) lub (a_n−2+czerwony/zielony/żółty) Wzór jawny można znaleźć z funkcji tworzących: A(x)=∑_n=0^∞(a_nxⁿ)=a₀x⁰+a₁x¹+∑_n=2^∞(a_nxⁿ)= =1+2x+∑_n=2^∞((2a_n−1+3a_n−2)xⁿ)= =1+2x+2∑_n=2^∞(a_n−1xⁿ)+3∑_n=2^∞(a_n−2xⁿ)= =1+2x+2x∑_n=2^∞(a_n−1xⁿ⁻¹)+3x²∑_n=2^∞(a_n−2xⁿ⁻²)= =1+2x+2x∑_n=1^∞(a_nxⁿ)+3x²∑_n=0^∞(a_nxⁿ)= =1+2x+2x(∑_n=0^∞(a_nxⁿ)−a₀x⁰)+3x²∑_n=0^∞(a_nxⁿ)= =1+2x+2x(A(x)−1)+3x²A(x)= =1+2xA(x)+3x²A(x) A(x)=1+2xA(x)+3x²A(x) (1−2x−3x²)A(x)=1

	1
A(x)=
	1−2x−3x2

Po rozkładzie na ułamki proste:

	1		1		3		1
A(x)=		(		+		)= // podstawowy wzór: ∑n=0∞((αx)n)=
	4		1−(−x)		1−3x		1−αx

	1
=		(∑n=0∞((−x)n)+3∑n=0∞((3x)n))=
	4

	1
=		(∑n=0∞((−1)nxn)+3∑n=0∞(3nxn))=
	4

	(−1)n+3n+1
=∑n=0∞(		xn) ⇒
	4

	(−1)n+3n+1
⇒ an=
	4

	(−1)2+32+1
a2=		=7
	4

	(−1)3+33+1
a3=		=20
	4

Mila: Z równania charakterystycznego krócej. Pozdrawiam.

Pytający: Krócej, ale równie dobrze. Pozdrawiam również!

Mila: A dlaczego a₀=1?

Pytający: Dlatego, bo jest 1 sposób ułożenia wieży wysokości 0 cm z tych klocków: nie kłaść żadnego klocka.

Mila: Jeszcze jutro będę miała pytanie. Dzisiaj Dobranoc

Pytający: Dobranoc.