|
|
| Linia 1: |
Linia 1: |
| <code>abc</code>
| | <math>\displaystyle {\large z^{\sum_{i=1}^{10}i}}</math> |
| ==Problemy ze wzorami na osiłku==
| | <math>\displaystyle {\large z+{\sum_{i=1}^{10}i}}</math> |
| <math>\displaystyle M</math> <math>\displaystyle M'</math> <math>\displaystyle M' </math>
| |
| <math>\displaystyle {\large b^{\sum_{i=1}^{10}i}}</math> | |
| | |
| A powinno to wyglądać tak:
| |
| http://www.ii.uj.edu.pl/~pawlik1/MediaWiki
| |
| | |
| <hr>
| |
| | |
| <table>
| |
| <tr><td>zxczxc</td><td>zxczxc</td></tr>
| |
| </table>
| |
| | |
| [[Konwersja Arka]]
| |
| [[Konwersja Arka 2]]
| |
| [[Konwersja Arka 3]]
| |
| | |
| | |
| <hr>
| |
| | |
| {thm}{Twierdzenie}
| |
| {obs}[thm]{Obserwacja}
| |
| {con}[thm]{Wniosek}
| |
| | |
| {article}
| |
| {../makraB}
| |
| | |
| ==Funkcje tworzące==
| |
| | |
| {{przyklad|[Uzupelnij]||
| |
| | |
| Słynny matematyk Georg Pólya rozważał problem polegający na
| |
| policzeniu wszystkich możliwych sposobów, na które można rozmienić 50 centów używając
| |
| jednocentówek <math>\left( 1 \right)</math>,
| |
| pięciocentówek <math>\left( 5 \right)</math>,
| |
| dziesięciocentówek <math>\left( 10 \right)</math>,
| |
| ćwierćdolarówek <math>\left( 25 \right)</math>,
| |
| oraz półdolarówki <math>\left( 50 \right)</math>.
| |
| Rozważania te doprowadziły go do użycia analitycznych metod funkcji tworzących
| |
| w zaproponowanym przez niego rozwiązaniu.
| |
| W tym i następnym wykładzie poznamy te metody
| |
| i zobaczymy jak mogą być pomocne w zliczaniu rożnych obiektów kombinatorycznych.
| |
| | |
| Wracając do problemu rozmieniania monet, wygodnie nam będzie posiadać
| |
| jeszcze monetę <math>\left[0\right]</math>, którą możemy interpretować jako brak monet.
| |
| Wypiszmy teraz (nadużywając trochę notacji)
| |
| nieskończoną sumę wszystkich możliwości rozmiany dowolnej kwoty
| |
| za pomocą jednocentówek
| |
| | |
| <center><math>A_1=\left[0\right]+\left( 1 \right)+\left( 1 \right)\left( 1 \right)+\left( 1 \right)\left( 1 \right)\left( 1 \right)+\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)+\ldots
| |
| </math></center>
| |
| | |
| i analogicznie przeanalizujmy sumę dla pieciocentówek
| |
| | |
| <center><math>A_5=\left[0\right]+\left( 5 \right)+\left( 5 \right)\left( 5 \right)+\left( 5 \right)\left( 5 \right)\left( 5 \right)+\left( 5 \right)\left( 5 \right)\left( 5 \right)\left( 5 \right)+\ldots
| |
| </math></center>
| |
| | |
| Wtedy zbiór par <math>A_1 \times A_5</math>
| |
| jest zbiorem wszystkich możliwości rozmiany kwoty mając do dyspozycji
| |
| dowolnie wiele jednocentówek oraz pięciocentówek.
| |
| | |
| <center><math>\aligned B= A_1 \times A_5
| |
| &=&\left( \left[0\right]+\left( 1 \right)+\left( 1 \right)\left( 1 \right)+\left( 1 \right)\left( 1 \right)\left( 1 \right)+\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)+\ldots \right)\\
| |
| &&\times\left( \left[0\right]+\left( 5 \right)+\left( 5 \right)\left( 5 \right)+\left( 5 \right)\left( 5 \right)\left( 5 \right)+\left( 5 \right)\left( 5 \right)\left( 5 \right)\left( 5 \right)+\ldots \right)\\
| |
| &=&\left[0\right]+\left( 1 \right)+\left( 5 \right)+\left( 1 \right)\left( 1 \right)+\left( 1 \right)\left( 5 \right)+\left( 5 \right)\left( 5 \right)+\left( 1 \right)\left( 1 \right)\left( 1 \right)+\ldots
| |
| \endaligned</math></center>
| |
| | |
| Sumy wszystkich możliwości rozmiany za pomocą dziesięciocentówek <math>\left( 10 \right)</math>,
| |
| ćwierćdolarówek <math>\left( 25 \right)</math>,
| |
| oraz półdolarówek <math>\left( 50 \right)</math> wyglądają następująco:
| |
| | |
| <center><math>\aligned A_{10} &=& \left[0\right]+\left( 10 \right)+\left( 10 \right)\left( 10 \right)+\left( 10 \right)\left( 10 \right)\left( 10 \right)+\left( 10 \right)\left( 10 \right)\left( 10 \right)\left( 10 \right)+\ldots\\
| |
| A_{25} &=& \left[0\right]+\left( 25 \right)+\left( 25 \right)\left( 25 \right)+\left( 25 \right)\left( 25 \right)\left( 25 \right)+\left( 25 \right)\left( 25 \right)\left( 25 \right)\left( 25 \right)+\ldots\\
| |
| A_{50} &=& \left[0\right]+\left( 50 \right)+\left( 50 \right)\left( 50 \right)+\left( 50 \right)\left( 50 \right)\left( 50 \right)+\left( 50 \right)\left( 50 \right)\left( 50 \right)\left( 50 \right)+\ldots.
| |
| \endaligned</math></center>
| |
| | |
| Dodając kolejno monety <math>\left( 10 \right)</math>, <math>\left( 25 \right)</math>,
| |
| i na końcu <math>\left( 50 \right)</math>
| |
| do możliwych rozmian uzyskujemy odpowiednio:
| |
| | |
| <center><math>\aligned C&=&B\times\left( \left[0\right]+\left( 10 \right)+\left( 10 \right)\left( 10 \right)+\left( 10 \right)\left( 10 \right)\left( 10 \right)+\left( 10 \right)\left( 10 \right)\left( 10 \right)\left( 10 \right)+\ldots \right)\\
| |
| D&=&C\times\left( \left[0\right]+\left( 25 \right)+\left( 25 \right)\left( 25 \right)+\left( 25 \right)\left( 25 \right)\left( 25 \right)+\left( 25 \right)\left( 25 \right)\left( 25 \right)\left( 25 \right)+\ldots \right)\\
| |
| E&=&D\times\left( \left[0\right]+\left( 50 \right)+\left( 50 \right)\left( 50 \right)+\left( 50 \right)\left( 50 \right)\left( 50 \right)+\left( 50 \right)\left( 50 \right)\left( 50 \right)\left( 50 \right)+\ldots \right)\\
| |
| &=&\left[0\right]+\left( 1 \right)+\left( 5 \right)+\left( 10 \right)+\left( 25 \right)+\left( 50 \right)+\left( 1 \right)\left( 1 \right)+\left( 1 \right)\left( 5 \right)+\left( 1 \right)\left( 10 \right)+\ldots
| |
| \endaligned</math></center>
| |
| | |
| Grupując teraz składniki sumy <math>E</math> w podsumy o tych samych wartościach
| |
| dostajemy wyrażenie:
| |
| | |
| <center><math>\begin{array} {rcl}
| |
| E&=&\big(\left( 1 \right)\big)+\big(\left( 1 \right)\left( 1 \right)\big)+\big(\left( 1 \right)\left( 1 \right)\left( 1 \right)\big)+\big(\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)\big)\\
| |
| &&+\big(\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)+\left( 5 \right)\big)\\
| |
| &&+\big(\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)\left( 1 \right)+\left( 5 \right)\left( 1 \right)\big)+\ldots
| |
| \end{array}
| |
| </math></center>
| |
| | |
| Zliczając zaś tylko składniki w podsumie odpowiadającej wartości <math>n</math> centów,
| |
| otrzymujemy liczbę sposobów, na które można rozmienić <math>n</math> centów przy użyciu monet
| |
| <math>\left( 1 \right)</math>, <math>\left( 5 \right)</math>, <math>\left( 10 \right)</math>, <math>\left( 25 \right)</math>, oraz <math>\left( 50 \right)</math>.
| |
| Pomysłem pochodzącym od Pólya, było zastąpienie
| |
| monety <math>\left( 1 \right)</math> przez zmienną <math>x</math>,
| |
| monety <math>\left( 5 \right)</math> przez <math>x\cdot x\cdot x\cdot x\cdot x=x^5</math>
| |
| i analogicznie <math>\left( 10 \right)</math> przez <math>x^{10}</math>,
| |
| <math>\left( 25 \right)</math> przez <math>x^{25}</math>,
| |
| oraz <math>\left( 50 \right)</math> przez <math>x^{50}</math>.
| |
| Uzyskujemy w ten sposób nieskończony szereg zmiennej <math>x</math>:
| |
| | |
| <center><math>\aligned E\!\left( x \right)&=&\left( 1+x+x^2+x^3\ldots \right)\cdot\left( 1+x^5+x^{10}+x^{15}\ldots \right)\cdot\left( 1+x^{10}+x^{20}+x^{30}\ldots \right)\\
| |
| &&\cdot\left( 1+x^{25}+x^{50}+x^{75}\ldots \right)\cdot\left( 1+x^{50}+x^{100}+x^{150}\ldots \right)\\
| |
| &=&1+x+x^2+x^3+x^4+2x^5+2x^6+2x^7+2x^8+2x^9+4x^{10}+\ldots
| |
| \endaligned</math></center>
| |
| | |
| Godne zauważenia jest, że liczba różnych możliwych sposobów rozmiany <math>n</math> centów
| |
| (równa liczbie grup monet w odpowiednim nawiasie we wzorze ([[##int wzor S|Uzupelnic int wzor S|]]))
| |
| jest równa współczynnikowi stojącemu przy jednomianie <math>x^n</math>.
| |
| }}
| |
| | |
| '''Funkcja tworząca''' <math> G\!\left( x \right)</math> dla ciągu liczb rzeczywistych
| |
| (lub zespolonych) <math>\left( g_0,g_1,g_2,g_3,\ldots \right)</math>
| |
| to szereg funkcyjny zmiennej rzeczywistej (lub zespolonej) <math>x</math> postaci
| |
| | |
| <center><math> G\!\left( x \right)=\sum_{n=0}^{\infty}{g_nx^n}=g_0+g_1x+g_2x^2+g_3x^3+g_4x^4+\ldots.
| |
| </math></center>
| |
| | |
| Na oznaczenie współczynnika <math>n</math>-tego wyrazu szeregu <math> G\!\left( x \right)</math>
| |
| używać będziemy oznaczenia <math>\left[x^n\right] G\!\left( x \right)=g_n</math>.
| |
| | |
| {{uwaga|[Uzupelnij]||
| |
| | |
| Na funkcje tworzące można spojrzeć dwoiście.
| |
| Pierwszym sposobem jest potraktowanie <math> G\!\left( x \right)</math> jako szeregu liczb rzeczywistych
| |
| (lub ogólniej zespolonych).
| |
| Oczywistym pytaniem jest tu kwestia zbieżności szeregu
| |
| <math> G\!\left( x \right)=\sum_{n=0}^{\infty}{g_nx^n}</math>.
| |
| Z wykładu Analiza Matematyczna wiemy,
| |
| że szereg <math> G\!\left( x \right)</math> jest zbieżny wtedy i tylko wtedy,
| |
| gdy istnieje stała <math>M\geq0</math> ograniczająca wszystkie skończone początkowe sumy, tzn.
| |
| | |
| <center><math>\left\vert g_0 \right\vert+\left\vert g_1x \right\vert+\left\vert g_2x^2 \right\vert+\ldots+\left\vert g_nx^n \right\vert\leq M
| |
| </math></center>
| |
| | |
| zachodzi dla dowolnego <math>n\geq0</math>.
| |
| Ponadto jeśli dla pewnej liczby <math>x_0\in\mathbb{R}</math>
| |
| szereg <math> G\!\left( x_0 \right)=g_0+g_1x_0+g_2x_0^2+\ldots</math> jest zbieżny,
| |
| to i także szereg <math> G\!\left( x_1 \right)=g_0+g_1x_1+g_2x_1^2+\ldots</math>
| |
| jest zbieżny dla dowolnego <math>x_1\in\mathbb{R}</math> spełniającego <math>\left\vert x_1 \right\vert\leq\left\vert x_0 \right\vert</math>.
| |
| Możemy więc określić ''promień zbieżności'' szeregu
| |
| jako taką liczbę <math>r\in\mathbb{R}_*\cup\left\lbrace \infty \right\rbrace=\left[0,+\infty\right]</math>, że
| |
| | |
| * jeśli <math>x<r</math>, to <math> G\!\left( x \right)</math> jest zbieżny;
| |
| | |
| * jeśli <math>x>r</math>, to <math> G\!\left( x \right)</math> jest rozbieżny.
| |
| | |
| Szereg <math> G\!\left( x \right)=g_0+g_1x+g_2x^2+\ldots</math> można więc potraktować jako funkcję
| |
| | |
| <center><math>G:\left( -r,r \right)\longrightarrow\mathbb{R},
| |
| </math></center>
| |
| | |
| o wartościach
| |
| <math> G\!\left( x \right)=\lim_{n\rightarrow\infty}{\left( g_0+g_1x+g_2x^2+\ldots+g_nx^n \right)}.
| |
| </math>
| |
| Oczywiście <math> G\!\left( 0 \right)=g_0</math>, więc dla <math>x=0</math> szereg <math> G\!\left( x \right)</math> jest zbieżny.
| |
| | |
| Drugim podejściem, bardziej użytecznym w praktycznych obliczeniach i przekształceniach
| |
| jest spojrzenie na szereg <math> G\!\left( x \right)=g_0+g_1x+g_2x^2+\ldots</math>
| |
| jako formę zapisu ciągu <math>\left( g_0,g_1,g_2,\ldots \right)</math>,
| |
| czyli jedynie jako ciąg symboli.
| |
| Równości pomiędzy odpowiednimi wzorami służą rozwiązaniu problemów kombinatorycznych,
| |
| tak więc traktujemy je jako równości dwu wyrażeń,
| |
| a nie jako równość dwu funkcji rzeczywistych,
| |
| pomimo że mają one uzasadnienia w języku analizy matematycznej.
| |
| | |
| Jak zobaczymy na wielu przykładach,
| |
| funkcje tworzące są bardzo użytecznym narzędziem
| |
| przy wyznaczaniu wartości elementów ciągu.
| |
| Jeśli bowiem <math> G\!\left( x \right)=g_0+g_1x+g_2x^2+\ldots</math>
| |
| jest funkcją tworzącą ciągu <math>\left( g_0,g_1,g_2,g_3,\ldots \right)</math>,
| |
| oraz w jakiś sposób będziemy w stanie poznać postać zwartą funkcji <math>G(x)</math>,
| |
| to rozwijając tę postać zwartą w szereg Taylora,
| |
| poznamy kolejne współczynniki tego rozwinięcia.
| |
| A współczynniki te, to właśnie kolejne wyrazy naszego ciągu.
| |
| | |
| Będziemy się zajmowali jedynie tymi funkcjami, dla których promień zbieżności <math>r>0</math>.
| |
| Ponadto będziemy pomijać problem zbieżności oraz wartość <math>r</math> promienia zbieżności,
| |
| skupiając się jedynie na przekształceniach wzorów.
| |
| Poniżej zebrane zostały te własności,
| |
| które często wykorzystywane są w takich przekształceniach.
| |
| }}
| |
| | |
| {{obserwacje|[Uzupelnij]||
| |
| | |
| Dla dwu funkcji tworzących <math> F\!\left( x \right)=f_0+f_1x+f_2x^2+\ldots</math>
| |
| oraz <math> G\!\left( x \right)=g_0+g_1x+g_2x^2+\ldots</math> mamy:
| |
| | |
| <center><math>\aligned F\!\left( x \right)= G\!\left( x \right)&\Leftrightarrow& f_0=g_0,\ f_1=g_1,\ f_2=g_2,\ \ldots\\
| |
| &&\\
| |
| \alpha\cdot F\!\left( x \right)+\beta\cdot G\!\left( x \right)&=& \sum_{n=0}^{\infty}{\left( \alpha\cdot f_n+\beta\cdot g_n \right)x^n}\\
| |
| &=&\left( \alpha\cdot f_0+\beta\cdot g_0 \right) + \left( \alpha\cdot f_1+\beta\cdot g_1 \right)x + \left( \alpha\cdot f_2+\beta\cdot g_2 \right)x^2 + \ldots\\
| |
| &&\\
| |
| F\!\left( x \right)\cdot G\!\left( x \right)&=&\sum_{n=0}^{\infty}\left( \sum_{k=0}^n f_k g_{n-k} \right) x^n\\
| |
| &=& f_0g_0 + \left( f_0g_1+f_1g_0 \right)x\\
| |
| && + \left( f_0g_2+f_1g_1+f_2g_0 \right)x^2\\
| |
| && + \left( f_0g_3+f_1g_2+f_2g_1+f_3g_0 \right)x^3+\ldots\\
| |
| \endaligned</math></center>
| |
| | |
| }}
| |
| | |
| Wyrażenie <math> F\!\left( x \right)\cdot G\!\left( x \right)</math> nazywać będziemy splotem szeregów <math> F\!\left( x \right)</math> oraz <math> G\!\left( x \right)</math>.
| |
| | |
| {{twierdzenie|[Uzupelnij]||
| |
| | |
| Funkcja tworząca postaci
| |
| | |
| <center><math> G\!\left( x \right)=g_0+g_1x+g_2x^2+g_3x^3+\ldots
| |
| </math></center>
| |
| | |
| ma odwrotną względem mnożenia (splotu),
| |
| tzn. istnieje funkcja tworząca <math> U\!\left( x \right)</math> taka,
| |
| że <math> U\!\left( x \right) G\!\left( x \right)=1</math>,
| |
| wtedy i tylko wtedy, gdy <math>g_0\neq0</math>.
| |
| }}
| |
| | |
| Następne własności są bardzo pomocne w dokonywanych przekształceniach
| |
| funkcji tworzących.
| |
| | |
| {{obserwacje|[Uzupelnij]||
| |
| | |
| Dla dwu funkcji tworzących <math> F\!\left( x \right)=f_0+f_1x+f_2x^2+\ldots</math>
| |
| oraz <math> G\!\left( x \right)=g_0+g_1x+g_2x^2+\ldots</math> mamy:
| |
| | |
| <center><math>\aligned x^m G\!\left( x \right)&=&0+\ldots+0x^{m-1}+g_0x^m+g_1x^{m+1}+g_2x^{m+2}+\ldots\\
| |
| \frac{ G\!\left( x \right)-\sum_{i=0}^{m-1}{g_ix^i}}{x^{m}}&=&g_m+g_{m+1}x+g_{m+2}x^{2}+g_{m+3}x^{3}+g_{m+4}x^{4}+\ldots\\
| |
| G\!\left( \alpha x \right)&=&g_0+g_1\alpha x+g_2\alpha^2x^2+g_3\alpha^3x^3+g_4\alpha^4x^4+\ldots\\
| |
| G'\!\left( x \right)&=&g_1+2g_2x+3g_3x^2+4g_4x^3+5g_5x^4+\ldots\\
| |
| \int G\!\left( x \right)dx &=& 0+g_0x+\frac{1}{2}g_1x^2+\frac{1}{3}g_2x^3+\frac{1}{4}g_3x^4+\ldots\\
| |
| \frac{ G\!\left( x \right)}{1-x}&=&g_0+\left( g_0+g_1 \right)x+\left( g_0+g_1+g_2 \right)x^2+\ldots
| |
| \endaligned</math></center>
| |
| | |
| }}
| |
| | |
| ===Funkcje tworzące w zliczaniu===
| |
| | |
| Widzieliśmy już, że dla <math>n\in \mathbb{N}</math>
| |
| | |
| <center><math>\left( 1+x \right)^m
| |
| ={m \choose 0}x^0 + {m \choose 1}x + {m \choose 2}x^2+\ldots+{m \choose m-1}x^{m-1}+{m \choose m}x^m
| |
| =\sum_{n=0}^\infty {m \choose n}x^n.
| |
| </math></center>
| |
| | |
| Przyjrzyjmy się teraz rozwinięciu w szereg funkcji <math>\left( 1+x \right)^y</math>,
| |
| gdzie <math>y\in\mathbb{R}</math> jest parametrem.
| |
| Rozwinięcie takie okaże się bardzo przydatne w rozwiązywaniu wielu przykładów.
| |
| Aby poznać ciąg odpowiadający tej funkcji wprowadźmy definicję.
| |
| | |
| '''Uogólniony symbol dwumianowy''' <math>{ y \choose n }</math>, gdzie <math>y\in\mathbb{R}</math> oraz <math>n\in\mathbb{N}</math> jest oznaczeniem na
| |
| | |
| <center><math>{ y \choose n }\ =\ \frac{y^{\underline{n}}}{n!}\ =\
| |
| \frac{y\cdot\left( y-1 \right)\cdot\ldots\cdot\left( y-\left( n-1 \right) \right)}{1\cdot2\cdot\ldots\cdot\left( n-1 \right)\cdot n}.
| |
| </math></center>
| |
| | |
| {{uwaga|[Uzupelnij]||
| |
| | |
| Oczywiście dla <math>y\in\mathbb{N}</math> spełniającego dodatkowo <math>y\geq n</math>,
| |
| uogólniony symbol dwumianowy <math>{ y \choose n }</math>
| |
| jest liczbą <math>n</math>-elementowych podzbiorów zbioru <math>y</math>-elementowego.
| |
| }}
| |
| | |
| {{twierdzenie|[Uzupelnij]||
| |
| | |
| Dla liczby rzeczywistej <math>y</math> oraz liczby naturalnej <math>n</math> zachodzi
| |
| | |
| <center><math>\left( 1+x \right)^y=\sum_{n=0}^{\infty}{ y \choose n }x^n.
| |
| </math></center>
| |
| | |
| }}
| |
| | |
| {{wniosek|[Uzupelnij]||
| |
| | |
| Dla liczby naturalnej <math>m</math> zachodzi
| |
| | |
| <center><math>\frac{1}{\left( 1-x \right)^{m+1}}=\sum_{n=0}^{\infty}{ m+n \choose n }x^n.
| |
| </math></center>
| |
| | |
| }}
| |
| | |
| {{dowod|[Uzupelnij]||
| |
| | |
| Dowód zostawiony jest jako ćwiczenie '''[ex][ex newton for integer]'''.
| |
| }}
| |
| | |
| {{przyklad|[Uzupelnij]||
| |
| | |
| Policzmy sumę
| |
| | |
| <center><math>\sum_{k=0}^nk^2=1+4+9+\ldots+n^2.
| |
| </math></center>
| |
| | |
| Zacznijmy od znalezienia zwartej postaci funkcji tworzącej
| |
| <math> G\!\left( x \right)=\sum_{n=0}^{\infty}n^2x^n</math>.
| |
| Korzystając z Wniosku [[##con newton for integer|Uzupelnic con newton for integer|]] otrzymujemy:
| |
| | |
| <center><math>\aligned \frac{1}{1-x}&=&\sum_{n=0}^{\infty}{n \choose n}x^n=\sum_{n=0}^{\infty}x^n,\\
| |
| \frac{1}{\left( 1-x \right)^2}&=&\sum_{n=0}^{\infty}{n+1 \choose n
| |
| }x^n\ =\ \sum_{n=0}^{\infty}nx^n+\sum_{n=0}^{\infty}x^n.
| |
| \endaligned</math></center>
| |
| | |
| Po przekształceniu równości ([[##eq 11|Uzupelnic eq 11|]]) uzyskuje się
| |
| | |
| <center><math>
| |
| \sum_{n=0}^{\infty}nx^n= \frac{1}{\left( 1-x \right)^2}
| |
| -\frac{1}{1-x}.
| |
| </math></center>
| |
| | |
| Powołując się ponownie na Wniosek [[##con newton for integer|Uzupelnic con newton for integer|]] otrzymujemy
| |
| | |
| <center><math>\frac{1}{\left( 1-x \right)^3}
| |
| =\sum_{n=0}^{\infty}{ n+2 \choose n}x^n
| |
| =\frac{1}{2}\sum_{n=0}^{\infty}n^2x^n+\frac{3}{2}\sum_{n=0}^{\infty}nx^n+\sum_{n=0}^{\infty}x^n,
| |
| </math></center>
| |
| | |
| co w połączeniu z równościami ([[##eq 11|Uzupelnic eq 11|]]) oraz ([[##eq 122|Uzupelnic eq 122|]])
| |
| daje zwartą postać funkcji tworzącej <math> G\!\left( x \right)</math> dla ciągu <math>1,4,9,\ldots,n^2,\ldots</math>:
| |
| | |
| <center><math> G\!\left( x \right)=\sum_{n=0}^{\infty}n^2x^n
| |
| =\frac{2}{\left( 1-x \right)^3}-\frac{3}{\left( 1-x \right)^2}+\frac{1}{1-x}.
| |
| </math></center>
| |
| | |
| Naszym zadaniem było jednakże policzenie funkcji tworzącej <math>H(x)</math> dla ciągu
| |
| <math>1,1+4,1+4+9,\ldots,1+4+9+\ldots+n^2,\ldots</math>,
| |
| tzn. ciągu sum początkowych wyrazów ciągu <math>1,4,9,\ldots,n^2,\ldots</math>.
| |
| Aby uzyskać <math> H\!\left( x \right)</math> wystarczy więc skorzystać ze wzoru ([[##eq 1 przez 1-x|Uzupelnic eq 1 przez 1-x|]])
| |
| i podzielić <math> G\!\left( x \right)</math> przez <math>1-x</math>. | |
| Tak więc poszukiwanym rozwiązaniem są współczynniki funkcji tworzącej
| |
| | |
| <center><math> H\!\left( x \right)=\frac{ G\!\left( x \right)}{1-x}
| |
| =\frac{2}{\left( 1-x \right)^4}-\frac{3}{\left( 1-x \right)^3}+\frac{1}{\left( 1-x \right)^2}.
| |
| </math></center>
| |
| | |
| Korzystając po raz kolejny z Wniosku [[##con newton for integer|Uzupelnic con newton for integer|]] otrzymujemy
| |
| | |
| <center><math>\aligned H\!\left( x \right)
| |
| &=&2\sum_{n=0}^{\infty}{n+3 \choose n}x^n-3\sum_{n=0}^{\infty}{n+2 \choose n}x^n+\sum_{n=0}^{\infty}{n+1 \choose n}x^n\\
| |
| &=&\sum_{n=0}^{\infty}\left( \frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n \right)x^n.
| |
| \endaligned</math></center>
| |
| | |
| W konsekwencji zachodzi równość
| |
| | |
| <center><math>\sum_{k=1}^nk^2=\left[x^n\right] H\!\left( x \right)=\frac{2n^3+3n+n}{6}.
| |
| </math></center>
| |
| | |
| }}
| |
| | |
| {{przyklad|[Uzupelnij]||
| |
| | |
| Wracamy do przykładu z monetami.
| |
| Występowały tam funkcje tworzące postaci
| |
| | |
| <center><math> A_k\!\left( x \right) = 1+x^k+x^{2k}+x^{3k}+\ldots,
| |
| </math></center>
| |
| | |
| dla <math>k=1,5,10,25</math> i <math>50</math>.
| |
| Z równości ([[##eq 1 przez 1-x|Uzupelnic eq 1 przez 1-x|]]) wiemy, że
| |
| | |
| <center><math>1+x^k+x^{2k}+x^{3k}+\ldots, =\frac{1}{1-x^k}
| |
| </math></center>
| |
| | |
| tak więc:
| |
| | |
| <center><math>\aligned A\!\left( x \right)= A_1\!\left( x \right)&=& \frac{1}{1-x},\\
| |
| B\!\left( x \right)= A\!\left( x \right)\cdot A_5\!\left( x \right) &=&\frac{ A\!\left( x \right)}{1-x^5},\\
| |
| C\!\left( x \right)= B\!\left( x \right)\cdot A_{10}\!\left( x \right) &=&\frac{ B\!\left( x \right)}{1-x^{10}},\\
| |
| D\!\left( x \right)= C\!\left( x \right)\cdot A_{25}\!\left( x \right) &=&\frac{ C\!\left( x \right)}{1-x^{25}},\\
| |
| E\!\left( x \right)= D\!\left( x \right)\cdot A_{50}\!\left( x \right) &=&\frac{ D\!\left( x \right)}{1-x^{50}},
| |
| \endaligned</math></center>
| |
| | |
| skąd natychmiast:
| |
| | |
| <center><math>\aligned A\!\left( x \right)&=&1+x A\!\left( x \right),\\
| |
| B\!\left( x \right)&=& A\!\left( x \right)+x^5 B\!\left( x \right),\\
| |
| C\!\left( x \right)&=& B\!\left( x \right)+x^{10} C\!\left( x \right),\\
| |
| C\!\left( x \right)&=& D\!\left( x \right)+x^{25} C\!\left( x \right),\\
| |
| D\!\left( x \right)&=& E\!\left( x \right)+x^{50} D\!\left( x \right).
| |
| \endaligned</math></center>
| |
| | |
| Równości te dają zależności między współczynnikami:
| |
| | |
| <center><math>a_n=1,\quad b_n=a_n+b_{n-5},\quad c_n=b_n+c_{n-10},\quad
| |
| d_n=c_n+d_{n-25},\quad e_n=d_n+e_{n-50}.
| |
| </math></center>
| |
| | |
| Wykorzystując te zależności rekurencyjne możemy wypełnić następującą tabelę:
| |
| | |
| {-2cm}
| |
| | |
| {| border=1
| |
| |+ <span style="font-variant:small-caps">Uzupelnij tytul</span>
| |
| |-
| |
| | <math>n</math> || 0 || 5 || 10 || 15 || 2 || 25 || 30 || 35 || 40 || 45 || 50 || 55 || 60 || 65 || 70 || 75 || 80 || 85 || 90 || 95 || 100
| |
| |-
| |
| | <math>a_n</math> || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1
| |
| |-
| |
| | <math>b_n</math> || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17 || 18 || 19 || 20 || 21
| |
| |-
| |
| | <math>c_n</math> || 1 || 2 || 4 || 6 || 9 || 12 || 16 || 10 || 25 || 30 || 36 || 42 || 49 || 56 || 64 || 72 || 81 || || 100 || || 121
| |
| |-
| |
| | <math>d_n</math> || 1 || || || || || 13 || || || || || 49 || || || || || 121 || || || || || 242
| |
| |-
| |
| | <math>e_n</math> || 1 || || || || || || || || || || 50 || || || || || || || || || || 292
| |
| |}
| |
| | |
| Pół dolara można rozmienić na <math>50</math> sposobów.
| |
| Z kolei rozmieniać jednego dolara można na aż <math>292</math> sposoby.
| |
| Do problemu tego wrócimy jeszcze w następnym wykładzie.
| |
| }}
| |
| | |
| ===Funkcje tworzące w rozwiązywaniu zależności rekurencyjnych.===
| |
| | |
| {{przyklad|[Uzupelnij]||
| |
| | |
| Rozważmy ciąg Fibonacci'ego, tzn. ciąg <math>\left( f_0,f_1,f_2,f_3,\ldots \right)</math>
| |
| zdefiniowany w następujący sposób:
| |
| | |
| <center><math>\aligned f_0&=&0,\\
| |
| f_1&=&1,\\
| |
| f_n&=&f_{n-1}+f_{n-2}\quad\textrm{dla}\ n\geq2.
| |
| \endaligned</math></center>
| |
| | |
| Znamy już postać zwartą jego wyrazów.
| |
| Tym razem zobaczymy jak można ją otrzymać używając funkcji tworzących.
| |
| Zależności rekurencyjne dla <math>f_n</math> przekładają się natychmiast na
| |
| następujące równanie, jakie musi spełniać funkcja tworząca <math> F\!\left( x \right)</math>
| |
| dla ciągu Fibonacci'ego
| |
| | |
| <center><math> F\!\left( x \right)
| |
| =\sum_{n=0}^{\infty}f_nx^n
| |
| =x+\sum_{n=2}^{\infty}\left( f_{n-1}+f_{n-2} \right)x^n=1+x+x F\!\left( x \right)+x^2 F\!\left( x \right).
| |
| </math></center>
| |
| | |
| Przekształcając powyższe równanie otrzymujemy:
| |
| | |
| <center><math>
| |
| F\!\left( x \right)=\frac{x}{1-x-x^2}.
| |
| </math></center>
| |
| | |
| Celem, który chcemy osiągnąć to wykorzystanie funkcji <math>\frac{x}{1-x-x^2}</math>
| |
| do przedstawienia współczynników <math>f_n</math> w postaci zwartej.
| |
| Pierwszym krokiem będzie rozłożenie ułamka w równaniu ([[##eq fib|Uzupelnic eq fib|]])
| |
| na sumę ułamków o mianownikach będących funkcjami liniowymi
| |
| | |
| <center><math> F\!\left( x \right)=\frac{x}{1-x-x^2}
| |
| =\frac{x}{\left( 1-\varphi x \right)\left( 1-\overline{\varphi} x \right)}
| |
| =\frac{1}{\sqrt{5}}\left( \frac{1}{\left( 1-\varphi x \right)}-\frac{1}{\left( 1-\overline{\varphi} x \right)} \right),
| |
| </math></center>
| |
| | |
| gdzie <math>\varphi=\frac{1+\sqrt{5}}{2}</math> jest złotą liczbą
| |
| oraz <math>\overline{\varphi}=\frac{1-\sqrt{5}}{2}</math> liczbą do niej sprzężoną.
| |
| Korzystając z równania ([[##eq 1 przez 1-x|Uzupelnic eq 1 przez 1-x|]]) otrzymujemy teraz
| |
| | |
| <center><math> F\!\left( x \right)
| |
| =\frac{1}{\sqrt{5}}\left( \sum_{n=1}^{\infty}{\varphi^nx^n}-\sum_{n=1}^{\infty}{\overline{\varphi}^nx^n} \right)
| |
| =\frac{1}{\sqrt{5}}\sum_{n=1}^{\infty}{\left( \varphi^n-\overline{\varphi}^n \right)x^n}.
| |
| </math></center>
| |
| | |
| Tak więc dostajemy szybko znaną nam już postać zwartą
| |
| <math>f_n=\frac{1}{\sqrt{5}}\left( \varphi^n-\overline{\varphi}^n \right)</math>.
| |
| }}
| |
| | |
| Podczas rozwiązywania przykładu związanego z liczbami Fibonacci'ego
| |
| natrafiliśmy na problem polegający na przedstawieniu w postaci szeregu wyrażenia
| |
| <math>\frac{x}{1-x-x^2}</math>.
| |
| Przyjrzymy się dokładniej tego typu wyrażeniom.
| |
| | |
| '''Stopień wielomianu''' <math>{\sf deg}\ P\!\left( x \right)=n</math>,
| |
| jeśli <math> P\!\left( x \right)=p_0+p_1x+\ldots+p_nx^n</math>.
| |
| | |
| '''Funkcja wymierna''' <math> R\!\left( x \right)</math> to funkcja postaci <math>\frac{ P\!\left( x \right)}{ Q\!\left( x \right)}</math>, gdzie <math> P\!\left( x \right)</math> oraz <math> Q\!\left( x \right)\neq0</math> są wielomianami skończonego stopnia.
| |
| | |
| {{obserwacje|[Uzupelnij]||
| |
| | |
| Niech <math> A\!\left( x \right)</math> oraz <math> B\!\left( x \right)</math> będą wielomianami
| |
| <math>{\sf deg}\ A\!\left( x \right)\geq {\sf deg}\ B\!\left( x \right)</math>.
| |
| Wtedy istnieją wielomiany <math> Q\!\left( x \right)</math> oraz <math> R\!\left( x \right)</math> takie, że
| |
| | |
| <center><math> A\!\left( x \right)= Q\!\left( x \right) B\!\left( x \right)+ R\!\left( x \right),
| |
| </math></center>
| |
| | |
| gdzie <math>{\sf deg}\ R\!\left( x \right)<{\sf deg}\ A\!\left( x \right)={\sf deg}\ Q\!\left( x \right)+{\sf deg}\ B\!\left( x \right)</math>.
| |
| }}
| |
| | |
| {{przyklad|[Uzupelnij]||
| |
| | |
| Niech
| |
| | |
| <center><math> A\!\left( x \right)=3x^5+5x^4+2x^3+x^2+2\quad\textrm{oraz}\quad B\!\left( x \right)=x^3+2x^2-1.
| |
| </math></center>
| |
| | |
| Wtedy wielomiany
| |
| | |
| <center><math> Q\!\left( x \right)=3x^2-x+3\quad\textrm{oraz}\quad R\!\left( x \right)=x+2
| |
| </math></center>
| |
| | |
| spełniają
| |
| | |
| <center><math>\aligned A\!\left( x \right)&=&3x^5+5x^4+2x^3+x^2+2\\
| |
| &=&\left( 3x^2-x+3 \right)\cdot\left( x^3+2x^2-1 \right)+x+2\\
| |
| &=& Q\!\left( x \right) B\!\left( x \right)+ R\!\left( x \right).
| |
| \endaligned</math></center>
| |
| | |
| Ponadto <math>{\sf deg}\ A\!\left( x \right)=5=2+3={\sf deg}\ Q\!\left( x \right)+{\sf deg}\ B\!\left( x \right)</math>.
| |
| }}
| |
| | |
| {{wniosek|[Uzupelnij]||
| |
| | |
| Niech <math> P\!\left( x \right)</math> oraz <math> Q\!\left( x \right)</math> będą wielomianami takimi,
| |
| że <math>{\sf deg}\ P\!\left( x \right)\geq{\sf deg}\ Q\!\left( x \right)</math>.
| |
| Wtedy funkcję wymierną
| |
| <math> R\!\left( x \right)= P\!\left( x \right)/ Q\!\left( x \right),
| |
| </math>
| |
| można przedstawić w postaci
| |
| | |
| <center><math> R\!\left( x \right)=\frac{ P\!\left( x \right)}{ Q\!\left( x \right)}= A\!\left( x \right)+\frac{ B\!\left( x \right)}{ Q\!\left( x \right)},
| |
| </math></center>
| |
| | |
| dla pewnych wielomianów <math> A\!\left( x \right)</math> oraz <math> B\!\left( x \right)</math>
| |
| spełniających <math>{\sf deg}\ B\!\left( x \right)<{\sf deg}\ Q\!\left( x \right)</math>.
| |
| }}
| |
| | |
| Będziemy więc skupiali się jedynie nad takimi funkcjami wymiernymi <math> R\!\left( x \right)= P\!\left( x \right)/ Q\!\left( x \right),
| |
| </math> dla których <math>{\sf deg}\ P\!\left( x \right)<{\sf deg}\ Q\!\left( x \right)</math>.
| |
| | |
| {{twierdzenie|[Uzupelnij]||
| |
| | |
| Niech <math> P\!\left( x \right)</math> oraz <math> Q\!\left( x \right)</math> będą wielomianami takimi, że
| |
| | |
| * <math>{\sf deg}\ P\!\left( x \right)<{\sf deg}\ Q\!\left( x \right)</math>,
| |
| | |
| * <math> Q\!\left( x \right)= S\!\left( x \right) T\!\left( x \right)</math>,
| |
| gdzie oba wielomiany <math> S\!\left( x \right), T\!\left( x \right)</math> są stopnia co najmniej <math>2</math>,
| |
| | |
| * <math>q_0\neq0</math>.
| |
| | |
| Wtedy istnieją wielomiany
| |
| <math> A\!\left( x \right)</math> oraz <math> B\!\left( x \right)</math> takie, że
| |
| <math>{\sf deg}\ A\!\left( x \right)<{\sf deg}\ S\!\left( x \right)</math> i
| |
| <math>{\sf deg}\ B\!\left( x \right)<{\sf deg}\ T\!\left( x \right)</math>
| |
| oraz
| |
| | |
| <center><math>\frac{ P\!\left( x \right)}{ Q\!\left( x \right)}
| |
| =\frac{ A\!\left( x \right)}{ S\!\left( x \right)}+\frac{ B\!\left( x \right)}{ T\!\left( x \right)}.
| |
| </math></center> | |
| | |
| }}
| |
| | |
| {{uwaga|[Uzupelnij]||
| |
| | |
| Twierdzenie [[##thm PQ <nowiki>=</nowiki> AS BT|Uzupelnic thm PQ <nowiki>=</nowiki> AS BT|]] pozwala na rozbijanie skomplikowanych funkcji wymiernych na sumę prostszych.
| |
| }}
| |
| | |
| {{dowod|[Uzupelnij]||
| |
| [Metoda rozwijania funkcji wymiernej w szereg.]
| |
| Rozważmy funkcję wymierną w postaci
| |
| | |
| <center><math> R\!\left( x \right)=\frac{ P\!\left( x \right)}{ Q\!\left( x \right)},
| |
| </math></center>
| |
| | |
| gdzie <math>{\sf deg}\ P\!\left( x \right)<{\sf deg}\ Q\!\left( x \right)</math>, oraz <math>q_0\neq0</math>.
| |
| Załóżmy ponadto, że wielomian <math> Q\!\left( x \right)</math> rozkłada się na
| |
| następujący iloczyn czynników liniowych
| |
| | |
| <center><math> Q\!\left( x \right)
| |
| =q_0\left( 1-\rho_1x \right)^{m_1}\cdot\left( 1-\rho_2x \right)^{m_2}\cdot\ldots\cdot\left( 1-\rho_kx \right)^{m_k}.
| |
| </math></center>
| |
| | |
| Warto wspomnieć, że dalecy nie każdy wielomian ma taki rozkład.
| |
| Na przykład <math>1+x^2</math> jest nierozkładalny i nieliniowy.
| |
| Wykorzystując parokrotnie Twierdzenie [[##thm PQ <nowiki>=</nowiki> AS BT|Uzupelnic thm PQ <nowiki>=</nowiki> AS BT|]]
| |
| otrzymujemy wielomiany <math> P_1\!\left( x \right),\ldots, P_k\!\left( x \right)</math> takie, że
| |
| | |
| <center><math> R\!\left( x \right)
| |
| =\frac{ P\!\left( x \right)}{ Q\!\left( x \right)}=\frac{ P_1\!\left( x \right)}{\left( 1-\rho_1x \right)^{m_1}}+\frac{ P_2\!\left( x \right)}{\left( 1-\rho_2x \right)^{m_2}}+\ldots+\frac{ P_k\!\left( x \right)}{\left( 1-\rho_kx \right)^{m_k}},
| |
| </math></center>
| |
| | |
| gdzie <math>{\sf deg}\ P_i\!\left( x \right)<m_i</math>.
| |
| Na mocy Obserwacji [[##obs div|Uzupelnic obs div|]] możemy sprowadzić wielomian <math> P_i\!\left( x \right)</math> do
| |
| | |
| <center><math>\aligned P_i\!\left( x \right)&=& P_i^1\!\left( x \right)\left( 1-\rho_ix \right)+\gamma_{m_i}\\
| |
| &=& P_i^2\!\left( x \right)\left( 1-\rho_ix \right)^2+\gamma_{m_i-1}\left( 1-\rho_ix \right)+\gamma_{m_i}\\
| |
| &\vdots&\\
| |
| &=&\gamma_1\left( 1-\rho_ix \right)^{m_i-1}+\ldots+\gamma_{m_i-1}\left( 1-\rho_ix \right)+\gamma_{m_i},
| |
| \endaligned</math></center>
| |
| | |
| gdzie <math>m_i\geq{\sf deg}\ P_i\!\left( x \right)>{\sf deg}\ P_i^1\!\left( x \right)>{\sf deg}\ P_i^2\!\left( x \right)>\ldots</math>.
| |
| W konsekwencji otrzymamy
| |
| | |
| <center><math> R\!\left( x \right)\ =\ \sum_{i=1}^k{\left( \frac{\gamma_{i,1}}{1-\rho_ix}+\frac{\gamma_{i,2}}{\left( 1-\rho_ix \right)^2}+\ldots+\frac{\gamma_{i,m_i}}{\left( 1-\rho_ix \right)^{m_i}} \right)}.
| |
| </math></center>
| |
| | |
| Mnożąc teraz obie strony przez
| |
| | |
| <center><math> Q\!\left( x \right)/q_0=\left( 1-\rho_1x \right)^{m_1}\cdot\left( 1-\rho_2x \right)^{m_2}\cdot\ldots\cdot\left( 1-\rho_kx \right)^{m_k}
| |
| </math></center>
| |
| | |
| i porównując współczynniki przy odpowiadających potęgach <math>x^i</math>
| |
| uzyskujemy pewien układ równań, rozwiązanie którego da nam
| |
| poszukiwane współczynniki <math>\gamma_{i,j}</math>.
| |
| Z drugiej strony, z wniosku [[##con newton for integer|Uzupelnic con newton for integer|]] wynika, że
| |
| | |
| <center><math>\frac{1}{\left( 1-\rho x \right)^{m+1}}
| |
| =\sum_{n=1}^{\infty}{ { m+n \choose m } \rho^n x^n}
| |
| </math></center>
| |
| | |
| i w konsekwencji:
| |
| | |
| <center><math>
| |
| [x^n] R\!\left( x \right)\ =\ \sum_{i=1}^k{\left( \gamma_{i,1}+
| |
| \gamma_{i,2}{n+1\choose 1}+
| |
| \ldots+
| |
| \gamma_{i,m_i}{n+m_i-1\choose m_i}
| |
| \right)}\rho_i^n.
| |
| </math></center>
| |
| | |
| }}
| |
| | |
| {{przyklad|[Uzupelnij]||
| |
| | |
| Opisaną wyżej metodę ogólną zilustrujemy na przykładzie funkcji
| |
| | |
| <center><math> R\!\left( x \right)=\frac{x^2}{1-x-x^2+x^3}.
| |
| </math></center>
| |
| | |
| Wielomian <math>1-x-x^2+x^3</math>
| |
| ma jeden podwójny pierwiastek <math>x=1</math>
| |
| oraz jeden pojedynczy <math>x=-1</math>.
| |
| Poznana metoda rozwijania funkcji wymiernej w szereg daje więc
| |
| | |
| <center><math> R\!\left( x \right)
| |
| =\frac{x^2}{\left( 1-x \right)^2\cdot\left( 1+x \right)}=\frac{\alpha}{1-x}+\frac{\beta}{\left( 1-x \right)^2}+\frac{\gamma}{1+x}.
| |
| </math></center>
| |
| | |
| Mnożąc obie strony przez <math>\left( 1-x \right)^2\cdot\left( 1+x \right)</math> otrzymujemy:
| |
| | |
| <center><math>x^2=\alpha\left( 1-x^2 \right)+\beta\left( 1+x \right)+\gamma\left( 1-2x+x^2 \right).
| |
| </math></center>
| |
| | |
| Dwa wielomiany są równe,
| |
| gdy współczynniki przy odpowiadających potęgach są sobie równe.
| |
| Wartości <math>\alpha, \beta, \gamma</math> można więc wyliczyć z układu równań
| |
| | |
| <center><math>\left\lbrace\begin{array} {rrrcl}
| |
| \alpha & +\ \beta & +\ \gamma & = & 0\\
| |
| \alpha & & -\ 2\gamma & = & 0\\
| |
| & -\ \beta & +\ \gamma & = & 1.
| |
| \end{array} \right.
| |
| </math></center>
| |
| | |
| Rozwiązaniem powyższego układu są wartości
| |
| <math>\alpha=-\frac{1}{4},\
| |
| \beta=\frac{1}{2},\
| |
| \gamma=-\frac{1}{4}.
| |
| </math>
| |
| W konsekwencji otrzymujemy szereg
| |
| | |
| <center><math>\aligned R\!\left( x \right)&=&\sum_{n=0}^{\infty}\left( -\frac{1}{4}+\frac{1}{2}\left( n+1 \right) - \frac{1}{4}\left( -1 \right)^n \right)x^n\\
| |
| &=&x^2+x^3+2x^4+2x^5+3x^6+3x^7+4x^8+\ldots.
| |
| \endaligned</math></center>
| |
| | |
| }}
| |
| | |
| Jeżeli mianownik <math> Q\!\left( x \right)</math>
| |
| funkcji wymiernej <math> R\!\left( x \right)=\frac{ P\!\left( x \right)}{ Q\!\left( x \right)}</math>
| |
| posiada jedynie pierwiastki jednokrotne,
| |
| to następne twierdzenie znacznie przyspiesza rozkład <math> R\!\left( x \right)</math> na sumę.
| |
| | |
| {{twierdzenie|[Uzupelnij]||
| |
| | |
| Jeśli <math> R\!\left( x \right)= P\!\left( x \right)/ Q\!\left( x \right)</math>,
| |
| gdzie <math> Q\!\left( x \right)=q_0\cdot\left( 1-\rho_1x \right)\cdot\ldots\cdot\left( 1-\rho_1x \right)</math>
| |
| i liczby <math>\rho_1,\ldots,\rho_l</math> są parami różne,
| |
| to w przypadku gdy <math> P\!\left( x \right)</math> jest wielomianem stopnia mniejszego niż <math>l</math>, zachodzi
| |
| | |
| <center><math>\left[x^n\right] R\!\left( x \right)
| |
| =a_1\rho_1^n+\ldots+a_l\rho_l^n,
| |
| \quad\textrm{dla}\ a_k=\frac{-\rho_k\cdot P\!\left( 1/\rho_k \right)}{ Q'\!\left( 1/\rho_k \right)}.
| |
| </math></center>
| |
| | |
| }}
| |
| | |
| {{przyklad|[Uzupelnij]||
| |
| | |
| Mianownik <math> Q\!\left( x \right)</math> funkcji wymiernej
| |
| | |
| <center><math> R\!\left( x \right)=\frac{ P\!\left( x \right)}{ Q\!\left( x \right)}=\frac{2x}{1-5x-2x^2+24x^3}.
| |
| </math></center>
| |
| | |
| ma trzy różne pierwiastki i można <math> R\!\left( x \right)</math> przedstawić jako
| |
| | |
| <center><math> R\!\left( x \right)=\frac{2x}{\left( 1+2x \right)\left( 1-3x \right)\left( 1-4x \right)}.
| |
| </math></center>
| |
| | |
| Na mocy twierdzenia [[##thm wymierne|Uzupelnic thm wymierne|]] otrzymujemy więc, że
| |
| | |
| <center><math>\left[x^n\right] R\!\left( x \right)=-\frac{2}{15}\left( -2 \right)^n-\frac{6}{5}3^n+\frac{4}{3}4^n.
| |
| </math></center>
| |
| | |
| }}
| |
| | |
| Jak widzieliśmy na przykładzie ciągu Fibonacci'ego,
| |
| funkcje tworzące mogą być bardzo pomocne przy szukaniu postaci zwartej
| |
| pewnych ciągów zadanych rekurencyjnie.
| |
| | |
| '''Jednorodne, liniowe równanie rekurencyjne''' to równanie postaci
| |
| | |
| <center><math>\left\lbrace
| |
| \begin{array} {rcl}
| |
| r_0&=&c_0,\\
| |
| &\cdots&\\
| |
| r_{k-1}&=&c_{k-1},\\
| |
| r_n&=&a_1r_{n-1}+a_2r_{n-2}+\ldots+a_kr_{n-k}\quad\textrm{dla}\ n\geq k,
| |
| \end{array}
| |
| \right.
| |
| </math></center>
| |
| | |
| gdzie <math>c_0,\ldots,c_{k-1},a_1,\ldots,a_k</math> są liczbami rzeczywistymi
| |
| (niezależnymi od parametru rekurencyjnego <math>n</math>).
| |
| | |
| Rozważmy najpierw przypadek, gdy <math>k=2</math>, tzn. równanie postaci
| |
| | |
| <center><math>
| |
| \left\lbrace
| |
| \begin{array} {rcl}
| |
| r_0&=&c_0,\\
| |
| r_1&=&c_1,\\
| |
| r_n&=&a_1r_{n-1}+a_2r_{n-2}\quad\textrm{dla}\ n\geq 2.
| |
| \end{array}
| |
| \right.
| |
| </math></center>
| |
| | |
| Przykładem takiego równania była zależność opisująca ciąg Fibonacci'ego.
| |
| Zastosowanie ostatniej równości z ([[##eq rec 2|Uzupelnic eq rec 2|]])
| |
| do funkcji tworzącej ciągu <math>\left( r_0,r_1,r_2,\ldots \right)</math> daje:
| |
| | |
| <center><math>\aligned R\!\left( x \right)&=&r_0+r_1x+r_2x^2+r_3x^3+\ldots+r_nx^n+\ldots\\
| |
| &=&c_0+c_1x+\left( a_1r_1+a_2r_0 \right)x^2+\ldots+\left( a_1r_{n-1}+a_2r_{n-2} \right)x^n+\ldots\\
| |
| &=&c_0+\left( c_1-a_1c_0 \right)x+a_1x R\!\left( x \right)+a_2x^2 R\!\left( x \right),
| |
| \endaligned</math></center>
| |
| | |
| tak więc
| |
| | |
| <center><math> R\!\left( x \right)\ =\ \frac{c_0+\left( c_1-a_1c_0 \right)x}{1-a_1x-a_2x^2}
| |
| </math></center>
| |
| | |
| Dla funkcji <math> A\!\left( x \right)=1-a_1x-a_2x^2=\left( 1-\rho_1x \right)\left( 1-\rho_2x \right)</math>
| |
| mogą zajść trzy przypadki:
| |
| | |
| * <math>\rho_1 \neq \rho_2</math> są różnymi liczbami rzeczywistymi. Wtedy
| |
| | |
| <center><math>r_n\ =\ \alpha\rho_1^n+\beta\rho_2^n,
| |
| </math></center>
| |
| | |
| gdzie <math>\alpha</math> oraz <math>\beta</math> są liczbami rzeczywistymi.
| |
| | |
| * <math>\rho_1 = \rho_2</math>. Wtedy
| |
| | |
| <center><math>r_n\ =\ \left( \alpha n+\beta \right)\rho_1^n,
| |
| </math></center>
| |
| | |
| gdzie <math>\alpha</math> oraz <math>\beta</math> są liczbami rzeczywistymi.
| |
| | |
| * <math>\bigtriangledown</math>
| |
| Wartości <math>\rho_1</math> oraz <math>\rho_2</math> są różnymi liczbami zespolonymi.
| |
| W tym wypadku całe rozumowanie przeprowadzone wcześniej dla liczb rzeczywistych
| |
| pozostaje w mocy, tyle że dokonywane jest teraz na liczbach zespolonych.
| |
| Dostajemy więc
| |
| | |
| <center><math>r_n\ =\ \alpha\rho_1^n+\beta\rho_2^n.
| |
| </math></center>
| |
| | |
| gdzie <math>\alpha</math> oraz <math>\beta</math> są pewnymi liczbami zespolonymi.
| |
| Przypadek pierwszy jest więc szczególną sytuacją obecnego przypadku.
| |
| Może być jednak rozważany bez znajomości liczb zespolonych.
| |
| {<math>\bigtriangleup</math>}
| |
| | |
| Wracamy teraz do ogólnego, jednorodnego liniowego równania rekurencyjnego.
| |
| Analogicznie do przypadku, gdy <math>k=2</math>, otrzymujemy że
| |
| | |
| <center><math> R\!\left( x \right)\ =\ \frac{ P\!\left( x \right)}{1-a_1x-a_2x^2-\ldots-a_kx^k},
| |
| </math></center>
| |
| | |
| gdzie <math> P\!\left( x \right)</math> jest wielomianem co najwyżej stopnia <math>k-1</math>,
| |
| zależnym od wartości <math>c_0,\ldots,c_{k-1},a_1,\ldots,a_k</math>.
| |
| Korzystając z ogólnej metody rozwijania funkcji wymiernej w szereg,
| |
| możemy odzyskać wyrazy ciągu <math>r_n</math>,
| |
| jako współczynniki <math>[x^n] R\!\left( x \right)</math> zgodnie z równaniem ([[##eq R(x)|Uzupelnic eq R(x)|]]).
| |
| | |
| {{przyklad|[Uzupelnij]||
| |
| | |
| Równanie rekurencyjne ma następującą postać
| |
| | |
| <center><math>\left\lbrace
| |
| \begin{array} {rcl}
| |
| r_0&=&0,\\
| |
| r_1&=&0,\\
| |
| r_2&=&1,\\
| |
| r_n&=&r_{n-1}+r_{n-2}-r_{n-3}\quad\textrm{dla}\ n\geq 3.
| |
| \end{array}
| |
| \right.
| |
| </math></center>
| |
| | |
| Ostatnia zależność prowadzi do funkcji tworzącej <math> R\!\left( x \right)</math> spełniającej
| |
| | |
| <center><math> R\!\left( x \right)=x^2 + x R\!\left( x \right) + x^2 R\!\left( x \right) - x^3 R\!\left( x \right).
| |
| </math></center>
| |
| | |
| Po dokonaniu prostego wyliczenia dostajemy:
| |
| | |
| <center><math> R\!\left( x \right)=\frac{x^2}{1-x-x^2+x^3}.
| |
| </math></center>
| |
| | |
| W przykładzie omawianym przy okazji metody rozwijania funkcji wymiernej w szereg,
| |
| wyliczyliśmy współczynniki <math>[x^n] R\!\left( x \right)</math>, a zatem mamy:
| |
| | |
| <center><math>r_n=-\frac{1}{4}+\frac{1}{2}\left( n+1 \right) - \frac{1}{4}\left( -1 \right)^n\quad\textrm{dla dowolnego}\ n=0,1,2,3,\ldots.
| |
| </math></center>
| |
| | |
| }}
| |
