Liczba ciągów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
lennyh
Użytkownik
Użytkownik
Posty: 96
Rejestracja: 14 lis 2009, o 22:22
Płeć: Mężczyzna
Podziękował: 4 razy

Liczba ciągów

Post autor: lennyh »

Zliczamy ciągi długości \(\displaystyle{ n}\) złożonych z cyfr \(\displaystyle{ 0,1,2}\) takich, że każdy z nich zawiera parzystą liczbę cyfr \(\displaystyle{ 0}\) i parzystą liczbę cyfr \(\displaystyle{ 1}\). Znaleźć zależność rekurencyjną.
Ostatnio zmieniony 21 lut 2014, o 20:16 przez , łącznie zmieniany 1 raz.
Powód: Wszystkie wyrażenia matematyczne umieszczaj w tagach [latex] [/latex].
piotr5
Użytkownik
Użytkownik
Posty: 70
Rejestracja: 1 lip 2012, o 20:02
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 2 razy
Pomógł: 7 razy

Liczba ciągów

Post autor: piotr5 »

Wzór rekurencyjny \(\displaystyle{ x_n = 3x_{n-1}}\), jeśli n jest parzyste oraz \(\displaystyle{ x_n = 3x_{n-1} - 2}\) gdy nie jest.
Udowodnię zależność dla n parzystych (dla nieparzystych jest podobnie).
Niech a liczba ciągów długości \(\displaystyle{ n-1}\) takich, że wszystkie liczby (0, 1 i 2) występują nieparzystą liczbę razy. Liczba wszystkich ciągów wynosi \(\displaystyle{ 3^{n-1}}\), a zatem
\(\displaystyle{ a + 3x_{n-1}=3^{n-1}}\)
Niech b liczba ciągów długości n takich, że jedna ustalona liczba występuje parzystą liczbę razy, a pozostałe nieparzystą. Wtedy:
\(\displaystyle{ x_n + 3b = 3^n}\)
Zauważmy teraz, że \(\displaystyle{ b = a + 2x_{n-1}}\), zatem \(\displaystyle{ x_n = 3^n - 3b = 3^n - 3a - 6x_{n-1} = 3^n - (3^n - 9x_{n-1}) - 6x_{n-1} = 3x_{n-1}.}\)
Gdyby któraś z użytych równości była niejasna, to pomogę.
ODPOWIEDZ