Funkcja tworząca - wzór ogólny

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
inzbartosz
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 11 cze 2009, o 00:07
Płeć: Mężczyzna
Podziękował: 1 raz
Pomógł: 1 raz

Funkcja tworząca - wzór ogólny

Post autor: inzbartosz »

Patrzę na te wszystkie zadania o funkcjach tworzących i w ogole nie widze w nich logiki... Jak Wy to liczycie? Jak wygląda wzór/algorytm liczenia tych funkcji? Ze zrodel, na ktore patrze rozumiem tylko tyle, ze funkcja tworzaca dla \(\displaystyle{ a_{n} =1}\) to \(\displaystyle{ \frac{1}{1-x}}\), a dla \(\displaystyle{ a_{n} =(1,2,3...)}\) ta funkcja to \(\displaystyle{ \frac{1}{(1-x)^{2}}}\) ale dlaczego? Bo tak.
sopi
Użytkownik
Użytkownik
Posty: 88
Rejestracja: 11 lut 2007, o 12:17
Płeć: Mężczyzna
Lokalizacja: Z kielc
Podziękował: 8 razy
Pomógł: 7 razy

Funkcja tworząca - wzór ogólny

Post autor: sopi »

inzbartosz pisze:ze funkcja tworzaca dla \(\displaystyle{ a_{n} =1}\) to \(\displaystyle{ \frac{1}{1-x}}\), a dla \(\displaystyle{ a_{n} =(1,2,3...)}\) ta funkcja to \(\displaystyle{ \frac{1}{(1-x)^{2}}}\) ale dlaczego? Bo tak.
... etna_1/Wykład_7:_Funkcje_tworzące

Bardzo dobra lektura, myślę , że Ci rozjaśni trochę tą kwestię

ale ogólnie mając jakiś ciąg , powiedzmy \(\displaystyle{ a_{n+2} = a_{n+1} + 3a_{n}}\) możemy wyznaczyć jego funkcję tworzącą, oraz wyraz ogólny [tez] a_{n}[/latex] ciągu, operacjąc na sumie szeregu geometrycznego , oraz wykorzytsując wspomniane przez Ciebie funkcji tworzących dla konkretnych ciągów
\(\displaystyle{ f(x) = \sum_{n=0}^{\infty}a_{n}x^{n}\\\sum_{n=0}^{\infty}a_{n}x^{n} = a_{0} + a_{1}x + \sum_{n=2}^{\infty}a_{n}x^{n} = a_{0} + a_{1}x + \sum_{n=0}^{\infty}a_{n+2}x^{n+2} = a_{0} + a_{1}x + \sum_{n=0}^{\infty}(a_{n+1} + 3a_{n})x^{n+2} = a_{0} + a_{1}x + x\sum_{n=0}^{\infty}a_{n+1}x^{n+1} + 3x^{2}\sum_{n=0}^{\infty}a_{n}x^{n}=a_{0} + a_{1}x + x\sum_{n=1}^{\infty}a_{n}x^{n} + 3x^{2}\sum_{n=0}^{\infty}a_{n}x^{n} = a_{0} + a_{1}x + x(f(x) - a_{0}) + 3x^{2}f(x) = 1 - 2x + x(f(x)-1) + 3x^{2}f(x)}\)
Po przekształceniach mamy
\(\displaystyle{ \\ f(x) = \frac{1+x}{1-x-3x^{2}}}\)
inzbartosz
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 11 cze 2009, o 00:07
Płeć: Mężczyzna
Podziękował: 1 raz
Pomógł: 1 raz

Funkcja tworząca - wzór ogólny

Post autor: inzbartosz »

OK. Wlasnie zrozumialem idee tego rozbijania. A moze ktos napisac na tym najprostszym przykladzie jak sie dochodzi do tego, ze \(\displaystyle{ f(x)= \frac{1}{1-x}}\)? Czy tych podstawowych sie po prostu trzeba nauczyc na pamiec?
Sage!
Użytkownik
Użytkownik
Posty: 65
Rejestracja: 7 wrz 2006, o 01:45
Płeć: Mężczyzna
Lokalizacja: Milanówek
Pomógł: 2 razy

Funkcja tworząca - wzór ogólny

Post autor: Sage! »

Wynika to z faktu, że jeżeli mamy \(\displaystyle{ f(x) = \sum_{n=0}^{\infty} a_n x^n}\) to jak postawimy dla każdego \(\displaystyle{ n \in \mathbb{N}: \ a_n = 1}\) to wtedy otrzymamy sumę ciągu geometrycznego, który jest zbieżny dla \(\displaystyle{ |x|<1}\). I suma ta właśnie wyraża się przez \(\displaystyle{ f(x) = \frac{1}{1-x}}\). Jeżeli chcielibyśmy otrzymać ciąg \(\displaystyle{ a_n = (1,2,3,4,...)}\) to wystarczy zauważyć, że zachodzi \(\displaystyle{ f'(x) = \left( \sum_{n = 0}^{\infty} x^n \right)' = \sum_{n = 0}^{\infty} (x^n)' = \sum_{n = 0}^{\infty} nx^n = \left( \frac{1}{1-x} \right)' = \frac{1}{(1-x)^2}}\) oczywiście stosując odpowiednie twierdzenie o różniczkowaniu szeregów.
Farokles
Użytkownik
Użytkownik
Posty: 111
Rejestracja: 9 wrz 2008, o 18:21
Płeć: Mężczyzna
Lokalizacja: Nibylandia
Podziękował: 50 razy

Funkcja tworząca - wzór ogólny

Post autor: Farokles »

sopi pisze: \(\displaystyle{ = a_{0} + a_{1}x + x(f(x) - a_{0}) + 3x^{2}f(x) = 1 - 2x + x(f(x)-1) + 3x^{2}f(x)}\)
drobna pomyłka powinien być + 2x

\(\displaystyle{ = 1 + 2x + x(f(x)-1) + 3x^{2}f(x)}\)
jj09
Użytkownik
Użytkownik
Posty: 6
Rejestracja: 15 cze 2009, o 13:40
Płeć: Mężczyzna
Podziękował: 1 raz

Funkcja tworząca - wzór ogólny

Post autor: jj09 »

a jakie jest \(\displaystyle{ a_{n}}\) dla f(x) = 1?
ODPOWIEDZ