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

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

Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle 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

Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle 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 mając do dyspozycji dowolnie wiele jednocentówek oraz pięciocentówek.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(10)} , ćwierćdolarówek Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(25)} , oraz półdolarówek Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(50)} wyglądają następująco:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(10)} , Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(25)} , i na końcu Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(50)} do możliwych rozmian uzyskujemy odpowiednio:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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:

Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(1)} , Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(5)} , Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(10)} , Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(25)} , oraz Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(50)} . Pomysłem pochodzącym od Pólya, było zastąpienie monety Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(1)} przez zmienną $x$, monety Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(5)} przez $x\cdot x\cdot x\cdot x\cdot x=x^5$ i analogicznie Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(10)} przez $x^{10}$, Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(25)} przez $x^{25}$, oraz Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta(50)} przez $x^{50}$. Uzyskujemy w ten sposób nieskończony szereg zmiennej $x$:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}} dla ciągu liczb rzeczywistych (lub zespolonych) $(g_0,g_1,g_2,g_3,\dots )$ to szereg funkcyjny zmiennej rzeczywistej (lub zespolonej) $x$ postaci

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\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 Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}} używać będziemy oznaczenia Parser nie mógł rozpoznać (nieznana funkcja „\vect”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}} jako szeregu liczb rzeczywistych (lub ogólniej zespolonych). Oczywistym pytaniem jest tu kwestia zbieżności szeregu Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}=\sum_{n=0}^{\infty}{g_nx^n}} . Z wykładu Analiza Matematyczna wiemy, że szereg Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}} jest zbieżny wtedy i tylko wtedy, gdy istnieje stała $M\ge 0$ ograniczająca wszystkie skończone początkowe sumy, tzn.

$\left|g_0\right|+\left|g_{1}x\right|+\left|g_2{x}^2\right|+\dots +\left|g_n{x}^n\right|\le M$

zachodzi dla dowolnego $n\ge 0$. Ponadto jeśli dla pewnej liczby $x_0\in \mathbb{ℝ}$ szereg Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x_0}=g_0+g_1x_0+g_2x_0^2+\ldots} jest zbieżny, to i także szereg Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x_1}=g_0+g_1x_1+g_2x_1^2+\ldots} jest zbieżny dla dowolnego $x_1\in \mathbb{ℝ}$ spełniającego $\left|x_1\right|\le \left|x_0\right|$. Możemy więc określić promień zbieżności szeregu jako taką liczbę Parser nie mógł rozpoznać (nieznana funkcja „\vect”): {\displaystyle r\in\mathbb{R}_*\cup{\left\{ {\infty} \right\}\ }=\vect{0,+\infty}} , że

• jeśli $x<r$, to Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}} jest zbieżny;

• jeśli $x>r$, to Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}} jest rozbieżny.

Szereg Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}=g_0+g_1x+g_2x^2+\ldots} można więc potraktować jako funkcję

$G:(-r,r)⟶\mathbb{ℝ},$

o wartościach Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}=\lim_{n\rightarrow\infty}{\left(g_0+g_1x+g_2x^2+\ldots+g_nx^n\right)}.} Oczywiście Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{0}=g_0} , więc dla $x=0$ szereg Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}} jest zbieżny.

Drugim podejściem, bardziej użytecznym w praktycznych obliczeniach i przekształceniach jest spojrzenie na szereg Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}=g_0+g_1x+g_2x^2+\ldots} jako formę zapisu ciągu $(g_0,g_1,g_2,\dots )$, 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 Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}=g_0+g_1x+g_2x^2+\ldots} jest funkcją tworzącą ciągu $(g_0,g_1,g_2,g_3,\dots )$, 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 Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{F}{x}=f_0+f_1x+f_2x^2+\ldots} oraz Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}=g_0+g_1x+g_2x^2+\ldots} mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{F}{x}\cdot\fGen{G}{x}} nazywać będziemy splotem szeregów Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{F}{x}} oraz Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}} .

Twierdzenie 7.2

Funkcja tworząca postaci

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \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 Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{U}{x}} taka, że Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{U}{x}\fGen{G}{x}=1} , wtedy i tylko wtedy, gdy $g_0\ne 0$.

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

Obserwacja 7.3

Dla dwu funkcji tworzących Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{F}{x}=f_0+f_1x+f_2x^2+\ldots} oraz Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}=g_0+g_1x+g_2x^2+\ldots} mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\alignedx”): {\displaystyle \alignedx^m\fGen{G}{x}&=&0+\ldots+0x^{m-1}+g_0x^m+g_1x^{m+1}+g_2x^{m+2}+\ldots\\ \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\\ \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\\ \fGen{G'}{x}&=&g_1+2g_2x+3g_3x^2+4g_4x^3+5g_5x^4+\ldots\\ \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\\ \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 \endaligned}

Funkcje tworzące w zliczaniu

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

${(1+x)}^m=(\genfrac{}{}{0ex}{}{m}{0})x^0+(\genfrac{}{}{0ex}{}{m}{1})x+(\genfrac{}{}{0ex}{}{m}{2})x^2+\dots +(\genfrac{}{}{0ex}{}{m}{m-1})x^{m-1}+(\genfrac{}{}{0ex}{}{m}{m})x^m=\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{m}{n})x^n.$

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle { 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{\mathbb{N}}$ spełniającego dodatkowo $y\ge n$, uogólniony symbol dwumianowy $(\genfrac{}{}{0ex}{}{y}{n})$ jest liczbą $n$-elementowych podzbiorów zbioru $y$-elementowego.

Twierdzenie 7.4

Dla liczby rzeczywistej $y$ oraz liczby naturalnej $n$ zachodzi

${(1+x)}^y=\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{y}{n})x^n.$

Wniosek 7.5

Dla liczby naturalnej $m$ zachodzi

$\frac{1}{{(1-x)}^{m+1}}=\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{m+n}{n})x^n.$

Dowód

Dowód zostawiony jest jako ćwiczenie [ex][ex newton for integer].

{{przyklad||| Policzmy sumę

$\sum _{k=0}^n{k}^2=1+4+9+\dots +n^2.$

Zacznijmy od znalezienia zwartej postaci funkcji tworzącej Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}=\sum_{n=0}^{\infty}n^2x^n} . Korzystając z Wniosku [[#wn_7.5|7.5] otrzymujemy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{1}{1-x}&=&\sum_{n=0}^{\infty}{n \choose n}x^n=\sum_{n=0}^{\infty}x^n,}      (8)

Parser nie mógł rozpoznać (błąd składni): {\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ę

$\sum _{n=0}^{\mathrm{\infty }}n{x}^n=\frac{1}{{(1-x)}^2}-\frac{1}{1-x}.$      (10)

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

$\frac{1}{{(1-x)}^3}=\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n+2}{n})x^n=\frac{1}{2}\sum _{n=0}^{\mathrm{\infty }}{n}^2{x}^n+\frac{3}{2}\sum _{n=0}^{\mathrm{\infty }}n{x}^n+\sum _{n=0}^{\mathrm{\infty }}{x}^n,$

co w połączeniu z równościami (9) oraz (10) daje zwartą postać funkcji tworzącej Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}} dla ciągu $1,4,9,\dots ,n^2,\dots$:

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\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,\dots ,1+4+9+\dots +n^2,\dots$, tzn. ciągu sum początkowych wyrazów ciągu $1,4,9,\dots ,n^2,\dots$. Aby uzyskać Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{H}{x}} wystarczy więc skorzystać ze wzoru (7) i podzielić Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \fGen{G}{x}} przez $1-x$. Tak więc poszukiwanym rozwiązaniem są współczynniki funkcji tworzącej

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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ść

Parser nie mógł rozpoznać (nieznana funkcja „\vect”): {\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

Parser nie mógł rozpoznać (nieznana funkcja „\fGen”): {\displaystyle \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}+\dots ,=\frac{1}{1-x^k}$

tak więc:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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,b_n=a_n+b_{n-5},c_n=b_n+c_{n-10},d_n=c_n+d_{n-25},e_n=d_n+e_{n-50}.$

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

$n$	0	5	10	15	2	25	30	35	40	45	50	55	60	65	70	75	80	85	90	95	100
$a_n$	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
$b_n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
$c_n$	1	2	4	6	9	12	16	10	25	30	36	42	49	56	64	72	81		100		121
$d_n$	1					13					49					121					242
$e_n$	1										50										292

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.