Funkcje tworzące,rekurencje,4zadania

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
jemcole
Użytkownik
Użytkownik
Posty: 6
Rejestracja: 7 wrz 2009, o 21:46
Płeć: Mężczyzna
Lokalizacja: warszawa

Funkcje tworzące,rekurencje,4zadania

Post autor: jemcole »

1) Niech \(\displaystyle{ a_{n}}\) oznacza liczbę podzbiorów zbioru {1..n} (wliczając zbiór pusty) nie zawierających sąsiednich liczb. Znaleźć wzór rekurencyjny \(\displaystyle{ a_{n}}\)
2) Rozwiązać metodą funkcji tworzących równanie różnicowe \(\displaystyle{ a_{n} -3a_{n-1} = 2^{n}}\) z warunkiem \(\displaystyle{ a_{0} = 1}\)
3) Niech \(\displaystyle{ a_{k}}\) oznacza liczbę słów złożonych z czterech liter {a,b,c,d} z których każda występuje w słowie przynajmniej raz i nie więcej niż trzy razy. Wyznaczyć metodą funkcji tworzących wartości ciągu \(\displaystyle{ a_{k}}\) dla każdego \(\displaystyle{ k \in N}\)
4) Rozwiązać metodą Eulera równanie różnicowe \(\displaystyle{ x_{n} = 4x_{n-1} - 4x_{n-2} + 2^{n+2}}\) z warunkami początkowymi \(\displaystyle{ x_{0} = 1, x_{1} = 0}\)
Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

Funkcje tworzące,rekurencje,4zadania

Post autor: Dumel »

1. \(\displaystyle{ a_{n+1}=a_n+a_{n-1}}\) (rozpatrujemy osobno zbiory zawierające \(\displaystyle{ n+1}\) i pozostałe)
ODPOWIEDZ