rekurencja areczek: Niech 𝑠𝑛 oznacza liczbę ciągów binarnych długości 𝑛, w których krotność wystąpienia 0 jest parzysta, a krotność wystąpienia 1 nieparzysta. Wyznacz rekurencyjną zależność dla 𝑠𝑛. Pomoże ktoś bo doszedłem do wniosku, że jak n mod 2 = 0 to jest tylko jeden poprawny ciąg ale nie wiem jak znaleźć zależność rekurencyjną

wredulus_pospolitus: jeżeli n jest parzyste to przecież nie ma ani jednego ciągu o długości n złożonego z parzystej liczby 0 i nieparzystej liczby 1

Saizou : wredulus, czy takich ciągów będzie

	n 0		n 2		n 4		n [n/2]
S(n) =		+		+		+...+		, jeżeli n jest nieparzyste.

Saizou :

	n n−1
a nie ... ostatni składnik to

wredulus_pospolitus: no nie do końca '0' nie może być na pierwszym miejscu

wredulus_pospolitus: chociaż nie no ... może być ... w końcu mówimy o ciagach a nie o liczbach więc tak ... tyle ich będzie tyle że zadanie polega na znalezieniu rekurencji

wredulus_pospolitus: można też zauważyć, że:

	(1+1)n
S(n) =		= 2n−1
	2

wredulus_pospolitus: co też można było wywnioskować albo patrząc na sumę tych dwumianów newtona (pierwotnie tak patrzyłem) albo przejść się po kombinatoryce: wszystkich ciągów mamy 2ⁿ ... jako że w danym ciągu mamy nieparzystą liczbę znaków, to albo 0 będzie nieparzysta liczba albo 1. Stąd − dokładnie połowa z nich będzie spełniać warunki zadania ... stąd s(n) = 2ⁿ⁻¹

Profesor: Próbowałeś zmienić Y na X?

Saizou : Dzięki za potwierdzenie wredulus

kerajs: Dziwna jest treść zadania. Przy waszej interpretacji ( parzysta liczba zer i nieparzysta ilość jedynek) słowa ''krotność'' są zbędne, a rekurencji nie można ułożyć. A może miało chodzić o to, że wszystkie maksymalne podciągi sąsiadujących ze sobą zer są liczbami parzystymi, a wszystkie maksymalne podciągi sąsiadujących ze sobą jedynek są liczbami nieparzystymi?

kerajs: Jeśli w binarnych ciągach wszystkie maksymalne podciągi sąsiadujących ze sobą zer są liczbami parzystymi, a wszystkie maksymalne podciągi sąsiadujących ze sobą jedynek są liczbami nieparzystymi to ich liczbę można (o ile się nie pomyliłem) wyrazić rekurencją: i_n=2i_n−2 +i_n−3 −i_n−4 oraz i₁=i₂=1 ; i₃=3 ; i₄=2