Matematyka dyskretna 1/Wykład 7: Funkcje tworzące

From Studia Informatyczne

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 (1), pięciocentówek (5), dziesięciocentówek (10), ćwierćdolarówek (25), oraz półdolarówki (50). 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ę [0], 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


A_1=[0]+\moneta(1)+\moneta(1)\moneta(1)+\moneta(1)\moneta(1)\moneta(1)+\moneta(1)\moneta(1)\moneta(1)\moneta(1)+\ldots


i analogicznie przeanalizujmy sumę dla pieciocentówek


A_5=[0]+\moneta(5)+\moneta(5)\moneta(5)+\moneta(5)\moneta(5)\moneta(5)+\moneta(5)\moneta(5)\moneta(5)\moneta(5)+\ldots


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


\aligned 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)\\ &\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)\\ &=[0]+\moneta(1)+\moneta(5)+\moneta(1)\moneta(1)+\moneta(1)\moneta(5)+\moneta(5)\moneta(5)+\moneta(1)\moneta(1)\moneta(1)+\ldots \endaligned


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


\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\\ 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_{50} &= [0]+\moneta(50)+\moneta(50)\moneta(50)+\moneta(50)\moneta(50)\moneta(50)+\moneta(50)\moneta(50)\moneta(50)\moneta(50)+\ldots. \endaligned


Dodając kolejno monety \moneta(10), \moneta(25), i na końcu \moneta(50) do możliwych rozmian, uzyskujemy odpowiednio:


\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)\\ 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)\\ 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)\\ &=[0]+\moneta(1)+\moneta(5)+\moneta(10)+\moneta(25)+\moneta(50)+\moneta(1)\moneta(1)+\moneta(1)\moneta(5)+\moneta(1)\moneta(10)+\ldots \endaligned


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


\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)\\ &&+\big(\moneta(1)\moneta(1)\moneta(1)\moneta(1)\moneta(1)+\moneta(5)\big)\\ &&+\big(\moneta(1)\moneta(1)\moneta(1)\moneta(1)\moneta(1)\moneta(1)+\moneta(5)\moneta(1)\big)+\ldots \end{array}      (1)


Zliczając zaś tylko składniki w podsumie odpowiadającej wartości n centów, otrzymujemy liczbę sposobów, na które można rozmienić n centów przy użyciu monet \moneta(1), \moneta(5), \moneta(10), \moneta(25), oraz \moneta(50). Pomysłem pochodzącym od Pólya, było zastąpienie monety \moneta(1) przez zmienną x, monety \moneta(5) przez x\cdot x\cdot x\cdot x\cdot x=x^5 i analogicznie \moneta(10) przez x^{10}, \moneta(25) przez x^{25}, oraz \moneta(50) przez x^{50}. Uzyskujemy w ten sposób nieskończony szereg zmiennej x:


\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)\\ &\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


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

Funkcja tworząca \fGen{G}(x) dla ciągu liczb rzeczywistych (lub zespolonych) \left(g_0,g_1,g_2,g_3,\ldots\right) to szereg funkcyjny zmiennej rzeczywistej (lub zespolonej) x postaci


\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.


Na oznaczenie współczynnika n-tego wyrazu szeregu \fGen{G}(x) używać będziemy oznaczenia \vect{x^n}\fGen{G}(x)=g_n.

Uwaga Jak traktowac funkcje tworzące

Na funkcje tworzące można spojrzeć dwoiście. Pierwszym sposobem jest potraktowanie \fGen{G}(x) jako szeregu liczb rzeczywistych (lub ogólniej zespolonych). Oczywistym pytaniem jest tu kwestia zbieżności szeregu \displaystyle \fGen{G}(x)=\sum_{n=0}^{\infty}{g_nx^n}. Z wykładu Analiza Matematyczna wiemy, że szereg \fGen{G}(x) jest zbieżny, jeśli istnieje stała M\geq0 ograniczająca wszystkie skończone początkowe sumy, tzn.


\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


zachodzi dla dowolnego n\geq0. Ponadto jeśli dla pewnej liczby x_0\in\mathbb{R} szereg \fGen{G}(x_0)=g_0+g_1x_0+g_2x_0^2+\ldots jest zbieżny, to i także szereg \fGen{G}(x_1)=g_0+g_1x_1+g_2x_1^2+\ldots jest zbieżny dla dowolnego x_1\in\mathbb{R} spełniającego \left\vert x_1\right\vert\leq\left\vert x_0\right\vert. Możemy więc określić promień zbieżności szeregu jako taką liczbę r\in\mathbb{R}_*\cup{\left\{ {\infty} \right\}\ }=\vect{0,+\infty}, że jeśli \left\vert x\righ\vert<r, to \fGen{G}(x) jest zbieżny.

Szereg \fGen{G}(x)=g_0+g_1x+g_2x^2+\ldots można więc potraktować jako funkcję


G:\left(-r,r\right)\longrightarrow\mathbb{R},


o wartościach \displaystyle \fGen{G}(x)=\lim_{n\rightarrow\infty}{\left(g_0+g_1x+g_2x^2+\ldots+g_nx^n\right)}. Oczywiście \fGen{G}(0)=g_0, więc dla x=0 szereg \fGen{G}(x) jest zbieżny.

Drugim podejściem, bardziej użytecznym w praktycznych obliczeniach i przekształceniach jest spojrzenie na szereg \fGen{G}(x)=g_0+g_1x+g_2x^2+\ldots jako formę zapisu ciągu \left(g_0,g_1,g_2,\ldots\right), 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 \fGen{G}(x)=g_0+g_1x+g_2x^2+\ldots jest funkcją tworzącą ciągu \left(g_0,g_1,g_2,g_3,\ldots\right), oraz w jakiś sposób będziemy w stanie poznać postać zwartą funkcji G(x), 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 r>0. Ponadto będziemy pomijać problem zbieżności oraz wartość r 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 \fGen{F}(x)=f_0+f_1x+f_2x^2+\ldots oraz \fGen{G}(x)=g_0+g_1x+g_2x^2+\ldots mamy:


\aligned\fGen{F}(x)=\fGen{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}\\ &=\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_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


Wyrażenie \fGen{F}(x)\cdot\fGen{G}(x) nazywać będziemy splotem szeregów \fGen{F}(x) oraz \fGen{G}(x).

Twierdzenie 7.2

Funkcja tworząca postaci


\fGen{G}(x)=g_0+g_1x+g_2x^2+g_3x^3+\ldots


ma odwrotną względem mnożenia (splotu), tzn. istnieje funkcja tworząca \fGen{U}(x) taka, że \fGen{U}(x)\fGen{G}(x)=1, wtedy i tylko wtedy, gdy g_0\neq0.

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

Obserwacja 7.3

Dla dwu funkcji tworzących \fGen{F}(x)=f_0+f_1x+f_2x^2+\ldots oraz \fGen{G}(x)=g_0+g_1x+g_2x^2+\ldots mamy:


\displaystyle x^m\fGen{G}(x)&=&0+\ldots+0x^{m-1}+g_0x^m+g_1x^{m+1}+g_2x^{m+2}+\ldots      (2)

\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      (3)

\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      (4)

\displaystyle \fGen{G'}(x)&=&g_1+2g_2x+3g_3x^2+4g_4x^3+5g_5x^4+\ldots      (5)

\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      (6)

\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      (7)


Funkcje tworzące w zliczaniu

Widzieliśmy już, że dla n\in \mathbb{N}


\displaystyle \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}^m {m \choose n}x^n.


Przyjrzyjmy się teraz rozwinięciu w szereg funkcji \left(1+x\right)^y, gdzie y\in\mathbb{R} 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 { y \choose n }, gdzie y\in\mathbb{R} oraz n\in\mathbb{N} jest oznaczeniem na


{ 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}.


Uwaga

Oczywiście dla y\in\mathbb{N} spełniającego dodatkowo y\geq n, uogólniony symbol dwumianowy { y \choose n } jest liczbą n-elementowych podzbiorów zbioru y-elementowego.

Twierdzenie 7.4

Dla liczby rzeczywistej y oraz liczby naturalnej n zachodzi


\displaystyle \left(1+x\right)^y=\sum_{n=0}^{\infty}{ y \choose n }x^n.


Wniosek 7.5

Dla liczby naturalnej m zachodzi


\displaystyle \frac{1}{\left(1-x\right)^{m+1}}=\sum_{n=0}^{\infty}{ m+n \choose n }x^n.


Dowód

Dowód zostawiony jest jako ćwiczenie 3.

image:End_of_proof.gif

Przykład

Policzmy sumę


\displaystyle \sum_{k=0}^nk^2=1+4+9+\ldots+n^2.


Zacznijmy od znalezienia zwartej postaci funkcji tworzącej

\fGen{G}(x)=\sum_{n=0}^{\infty}n^2x^n. Korzystając z Wniosku 7.5 otrzymujemy:


\displaystyle \frac{1}{1-x}&=&\sum_{n=0}^{\infty}{n \choose n}x^n=\sum_{n=0}^{\infty}x^n,      (8)

\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.      (9)


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


\displaystyle  \sum_{n=0}^{\infty}nx^n= \frac{1}{\left(1-x\right)^2} -\frac{1}{1-x}.      (10)


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


\displaystyle \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,


co w połączeniu z równościami (9) oraz (10) daje zwartą postać funkcji tworzącej \fGen{G}(x) dla ciągu 1,4,9,\ldots,n^2,\ldots:


\displaystyle \fGen{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}.


Naszym zadaniem było jednakże policzenie funkcji tworzącej H(x) dla ciągu 1,1+4,1+4+9,\ldots,1+4+9+\ldots+n^2,\ldots, tzn. ciągu sum początkowych wyrazów ciągu 1,4,9,\ldots,n^2,\ldots. Aby uzyskać \fGen{H}(x) wystarczy więc skorzystać ze wzoru (7) i podzielić \fGen{G}(x) przez 1-x. Tak więc poszukiwanym rozwiązaniem są współczynniki funkcji tworzącej


\fGen{H}(x)=\frac{\fGen{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}.


Korzystając po raz kolejny z Wniosku 7.5 otrzymujemy


\aligned\fGen{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\\ &=\sum_{n=0}^{\infty}\left(\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n\right)x^n. \endaligned


W konsekwencji zachodzi równość


\displaystyle \sum_{k=1}^nk^2=\vect{x^n}\fGen{H}(x)=\frac{2n^3+3n+n}{6}.


Przykład

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


\fGen{A_k}(x) = 1+x^k+x^{2k}+x^{3k}+\ldots,


dla k=1,5,10,25 i 50. Z równości (7) wiemy, że


1+x^k+x^{2k}+x^{3k}+\ldots, =\frac{1}{1-x^k}


tak więc:


\aligned\fGen{A}(x)= \fGen{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},\\ \fGen{C}(x)= \fGen{B}(x)\cdot \fGen{A_{10}}(x) &=\frac{\fGen{B}(x)}{1-x^{10}},\\ \fGen{D}(x)= \fGen{C}(x)\cdot \fGen{A_{25}}(x) &=\frac{\fGen{C}(x)}{1-x^{25}},\\ \fGen{E}(x)= \fGen{D}(x)\cdot \fGen{A_{50}}(x) &=\frac{\fGen{D}(x)}{1-x^{50}}, \endaligned


skąd natychmiast:


\aligned\fGen{A}(x)&=1+x\fGen{A}(x),\\ \fGen{B}(x)&=\fGen{A}(x)+x^5\fGen{B}(x),\\ \fGen{C}(x)&=\fGen{B}(x)+x^{10}\fGen{C}(x),\\ \fGen{C}(x)&=\fGen{D}(x)+x^{25}\fGen{C}(x),\\ \fGen{D}(x)&=\fGen{E}(x)+x^{50}\fGen{D}(x). \endaligned


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


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\quad e_n=d_n+e_{n-50}.


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


\array{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline  n & 0 & 5 & 10 & 15 & 20 & 25 & 30 & 35 & 40 & 45 & 50 & 55 & 60 & 65 & 70 & 75 & 80 & 85 & 90 & 95 & 100\\ \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\\ \hline b_n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21\\ \hline c_n & 1 & 2 & 4 & 6 & 9 & 12 & 16 & 10 & 25 & 30 & 36 & 42 & 49 & 56 & 64 & 72 & 81 &   & 100 &   & 121\\ \hline d_n & 1 &   &   &   &   & 13 &    &    &    &    & 49 &    &    &    &   & 121 &    &   &     &   & 242\\ \hline e_n & 1 &   &   &   &   &    &    &    &    &    & 50 &    &    &    &   &     &    &   &     &   & 292\\ \hline \endarray


Pół dolara można rozmienić na 50 sposobów. Z kolei rozmieniać jednego dolara można na aż 292 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 \left(f_0,f_1,f_2,f_3,\ldots\right) zdefiniowany w następujący sposób:


\aligned f_0&=0,\\ f_1&=1,\\ f_n&=f_{n-1}+f_{n-2}\quad\textrm{dla}\ n\geq 2. \endaligned


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


\displaystyle \fGen{F}(x) =\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).


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


\fGen{F}(x)=\frac{x}{1-x-x^2}.      (11)


Celem, który chcemy osiągnąć to wykorzystanie funkcji \frac{x}{1-x-x^2} do przedstawienia współczynników f_n 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


\fGen{F}(x)=\frac{x}{1-x-x^2} =\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),


gdzie z_0=\frac{1+\sqrt{5}}{2} jest złotą liczbą oraz z_1=\frac{1-\sqrt{5}}{2} liczbą do niej sprzężoną. Korzystając z równania (7) otrzymujemy teraz


\displaystyle \fGen{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}}\sum_{n=0}^{\infty}{\left({z_0}^n-{z_1}^n\right)x^n}.


Tak więc dostajemy szybko znaną nam już postać zwartą f_n=\frac{1}{\sqrt{5}}\left({z_0}^n-{z_1}^n\right).

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

Stopień wielomianu deg{\fGen{P}(x)}=n, jeśli \fGen{P}(x)=p_0+p_1x+\ldots+p_nx^n.

Funkcja wymierna \fGen{R}(x) to funkcja postaci \frac{\fGen{P}(x)}{\fGen{Q}(x)}, gdzie \fGen{P}(x) oraz \fGen{Q}(x)\neq0 są wielomianami skończonego stopnia.

Obserwacja 7.6

Niech A(x) oraz \fGen{B}(x) będą wielomianami deg{\fGen{A}(x)}\geq deg{\fGen{B}(x)}. Wtedy istnieją wielomiany \fGen{Q}(x) oraz \fGen{R}(x) takie, że


\fGen{A}(x)=\fGen{Q}(x)\fGen{B}(x)+\fGen{R}(x),


gdzie deg{\fGen{R}(x)}< deg{\fGen{A}(x)}=deg{\fGen{Q}(x)}+deg{\fGen{B}(x)}.

Przykład

Niech


\fGen{A}(x)=3x^5+5x^4+2x^3+x^2+2\quad\textrm{oraz}\quad\fGen{B}(x)=x^3+2x^2-1.


Wtedy wielomiany


\fGen{Q}(x)=3x^2-x+3\quad\textrm{oraz}\quad\fGen{R}(x)=x+2


spełniają


\aligned\fGen{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\\ &=\fGen{Q}(x)\fGen{B}(x)+\fGen{R}(x). \endaligned


Ponadto deg{\fGen{A}(x)}=5=2+3=deg{\fGen{Q}(x)}+deg{\fGen{B}(x)}.

Wniosek 7.7

Niech \fGen{P}(x) oraz \fGen{Q}(x) będą wielomianami takimi, że deg{\fGen{P}(x)}\geq deg{\fGen{Q}(x)}. Wtedy funkcję wymierną \fGen{R}(x)=\fGen{P}(x)/ \fGen{Q}(x), można przedstawić w postaci


\fGen{R}(x)=\frac{\fGen{P}(x)}{\fGen{Q}(x)}=\fGen{A}(x)+\frac{\fGen{B}(x)}{\fGen{Q}(x)},


dla pewnych wielomianów \fGen{A}(x) oraz \fGen{B}(x)

spełniających deg{\fGen{B}(x)}<deg{\fGen{Q}(x)}.

Będziemy więc skupiali się jedynie nad takimi funkcjami wymiernymi \fGen{R}(x)=\fGen{P}(x)/\fGen{Q}(x), dla których deg{\fGen{P}(x)}<deg{\fGen{Q}(x)}.

Twierdzenie 7.8

Niech \fGen{P}(x) oraz \fGen{Q}(x) będą wielomianami takimi, że

  • deg{\fGen{P}(x)}<deg{\fGen{Q}(x)},
  • \fGen{Q}(x)=\fGen{S}(x)\fGen{T}(x), gdzie oba wielomiany \fGen{S}(x),\fGen{T}(x) są stopnia co najmniej 2,
  • q_0\neq0.

Wtedy istnieją wielomiany \fGen{A}(x) oraz \fGen{B}(x) takie, że deg{\fGen{A}(x)}<deg{\fGen{S}(x)} i deg{\fGen{B}(x)}<deg{\fGen{T}(x)} oraz


\frac{\fGen{P}(x)}{\fGen{Q}(x)} =\frac{\fGen{A}(x)}{\fGen{S}(x)}+\frac{\fGen{B}(x)}{\fGen{T}(x)}.


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


\fGen{R}(x)=\frac{\fGen{P}(x)}{\fGen{Q}(x)},


gdzie deg{\fGen{P}(x)}<deg{\fGen{Q}(x)}, oraz q_0\neq0. Załóżmy ponadto, że wielomian \fGen{Q}(x) rozkłada się na następujący iloczyn czynników liniowych


\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}.


Warto wspomnieć, że dalecy nie każdy wielomian ma taki rozkład. Na przykład 1+x^2 jest nierozkładalny i nieliniowy. Wykorzystując parokrotnie Twierdzenie 7.8 otrzymujemy wielomiany \fGen{P_1}(x),\ldots,\fGen{P_k}(x) takie, że


\fGen{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}},


gdzie deg{\fGen{P_i}(x)}<m_i. Na mocy Obserwacji 7.6 możemy sprowadzić wielomian \fGen{P_i}(x) do


\aligned\fGen{P_i}(x)&=\fGen{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}\\ &\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


gdzie m_i\geq deg{\fGen{P_i}(x)}>deg{\fGen{P_i^1}(x)}>deg{\fGen{P_i^2}(x)}>\ldots. W konsekwencji otrzymamy


\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)}.


Mnożąc teraz obie strony przez


\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}


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


\displaystyle \frac{1}{\left(1-\rho x\right)^{m+1}} =\sum_{n=1}^{\infty}{ { m+n \choose m } \rho^n x^n}


i w konsekwencji:


\displaystyle  [x^n]\fGen{R}(x)\ =\ \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 - 1} \right)}\rho_i^n.      (12)


Przykład

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


\fGen{R}(x)=\frac{x^2}{1-x-x^2+x^3}.


Wielomian 1-x-x^2+x^3 ma jeden podwójny pierwiastek x=1 oraz jeden pojedynczy x=-1. Poznana metoda rozwijania funkcji wymiernej w szereg daje więc


\fGen{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}.


Mnożąc obie strony przez \left(1-x\right)^2\cdot\left(1+x\right) otrzymujemy:


x^2=\alpha\left(1-x^2\right)+\beta\left(1+x\right)+\gamma\left(1-2x+x^2\right).


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


\left\lbrace\begin{array} {rrrcl} \alpha & +\ \beta &  +\ \gamma & = & 0\\ \alpha &          & -\ 2\gamma & = & 0\\ & -\ \beta &  +\ \gamma & = & 1. \end{array} \right.


Rozwiązaniem powyższego układu są wartości \alpha=-\frac{1}{4},\  \beta=\frac{1}{2},\ \gamma=-\frac{1}{4}. W konsekwencji otrzymujemy szereg


\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\\ &=x^2+x^3+2x^4+2x^5+3x^6+3x^7+4x^8+\ldots. \endaligned


Jeżeli mianownik \fGen{Q}(x) funkcji wymiernej \fGen{R}(x)=\frac{\fGen{P}(x)}{\fGen{Q}(x)} posiada jedynie pierwiastki jednokrotne, to następne twierdzenie znacznie przyspiesza rozkład \fGen{R}(x) na sumę.

Twierdzenie 7.9

Jeśli \fGen{R}(x)=\fGen{P}(x)/\fGen{Q}(x), gdzie \fGen{Q}(x)=q_0\cdot\left(1-\rho_1x\right)\cdot\ldots\cdot\left(1-\rho_1x\right) i liczby \rho_1,\ldots,\rho_l są parami różne, to w przypadku gdy \fGen{P}(x) jest wielomianem stopnia mniejszego niż l, zachodzi


\vect{x^n}\fGen{R}(x) =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)}.


Przykład

Mianownik \fGen{Q}(x) funkcji wymiernej


\fGen{R}(x)=\frac{\fGen{P}(x)}{\fGen{Q}(x)}=\frac{2x}{1-5x-2x^2+24x^3}.


ma trzy różne pierwiastki i można \fGen{R}(x) przedstawić jako


\fGen{R}(x)=\frac{2x}{\left(1+2x\right)\left(1-3x\right)\left(1-4x\right)}.


Na mocy Twierdzenia 7.9 otrzymujemy więc, że


\vect{x^n}\fGen{R}(x)=-\frac{2}{15}\left(-2\right)^n-\frac{6}{5}3^n+\frac{4}{3}4^n.


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


\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.


gdzie c_0,\ldots,c_{k-1},a_1,\ldots,a_k są liczbami rzeczywistymi (niezależnymi od parametru rekurencyjnego n).

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


\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.      (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 \left(r_0,r_1,r_2,\ldots\right) daje:


\aligned\fGen{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+\left(c_1-a_1c_0\right)x+a_1x\fGen{R}(x)+a_2x^2\fGen{R}(x), \endaligned


tak więc


\fGen{R}(x)\ =\ \frac{c_0+\left(c_1-a_1c_0\right)x}{1-a_1x-a_2x^2}


Dla funkcji \fGen{A}(x)=1-a_1x-a_2x^2=\left(1-\rho_1x\right)\left(1-\rho_2x\right) mogą zajść trzy przypadki:

  • \rho_1 \neq \rho_2 są różnymi liczbami rzeczywistymi. Wtedy
r_n\ =\ \alpha\rho_1^n+\beta\rho_2^n,


gdzie \alpha oraz \beta są liczbami rzeczywistymi.

  • \rho_1 = \rho_2. Wtedy
r_n\ =\ \left(\alpha n+\beta\right)\rho_1^n,


gdzie \alpha oraz \beta są liczbami rzeczywistymi.

  • \bigtriangledown Wartości \rho_1 oraz \rho_2 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


r_n\ =\ \alpha\rho_1^n+\beta\rho_2^n.


gdzie \alpha oraz \beta 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 k=2, otrzymujemy że


\fGen{R}(x)\ =\ \frac{\fGen{P}(x)}{1-a_1x-a_2x^2-\ldots-a_kx^k},


gdzie \fGen{P}(x) jest wielomianem co najwyżej stopnia k-1, zależnym od wartości c_0,\ldots,c_{k-1},a_1,\ldots,a_k. Korzystając z ogólnej metody rozwijania funkcji wymiernej w szereg, możemy odzyskać wyrazy ciągu r_n, jako współczynniki [x^n]\fGen{R}(x) zgodnie z równaniem (12).


Przykład

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


\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.


Ostatnia zależność prowadzi do funkcji tworzącej \fGen{R}(x) spełniającej


\fGen{R}(x)=x^2 + x\fGen{R}(x) + x^2\fGen{R}(x) - x^3\fGen{R}(x).


Po dokonaniu prostego wyliczenia dostajemy:


\fGen{R}(x)=\frac{x^2}{1-x-x^2+x^3}.


W przykładzie omawianym przy okazji metody rozwijania funkcji wymiernej w szereg, wyliczyliśmy współczynniki [x^n]\fGen{R}(x), a zatem mamy:


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.