Matematyka dyskretna 1/Wykład 7: Funkcje tworzące: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
 
(Nie pokazano 14 wersji utworzonych przez 2 użytkowników)
Linia 6: Linia 6:
  
  
<center><math>A_1=[0]+\moneta(1)+\moneta(1)\moneta(1)+\moneta(1)\moneta(1)\moneta(1)+\moneta(1)\moneta(1)\moneta(1)\moneta(1)+\ldots
+
<center><math>A_1=[0]+(1)+(1)(1)+(1)(1)(1)+(1)(1)(1)(1)+\ldots
 
</math></center>
 
</math></center>
  
Linia 13: Linia 13:
  
  
<center><math>A_5=[0]+\moneta(5)+\moneta(5)\moneta(5)+\moneta(5)\moneta(5)\moneta(5)+\moneta(5)\moneta(5)\moneta(5)\moneta(5)+\ldots
+
<center><math>A_5=[0]+(5)+(5)(5)+(5)(5)(5)+(5)(5)(5)(5)+\ldots
 
</math></center>
 
</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.
+
Wtedy zbiór par  <math>A_1 \times A_5</math> jest zbiorem wszystkich możliwości rozmiany kwoty przy użyciu dowolnie wielu jednocentówek oraz pięciocentówek.
  
  
<center><math>\aligned B= A_1 \times A_5  
+
<center><math>\begin{align} B= A_1 \times A_5  
&=\left([0]+\moneta(1)+\moneta(1)\moneta(1)+\moneta(1)\moneta(1)\moneta(1)+\moneta(1)\moneta(1)\moneta(1)\moneta(1)+\ldots\right)\\
+
&=\left([0]+(1)+(1)(1)+(1)(1)(1)+(1)(1)(1)(1)+\ldots\right)\\
&\times\left([0]+\moneta(5)+\moneta(5)\moneta(5)+\moneta(5)\moneta(5)\moneta(5)+\moneta(5)\moneta(5)\moneta(5)\moneta(5)+\ldots\right)\\
+
&\times\left([0]+(5)+(5)(5)+(5)(5)(5)+(5)(5)(5)(5)+\ldots\right)\\
&=[0]+\moneta(1)+\moneta(5)+\moneta(1)\moneta(1)+\moneta(1)\moneta(5)+\moneta(5)\moneta(5)+\moneta(1)\moneta(1)\moneta(1)+\ldots
+
&=[0]+(1)+(5)+(1)(1)+(1)(5)+(5)(5)+(1)(1)(1)+\ldots
\endaligned</math></center>
+
\end{align}</math></center>
  
  
Sumy wszystkich możliwości rozmiany za pomocą dziesięciocentówek <math>\moneta(10)</math>, ćwierćdolarówek <math>\moneta(25)</math>, oraz półdolarówek <math>\moneta(50)</math> wyglądają następująco:
+
Sumy wszystkich możliwości rozmiany za pomocą dziesięciocentówek <math>(10)</math>, ćwierćdolarówek <math>(25)</math>, oraz półdolarówek <math>(50)</math> wyglądają następująco:
  
  
<center><math>\aligned A_{10} &= [0]+\moneta(10)+\moneta(10)\moneta(10)+\moneta(10)\moneta(10)\moneta(10)+\moneta(10)\moneta(10)\moneta(10)\moneta(10)+\ldots\\
+
<center><math>\begin{align} A_{10} &= [0]+(10)+(10)(10)+(10)(10)(10)+(10)(10)(10)(10)+\ldots\\
A_{25} &= [0]+\moneta(25)+\moneta(25)\moneta(25)+\moneta(25)\moneta(25)\moneta(25)+\moneta(25)\moneta(25)\moneta(25)\moneta(25)+\ldots\\
+
A_{25} &= [0]+(25)+(25)(25)+(25)(25)(25)+(25)(25)(25)(25)+\ldots\\
A_{50} &= [0]+\moneta(50)+\moneta(50)\moneta(50)+\moneta(50)\moneta(50)\moneta(50)+\moneta(50)\moneta(50)\moneta(50)\moneta(50)+\ldots.
+
A_{50} &= [0]+(50)+(50)(50)+(50)(50)(50)+(50)(50)(50)(50)+\ldots.
\endaligned</math></center>
+
\end{align}</math></center>
  
  
Dodając kolejno  monety <math>\moneta(10)</math>, <math>\moneta(25)</math>, i na końcu <math>\moneta(50)</math> do możliwych rozmian uzyskujemy odpowiednio:
+
Dodając kolejno  monety <math>(10)</math>, <math>(25)</math>, i na końcu <math>(50)</math> do możliwych rozmian, uzyskujemy odpowiednio:
  
  
<center><math>\aligned C&=B\times\left([0]+\moneta(10)+\moneta(10)\moneta(10)+\moneta(10)\moneta(10)\moneta(10)+\moneta(10)\moneta(10)\moneta(10)\moneta(10)+\ldots\right)\\
+
<center><math>\begin{align} C&=B\times\left([0]+(10)+(10)(10)+(10)(10)(10)+(10)(10)(10)(10)+\ldots\right)\\
D&=C\times\left([0]+\moneta(25)+\moneta(25)\moneta(25)+\moneta(25)\moneta(25)\moneta(25)+\moneta(25)\moneta(25)\moneta(25)\moneta(25)+\ldots\right)\\
+
D&=C\times\left([0]+(25)+(25)(25)+(25)(25)(25)+(25)(25)(25)(25)+\ldots\right)\\
E&=D\times\left([0]+\moneta(50)+\moneta(50)\moneta(50)+\moneta(50)\moneta(50)\moneta(50)+\moneta(50)\moneta(50)\moneta(50)\moneta(50)+\ldots\right)\\
+
E&=D\times\left([0]+(50)+(50)(50)+(50)(50)(50)+(50)(50)(50)(50)+\ldots\right)\\
&=[0]+\moneta(1)+\moneta(5)+\moneta(10)+\moneta(25)+\moneta(50)+\moneta(1)\moneta(1)+\moneta(1)\moneta(5)+\moneta(1)\moneta(10)+\ldots
+
&=[0]+(1)+(5)+(10)+(25)+(50)+(1)(1)+(1)(5)+(1)(10)+\ldots
\endaligned</math></center>
+
\end{align}</math></center>
  
  
Linia 51: Linia 51:
 
{{wzor|int|1|
 
{{wzor|int|1|
 
<math>\begin{array} {rcl}
 
<math>\begin{array} {rcl}
E&=&\big(\moneta(1)\big)+\big(\moneta(1)\moneta(1)\big)+\big(\moneta(1)\moneta(1)\moneta(1)\big)+\big(\moneta(1)\moneta(1)\moneta(1)\moneta(1)\big)\\
+
E&=&\big((1)\big)+\big((1)(1)\big)+\big((1)(1)(1)\big)+\big((1)(1)(1)(1)\big)\\
&&+\big(\moneta(1)\moneta(1)\moneta(1)\moneta(1)\moneta(1)+\moneta(5)\big)\\
+
&&+\big((1)(1)(1)(1)(1)+(5)\big)\\
&&+\big(\moneta(1)\moneta(1)\moneta(1)\moneta(1)\moneta(1)\moneta(1)+\moneta(5)\moneta(1)\big)+\ldots
+
&&+\big((1)(1)(1)(1)(1)(1)+(5)(1)\big)+\ldots
 
\end{array}  
 
\end{array}  
 
</math>}}
 
</math>}}
  
  
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>\moneta(1)</math>, <math>\moneta(5)</math>, <math>\moneta(10)</math>, <math>\moneta(25)</math>, oraz <math>\moneta(50)</math>. Pomysłem pochodzącym od Pólya, było zastąpienie monety <math>\moneta(1)</math> przez zmienną <math>x</math>, monety <math>\moneta(5)</math> przez <math>x\cdot x\cdot x\cdot x\cdot x=x^5</math> i analogicznie <math>\moneta(10)</math> przez <math>x^{10}</math>, <math>\moneta(25)</math> przez <math>x^{25}</math>, oraz <math>\moneta(50)</math> przez <math>x^{50}</math>. Uzyskujemy w ten sposób nieskończony szereg zmiennej <math>x</math>:
+
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>(1)</math>, <math>(5)</math>, <math>(10)</math>, <math>(25)</math>, oraz <math>(50)</math>. Pomysłem pochodzącym od Pólya, było zastąpienie monety <math>(1)</math> przez zmienną <math>x</math>, monety <math>(5)</math> przez <math>x\cdot x\cdot x\cdot x\cdot x=x^5</math> i analogicznie <math>(10)</math> przez <math>x^{10}</math>, <math>(25)</math> przez <math>x^{25}</math>, oraz <math>(50)</math> przez <math>x^{50}</math>. Uzyskujemy w ten sposób nieskończony szereg zmiennej <math>x</math>:
  
  
<center><math>\aligned\fGen{E}(x)&=\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)\\
+
<center><math>\begin{align}{E}(x)&=\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)\\
 
&\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
 
&=1+x+x^2+x^3+x^4+2x^5+2x^6+2x^7+2x^8+2x^9+4x^{10}+\ldots
\endaligned</math></center>
+
\end{align}</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|1]])) jest równa współczynnikowi stojącemu przy jednomianie <math>x^n</math>.
 
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|1]])) jest równa współczynnikowi stojącemu przy jednomianie <math>x^n</math>.
  
{{kotwica|funktw|'''Funkcja tworząca'''}} <math>\fGen{G}(x)</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
+
{{kotwica|funktw|'''Funkcja tworząca'''}} <math>{G}(x)</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>\displaystyle \fGen{G}(x)=\sum_{n=0}^{\infty}{g_nx^n}=g_0+g_1x+g_2x^2+g_3x^3+g_4x^4+\ldots.
+
<center><math>\displaystyle {G}(x)=\sum_{n=0}^{\infty}{g_nx^n}=g_0+g_1x+g_2x^2+g_3x^3+g_4x^4+\ldots.
 
</math></center>
 
</math></center>
  
  
Na oznaczenie współczynnika <math>n</math>-tego wyrazu szeregu <math>\fGen{G}(x)</math> używać będziemy  oznaczenia  <math>\vect{x^n}\fGen{G}(x)=g_n</math>.
+
Na oznaczenie współczynnika <math>n</math>-tego wyrazu szeregu <math>{G}(x)</math> używać będziemy  oznaczenia  <math>{x^n}{G}(x)=g_n</math>.
  
 
{{uwaga|Jak traktowac funkcje tworzące||
 
{{uwaga|Jak traktowac funkcje tworzące||
Na funkcje tworzące można spojrzeć dwoiście. Pierwszym sposobem jest potraktowanie <math>\fGen{G}(x)</math> jako szeregu liczb rzeczywistych
+
Na funkcje tworzące można spojrzeć dwoiście. Pierwszym sposobem jest potraktowanie <math>{G}(x)</math> jako szeregu liczb rzeczywistych
(lub ogólniej zespolonych). Oczywistym pytaniem jest tu kwestia zbieżności szeregu <math>\displaystyle \fGen{G}(x)=\sum_{n=0}^{\infty}{g_nx^n}</math>. Z wykładu Analiza Matematyczna wiemy, że szereg <math>\fGen{G}(x)</math> jest zbieżny, jeśli istnieje stała <math>M\geq0</math> ograniczająca wszystkie skończone początkowe sumy, tzn.
+
(lub ogólniej zespolonych). Oczywistym pytaniem jest tu kwestia zbieżności szeregu <math>\displaystyle {G}(x)=\sum_{n=0}^{\infty}{g_nx^n}</math>. Z wykładu Analiza Matematyczna wiemy, że szereg <math>{G}(x)</math> jest zbieżny, jeśli istnieje stała <math>M\geq0</math> ograniczająca wszystkie skończone początkowe sumy, tzn.
  
  
Linia 87: Linia 87:
  
  
zachodzi dla dowolnego <math>n\geq0</math>. Ponadto jeśli dla pewnej liczby <math>x_0\in\mathbb{R}</math> szereg <math>\fGen{G}(x_0)=g_0+g_1x_0+g_2x_0^2+\ldots</math> jest zbieżny, to i także szereg <math>\fGen{G}(x_1)=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\{ {\infty} \right\}\ }=\vect{0,+\infty}</math>, że jeśli <math>\left\vert x\righ\vert<r</math>, to  <math>\fGen{G}(x)</math> jest zbieżny.
+
zachodzi dla dowolnego <math>n\geq0</math>. Ponadto jeśli dla pewnej liczby <math>x_0\in\mathbb{R}</math> szereg <math>{G}(x_0)=g_0+g_1x_0+g_2x_0^2+\ldots</math> jest zbieżny, to i także szereg <math>{G}(x_1)=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\{ {\infty} \right\}\ }={0,+\infty}</math>, że jeśli <math>\left\vert x\right\vert<r</math>, to  <math>{G}(x)</math> jest zbieżny.
  
Szereg <math>\fGen{G}(x)=g_0+g_1x+g_2x^2+\ldots</math> można więc potraktować jako funkcję
+
Szereg <math>{G}(x)=g_0+g_1x+g_2x^2+\ldots</math> można więc potraktować jako funkcję
  
  
Linia 96: Linia 96:
  
  
o wartościach <math>\displaystyle \fGen{G}(x)=\lim_{n\rightarrow\infty}{\left(g_0+g_1x+g_2x^2+\ldots+g_nx^n\right)}.</math> Oczywiście <math>\fGen{G}(0)=g_0</math>, więc dla <math>x=0</math> szereg <math>\fGen{G}(x)</math> jest zbieżny.
+
o wartościach <math>\displaystyle {G}(x)=\lim_{n\rightarrow\infty}{\left(g_0+g_1x+g_2x^2+\ldots+g_nx^n\right)}.</math> Oczywiście <math>{G}(0)=g_0</math>, więc dla <math>x=0</math> szereg <math>{G}(x)</math> jest zbieżny.
  
Drugim podejściem, bardziej użytecznym w praktycznych obliczeniach i przekształceniach jest spojrzenie na szereg <math>\fGen{G}(x)=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,  
+
Drugim podejściem, bardziej użytecznym w praktycznych obliczeniach i przekształceniach jest spojrzenie na szereg <math>{G}(x)=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.
 
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>\fGen{G}(x)=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.
+
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}(x)=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.
 
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.
Linia 107: Linia 107:
  
 
{{obserwacje|7.1|obs 7.1|
 
{{obserwacje|7.1|obs 7.1|
Dla dwu funkcji tworzących <math>\fGen{F}(x)=f_0+f_1x+f_2x^2+\ldots</math>  
+
Dla dwu funkcji tworzących <math>{F}(x)=f_0+f_1x+f_2x^2+\ldots</math>  
oraz  <math>\fGen{G}(x)=g_0+g_1x+g_2x^2+\ldots</math> mamy:
+
oraz  <math>{G}(x)=g_0+g_1x+g_2x^2+\ldots</math> mamy:
  
  
<center><math>\aligned\fGen{F}(x)=\fGen{G}{x}&\Leftrightarrow f_0=g_0,\ f_1=g_1,\ f_2=g_2,\ \ldots\\
+
<center><math>\begin{align}{F}(x)={G}{x}&\Leftrightarrow f_0=g_0,\ f_1=g_1,\ f_2=g_2,\ \ldots\\
 
&&\\
 
&&\\
\alpha\cdot\fGen{F}(x)+\beta\cdot\fGen{G}{x}&= \sum_{n=0}^{\infty}{\left(\alpha\cdot f_n+\beta\cdot g_n\right)x^n}\\
+
\alpha\cdot{F}(x)+\beta\cdot{G}{x}&= \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\\
 
&=\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\\
 
&&\\
 
&&\\
\fGen{F}(x)\cdot\fGen{G}(x)&=\sum_{n=0}^{\infty}\left(\sum_{k=0}^n f_k g_{n-k}\right) x^n\\
+
{F}(x)\cdot{G}(x)&=\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\\
 
&= 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_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\\
 
& + \left(f_0g_3+f_1g_2+f_2g_1+f_3g_0\right)x^3+\ldots\\
\endaligned</math></center>}}
+
\end{align}</math></center>}}
  
  
Wyrażenie <math>\fGen{F}(x)\cdot\fGen{G}(x)</math> nazywać będziemy splotem szeregów <math>\fGen{F}(x)</math> oraz <math>\fGen{G}(x)</math>.  
+
Wyrażenie <math>{F}(x)\cdot{G}(x)</math> nazywać będziemy splotem szeregów <math>{F}(x)</math> oraz <math>{G}(x)</math>.  
  
 
{{twierdzenie|7.2|tw 7.2|
 
{{twierdzenie|7.2|tw 7.2|
Linia 129: Linia 129:
  
  
<center><math>\fGen{G}(x)=g_0+g_1x+g_2x^2+g_3x^3+\ldots
+
<center><math>{G}(x)=g_0+g_1x+g_2x^2+g_3x^3+\ldots
 
</math></center>
 
</math></center>
  
  
ma odwrotną względem mnożenia (splotu), tzn. istnieje funkcja tworząca <math>\fGen{U}(x)</math> taka, że <math>\fGen{U}(x)\fGen{G}(x)=1</math>,  
+
ma odwrotną względem mnożenia (splotu), tzn. istnieje funkcja tworząca <math>{U}(x)</math> taka, że <math>{U}(x){G}(x)=1</math>,  
 
wtedy i tylko wtedy, gdy <math>g_0\neq0</math>.
 
wtedy i tylko wtedy, gdy <math>g_0\neq0</math>.
 
}}
 
}}
Linia 141: Linia 141:
  
 
{{obserwacje|7.3|obs 7.3|
 
{{obserwacje|7.3|obs 7.3|
Dla dwu funkcji tworzących <math>\fGen{F}(x)=f_0+f_1x+f_2x^2+\ldots</math> oraz <math>\fGen{G}(x)=g_0+g_1x+g_2x^2+\ldots</math> mamy:}}
+
Dla dwu funkcji tworzących <math>{F}(x)=f_0+f_1x+f_2x^2+\ldots</math> oraz <math>{G}(x)=g_0+g_1x+g_2x^2+\ldots</math> mamy:}}
  
  
 
{{wzor|wzor_2|2|
 
{{wzor|wzor_2|2|
<math>\displaystyle x^m\fGen{G}(x)&=&0+\ldots+0x^{m-1}+g_0x^m+g_1x^{m+1}+g_2x^{m+2}+\ldots</math>}}
+
<math>\displaystyle x^m{G}(x)=0+\ldots+0x^{m-1}+g_0x^m+g_1x^{m+1}+g_2x^{m+2}+\ldots</math>}}
  
 
{{wzor|wzor_3|3|
 
{{wzor|wzor_3|3|
<math>\displaystyle \frac{\fGen{G}(x)-\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</math>}}
+
<math>\displaystyle \frac{{G}(x)-\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</math>}}
  
 
{{wzor|wzor_4|4|
 
{{wzor|wzor_4|4|
<math>\displaystyle \fGen{G}(\alpha x)&=&g_0+g_1\alpha x+g_2\alpha^2x^2+g_3\alpha^3x^3+g_4\alpha^4x^4+\ldots</math>}}
+
<math>\displaystyle {G}(\alpha x)=g_0+g_1\alpha x+g_2\alpha^2x^2+g_3\alpha^3x^3+g_4\alpha^4x^4+\ldots</math>}}
  
 
{{wzor|wzor_5|5|
 
{{wzor|wzor_5|5|
<math>\displaystyle \fGen{G'}(x)&=&g_1+2g_2x+3g_3x^2+4g_4x^3+5g_5x^4+\ldots</math>}}
+
<math>\displaystyle {G'}(x)=g_1+2g_2x+3g_3x^2+4g_4x^3+5g_5x^4+\ldots</math>}}
  
 
{{wzor|wzor_6|6|
 
{{wzor|wzor_6|6|
<math>\displaystyle \int \fGen{G}(x)dx &=& 0+g_0x+\frac{1}{2}g_1x^2+\frac{1}{3}g_2x^3+\frac{1}{4}g_3x^4+\ldots</math>}}
+
<math>\displaystyle \int {G}(x)dx = 0+g_0x+\frac{1}{2}g_1x^2+\frac{1}{3}g_2x^3+\frac{1}{4}g_3x^4+\ldots</math>}}
  
 
{{wzor|wzor_7|7|
 
{{wzor|wzor_7|7|
<math>\displaystyle \frac{\fGen{G}(x)}{1-x}&=&g_0+\left(g_0+g_1\right)x+\left(g_0+g_1+g_2\right)x^2+\ldots</math>}}
+
<math>\displaystyle \frac{{G}(x)}{1-x}=g_0+\left(g_0+g_1\right)x+\left(g_0+g_1+g_2\right)x^2+\ldots</math>}}
  
  
Linia 179: Linia 179:
  
  
<center><math>{ y \choose n }\ =\ \frac{y^{\underline{n}}}{n!}\ =\
+
<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}.
 
\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>
 
</math></center>
Linia 219: Linia 219:
  
 
Zacznijmy od znalezienia zwartej postaci funkcji tworzącej
 
Zacznijmy od znalezienia zwartej postaci funkcji tworzącej
<math>\fGen{G}(x)=\sum_{n=0}^{\infty}n^2x^n</math>. Korzystając z [[#wn_7.5|Wniosku 7.5]] otrzymujemy:}}
+
<math>{G}(x)=\sum_{n=0}^{\infty}n^2x^n</math>. Korzystając z [[#wn_7.5|Wniosku 7.5]] otrzymujemy:}}
  
  
 
{{wzor|wzor_8|8|
 
{{wzor|wzor_8|8|
<math>\displaystyle \frac{1}{1-x}&=&\sum_{n=0}^{\infty}{n \choose n}x^n=\sum_{n=0}^{\infty}x^n,</math>}}
+
<math>\displaystyle \frac{1}{1-x} = \sum_{n=0}^{\infty}{n \choose n}x^n=\sum_{n=0}^{\infty}x^n,</math>}}
  
 
{{wzor|wzor_9|9|
 
{{wzor|wzor_9|9|
<math>\displaystyle \frac{1}{\left(1-x\right)^2}&=&\sum_{n=0}^{\infty}{n+1 \choose n
+
<math>\displaystyle \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.
}x^n\ =\ \sum_{n=0}^{\infty}nx^n+\sum_{n=0}^{\infty}x^n.
 
 
</math>}}
 
</math>}}
  
Linia 251: Linia 250:
  
 
co w połączeniu z równościami ([[#wzor_9|9]]) oraz ([[#wzor_10|10]])
 
co w połączeniu z równościami ([[#wzor_9|9]]) oraz ([[#wzor_10|10]])
daje zwartą postać funkcji tworzącej <math>\fGen{G}(x)</math> dla ciągu <math>1,4,9,\ldots,n^2,\ldots</math>:
+
daje zwartą postać funkcji tworzącej <math>{G}(x)</math> dla ciągu <math>1,4,9,\ldots,n^2,\ldots</math>:
  
  
<center><math>\displaystyle \fGen{G}(x)=\sum_{n=0}^{\infty}n^2x^n
+
<center><math>\displaystyle {G}(x)=\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}.
 
=\frac{2}{\left(1-x\right)^3}-\frac{3}{\left(1-x\right)^2}+\frac{1}{1-x}.
 
</math></center>
 
</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>\fGen{H}(x)</math> wystarczy więc skorzystać ze wzoru ([[#wzor_7|7]]) i podzielić <math>\fGen{G}(x)</math> przez <math>1-x</math>.  
+
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}(x)</math> wystarczy więc skorzystać ze wzoru ([[#wzor_7|7]]) i podzielić <math>{G}(x)</math> przez <math>1-x</math>.  
 
Tak więc poszukiwanym rozwiązaniem są współczynniki funkcji tworzącej
 
Tak więc poszukiwanym rozwiązaniem są współczynniki funkcji tworzącej
  
  
<center><math>\fGen{H}(x)=\frac{\fGen{G}(x)}{1-x}
+
<center><math>{H}(x)=\frac{{G}(x)}{1-x}
 
=\frac{2}{\left(1-x\right)^4}-\frac{3}{\left(1-x\right)^3}+\frac{1}{\left(1-x\right)^2}.
 
=\frac{2}{\left(1-x\right)^4}-\frac{3}{\left(1-x\right)^3}+\frac{1}{\left(1-x\right)^2}.
 
</math></center>
 
</math></center>
Linia 271: Linia 270:
  
  
<center><math>\aligned\fGen{H}(x)
+
<center><math>\begin{align}{H}(x)
 
&=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\\
 
&=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.
 
&=\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>
+
\end{align}</math></center>
  
  
Linia 280: Linia 279:
  
  
<center><math>\displaystyle \sum_{k=1}^nk^2=\vect{x^n}\fGen{H}(x)=\frac{2n^3+3n+n}{6}.
+
<center><math>\displaystyle \sum_{k=1}^nk^2={x^n}{H}(x)=\frac{2n^3+3n+n}{6}.
 
</math></center>
 
</math></center>
  
Linia 288: Linia 287:
  
  
<center><math>\fGen{A_k}(x) = 1+x^k+x^{2k}+x^{3k}+\ldots,
+
<center><math>{A_k}(x) = 1+x^k+x^{2k}+x^{3k}+\ldots,
 
</math></center>
 
</math></center>
  
Linia 303: Linia 302:
  
  
<center><math>\aligned\fGen{A}(x)= \fGen{A_1}(x)&= \frac{1}{1-x},\\
+
<center><math>\begin{align}{A}(x)= {A_1}(x)&= \frac{1}{1-x},\\
\fGen{B}(x)= \fGen{A}(x)\cdot \fGen{A_5}(x) &=\frac{\fGen{A}(x)}{1-x^5},\\
+
{B}(x)= {A}(x)\cdot {A_5}(x) &=\frac{{A}(x)}{1-x^5},\\
\fGen{C}(x)= \fGen{B}(x)\cdot \fGen{A_{10}}(x) &=\frac{\fGen{B}(x)}{1-x^{10}},\\
+
{C}(x)= {B}(x)\cdot {A_{10}}(x) &=\frac{{B}(x)}{1-x^{10}},\\
\fGen{D}(x)= \fGen{C}(x)\cdot \fGen{A_{25}}(x) &=\frac{\fGen{C}(x)}{1-x^{25}},\\
+
{D}(x)= {C}(x)\cdot {A_{25}}(x) &=\frac{{C}(x)}{1-x^{25}},\\
\fGen{E}(x)= \fGen{D}(x)\cdot \fGen{A_{50}}(x) &=\frac{\fGen{D}(x)}{1-x^{50}},
+
{E}(x)= {D}(x)\cdot {A_{50}}(x) &=\frac{{D}(x)}{1-x^{50}},
\endaligned</math></center>
+
\end{align}</math></center>
  
  
Linia 314: Linia 313:
  
  
<center><math>\aligned\fGen{A}(x)&=1+x\fGen{A}(x),\\
+
<center><math>\begin{align}{A}(x)&=1+x{A}(x),\\
\fGen{B}(x)&=\fGen{A}(x)+x^5\fGen{B}(x),\\
+
{B}(x)&={A}(x)+x^5{B}(x),\\
\fGen{C}(x)&=\fGen{B}(x)+x^{10}\fGen{C}(x),\\
+
{C}(x)&={B}(x)+x^{10}{C}(x),\\
\fGen{C}(x)&=\fGen{D}(x)+x^{25}\fGen{C}(x),\\
+
{C}(x)&={D}(x)+x^{25}{C}(x),\\
\fGen{D}(x)&=\fGen{E}(x)+x^{50}\fGen{D}(x).
+
{D}(x)&={E}(x)+x^{50}{D}(x).
\endaligned</math></center>
+
\end{align}</math></center>
  
  
Linia 334: Linia 333:
  
 
<center><math>
 
<center><math>
\array{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
+
\begin{array}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
 
\hline  
 
\hline  
n & 0 & 5 & 10 & 15 & 2 & 25 & 30 & 35 & 40 & 45 & 50 & 55 & 60 & 65 & 70 & 75 & 80 & 85 & 90 & 95 & 100\\
+
n & 0 & 5 & 10 & 15 & 20 & 25 & 30 & 35 & 40 & 45 & 50 & 55 & 60 & 65 & 70 & 75 & 80 & 85 & 90 & 95 & 100\\
 
\hline\hline
 
\hline\hline
 
a_n & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
 
a_n & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
Linia 348: Linia 347:
 
e_n & 1 &  &  &  &  &    &    &    &    &    & 50 &    &    &    &  &    &    &  &    &  & 292\\
 
e_n & 1 &  &  &  &  &    &    &    &    &    & 50 &    &    &    &  &    &    &  &    &  & 292\\
 
\hline
 
\hline
\endarray
+
\end{array}
 
</math></center>
 
</math></center>
  
Linia 362: Linia 361:
  
  
<center><math>\aligned f_0&=0,\\
+
<center><math>\begin{align} f_0&=0,\\
 
f_1&=1,\\
 
f_1&=1,\\
f_n&=f_{n-1}+f_{n-2}\quad\textrm{dla}\ n\geq 2.
+
f_n&=f_{n-1}+f_{n-2}\quad\text{dla}\ n\geq 2.
\endaligned</math></center>
+
\end{align}</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>\fGen{F}(x)</math> dla ciągu Fibonacci'ego
+
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}(x)</math> dla ciągu Fibonacci'ego
  
  
<center><math>\displaystyle \fGen{F}(x)
+
<center><math>\displaystyle {F}(x)
 
=\sum_{n=0}^{\infty}f_nx^n
 
=\sum_{n=0}^{\infty}f_nx^n
=x+\sum_{n=2}^{\infty}\left(f_{n-1}+f_{n-2}\right)x^n=x+x\fGen{F}(x)+x^2\fGen{F}(x).
+
=x+\sum_{n=2}^{\infty}\left(f_{n-1}+f_{n-2}\right)x^n=x+x{F}(x)+x^2{F}(x).
 
</math></center>
 
</math></center>
  
Linia 382: Linia 381:
 
{{wzor|wzor_11|11|
 
{{wzor|wzor_11|11|
 
<math>
 
<math>
\fGen{F}(x)=\frac{x}{1-x-x^2}.
+
{F}(x)=\frac{x}{1-x-x^2}.
 
</math>}}
 
</math>}}
  
Linia 391: Linia 390:
  
  
<center><math>\fGen{F}(x)=\frac{x}{1-x-x^2}
+
<center><math>{F}(x)=\frac{x}{1-x-x^2}
 
=\frac{x}{\left(1-z_0 x\right)\left(1-z_1 x\right)}
 
=\frac{x}{\left(1-z_0 x\right)\left(1-z_1 x\right)}
 
=\frac{1}{\sqrt{5}}\left(\frac{1}{\left(1-z_0 x\right)}-\frac{1}{\left(1-z_1 x\right)}\right),
 
=\frac{1}{\sqrt{5}}\left(\frac{1}{\left(1-z_0 x\right)}-\frac{1}{\left(1-z_1 x\right)}\right),
Linia 400: Linia 399:
  
  
<center><math>\displaystyle \fGen{F}(x)
+
<center><math>\displaystyle {F}(x)
 
=\frac{1}{\sqrt{5}}\left(\sum_{n=0}^{\infty}{{z_0}^nx^n}-\sum_{n=0}^{\infty}{{z_1}^nx^n}\right)
 
=\frac{1}{\sqrt{5}}\left(\sum_{n=0}^{\infty}{{z_0}^nx^n}-\sum_{n=0}^{\infty}{{z_1}^nx^n}\right)
 
=\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}{\left({z_0}^n-{z_1}^n\right)x^n}.
 
=\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}{\left({z_0}^n-{z_1}^n\right)x^n}.
Linia 413: Linia 412:
 
Przyjrzymy się dokładniej tego typu wyrażeniom.
 
Przyjrzymy się dokładniej tego typu wyrażeniom.
  
{{kotwica|stwiel|'''Stopień wielomianu'''}} <math>deg{\fGen{P}(x)}=n</math>,  
+
{{kotwica|stwiel|'''Stopień wielomianu'''}} <math>deg{{P}(x)}=n</math>,  
jeśli <math>\fGen{P}(x)=p_0+p_1x+\ldots+p_nx^n</math>.
+
jeśli <math>{P}(x)=p_0+p_1x+\ldots+p_nx^n</math>.
  
{{kotwica|funkwym|'''Funkcja wymierna'''}} <math>\fGen{R}(x)</math> to funkcja postaci <math>\frac{\fGen{P}(x)}{\fGen{Q}(x)}</math>, gdzie <math>\fGen{P}(x)</math> oraz <math>\fGen{Q}(x)\neq0</math> są wielomianami skończonego stopnia.
+
{{kotwica|funkwym|'''Funkcja wymierna'''}} <math>{R}(x)</math> to funkcja postaci <math>\frac{{P}(x)}{{Q}(x)}</math>, gdzie <math>{P}(x)</math> oraz <math>{Q}(x)\neq0</math> są wielomianami skończonego stopnia.
  
 
{{obserwacje|7.6|obs 7.6|
 
{{obserwacje|7.6|obs 7.6|
Niech <math>A(x)</math> oraz <math>\fGen{B}(x)</math> będą wielomianami  
+
Niech <math>A(x)</math> oraz <math>{B}(x)</math> będą wielomianami  
<math>deg{\fGen{A}(x)}\geq deg{\fGen{B}(x)}</math>. Wtedy istnieją wielomiany <math>\fGen{Q}(x)</math> oraz <math>\fGen{R}(x)</math> takie, że  
+
<math>deg{{A}(x)}\geq deg{{B}(x)}</math>. Wtedy istnieją wielomiany <math>{Q}(x)</math> oraz <math>{R}(x)</math> takie, że  
  
  
<center><math>\fGen{A}(x)=\fGen{Q}(x)\fGen{B}(x)+\fGen{R}(x),
+
<center><math>{A}(x)={Q}(x){B}(x)+{R}(x),
 
</math></center>
 
</math></center>
  
  
gdzie <math>deg{\fGen{R}(x)}< deg{\fGen{A}(x)}=deg{\fGen{Q}(x)}+deg{\fGen{B}(x)}</math>.}}
+
gdzie <math>deg{{R}(x)}< deg{{A}(x)}=deg{{Q}(x)}+deg{{B}(x)}</math>.}}
  
 
{{przyklad|||
 
{{przyklad|||
Linia 433: Linia 432:
  
  
<center><math>\fGen{A}(x)=3x^5+5x^4+2x^3+x^2+2\quad\textrm{oraz}\quad\fGen{B}(x)=x^3+2x^2-1.</math></center>
+
<center><math>{A}(x)=3x^5+5x^4+2x^3+x^2+2\quad\text{oraz}\quad{B}(x)=x^3+2x^2-1.</math></center>
  
  
Linia 439: Linia 438:
  
  
<center><math>\fGen{Q}(x)=3x^2-x+3\quad\textrm{oraz}\quad\fGen{R}(x)=x+2
+
<center><math>{Q}(x)=3x^2-x+3\quad\text{oraz}\quad{R}(x)=x+2
 
</math></center>
 
</math></center>
  
Linia 446: Linia 445:
  
  
<center><math>\aligned\fGen{A}(x)}&=3x^5+5x^4+2x^3+x^2+2\\
+
<center><math>\begin{align} {A}(x) & =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\\
+
& =(3x^2-x+3) \cdot (x^3+2x^2-1)+x+2\\
&=\fGen{Q}(x)\fGen{B}(x)+\fGen{R}(x).
+
& ={Q}(x){B}(x)+{R}(x).
\endaligned</math></center>
+
\end{align}</math></center>
  
  
Ponadto <math>deg{\fGen{A}(x)}=5=2+3=deg{\fGen{Q}(x)}+deg{\fGen{B}(x)}</math>.}}
+
Ponadto <math>deg{{A}(x)}=5=2+3=deg{{Q}(x)}+deg{{B}(x)}</math>.}}
  
 
{{wniosek|7.7|wn 7.7|
 
{{wniosek|7.7|wn 7.7|
Niech <math>\fGen{P}(x)</math> oraz <math>\fGen{Q}(x)</math> będą wielomianami takimi, że <math>deg{\fGen{P}(x)}\geq deg{\fGen{Q}(x)}</math>. Wtedy funkcję wymierną <math>\fGen{R}(x)=\fGen{P}(x)/ \fGen{Q}(x),</math> można przedstawić w postaci
+
Niech <math>{P}(x)</math> oraz <math>{Q}(x)</math> będą wielomianami takimi, że <math>deg{{P}(x)}\geq deg{{Q}(x)}</math>. Wtedy funkcję wymierną <math>{R}(x)={P}(x)/ {Q}(x),</math> można przedstawić w postaci
  
  
<center><math>\fGen{R}(x)=\frac{\fGen{P}(x)}{\fGen{Q}(x)}=\fGen{A}(x)+\frac{\fGen{B}(x)}{\fGen{Q}(x)},
+
<center><math>{R}(x)=\frac{{P}(x)}{{Q}(x)}={A}(x)+\frac{{B}(x)}{{Q}(x)},
 
</math></center>
 
</math></center>
  
  
dla pewnych wielomianów <math>\fGen{A}(x)</math> oraz <math>\fGen{B}(x)</math>  
+
dla pewnych wielomianów <math>{A}(x)</math> oraz <math>{B}(x)</math>  
spełniających <math>deg{\fGen{B}(x)}<deg{\fGen{Q}(x)}</math>.}}
+
spełniających <math>deg{{B}(x)}<deg{{Q}(x)}</math>.}}
  
Będziemy więc skupiali się jedynie nad takimi funkcjami wymiernymi <math>\fGen{R}(x)=\fGen{P}(x)/\fGen{Q}(x), </math> dla których <math>deg{\fGen{P}(x)}<deg{\fGen{Q}(x)}</math>.
+
Będziemy więc skupiali się jedynie nad takimi funkcjami wymiernymi <math>{R}(x)={P}(x)/{Q}(x), </math> dla których <math>deg{{P}(x)}<deg{{Q}(x)}</math>.
  
 
{{twierdzenie|7.8|tw 7.8|
 
{{twierdzenie|7.8|tw 7.8|
Niech <math>\fGen{P}(x)</math> oraz <math>\fGen{Q}(x)</math> będą wielomianami takimi, że
+
Niech <math>{P}(x)</math> oraz <math>{Q}(x)</math> będą wielomianami takimi, że
  
* <math>deg{\fGen{P}(x)}<deg{\fGen{Q}(x)}</math>,
+
* <math>deg{{P}(x)}<deg{{Q}(x)}</math>,
  
* <math>\fGen{Q}(x)=\fGen{S}(x)\fGen{T}(x)</math>, gdzie oba wielomiany <math>\fGen{S}(x),\fGen{T}(x)</math> są stopnia co najmniej <math>2</math>,
+
* <math>{Q}(x)={S}(x){T}(x)</math>, gdzie oba wielomiany <math>{S}(x),{T}(x)</math> są stopnia co najmniej <math>2</math>,
  
 
* <math>q_0\neq0</math>.
 
* <math>q_0\neq0</math>.
  
Wtedy istnieją wielomiany <math>\fGen{A}(x)</math> oraz <math>\fGen{B}(x)</math> takie, że <math>deg{\fGen{A}(x)}<deg{\fGen{S}(x)}</math> i
+
Wtedy istnieją wielomiany <math>{A}(x)</math> oraz <math>{B}(x)</math> takie, że <math>deg{{A}(x)}<deg{{S}(x)}</math> i
<math>deg{\fGen{B}(x)}<deg{\fGen{T}(x)}</math> oraz
+
<math>deg{{B}(x)}<deg{{T}(x)}</math> oraz
  
  
<center><math>\frac{\fGen{P}(x)}{\fGen{Q}(x)}
+
<center><math>\frac{{P}(x)}{{Q}(x)}
=\frac{\fGen{A}(x)}{\fGen{S}(x)}+\frac{\fGen{B}(x)}{\fGen{T}(x)}.
+
=\frac{{A}(x)}{{S}(x)}+\frac{{B}(x)}{{T}(x)}.
 
</math></center>
 
</math></center>
  
Linia 495: Linia 494:
  
  
<center><math>\fGen{R}(x)=\frac{\fGen{P}(x)}{\fGen{Q}(x)},
+
<center><math>{R}(x)=\frac{{P}(x)}{{Q}(x)},
 
</math></center>
 
</math></center>
  
  
gdzie <math>deg{\fGen{P}(x)}<deg{\fGen{Q}(x)}</math>, oraz <math>q_0\neq0</math>. Załóżmy ponadto, że wielomian <math>\fGen{Q}(x)</math> rozkłada się na następujący iloczyn czynników liniowych
+
gdzie <math>deg{{P}(x)}<deg{{Q}(x)}</math>, oraz <math>q_0\neq0</math>. Załóżmy ponadto, że wielomian <math>{Q}(x)</math> rozkłada się na następujący iloczyn czynników liniowych
  
  
<center><math>\fGen{Q}(x)
+
<center><math>{Q}(x)
 
=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}.
 
=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>
 
</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 [[#tw_7.8|Twierdzenie 7.8]] otrzymujemy wielomiany <math>\fGen{P_1}(x),\ldots,\fGen{P_k}(x)</math> takie, że
+
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 [[#tw_7.8|Twierdzenie 7.8]] otrzymujemy wielomiany <math>{P_1}(x),\ldots,{P_k}(x)</math> takie, że
  
  
<center><math>\fGen{R}(x)
+
<center><math>{R}(x)
=\frac{\fGen{P}(x)}{\fGen{Q}(x)}=\frac{\fGen{P_1}(x)}{\left(1-\rho_1x\right)^{m_1}}+\frac{\fGen{P_2}(x)}{\left(1-\rho_2x\right)^{m_2}}+\ldots+\frac{\fGen{P_k}(x)}{\left(1-\rho_kx\right)^{m_k}},
+
=\frac{{P}(x)}{{Q}(x)}=\frac{{P_1}(x)}{\left(1-\rho_1x\right)^{m_1}}+\frac{{P_2}(x)}{\left(1-\rho_2x\right)^{m_2}}+\ldots+\frac{{P_k}(x)}{\left(1-\rho_kx\right)^{m_k}},
 
</math></center>
 
</math></center>
  
  
gdzie <math>deg{\fGen{P_i}(x)}<m_i</math>. Na mocy [[#obs_7.6|Obserwacji 7.6]] możemy sprowadzić wielomian <math>\fGen{P_i}(x)</math> do
+
gdzie <math>deg{{P_i}(x)}<m_i</math>. Na mocy [[#obs_7.6|Obserwacji 7.6]] możemy sprowadzić wielomian <math>{P_i}(x)</math> do
  
  
<center><math>\aligned\fGen{P_i}(x)&=\fGen{P_i^1}(x)\left(1-\rho_ix\right)+\gamma_{m_i}\\
+
<center><math>\begin{align}{P_i}(x)&={P_i^1}(x)\left(1-\rho_ix\right)+\gamma_{m_i}\\
&=\fGen{P_i^2}(x)\left(1-\rho_ix\right)^2+\gamma_{m_i-1}\left(1-\rho_ix\right)+\gamma_{m_i}\\
+
&={P_i^2}(x)\left(1-\rho_ix\right)^2+\gamma_{m_i-1}\left(1-\rho_ix\right)+\gamma_{m_i}\\
 
&\vdots\\
 
&\vdots\\
 
&=\gamma_1\left(1-\rho_ix\right)^{m_i-1}+\ldots+\gamma_{m_i-1}\left(1-\rho_ix\right)+\gamma_{m_i},
 
&=\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>
+
\end{align}</math></center>
  
  
gdzie <math>m_i\geq deg{\fGen{P_i}(x)}>deg{\fGen{P_i^1}(x)}>deg{\fGen{P_i^2}(x)}>\ldots</math>. W konsekwencji otrzymamy
+
gdzie <math>m_i\geq deg{{P_i}(x)}>deg{{P_i^1}(x)}>deg{{P_i^2}(x)}>\ldots</math>. W konsekwencji otrzymamy
  
  
<center><math>\displaystyle \fGen{R}(x)\ =\ \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)}.
+
<center><math>\displaystyle {R}(x)= \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>
 
</math></center>
  
Linia 535: Linia 534:
  
  
<center><math>\fGen{Q}(x)/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}
+
<center><math>{Q}(x)/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>
 
</math></center>
  
Linia 552: Linia 551:
 
{{wzor|wzor_12|12|
 
{{wzor|wzor_12|12|
 
<math>\displaystyle  
 
<math>\displaystyle  
[x^n]\fGen{R}(x)\ =\ \sum_{i=1}^k{\left(\gamma_{i,1}+
+
[x^n]{R}(x)= \sum_{i=1}^k{\left(\gamma_{i,1}+
 
\gamma_{i,2}{n+1\choose 1}+
 
\gamma_{i,2}{n+1\choose 1}+
 
\ldots+
 
\ldots+
Linia 564: Linia 563:
  
  
<center><math>\fGen{R}(x)=\frac{x^2}{1-x-x^2+x^3}.
+
<center><math>{R}(x)=\frac{x^2}{1-x-x^2+x^3}.
 
</math></center>
 
</math></center>
  
Linia 571: Linia 570:
  
  
<center><math>\fGen{R}(x)
+
<center><math>{R}(x)
 
=\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}.
 
=\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>
 
</math></center>
Linia 598: Linia 597:
  
  
<center><math>\aligned\fGen{R}(x)&=\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\\
+
<center><math>\begin{align}{R}(x)&=\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.
 
&=x^2+x^3+2x^4+2x^5+3x^6+3x^7+4x^8+\ldots.
\endaligned</math></center>
+
\end{align}</math></center>
  
  
Jeżeli mianownik <math>\fGen{Q}(x)</math> funkcji wymiernej <math>\fGen{R}(x)=\frac{\fGen{P}(x)}{\fGen{Q}(x)}</math> posiada jedynie pierwiastki jednokrotne, to następne twierdzenie znacznie przyspiesza rozkład <math>\fGen{R}(x)</math> na sumę.}}
+
Jeżeli mianownik <math>{Q}(x)</math> funkcji wymiernej <math>{R}(x)=\frac{{P}(x)}{{Q}(x)}</math> posiada jedynie pierwiastki jednokrotne, to następne twierdzenie znacznie przyspiesza rozkład <math>{R}(x)</math> na sumę.}}
  
 
{{twierdzenie|7.9|tw 7.9|
 
{{twierdzenie|7.9|tw 7.9|
Jeśli <math>\fGen{R}(x)=\fGen{P}(x)/\fGen{Q}(x)</math>, gdzie <math>\fGen{Q}(x)=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>\fGen{P}(x)</math> jest wielomianem stopnia mniejszego niż <math>l</math>, zachodzi
+
Jeśli <math>{R}(x)={P}(x)/{Q}(x)</math>, gdzie <math>{Q}(x)=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}(x)</math> jest wielomianem stopnia mniejszego niż <math>l</math>, zachodzi
  
  
<center><math>\vect{x^n}\fGen{R}(x)
+
<center><math>{x^n}{R}(x)
 
=a_1\rho_1^n+\ldots+a_l\rho_l^n,
 
=a_1\rho_1^n+\ldots+a_l\rho_l^n,
\quad\textrm{dla}\ a_k=\frac{-\rho_k\cdot\fGen{P}(1/\rho_k)}{\fGen{Q'}(1/\rho_k)}.
+
\quad\text{dla}\ a_k=\frac{-\rho_k\cdot{P}(1/\rho_k)}{{Q'}(1/\rho_k)}.
 
</math></center>
 
</math></center>
  
Linia 618: Linia 617:
  
 
{{przyklad|||
 
{{przyklad|||
Mianownik <math>\fGen{Q}(x)</math> funkcji wymiernej  
+
Mianownik <math>{Q}(x)</math> funkcji wymiernej  
  
  
<center><math>\fGen{R}(x)=\frac{\fGen{P}(x)}{\fGen{Q}(x)}=\frac{2x}{1-5x-2x^2+24x^3}.
+
<center><math>{R}(x)=\frac{{P}(x)}{{Q}(x)}=\frac{2x}{1-5x-2x^2+24x^3}.
 
</math></center>
 
</math></center>
  
  
ma trzy różne pierwiastki i można <math>\fGen{R}(x)</math> przedstawić jako
+
ma trzy różne pierwiastki i można <math>{R}(x)</math> przedstawić jako
  
  
<center><math>\fGen{R}(x)=\frac{2x}{\left(1+2x\right)\left(1-3x\right)\left(1-4x\right)}.
+
<center><math>{R}(x)=\frac{2x}{\left(1+2x\right)\left(1-3x\right)\left(1-4x\right)}.
 
</math></center>
 
</math></center>
  
Linia 635: Linia 634:
  
  
<center><math>\vect{x^n}\fGen{R}(x)=-\frac{2}{15}\left(-2\right)^n-\frac{6}{5}3^n+\frac{4}{3}4^n.
+
<center><math>{x^n}{R}(x)=-\frac{2}{15}\left(-2\right)^n-\frac{6}{5}3^n+\frac{4}{3}4^n.
 
</math></center>}}
 
</math></center>}}
  
Linia 649: Linia 648:
 
&\cdots&\\
 
&\cdots&\\
 
r_{k-1}&=&c_{k-1},\\
 
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,
+
r_n&=&a_1r_{n-1}+a_2r_{n-2}+\ldots+a_kr_{n-k}\quad\text{dla}\ n\geq k,
 
\end{array}  
 
\end{array}  
 
\right.
 
\right.
Linia 666: Linia 665:
 
r_0&=&c_0,\\
 
r_0&=&c_0,\\
 
r_1&=&c_1,\\
 
r_1&=&c_1,\\
r_n&=&a_1r_{n-1}+a_2r_{n-2}\quad\textrm{dla}\ n\geq 2.
+
r_n&=&a_1r_{n-1}+a_2r_{n-2}\quad\text{dla}\ n\geq 2.
 
\end{array}  
 
\end{array}  
 
\right.
 
\right.
Linia 675: Linia 674:
  
  
<center><math>\aligned\fGen{R}(x)&=r_0+r_1x+r_2x^2+r_3x^3+\ldots+r_nx^n+\ldots\\
+
<center><math>\begin{align}{R}(x)&=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+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\fGen{R}(x)+a_2x^2\fGen{R}(x),
+
&=c_0+\left(c_1-a_1c_0\right)x+a_1x{R}(x)+a_2x^2{R}(x),
\endaligned</math></center>
+
\end{align}</math></center>
  
  
Linia 684: Linia 683:
  
  
<center><math>\fGen{R}(x)\ =\ \frac{c_0+\left(c_1-a_1c_0\right)x}{1-a_1x-a_2x^2}
+
<center><math>{R}(x)= \frac{c_0+\left(c_1-a_1c_0\right)x}{1-a_1x-a_2x^2}
 
</math></center>
 
</math></center>
  
  
Dla funkcji <math>\fGen{A}(x)=1-a_1x-a_2x^2=\left(1-\rho_1x\right)\left(1-\rho_2x\right)</math> mogą zajść trzy przypadki:
+
Dla funkcji <math>{A}(x)=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  
 
* <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,
+
<center><math>r_n= \alpha\rho_1^n+\beta\rho_2^n,
 
</math></center>
 
</math></center>
  
Linia 699: Linia 698:
 
* <math>\rho_1 = \rho_2</math>. Wtedy
 
* <math>\rho_1 = \rho_2</math>. Wtedy
  
<center><math>r_n\ =\ \left(\alpha n+\beta\right)\rho_1^n,
+
<center><math>r_n= \left(\alpha n+\beta\right)\rho_1^n,
 
</math></center>
 
</math></center>
  
Linia 707: Linia 706:
  
  
<center><math>r_n\ =\ \alpha\rho_1^n+\beta\rho_2^n.
+
<center><math>r_n= \alpha\rho_1^n+\beta\rho_2^n.
 
</math></center>
 
</math></center>
  
Linia 717: Linia 716:
  
  
<center><math>\fGen{R}(x)\ =\ \frac{\fGen{P}(x)}{1-a_1x-a_2x^2-\ldots-a_kx^k},
+
<center><math>{R}(x)= \frac{{P}(x)}{1-a_1x-a_2x^2-\ldots-a_kx^k},
 
</math></center>
 
</math></center>
  
  
gdzie <math>\fGen{P}(x)</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>.
+
gdzie <math>{P}(x)</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]\fGen{R}(x)</math> zgodnie z równaniem ([[#wzor_12|12]]).
+
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}(x)</math> zgodnie z równaniem ([[#wzor_12|12]]).
  
  
Linia 734: Linia 733:
 
r_1&=&0,\\
 
r_1&=&0,\\
 
r_2&=&1,\\
 
r_2&=&1,\\
r_n&=&r_{n-1}+r_{n-2}-r_{n-3}\quad\textrm{dla}\ n\geq 3.
+
r_n&=&r_{n-1}+r_{n-2}-r_{n-3}\quad\text{dla}\ n\geq 3.
 
\end{array}  
 
\end{array}  
 
\right.
 
\right.
Linia 740: Linia 739:
  
  
Ostatnia zależność prowadzi do funkcji tworzącej <math>\fGen{R}(x)</math> spełniającej
+
Ostatnia zależność prowadzi do funkcji tworzącej <math>{R}(x)</math> spełniającej
  
  
<center><math>\fGen{R}(x)=x^2 + x\fGen{R}(x) + x^2\fGen{R}(x) - x^3\fGen{R}(x).
+
<center><math>{R}(x)=x^2 + x{R}(x) + x^2{R}(x) - x^3{R}(x).
 
</math></center>
 
</math></center>
  
Linia 750: Linia 749:
  
  
<center><math>\fGen{R}(x)=\frac{x^2}{1-x-x^2+x^3}.
+
<center><math>{R}(x)=\frac{x^2}{1-x-x^2+x^3}.
 
</math></center>
 
</math></center>
  
  
W przykładzie omawianym przy okazji metody rozwijania funkcji wymiernej w szereg, wyliczyliśmy współczynniki <math>[x^n]\fGen{R}(x)</math>, a zatem mamy:
+
W przykładzie omawianym przy okazji metody rozwijania funkcji wymiernej w szereg, wyliczyliśmy współczynniki <math>[x^n]{R}(x)</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.
+
<center><math>r_n=-\frac{1}{4}+\frac{1}{2}\left(n+1\right) - \frac{1}{4}\left(-1\right)^n\quad\text{dla dowolnego}\ n=0,1,2,3,\ldots.
 
</math></center>}}
 
</math></center>}}

Aktualna wersja na dzień 13:20, 28 wrz 2020

Przykład

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 , pięciocentówek , dziesięciocentówek , ćwierćdolarówek , oraz półdolarówki . 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ę , 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



i analogicznie przeanalizujmy sumę dla pieciocentówek



Wtedy zbiór par jest zbiorem wszystkich możliwości rozmiany kwoty przy użyciu dowolnie wielu jednocentówek oraz pięciocentówek.



Sumy wszystkich możliwości rozmiany za pomocą dziesięciocentówek , ćwierćdolarówek , oraz półdolarówek wyglądają następująco:



Dodając kolejno monety , , i na końcu do możliwych rozmian, uzyskujemy odpowiednio:



Grupując teraz składniki sumy w podsumy o tych samych wartościach dostajemy wyrażenie:


     (1)


Zliczając zaś tylko składniki w podsumie odpowiadającej wartości centów, otrzymujemy liczbę sposobów, na które można rozmienić centów przy użyciu monet , , , , oraz . Pomysłem pochodzącym od Pólya, było zastąpienie monety przez zmienną , monety przez i analogicznie przez , przez , oraz przez . Uzyskujemy w ten sposób nieskończony szereg zmiennej :



Godne zauważenia jest, że liczba różnych możliwych sposobów rozmiany centów (równa liczbie grup monet w odpowiednim nawiasie we wzorze (1)) jest równa współczynnikowi stojącemu przy jednomianie .

Funkcja tworząca dla ciągu liczb rzeczywistych (lub zespolonych) to szereg funkcyjny zmiennej rzeczywistej (lub zespolonej) postaci



Na oznaczenie współczynnika -tego wyrazu szeregu używać będziemy oznaczenia .

Uwaga Jak traktowac funkcje tworzące

Na funkcje tworzące można spojrzeć dwoiście. Pierwszym sposobem jest potraktowanie jako szeregu liczb rzeczywistych (lub ogólniej zespolonych). Oczywistym pytaniem jest tu kwestia zbieżności szeregu . Z wykładu Analiza Matematyczna wiemy, że szereg jest zbieżny, jeśli istnieje stała ograniczająca wszystkie skończone początkowe sumy, tzn.



zachodzi dla dowolnego . Ponadto jeśli dla pewnej liczby szereg jest zbieżny, to i także szereg jest zbieżny dla dowolnego spełniającego . Możemy więc określić promień zbieżności szeregu jako taką liczbę , że jeśli , to jest zbieżny.

Szereg można więc potraktować jako funkcję



o wartościach Oczywiście , więc dla szereg jest zbieżny.

Drugim podejściem, bardziej użytecznym w praktycznych obliczeniach i przekształceniach jest spojrzenie na szereg jako formę zapisu ciągu , 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 jest funkcją tworzącą ciągu , oraz w jakiś sposób będziemy w stanie poznać postać zwartą funkcji , 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 . Ponadto będziemy pomijać problem zbieżności oraz wartość 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.

Obserwacja 7.1

Dla dwu funkcji tworzących oraz mamy:



Wyrażenie nazywać będziemy splotem szeregów oraz .

Twierdzenie 7.2

Funkcja tworząca postaci



ma odwrotną względem mnożenia (splotu), tzn. istnieje funkcja tworząca taka, że , wtedy i tylko wtedy, gdy .

Następne własności są bardzo pomocne w dokonywanych przekształceniach funkcji tworzących.

Obserwacja 7.3

Dla dwu funkcji tworzących oraz mamy:


     (2)

     (3)

     (4)

     (5)

     (6)

     (7)


Funkcje tworzące w zliczaniu

Widzieliśmy już, że dla



Przyjrzyjmy się teraz rozwinięciu w szereg funkcji , gdzie 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 , gdzie oraz jest oznaczeniem na



Uwaga

Oczywiście dla spełniającego dodatkowo , uogólniony symbol dwumianowy jest liczbą -elementowych podzbiorów zbioru -elementowego.

Twierdzenie 7.4

Dla liczby rzeczywistej oraz liczby naturalnej zachodzi



Wniosek 7.5

Dla liczby naturalnej zachodzi



Dowód

Dowód zostawiony jest jako ćwiczenie 3.

End of proof.gif

Przykład

Policzmy sumę



Zacznijmy od znalezienia zwartej postaci funkcji tworzącej

. Korzystając z Wniosku 7.5 otrzymujemy:


     (8)

     (9)


Po przekształceniu równości (9) uzyskuje się


     (10)


Powołując się ponownie na Wniosek 7.5 otrzymujemy



co w połączeniu z równościami (9) oraz (10) daje zwartą postać funkcji tworzącej dla ciągu :



Naszym zadaniem było jednakże policzenie funkcji tworzącej dla ciągu , tzn. ciągu sum początkowych wyrazów ciągu . Aby uzyskać wystarczy więc skorzystać ze wzoru (7) i podzielić przez . Tak więc poszukiwanym rozwiązaniem są współczynniki funkcji tworzącej



Korzystając po raz kolejny z Wniosku 7.5 otrzymujemy



W konsekwencji zachodzi równość



Przykład

Wracamy do przykładu z monetami. Występowały tam funkcje tworzące postaci



dla i . Z równości (7) wiemy, że



tak więc:



skąd natychmiast:



Równości te dają zależności między współczynnikami:



Wykorzystując te zależności rekurencyjne możemy wypełnić następującą tabelę:



Pół dolara można rozmienić na sposobów. Z kolei rozmieniać jednego dolara można na aż sposoby. Do problemu tego wrócimy jeszcze w następnym wykładzie.

Funkcje tworzące w rozwiązywaniu zależności rekurencyjnych

Przykład

Rozważmy ciąg Fibonacci'ego, tzn. ciąg zdefiniowany w następujący sposób:



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 przekładają się natychmiast na następujące równanie, jakie musi spełniać funkcja tworząca dla ciągu Fibonacci'ego



Przekształcając powyższe równanie otrzymujemy:


     (11)


Celem, który chcemy osiągnąć to wykorzystanie funkcji do przedstawienia współczynników w postaci zwartej. Pierwszym krokiem będzie rozłożenie ułamka w równaniu (11) na sumę ułamków o mianownikach będących funkcjami liniowymi



gdzie jest złotą liczbą oraz liczbą do niej sprzężoną. Korzystając z równania (7) otrzymujemy teraz



Tak więc dostajemy szybko znaną nam już postać zwartą .

Podczas rozwiązywania przykładu związanego z liczbami Fibonacci'ego natrafiliśmy na problem polegający na przedstawieniu w postaci szeregu wyrażenia . Przyjrzymy się dokładniej tego typu wyrażeniom.

Stopień wielomianu , jeśli .

Funkcja wymierna to funkcja postaci , gdzie oraz są wielomianami skończonego stopnia.

Obserwacja 7.6

Niech oraz będą wielomianami . Wtedy istnieją wielomiany oraz takie, że



gdzie .

Przykład

Niech



Wtedy wielomiany



spełniają



Ponadto .

Wniosek 7.7

Niech oraz będą wielomianami takimi, że . Wtedy funkcję wymierną można przedstawić w postaci



dla pewnych wielomianów oraz

spełniających .

Będziemy więc skupiali się jedynie nad takimi funkcjami wymiernymi dla których .

Twierdzenie 7.8

Niech oraz będą wielomianami takimi, że

  • ,
  • , gdzie oba wielomiany są stopnia co najmniej ,
  • .

Wtedy istnieją wielomiany oraz takie, że i oraz



Uwaga

Twierdzenie 7.8 pozwala na rozbijanie skomplikowanych funkcji wymiernych na sumę prostszych.

Wniosek [Metoda rozwijania funkcji wymiernej w szereg]

Rozważmy funkcję wymierną w postaci



gdzie , oraz . Załóżmy ponadto, że wielomian rozkłada się na następujący iloczyn czynników liniowych



Warto wspomnieć, że dalecy nie każdy wielomian ma taki rozkład. Na przykład jest nierozkładalny i nieliniowy. Wykorzystując parokrotnie Twierdzenie 7.8 otrzymujemy wielomiany takie, że



gdzie . Na mocy Obserwacji 7.6 możemy sprowadzić wielomian do



gdzie . W konsekwencji otrzymamy



Mnożąc teraz obie strony przez



i porównując współczynniki przy odpowiadających potęgach uzyskujemy pewien układ równań, rozwiązanie którego da nam poszukiwane współczynniki . Z drugiej strony, z Wniosku 7.5 wynika, że



i w konsekwencji:


     (12)


Przykład

Opisaną wyżej metodę ogólną zilustrujemy na przykładzie funkcji



Wielomian ma jeden podwójny pierwiastek oraz jeden pojedynczy . Poznana metoda rozwijania funkcji wymiernej w szereg daje więc



Mnożąc obie strony przez otrzymujemy:



Dwa wielomiany są równe, gdy współczynniki przy odpowiadających potęgach są sobie równe. Wartości można więc wyliczyć z układu równań



Rozwiązaniem powyższego układu są wartości W konsekwencji otrzymujemy szereg



Jeżeli mianownik funkcji wymiernej posiada jedynie pierwiastki jednokrotne, to następne twierdzenie znacznie przyspiesza rozkład na sumę.

Twierdzenie 7.9

Jeśli , gdzie i liczby są parami różne, to w przypadku gdy jest wielomianem stopnia mniejszego niż , zachodzi



Przykład

Mianownik funkcji wymiernej



ma trzy różne pierwiastki i można przedstawić jako



Na mocy Twierdzenia 7.9 otrzymujemy więc, że



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



gdzie są liczbami rzeczywistymi (niezależnymi od parametru rekurencyjnego ).

Rozważmy najpierw przypadek, gdy , tzn. równanie postaci


     (13)


Przykładem takiego równania była zależność opisująca ciąg Fibonacci'ego. Zastosowanie ostatniej równości z (13) do funkcji tworzącej ciągu daje:



tak więc



Dla funkcji mogą zajść trzy przypadki:

  • są różnymi liczbami rzeczywistymi. Wtedy


gdzie oraz są liczbami rzeczywistymi.

  • . Wtedy


gdzie oraz są liczbami rzeczywistymi.

  • Wartości oraz 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



gdzie oraz 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.

Wracamy teraz do ogólnego, jednorodnego liniowego równania rekurencyjnego. Analogicznie do przypadku, gdy , otrzymujemy że



gdzie jest wielomianem co najwyżej stopnia , zależnym od wartości . Korzystając z ogólnej metody rozwijania funkcji wymiernej w szereg, możemy odzyskać wyrazy ciągu , jako współczynniki zgodnie z równaniem (12).


Przykład

Równanie rekurencyjne ma następującą postać



Ostatnia zależność prowadzi do funkcji tworzącej spełniającej



Po dokonaniu prostego wyliczenia dostajemy:



W przykładzie omawianym przy okazji metody rozwijania funkcji wymiernej w szereg, wyliczyliśmy współczynniki , a zatem mamy: