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] + (1) + (1) (1) + (1) (1)(1) + (1)(1)(1)(1)+\ldots \)
i analogicznie przeanalizujmy sumę dla pieciocentówek
\( A_5=[0] + (5) + (5)(5) + (5)(5)(5) + (5)(5)(5)(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.
\( \begin{align*} B= A_1 \times A_5 & =([0]+ (1)+ (1)(1)+ (1)(1)(1)+ (1)(1)(1)(1)+\ldots) \\ & \times([0]+(5) + (5)(5) + (5)(5)(5) + (5)(5)(5)(5)+\ldots) \\ & =[0] + (1) + (5) + (1)(1) + (1)(5) + (5)(5) + (1)(1)(1) + \ldots \end{align*} \)
Sumy wszystkich możliwości rozmiany za pomocą dziesięciocentówek \( (10) \), ćwierćdolarówek \((25) \), oraz półdolarówek \((50) \) wyglądają następująco:
\( \begin{align*} A_{10} & = [0]+(10)+(10)(10)+(10)(10)(10)+(10)(10)(10)(10)+\ldots \\ A_{25} & = [0]+(25)+(25)(25)+(25)(25)(25)+(25)(25)(25)(25)+\ldots \\ A_{50} & = [0]+(50)+(50)(50)+(50)(50)(50)+(50)(50)(50)(50)+\ldots. \end{align*} \)
Dodając kolejno monety \((10) \), \((25) \), i na końcu \( (50) \) do możliwych rozmian uzyskujemy odpowiednio:
\( \begin{align*} C & =B\times([0]+(10)+(10)(10)+(10)(10)(10)+(10)(10)(10)(10)+\ldots) \\ D & =C\times([0]+(25)+(25)(25)+(25)(25)(25)+(25)(25)(25)(25)+\ldots) \\ E & =D\times([0]+(50)+(50)(50) + (50)(50)(50) + (50)(50)(50)(50) + \ldots) \\ & =[0]+(1)+(5)+(10)+(25)+(50)+(1)(1)+(1)(5)+(1)(10) + \ldots \end{align*} \)
Grupując teraz składniki sumy \( E \) w podsumy o tych samych wartościach dostajemy wyrażenie:
\( \begin{array} {rcl} E & = & \big((1)\big)+\big((1)(1)\big)+\big((1)(1)(1)\big)+\big((1)(1)(1)(1)\big) \\ & & +\big((1)(1)(1)(1)(1)+(5)\big) \\ & & +\big((1)(1)(1)(1)(1)(1)+(5)(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 \( (1) \), \( (5) \), \( (10) \), \( (25) \), oraz \( (50) \). Pomysłem pochodzącym od Pólya, było zastąpienie monety \( (1) \) przez zmienną \( x \), monety \((5) \) przez \( x\cdot x\cdot x\cdot x\cdot x=x^5 \) i analogicznie \( (10) \) przez \( x^{10} \), \((25) \) przez \( x^{25} \), oraz \( (50) \) przez \( x^{50} \). Uzyskujemy w ten sposób nieskończony szereg zmiennej \( x \):
\( \begin{align*} {E}(x) & =(1+x+x^2+x^3\ldots)\cdot(1+x^5+x^{10}+x^{15}\ldots)\cdot(1+x^{10}+x^{20}+x^{30}\ldots) \\ & \cdot(1+x^{25}+x^{50}+x^{75}\ldots)\cdot(1+x^{50}+x^{100}+x^{150}\ldots) \\ & =1+x+x^2+x^3+x^4+2x^5+2x^6+2x^7+2x^8+2x^9+4x^{10}+\ldots \end{align*} \)
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 \({G}(x) \) dla ciągu liczb rzeczywistych (lub zespolonych) \( (g_0,g_1,g_2,g_3,\ldots) \) to szereg funkcyjny zmiennej rzeczywistej (lub zespolonej) \( x \) postaci
\( \displaystyle {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 \({G}(x) \) używać będziemy oznaczenia \( {x^n} {G}(x)=g_n \).
Uwaga Jak traktowac funkcje tworzące
Na funkcje tworzące można spojrzeć dwoiście. Pierwszym sposobem jest potraktowanie \( {G}(x) \) jako szeregu liczb rzeczywistych (lub ogólniej zespolonych). Oczywistym pytaniem jest tu kwestia zbieżności szeregu \( \displaystyle{G}(x)=\sum_{n=0}^{\infty}{g_nx^n} \). Z wykładu Analiza Matematyczna wiemy, że szereg \( {G}(x) \) jest zbieżny, jeśli istnieje stała \( M\geq0 \) ograniczająca wszystkie skończone początkowe sumy, tzn.
\( \vert g_0\vert+\vert g_1x\vert+\vert g_2x^2\vert+\ldots+\vert g_nx^n\vert\leq M \)
zachodzi dla dowolnego \( n\geq0 \). Ponadto jeśli dla pewnej liczby \( x_0\in\mathbb{R} \) szereg \( {G}(x_0)=g_0+g_1x_0+g_2x_0^2+\ldots \) jest zbieżny, to i także szereg \( {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 \( \vert x_1\vert\leq\vert x_0\vert \). Możemy więc określić promień zbieżności szeregu jako taką liczbę \( r\in\mathbb{R}_*\cup{\{ {\infty} \}\ }= {0,+\infty} \), że jeśli \( \vert x\vert < r \), to \( {G}(x) \) jest zbieżny.
Szereg \({G}(x)=g_0+g_1x+g_2x^2+\ldots \) można więc potraktować jako funkcję
\( G:(-r,r)\longrightarrow\mathbb{R}, \)
o wartościach \( \displaystyle {G}(x)=\lim_{n\to\infty}{(g_0+g_1x+g_2x^2+\ldots+g_nx^n)}. \) Oczywiście \( {G}(0)=g_0 \), więc dla \( x=0 \) szereg \( {G}(x) \) jest zbieżny.
Drugim podejściem, bardziej użytecznym w praktycznych obliczeniach i przekształceniach jest spojrzenie na szereg \( {G}(x)=g_0+g_1x+g_2x^2+\ldots \) jako formę zapisu ciągu \( (g_0,g_1,g_2,\ldots) \), 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 \( {G}(x)=g_0+g_1x+g_2x^2+\ldots \) jest funkcją tworzącą ciągu \( (g_0,g_1,g_2,g_3,\ldots) \), 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 \( {F}(x)=f_0+f_1x+f_2x^2+\ldots \) oraz \( {G}(x)=g_0+g_1x+g_2x^2+\ldots \) mamy:
\( \begin{align*} {F}(x)= {G}{x} & \Leftrightarrow f_0=g_0,\ f_1=g_1,\ f_2=g_2,\ \ldots \\ & & \\ \alpha\cdot {F}(x)+\beta\cdot {G}{x} & = \sum_{n=0}^{\infty}{(\alpha\cdot f_n+\beta\cdot g_n)x^n} \\ & =(\alpha\cdot f_0+\beta\cdot g_0) + (\alpha\cdot f_1+\beta\cdot g_1)x + (\alpha\cdot f_2+\beta\cdot g_2)x^2 + \ldots \\ & & \\ {F}(x)\cdot {G}(x) & =\sum_{n=0}^{\infty}(\sum_{k=0}^n f_k g_{n-k}) x^n \\ & = f_0g_0 + (f_0g_1+f_1g_0)x \\ & + (f_0g_2+f_1g_1+f_2g_0)x^2 \\ & + (f_0g_3+f_1g_2+f_2g_1+f_3g_0)x^3+\ldots \\ \end{align*} \)
Wyrażenie \( {F}(x)\cdot {G}(x) \) nazywać będziemy splotem szeregów \( {F}(x) \) oraz \({G}(x) \).
Twierdzenie 7.2
Funkcja tworząca postaci
\( {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 \( {U}(x) \) taka, że \( {U}(x) {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 \({F}(x)=f_0+f_1x+f_2x^2+\ldots \) oraz \( {G}(x)=g_0+g_1x+g_2x^2+\ldots \) mamy:
\( \displaystyle x^m {G}(x) = 0+\ldots+0x^{m-1}+g_0x^m+g_1x^{m+1}+g_2x^{m+2}+\ldots \) (2)
\( \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 \) (3)
\( \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 \) (4)
\( \displaystyle {G'}(x) = g_1+2g_2x+3g_3x^2+4g_4x^3+5g_5x^4+\ldots \) (5)
\( \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 \) (6)
\( \displaystyle \frac{ {G}(x)}{1-x} = g_0+(g_0+g_1)x+(g_0+g_1+g_2)x^2+\ldots \) (7)