Informatyka MIMUW

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)