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 Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta{1}} , pięciocentówek Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta{5}} , 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ówki Parser nie mógł rozpoznać (nieznana funkcja „\moneta”): {\displaystyle \moneta{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ę Parser nie mógł rozpoznać (nieznana funkcja „\brak”): {\displaystyle \brak} , 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 „\brak”): {\displaystyle A_1=\brak+\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 „\brak”): {\displaystyle A_5=\brak+\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 „\alignedB”): {\displaystyle \alignedB= A_1 \times A_5 &=&\left(\brak+\moneta{1}+\moneta{1}\moneta{1}+\moneta{1}\moneta{1}\moneta{1}+\moneta{1}\moneta{1}\moneta{1}\moneta{1}+\ldots\right)\\ &&\times\left(\brak+\moneta{5}+\moneta{5}\moneta{5}+\moneta{5}\moneta{5}\moneta{5}+\moneta{5}\moneta{5}\moneta{5}\moneta{5}+\ldots\right)\\ &=&\brak+\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 „\alignedA”): {\displaystyle \alignedA_{10} &=& \brak+\moneta{10}+\moneta{10}\moneta{10}+\moneta{10}\moneta{10}\moneta{10}+\moneta{10}\moneta{10}\moneta{10}\moneta{10}+\ldots\\ A_{25} &=& \brak+\moneta{25}+\moneta{25}\moneta{25}+\moneta{25}\moneta{25}\moneta{25}+\moneta{25}\moneta{25}\moneta{25}\moneta{25}+\ldots\\ A_{50} &=& \brak+\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 „\alignedC”): {\displaystyle \alignedC&=&B\times\left(\brak+\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(\brak+\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(\brak+\moneta{50}+\moneta{50}\moneta{50}+\moneta{50}\moneta{50}\moneta{50}+\moneta{50}\moneta{50}\moneta{50}\moneta{50}+\ldots\right)\\ &=&\brak+\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ę.