Funckja tworząca ciągu.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
dizel1988
Użytkownik
Użytkownik
Posty: 98
Rejestracja: 30 lis 2006, o 18:23
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 35 razy

Funckja tworząca ciągu.

Post autor: dizel1988 » 9 gru 2008, o 10:25

Witam.

Czy mógłby mi ktoś wyjaśnić na czym polega tworzenie funkcji tworzącej ciągu? Problem u mnie polega na tym że dostane ciąg np taki: 0 0 0 1 1 1 2 2 2 3 3 3 .... i muszę napisać funkcję towrząca tego ciągu. Bardzo proszę o pomoc. Na zajęciach coś mówili o jakims przesuwaniu w lewo ale kompletnie niemam pojęcia na czym to polega. Pomóżcie .

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2629 razy

Funckja tworząca ciągu.

Post autor: » 9 gru 2008, o 13:12

Funkcja tworząca ciągu \(\displaystyle{ a_n}\) to \(\displaystyle{ A(x) = \sum_{n=0 }^{\infty} a_n x^n}\). Tutaj mamy więc:
\(\displaystyle{ A(x)=x^3+x^4+x^5 + 2x^6+2x^7+2x^8+3x^9+3x^{10}+3x^{11}+4 x^{12}+ \dots =
\\ =
x^3[( 1+x+x^2) + (2x^3+2x^4+2x^5)+(3x^6+3x^{7}+3x^{8})+(4 x^{9}+ \dots )] = \\ =
x^3( 1+x+x^2) (1 + 2x^3+3x^6+4 x^{9}+ \dots ) = \\ =
\frac{x^3}{1-x}\cdot (1-x^3)(1 + 2x^3+3x^6+4 x^{9}+ \dots ) = \\ =
\frac{x^3}{1-x} (1+x^3+x^6+x^9 + \dots ) = \\ =
\frac{x^3}{1-x}\cdot \frac{1}{1-x^3}= \frac{x^3}{(1-x)^2(1+x+x^2)}}\)


Q.

ODPOWIEDZ