Funkcja tworzaca

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
matkus1
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 11 lut 2008, o 22:06
Płeć: Mężczyzna
Lokalizacja: radno
Podziękował: 1 raz

Funkcja tworzaca

Post autor: matkus1 »

Prosiłbym o sprawdzenie czy dobrze zrobiłem zadanko.

Dana jest funkcja tworząca. Oblicz wzór jawny.
\(\displaystyle{ f(x)=\frac{3x-2}{x^{2}-3x-4}}\)

\(\displaystyle{ \Delta=9-4(1)(-4)=25 \ \ \ \ \ \ \ \ x_{1}=\frac{3-5}{2}=-1 \ \ \ \ \ \ \ \ x_{2}=\frac{3+5}{2}=4
\\
\frac{3x-2}{x^{2}-3x-4}=\frac{A}{x+1}+\frac{B}{x-4}
\\\\
3x-2 \equiv A(x-4)+B(x+1)
\\\\
3x-2 \equiv Ax-4A+Bx+B
\\\\
stad A=1 \ \ \ \ \ \ \ B=2
\\
\\
f(x)=\frac{1}{x+1}+\frac{2}{x-4}
\\
\\
f(x)=\frac{1}{1-(-x)}+2*\frac{1}{-4+x}
\\
\\
f(x)=\frac{1}{1-(-x)}+2*(-\frac{1}{4})*\frac{1}{1-\frac{1}{4}x}
\\
\\
f(x)= \sum_{n=0}^{\infty}(-x)^n-\frac{1}{2}\sum_{n=0}^{\infty}(\frac{1}{4}x)^n
\\
\\
f(x)= \sum_{n=0}^{\infty}x^n(-1)^n-\frac{1}{2}\sum_{n=0}^{\infty}(\frac{1}{4})^nx^n


wynik:\\\\
a_n=(-1)^n-\frac{1}{2}*(\frac{1}{4})^n}\)
Ostatnio zmieniony 12 lut 2008, o 02:28 przez matkus1, łącznie zmieniany 1 raz.
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Funkcja tworzaca

Post autor: »

matkus1 pisze:f(x)=a_n=(-1)^n-frac{1}{2}*(frac{1}{4})^n
[/latex]
Wszystko ok, tylko ten zapis niefortunny - \(\displaystyle{ f(x)}\) nie jest równe \(\displaystyle{ a_n}\). Ale pomijając ten drobiazg, wszystkie obliczenia są poprawne.

Q.
matkus1
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 11 lut 2008, o 22:06
Płeć: Mężczyzna
Lokalizacja: radno
Podziękował: 1 raz

Funkcja tworzaca

Post autor: matkus1 »

Swietnie Qn - dzięki za pomoc.
Nieścisłość poprawiona.


Mam jeszcze pytanie odnosnie podobnego przykładu


Jest to przykładzik z Knutha "matematyka konkretna". Na czerwono zaznaczyłem to co mi sie nie podoba.
Otóż jak bym nie liczył wychodzi mi że zamaist tego "z" powinna być "1".
Czyli w końcowej wersji funkcji tworzącej G(z) w liczniku raczej \(\displaystyle{ 2+x}\) być pwoinno a nie jak jest \(\displaystyle{ 1+z+z^2}\).
Dlaczego tak? no bo skoro \(\displaystyle{ q_0=1}\) i \(\displaystyle{ q_1=1}\) więc więc powinno to lecieć tak:

\(\displaystyle{ G(z)= \sum_{n=0}^{\infty} a_nx^n=a_0x^0+a_1x^1+...............= \\
= \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1 \ \ +1*x+..............=}\)

właśnie barkuje mi tej jedynki.

Mógłby mi ktoś napisać dlaczego jest tak, albo jednoznacznie stwierdzić że książce jest błąd.
Mianownik oczywiscie OK, tutaj nie mam zastrzeżeń, tylko właśnie ten licznik......
\(\displaystyle{ 1+z+z^2}\)


Ze względu na zabezpieczenia dla nowych userów w swoim podpisie zamieszczam link do omawianego skanu
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Funkcja tworzaca

Post autor: »

Nie ma żadnego błędu, a jak przepiszesz ten przykład w TeX-u zamiast wklejać linki do skanów, to nawet chętnie wytłumaczę dlaczego.

Q.
matkus1
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 11 lut 2008, o 22:06
Płeć: Mężczyzna
Lokalizacja: radno
Podziękował: 1 raz

Funkcja tworzaca

Post autor: matkus1 »

Już pisze Qn

Zadanko:
\(\displaystyle{ a_0=1 \ \ \ \ \ a_1=1}\)
\(\displaystyle{ a_n=a_{n-1}+2a_{n-2}+(-1)^n}\)

Roziwzanie(moje)

\(\displaystyle{ F(x)= \sum_{n=0}^{\infty}a_{n}x^{n}=a_{0}x^{0}+a_{1}x^{1}+........=}\)
\(\displaystyle{ F(x)= \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =1+1*x+\sum_{n=0}^{\infty}(a_{n-1}+2a_{n-2})x^{n}=}\)
\(\displaystyle{ F(x)= \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 1+x+x\sum_{n=2}^{\infty}a_{n-1}x^{n-1}+2x^{2}\sum_{n=2}^{\infty}a_{n-2}x^{n-2}+\sum_{n=0}^{\infty}(-1)^{n}x^{n}=}\)
\(\displaystyle{ F(x)= \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 1+x+x(F(x)-1)+2x^{2}F(x)+\frac{1}{1+x}=}\)
\(\displaystyle{ F(x)= \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 1+x+xF(x)-x+2x^{2}F(x)+\frac{1}{1+x}}\)
\(\displaystyle{ F(x)-xF(x)-2x^{2}F(x)=1+\frac{1}{1+x}}\)
\(\displaystyle{ F(x)(1-x-2x^2)=\frac{2+x}{1+x}}\)
\(\displaystyle{ F(x)=\frac{2+x}{(1-x-2x^2)(1+x)}}\)
\(\displaystyle{ F(x)=\frac{2+x}{(1-2x)(1+x)^{2}}}\)


Rozwiazanie(wg.podrecznika)
\(\displaystyle{ F(x)= \sum_{n=0}^{\infty}a_{n}x^{n}=}\)
\(\displaystyle{ F(x)= \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{n=0}^{\infty}a_{n-1} \ x^{n}+2 \sum_{n=2}^{\infty}a_{n-2} \ x^n+\sum_{n=0}^{\infty}(-1)^{n} \ x^{n}+\sum_{n=1}^{1}x^{n} =}\)
\(\displaystyle{ F(x)= \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =xF(x)+2x^{2}F(x)+\frac{1}{1+x}+x}\)

Po przekszatlceniu funkcja tworząca:
\(\displaystyle{ F(x)=\frac{1+x+x^{2}}{(1-2x)(1+x)^{2}}}\)

A wiec niestety inaczej
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Funkcja tworzaca

Post autor: »

\(\displaystyle{ a_0=1 \ \ \ \ \ a_1=1}\)
\(\displaystyle{ a_n=a_{n-1}+2a_{n-2}+(-1)^n}\)
Pierwszym krokiem jaki musimy zrobić, jest zapisanie w jednym równaniu warunków początkowych oraz naszego wzoru rekurencyjnego. Zakładamy tutaj, że \(\displaystyle{ a_n = 0}\) dla \(\displaystyle{ n 0 +1 = 1}\)
co zgadza się z warunkiem początkowym.
Z kolei dla \(\displaystyle{ n=1}\) mamy:
\(\displaystyle{ a_1=1 + 2 0 -1 = 0}\)
czyli źle, bo ma być równe \(\displaystyle{ 1}\). Dlatego podrasujemy nasze równanie do:
\(\displaystyle{ a_n=a_{n-1}+2a_{n-2}+(-1)^n + [n=1]}\) (*)
gdzie dla zdania \(\displaystyle{ p}\) definiujemy:
\(\displaystyle{ [p]= \begin{cases} 1 \ gdy \ p \ prawdziwe\\ 0 \ gdy \ p \ falszywe \end{cases}}\)

Teraz wzór (*) określa nam dobrze wszystkie wyrazy ciągu, dlatego możemy stronami wymnożyć go przez \(\displaystyle{ x^n}\) i przesumować po \(\displaystyle{ n}\) od \(\displaystyle{ 0}\) do \(\displaystyle{ \infty}\). Zwrócmy przy tym uwagę, że:
\(\displaystyle{ \sum_{n=0}^{\infty} [n=1] x^n = x}\)

Stąd też wynika wzór na funkcję tworzącą podany w książce. Pisałem to już chyba kiedyś na tym forum, ale powtórzę: jednej z lepszych książek jakie kiedykolwiek napisano o matematyce.

Q.
matkus1
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 11 lut 2008, o 22:06
Płeć: Mężczyzna
Lokalizacja: radno
Podziękował: 1 raz

Funkcja tworzaca

Post autor: matkus1 »

jakoś nie bardzo to do mnie przemawia;
skoro trzeba dodać 1 tylko dla jednego wyrazu ciągu(gdy n=1) i żadnego innego dlaczego modyfikuje się funkcje tworzacą odpowiadającą za wszystkie wyrazy ciągu?


No ale spoko taka jes treguła, juz to sobie zakceptowałem
nie mniej wątku jeszcze nie zamykam, drąże nadal temat.

Tymczasem punkcik dla Qnia.
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Funkcja tworzaca

Post autor: »

To spójrz na inny przykład, może się coś rozjaśni:
\(\displaystyle{ a_0 = 3 \\
a_1 = -5 \\
a_n = a_{n-1} + 2a_{n-2}}\)

Chcemy, żeby ten ostatni wzór rekurencyjny był prawdziwy dla dowolnego \(\displaystyle{ n}\). Ale póki co ten wzór mówi tyle, że \(\displaystyle{ a_0 = 0}\) oraz \(\displaystyle{ a_1 = 3}\). Więc dopiszmy co trzeba:
\(\displaystyle{ a_n = a_{n-1} + 2a_{n-2}+ 3 [n=0] - 8 [n=1]}\)
Teraz zgadza się dla dowolnego \(\displaystyle{ n}\), a funkcja tworząca będzie spełniać równanie:
\(\displaystyle{ f(x)=xf(x)+2x^2f(x) + 3 - 8x}\)

Q.
matkus1
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 11 lut 2008, o 22:06
Płeć: Mężczyzna
Lokalizacja: radno
Podziękował: 1 raz

Funkcja tworzaca

Post autor: matkus1 »

Rozjaśnił Qn bardzo wiele.
Od razu zrobiłemm go sobie do konca i ładnie wyszedł.
Jeszcze ra z dzięki za ten przykładzik.


Zanim zamkne watek miałbym jeszcze jedno pytanko. Chodzi o dalsza czesc roziazania tego przykladu z Knutha.

\(\displaystyle{ F(x)=\frac{1+x+x^{2}}{(1-2x)(1+x)^{2}}}\)

rozkładam na ułamki proste jak zwykle:

\(\displaystyle{ F(x)=\frac{A}{1-2x}+\frac{B}{1+x}+\frac{C}{({1+x})^{2}}}\)

po obliczeniach wychodzi:

\(\displaystyle{ F(x)=\frac{\frac{7}{9}}{1-2x}+\frac{-\frac{1}{9}}{1+x}+\frac{\frac{1}{3}}{({1+x})^{2}}}\)

\(\displaystyle{ F(x)=\frac{7}{9} \ \frac{1}{1-2x}-\frac{1}{9} \ \frac{1}{1-(-x)}+\frac{1}{3} \ \frac{1}{{(1+x)}^{2}}}\)

\(\displaystyle{ F(x)= \frac{7}{9} \ \sum_{n=0}^{\infty} \ (2)^nx^n - \frac{1}{9} \ \sum_{n=0}^{\infty} \ (-1)^nx^n + \frac{1}{3} \ \sum_{n=0}^{\infty} ???????}\)


Właśnie w tym miejscu utkwilem. Nie wiem jak ten ułamek dalej rozpisywać.
Byłbym wdzieczny za sugestie.
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Funkcja tworzaca

Post autor: »

Mamy:
\(\displaystyle{ \frac{1}{1+x} = \sum_{n=0}^{\infty} (-1)^nx^n \\
ft( \frac{1}{1+x} \right )^{'} = ft( \sum_{n=1}^{\infty} (-1)^nx^n \right)^{'} \\
\frac{-1}{(1+x)^2} = \sum_{n=0}^{\infty} (-1)^nnx^{n-1} \\
\frac{1}{(1+x)^2} = \sum_{n=0}^{\infty} (-1)^n(n+1)x^n}\)

(w ostatniej równości przesunięty został wskaźnik sumowania).

Q.
matkus1
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 11 lut 2008, o 22:06
Płeć: Mężczyzna
Lokalizacja: radno
Podziękował: 1 raz

Funkcja tworzaca

Post autor: matkus1 »

Ufff i zrobiony do końca.

Heh, im głebiej w las tym widzę wiekszą swoją niewiedzę. Zawsze tak jest?


Dzieki, mysle ze watek mozna uznac za zamkniety.




Pozdrwaiam

[ Dodano: 14 Lutego 2008, 03:29 ]
Spytam jeszcze o inny rodzaj ciągu. Tutaj cos nie zgadza gdy go rozpisuję:

\(\displaystyle{ a_0=3}\)
\(\displaystyle{ a_n=2\ a_{n-1}-(-2)^{n}}\)


Zgodnie z reguła podrasowywyje, bo \(\displaystyle{ a_0=-1}\)
\(\displaystyle{ a_n=2\ a_{n-1}-(-2)^{n}+4 [n=0] \right|}\)


Czyli mam:
\(\displaystyle{ F(x)=2 \sum_{n=0}^{ } a_{n-1}x^n - \sum_{n=0}^{ }(-2)^nx^n+4 \sum_{n=0}^{ } |n=0| x^n}\)
\(\displaystyle{ F(x)=2xF(x)-\frac{1}{x+2}+4}\)
\(\displaystyle{ F(x)=\frac{4x+7}{(2+x)(1-2x)}}\)

\(\displaystyle{ F(x)=\frac{-\frac{1}{5}}{2+x}+\frac{\frac{18}{5}}{1-2x} \\\\\\\\\\\\\\\\}\)
stąd:

\(\displaystyle{ a_n=-\frac{1}{10}(-\frac{1}{2})^n+\frac{18}{5}(2)^n}\)



Niestety coś jest nie tak a błedu nie widze.
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Funkcja tworzaca

Post autor: »

\(\displaystyle{ \sum_{n=0}^{ }(-2)^nx^n = \frac{1}{1+2x}}\)

Q.
matkus1
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 11 lut 2008, o 22:06
Płeć: Mężczyzna
Lokalizacja: radno
Podziękował: 1 raz

Funkcja tworzaca

Post autor: matkus1 »

Heh,

ostatecznie wiec wyszło coś takiego:
\(\displaystyle{ a_n=-\frac{7}{2}(-2)^{n}+\frac{1}{2}(2)^{n}}\)
Prawie idealnie ale nie dok konca.(w podpisie link do wypisania wyrazów dowma metodami)
Rozumiem że jednak nie wszytskie ciągi da się idealnie przedstawic wzorem jawnym?


Po wrzuceniu do programu wypisuje bowiem nastepująco:
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Funkcja tworzaca

Post autor: »

A mi wyszło:
\(\displaystyle{ a_n=\frac{7}{2}(2)^{n}-\frac{1}{2}(-2)^{n}}\)
lub co na jedno wychodzi:
\(\displaystyle{ a_n=7 2^{n-1} + (-2)^{n-1}}\).

Q.
Ostatnio zmieniony 15 lut 2008, o 13:24 przez , łącznie zmieniany 1 raz.
matkus1
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 11 lut 2008, o 22:06
Płeć: Mężczyzna
Lokalizacja: radno
Podziękował: 1 raz

Funkcja tworzaca

Post autor: matkus1 »

Racja mój bład.
ODPOWIEDZ