--- title: "Funkcje tworzące" lecture_number: 4 haa_solutions: true haa_exercises: true file_format: mystnb kernelspec: name: sagemath display_name: SageMath --- ```{include} ../_includes/sagecell-loader.md ``` # Funkcje tworzące :::{narration} W wielu zagadnieniach kombinatorycznych szukamy wzoru jawnego (lub choćby efektywnego sposobu obliczania) na wyraz $a_n$ ciągu, który zlicza obiekty pewnego typu -- np. liczbę podziałów zbioru, liczbę sposobów nawiasowania iloczynu, liczbę dróg na kracie itp. Często taki ciąg zadany jest **rekurencyjnie**, a bezpośrednie rozwikłanie rekurencji bywa trudne. **Funkcje tworzące** {index}`funkcja tworząca` to metoda kodowania całego ciągu $(a_n)_{n\in \nn_0}$ za pomocą jednego obiektu analitycznego -- szeregu potęgowego -- na którym rekurencje przekładają się na (zazwyczaj prostsze) równania algebraiczne. ::: ## Ciągi rekurencyjne :::{prf:definition} **Ciągiem rekurencyjnym** {index}`ciąg rekurencyjny` nazywamy ciąg liczbowy $(a_n)_{n\in \nn_0}$, którego wyrazy -- począwszy od pewnego miejsca -- są wyznaczone przez wcześniejsze wyrazy tego ciągu za pomocą ustalonego wzoru {index}`równanie rekurencyjne` (**równania rekurencyjnego**), przy zadanych **warunkach początkowych**. ::: :::{prf:example} Ciągi rekurencyjne pojawiają się naturalnie przy modelowaniu zjawisk, w których stan (koszt, liczba obiektów, liczba operacji) w kroku $n$ zależy od stanów w krokach wcześniejszych -- co jest szczególnie częste przy analizie algorytmów rekurencyjnych i przy zliczaniu struktur danych. Poniżej trzy typowe przykłady takich zależności -- ich jawne rozwiązanie poznamy w dalszej części wykładu, właśnie za pomocą funkcji tworzących. 1. **Rekurencja liniowa** Rozważmy funkcję rekurencyjną, która na każdym poziomie rekursji rozgałęzia się na $q\in\nn$ wywołań potomnych (np. funkcja obsługująca listę złożoną z $q$ mniejszych list tego samego typu, wywołująca się rekurencyjnie dla każdej z nich). Niezależnie od tego, na każdym poziomie rekursji -- bez względu na to, ile jest w danym momencie aktywnych wywołań -- wykonywanych jest dodatkowo $c\in\nn$ stałych wywołań pomocniczych, niezwiązanych z dalszym rozgałęzieniem (np. jednorazowy zapis do dziennika zdarzeń albo sprawdzenie globalnego warunku stopu na danym poziomie). Niech $a_n$ oznacza łączną liczbę wywołań (rekurencyjnych i pomocniczych) na $n$-tym poziomie rekursji. Wtedy ```{math} a_0 = 1, \qquad a_n = q\cdot a_{n-1} + c, \quad n\in \nn. ``` Dla $c=0$ dostajemy zwykły ciąg geometryczny -- rozgałęzienie bez narzutu. 2. **Liczby Fibonacciego** Na ile sposobów można pokonać schody o $n$ stopniach, jeśli jednym krokiem można pokonać $1$ lub $2$ stopnie? Oznaczmy tę liczbę przez $\mathcal F_n .$ Rozpatrując długość ($1$ lub $2$) pierwszego kroku, otrzymujemy ```{math} \mathcal F_0 = 0,\quad \mathcal F_1 = 1, \qquad \mathcal F_n = \mathcal F_{n-1}+\mathcal F_{n-2}, \quad n\in \nn_2. ``` Istotnie, aby dostać się na $n$-ty stopień, trzeba w poprzednim kroku stanąć na stopniu $(n-1)$-szym lub $(n-2)$-gim. Jest to klasyczny przykład programowania dynamicznego. 3. **Liczby Catalana** Ile jest poprawnych (zbalansowanych) ciągów nawiasów złożonych z $n$ nawiasów otwierających i $n$ nawiasów zamykających -- tzn. takich, w których w każdym prefiksie liczba nawiasów zamykających nie przekracza liczby nawiasów otwierających? Dokładnie taki warunek sprawdza np. parser kompilatora, weryfikując zbalansowanie nawiasów w kodzie źródłowym. Ten sam schemat opisuje też dopuszczalne kolejności $n$ operacji `push` i $n$ operacji `pop` na stosie (nawias otwierający = `push`, zamykający = `pop`). Oznaczmy szukaną liczbę przez $C_n .$ Ustalmy $i\in\{0,\ldots,n-1\}$ -- liczbę par nawiasów **wewnątrz** pierwszej pary domykającej się w całym ciągu. Ciąg rozpada się wówczas jednoznacznie na ```{math} \underbrace{(\ \cdots\ )}_{i \text{ par wewnątrz}} \ \underbrace{\cdots}_{n-1-i \text{ par po}}, ``` gdzie wnętrze pierwszej pary jest dowolnym poprawnym ciągiem $i$ par nawiasów ($C_i$ możliwości), a reszta -- dowolnym poprawnym ciągiem pozostałych $n-1-i$ par ($C_{n-1-i}$ możliwości). Na przykład dla $n=7$ i $i=3$ (czyli $n-1-i=3$) trzy spośród takich ciągów długości $2n=14$ to: ```{math} \begin{aligned} & \underbrace{(\ ()()()\ )}_{i=3 \text{ pary wewnątrz}}\ \underbrace{()()()}_{n-1-i=3 \text{ pary po}}, \\ & \underbrace{(\ (())()\ )}_{i=3 \text{ pary wewnątrz}}\ \underbrace{()(())}_{n-1-i=3 \text{ pary po}}, \\ & \underbrace{(\ ((()))\ )}_{i=3 \text{ pary wewnątrz}}\ \underbrace{(()())}_{n-1-i=3 \text{ pary po}}, \end{aligned} ``` gdzie w każdym przypadku pierwszy (najbardziej wysunięty na lewo) nawias otwierający domyka się dopiero po $3$ parach znajdujących się w jego wnętrzu, pozostawiając kolejne $3$ pary na zewnątrz, po prawej stronie. Sumując po wszystkich $i\in\{0,\ldots,n-1\}$: ```{math} C_n = \sum_{i=0}^{n-1} C_i\, C_{n-1-i}, \qquad n\in \nn, ``` czyli, po przesunięciu wskaźnika (i przyjęciu $C_0=1$ dla ciągu pustego): ```{math} C_{n+1} = \sum_{i=0}^{n} C_i\, C_{n-i}, \quad n\in \nn_0. ``` ::: ## Funkcja tworząca ciągu :::{prf:definition} **Funkcją tworzącą** {index}`funkcja tworząca` ciągu liczbowego $(a_n)_{n\in \nn_0}$ nazywamy (formalny) szereg potęgowy ```{math} G(x) = \sum_{n=0}^{\infty} a_n x^n. ``` ::: :::{prf:example} :label: lec-04-example-01 1. Dla ciągu stałego $a_n = 1$ mamy $$ G(x) = \sum_{n=0}^\infty x^n = \frac 1 {1-x} \quad \text{ dla } |x|<1. $$ 2. Ogólniej, dla ciągu geometrycznego $a_n = q^n$ ($q\in\rr$ ustalone) mamy ```{math} G(x) = \sum_{n=0}^{\infty} q^n x^n = \sum_{n=0}^{\infty} (qx)^n = \frac{1}{1-qx}. ``` 3. Dla ustalonego $m\in\nn$ i ciągu $a_n = \binom{m}{n}$ (przyjmujemy $a_n=0$ dla $n>m$) mamy, na mocy dwumianu Newtona, ```{math} G(x) = \sum_{n=0}^{\infty} \binom{m}{n} x^n = \sum_{n=0}^{m} \binom{m}{n} x^n = (1+x)^m. ``` 4. Dla ciągu $a_n = \dfrac{1}{n!}$ mamy ```{math} G(x) = \sum_{n=0}^{\infty} \frac{x^n}{n!} = e^x. ``` 5. Dla ciągu $a_n = \dfrac{(-1)^{n+1}}{n}$, $n\in \nn$ (oraz $a_0=0$), mamy ```{math} G(x) = \sum_{n=1}^{\infty} \frac{(-1)^{n+1}}{n} x^n = \ln(1+x) \quad \text{ dla } -1 < x \leq 1. ``` ::: ## Uogólniony wzór dwumianowy Newtona :::{prf:definition} Niech $x \in \mathbb{R}$ będzie taką liczbą rzeczywistą, że $|x| < 1$, a $r \in \mathbb{R}$ dowolną liczbą rzeczywistą. **Uogólnionym współczynnikiem dwumianowym** {index}`uogólniony współczynnik dwumianowy` $\binom{r}{k}$ dla nieujemnych liczb całkowitych $k$ nazywamy liczbę: ```{math} \binom{r}{k} = \frac{r(r-1)(r-2)\cdots(r-k+1)}{k!} \quad \text{dla } k \ge 1, \quad \text{oraz} \quad \binom{r}{0} = 1. ``` ::: :::{prf:example} Obliczmy uogólniony współczynnik dwumianowy $\binom{-3}{4}$ oraz $\binom{\frac{1}{2}}{3}$: - $\displaystyle \dbinom{-3}{4} = \frac{(-3)(-4)(-5)(-6)}{4!} = \frac{360}{24} = 15 .$ - $\displaystyle \dbinom{\frac{1}{2}}{3} = \frac{\frac{1}{2} \cdot \left(\frac{1}{2}-1\right) \cdot \left(\frac{1}{2}-2\right)}{3!} = \frac{\frac{1}{2} \cdot \left(-\frac{1}{2}\right) \cdot \left(-\frac{3}{2}\right)}{6} = \frac{\frac{3}{8}}{6} = \frac{1}{16} .$ ::: :::{prf:theorem} Uogólniony wzór dwumianowy Newtona Dla dowolnej liczby rzeczywistej $r$ oraz $z$ spełniającego $|z| < 1$ zachodzi rozwinięcie w szereg potęgowy: ```{math} (1+z)^r = \sum_{k=0}^{\infty} \binom{r}{k} z^k = 1 + r z + \frac{r(r-1)}{2!} z^2 + \frac{r(r-1)(r-2)}{3!} z^3 + \cdots ``` ::: :::{exercise} :label: m-lec-04-ex-01 :class: [exercise] Pokażmy, że ```{math} \sqrt{1-4x} = 1 - 2 \cdot \sum_{n=1}^{\infty} \frac{1}{n} \binom{2n-2}{n-1} x^n \, . ``` ::: :::{solution-without-reference} :class: [solution] dropdown Wyznaczmy rozwinięcie funkcji $$ f(x) = \sqrt{1-4x} = (1 - 4x)^{\frac{1}{2}} $$ dla $|4x| < 1$ (czyli $|x| < \frac{1}{4}$). Stosując uogólniony wzór dwumianowy dla $r = \dfrac{1}{2}$ oraz zmiennej $z = -4x$ otrzymujemy ```{math} \sqrt{1-4x} = \sum_{n=0}^{\infty} \binom{\frac{1}{2}}{n} (-4x)^n = \sum_{n=0}^{\infty} \binom{\frac{1}{2}}{n} (-1)^n 4^n x^n. ``` Wyznaczmy ogólny wzór na współczynnik $\displaystyle \binom{\frac{1}{2}}{n} (-1)^n 4^n$ dla $n \ge 1 .$ Zaczynamy od obliczenia z definicji ```{math} \binom{\frac{1}{2}}{n} = \frac{\frac{1}{2} \cdot \left(-\frac{1}{2}\right) \cdot \left(-\frac{3}{2}\right) \cdots \left(\frac{1}{2}-n+1\right)}{n!} = \frac{(-1)^{n-1} \cdot 1 \cdot 3 \cdot 5 \cdots (2n-3)}{2^n \cdot n!}. ``` Mnożąc to przez $(-1)^n 4^n$, otrzymujemy ```{math} \binom{\frac{1}{2}}{n} (-1)^n 4^n = \frac{(-1)^{2n-1} \cdot 1 \cdot 3 \cdot 5 \cdots (2n-3) \cdot 2^{2n}}{2^n \cdot n!} = - \frac{1 \cdot 3 \cdot 5 \cdots (2n-3) \cdot 2^n}{n!}. ``` W celu uproszczenia tego wyrażenia zauważmy, że $$ (2n-2)! & = \underbrace{[1 \cdot 3 \cdot 5 \cdots (2n-3)]}_{\text{czynniki nieparzyste}} \;\cdot\; \underbrace{[2 \cdot 4 \cdot 6 \cdots (2n-2)]}_{\text{czynniki parzyste}} \\ & = [1 \cdot 3 \cdot 5 \cdots (2n-3)]\cdot 2^{n-1} \cdot [1 \cdot 2 \cdot 3 \cdots (n-1)] \\ & = [1 \cdot 3 \cdots (2n-3)] \cdot 2^{n-1}(n-1)! $$ Dzieląc obie strony przez $2^{n-1}(n-1)!$, dostajemy $$ 1 \cdot 3 \cdots (2n-3) = \frac{(2n-2)!}{2^{n-1}(n-1)!} . $$ Stąd wniosnujemy, że $$ \binom{\frac{1}{2}}{n} (-1)^n 4^n & = - \frac{1 \cdot 3 \cdot 5 \cdots (2n-3) \cdot 2^n}{n!} \\ & = - \frac{(2n-2)! \cdot 2^n}{2^{n-1}(n-1)! \cdot n!} \\ & = - \frac{2}{n} \binom{2n-2}{n-1} = - \frac{1}{2n-1} \binom{2n}{n}. $$ Ostatecznie rozwinięcie funkcji $\sqrt{1-4x}$ przybiera postać ```{math} \sqrt{1-4x} = 1 - \sum_{n=1}^{\infty} \frac{2}{n} \binom{2n-2}{n-1} x^n \, . ``` ::: ## Działania na funkcjach tworzących ### Liniowość i translacja :::{prf:theorem} :label: thm-05-slownik Niech $(a_n)_{n\in \nn_0}$ będzie ciągiem o funkcji tworzącej $G(x)$, a $(b_n)_{n\in \nn_0}$ ciągiem o funkcji tworzącej $H(x) .$ Wówczas: 1. **Liniowość.** Dla dowolnych $\alpha,\beta\in\rr$ funkcją tworzącą ciągu $(\alpha a_n + \beta b_n)_{n\in \nn_0}$ jest $\alpha G(x) + \beta H(x) .$ 2. **Translacja.** Dla dowolnego $k\in\nn$ ```{math} \sum_{n=0}^{\infty} a_{n+k}\, x^n = \frac{G(x) - a_0 - a_1 x - \cdots - a_{k-1}x^{k-1}}{x^k}. ``` W szczególności $\quad \displaystyle \sum_{n=0}^{\infty} a_{n+1}\, x^n = \frac{G(x) - a_0}{x}.$ ::: :::{proof} :class: [proof] dropdown 1. Bezpośrednio z definicji funkcji tworzącej, współczynnik przy $x^n$ w $\alpha G(x)+\beta H(x)$ wynosi ```{math} \alpha a_n + \beta b_n, ``` czyli jest dokładnie $n$-tym wyrazem ciągu $(\alpha a_n+\beta b_n)$ -- co należało pokazać. 2. (dla $k=1$) Mnożąc $G(x)=\sum_{n=0}^{\infty}a_n x^n$ przez $x$ i przesuwając wskaźnik sumowania: ```{math} x\,G(x) = \sum_{n=0}^{\infty} a_n x^{n+1} = \sum_{n=1}^{\infty} a_{n-1}\,x^n. ``` Z drugiej strony, wydzielając wyraz wolny szeregu $G(x)$: ```{math} G(x) = a_0 + \sum_{n=1}^{\infty} a_n x^n = a_0 + \sum_{n=0}^{\infty} a_{n+1} x^{n+1} = a_0 + x\sum_{n=0}^{\infty} a_{n+1}\,x^n, ``` skąd ```{math} \sum_{n=0}^{\infty} a_{n+1}\,x^n = \frac{G(x)-a_0}{x}. ``` Dla ogólnego $k\geq 2$ rozumowanie jest analogiczne. ::: :::{prf:example} Rozwiążmy rekurencję (tzn. znajdźmy jawny wzór na $n$-ty wyraz ciągu $(a_n)$) ```{math} a_0=1, \qquad a_{n+1} = 2a_n + 3, \quad n\in \nn_0. ``` Niech $\displaystyle a(x)=\sum_{n=0}^\infty a_n x^n .$ Ze wzoru na przesunięcie ($k=1$, {prf:ref}`thm-05-slownik`) oraz z liniowości: ```{math} \frac{a(x)-a_0}{x} & = \sum_{n=0}^{\infty} a_{n+1}x^n = \sum_{n=0}^{\infty} (2a_n+3)x^n \\ & = 2\cdot \sum_{n=0}^{\infty} a_n x^n + 3\cdot\sum_{n=0}^{\infty} x^n \\ & = 2\,a(x) + \frac{3}{1-x}. ``` Ponieważ $a_0=1$, to po pomnożeniu obustronnie przez $x$ otrzymamy ```{math} a(x) - 1 & = 2x\,a(x) + \frac{3x}{1-x} \\ a(x)(1-2x) & = 1+\frac{3x}{1-x} = \frac{1+2x}{1-x} \\ a(x) & = \frac{1+2x}{(1-x)(1-2x)}. ``` Rozkład na ułamki proste $$ \frac{1+2x}{(1-x)(1-2x)} = \frac{4}{1-2x}-\frac{3}{1-x} $$ daje ```{math} a(x) & = \frac{4}{1-2x} - \frac{3}{1-x} \\ & = \sum_{n=0}^{\infty} 4\cdot2^n\,x^n - \sum_{n=0}^{\infty} 3\,x^n \\ & = \sum_{n=0}^{\infty} \Paren{2^{n+2}-3}x^n. ``` Zatem $a_n = 2^{n+2}-3 .$ ::: :::{prf:example} Rozwiążmy rekurencję Fibonacciego: $$ \mathcal F_0=0,\quad \mathcal F_1=1, \qquad \mathcal F_n = \mathcal F_{n-1}+\mathcal F_{n-2}, \quad n\geq2. $$ Niech $\displaystyle F(x)=\sum_{n=0}^{\infty} \mathcal F_n\, x^n .$ Mnożąc rekurencję przez $x^n$ i sumując po $n\geq2$: $$ A = \sum_{n=2}^{\infty}\mathcal F_n\, x^n & = \sum_{n=2}^{\infty}\mathcal F_{n-1}\, x^n + \sum_{n=2}^{\infty}\mathcal F_{n-2}\, x^n \\ & = x\sum_{n=1}^{\infty}\mathcal F_{n}\, x^{n} + x^2\sum_{n=0}^{\infty} \mathcal F_{n}\, x^{n} = x\, B + x^2 F(x). $$ Ponieważ $$ A = \sum_{n=2}^{\infty}\mathcal F_n\, x^n & = \Paren{\sum_{n=0}^{\infty} \mathcal F_n\, x^n} - \mathcal F_0 - \mathcal F_1 x \\ & = F(x) - \mathcal F_0 - \mathcal F_1 x = F(x)-x $$ oraz analogicznie $$ B = \sum_{n=1}^{\infty}\mathcal F_n\, x^n = F(x)-\mathcal F_0 = F(x), $$ otrzymujemy $$ A & = x\, B + x^2 F(x) \\ F(x) - x & = x F(x) + x^2 F(x) \\ F(x)\Paren{1-x-x^2} & = x \\ F(x) & = \frac{x}{1-x-x^2}. $$ Niech $$ \phi_1 = \dfrac{1+\sqrt 5}2,\quad \phi_2 = \dfrac{1-\sqrt 5}2 $$ będą pierwiastki mianownika $1-x-x^2 .$ To tzw. **złota liczba** i jej "sprzężenie". Ponieważ $\phi_1 + \phi_2=1$ i $\phi_1 \cdot \phi_2=-1$, zachodzi $$ 1-x-x^2 = (1-\phi_1 x)(1-\phi_2 x). $$ Rozkład funkcji $F$ na ułamki proste daje $$ F(x) & = \frac{x}{(1-\phi_1 x)(1-\phi_2 x)} \\ & = \frac{1}{\sqrt5}\Paren{\frac{1}{1-\phi_1 x} - \frac{1}{1-\phi_2 x}} \\ & = \frac{1}{\sqrt5}\sum_{n=0}^{\infty} \Paren{\phi_1^{n}-\phi_2^{n}}x^n. $$ Tym samym, otrzymujemy **wzór Bineta** $$ \mathcal F_n = \dfrac{\Paren{\dfrac{1+\sqrt5}2}^{n}-\Paren{\dfrac{1-\sqrt5}2}^{n}}{\sqrt 5}. $$ ::: ### Splot ciągów :::{prf:definition} :label: def-05-splot **Splotem** {index}`splot ciągów` ciągów $(a_n)_{n\in \nn_0}$ i $(b_n)_{n\in \nn_0}$ nazywamy ciąg $(c_n)_{n\in \nn_0}$ zadany wzorem ```{math} c_n = \sum_{i=0}^{n} a_i b_{n-i}. ``` ::: :::{prf:theorem} :label: lec-04-thm-03 Jeśli $(c_n)$ jest splotem ciągów $(a_n)$ i $(b_n)$, to dla funkcji tworzących tych ciągów $c(x), a(x)$ i $b(x)$ zachodzi tożsamość $$ c(x) = a(x)\cdot b(x). $$ Innymi słowy, funkcja tworząca splotu dwóch ciągów jest iloczynem ich funkcji tworzących. ::: :::{proof} :class: [proof] dropdown Zauważmy, że $$ \begin{aligned} \sum_{n=0}^{\infty} c_n x^n & = c(x) = a(x)\cdot b(x) = \left(\sum_{n=0}^{\infty} a_{n}x^n\right)\cdot \left(\sum_{n=0}^{\infty} b_{n}x^n\right) \\ & = (a_0 + a_1 x + a_2 x^2 + \ldots )(b_0 + b_1 x + b_2 x^2 + \ldots ) \\ & = a_0 b_0 + (a_0 b_1 + a_1 b_0) x + (a_0 b_2 + a_1 b_1 + a_2 b_0) x^2 + \ldots \\ & = \sum_{n=0}^{\infty} \left(\sum_{i=0}^{n}a_{i}b_{n-i}\right)x^n \, . \end{aligned} $$ Stąd $$ c_n = \sum_{i=0}^{n} a_i b_{n-i}. $$ ::: :::{prf:example} :label: lec-04-example-06 Splot ciągu stałego $a_n=1$ ze sobą to $\displaystyle c_n = \sum_{i=0}^n 1 = n+1 .$ Zgodnie z powyższym twierdzeniem otrzymujemy ```{math} \sum_{n=0}^{\infty} (n+1)x^n = \Paren{\frac{1}{1-x}}^2 = \frac{1}{(1-x)^2}. ``` ::: ::::{exercise} :class: [exercise] Znajdźmy wyraz ogólny ciągu $(a_n)_{n\in\nn_0}$, którego funkcją tworzącą jest ```{math} f(x) = \frac{2-x}{(1-x)^2(1-2x)}. ``` :::: :::{solution-without-reference} :class: [solution] dropdown Mianownik ma **podwójny** pierwiastek $x=1$, więc rozkład na ułamki proste ma postać ```{math} f(x) = \frac{A}{1-x} + \frac{B}{(1-x)^2} + \frac{C}{1-2x}. ``` Mnożąc obustronnie przez $(1-x)^2(1-2x)$: ```{math} 2-x = A(1-x)(1-2x) + B(1-2x) + C(1-x)^2. ``` Podstawiając $x=1$: $2-1=1=B(1-2)=-B$, więc $B=-1 .$ Podstawiając $x=\tfrac12$: $2-\tfrac12=\tfrac32=C\Paren{1-\tfrac12}^2=\tfrac C4$, więc $C=6 .$ Porównując współczynniki przy $x^2$ po obu stronach ($0$ po lewej, $2A+C$ po prawej): $2A+6=0$, więc $A=-3$ (sprawdzenie przy $x=0$: $A+B+C=-3-1+6=2$, zgadza się z lewą stroną). Zatem ```{math} f(x) = \frac{-3}{1-x} - \frac{1}{(1-x)^2} + \frac{6}{1-2x}. ``` Korzystając z {prf:ref}`lec-04-example-06`, gdzie znaleźliśmy $$ \dfrac{1}{(1-x)^2}=\sum_{n=0}^{\infty}(n+1)x^n $$ oraz geometrycznych szeregów potęgowych (patrz {prf:ref}`lec-04-example-01`): $$ \dfrac1{1-x}=\sum_{n=0}^{\infty}x^n, \qquad \dfrac1{1-2x}=\sum_{n=0}^{\infty}2^nx^n, $$ otrzymujemy ```{math} f(x) = \sum_{n=0}^{\infty}\Paren{-3-(n+1)+6\cdot2^n}x^n = \sum_{n=0}^{\infty}\Paren{6\cdot2^n-n-4}x^n. ``` Zatem $a_n = 6\cdot2^n-n-4 .$ ::: :::{prf:proposition} :label: rem-05-sumy-czesciowe Jeśli $(a_n)_{n\in\nn_0}$ ma funkcję tworzącą $a(x)$, to ciąg **sum częściowych** $\displaystyle s_n = \sum_{i=0}^{n} a_i$ ma funkcję tworzącą ```{math} s(x) = \frac{a(x)}{1-x}. ``` ::: :::{proof} :class: [proof] dropdown Niech $b_n=1$ dla każdego $n\in\nn_0 .$ Funkcją tworzącą ciągu $(b_n)$ jest $b(x) = \dfrac1{1-x}$ -- to pierwszy przykład tego wykładu. Pokażmy, że $(s_n)$ jest splotem ciągów $(a_n)$ i $(b_n) .$ Z definicji splotu: ```{math} \sum_{i=0}^n a_i\, b_{n-i} = \sum_{i=0}^n a_i \cdot 1 = \sum_{i=0}^n a_i = s_n. ``` Z twierdzenia o splocie ({prf:ref}`lec-04-thm-03`) otrzymujemy, że funkcją tworzącą ciągu $(s_n)$ jest ```{math} a(x)\cdot b(x) = a(x)\cdot\frac{1}{1-x} = \frac{a(x)}{1-x}. ``` ::: ::::{exercise} :class: [exercise] Znajdźmy funkcję tworzącą ciągu liczb trójkątnych ```{math} T_n = 1+2+\cdots+(n+1) = \binom{n+2}{2} = \frac {n (n+1)} 2, \qquad n\in\nn_0. ``` :::: :::{solution-without-reference} :class: [solution] dropdown Zauważmy, że $T_n$ jest sumą częściową ciągu $(n+1)_{n\in\nn_0}$: ```{math} T_n = \sum_{i=0}^{n} (i+1). ``` Funkcję tworzącą ciągu $(n+1)_{n\in\nn_0}$ wyznaczyliśmy już w {prf:ref}`lec-04-example-06` i jest ona równa ```{math} \frac{1}{(1-x)^2}. ``` Na mocy {prf:ref}`rem-05-sumy-czesciowe`, funkcją tworzącą ciągu sum częściowych $(T_n)_{n\in\nn_0}$ jest ```{math} \frac{1}{1-x}\cdot\frac{1}{(1-x)^2} = \frac{1}{(1-x)^3}. ``` ::: ### Różniczkowanie funkcji tworzącej :::{prf:proposition} :label: rem-05-diff Jeśli $\displaystyle a(x)=\sum_{n=0}^{\infty} a_n x^n$ jest funkcją tworzącą ciągu $(a_n)$, to $b(x) = x\,a'(x)$ jest funkcją tworzącą ciągu $(n\,a_n)_{n\in\nn_0} .$ ::: :::{proof} :class: [proof] dropdown Różniczkując $a(x)$ wyraz po wyrazie otrzymamy ```{math} a'(x) = \sum_{n=1}^{\infty} n\,a_n\,x^{n-1}. ``` Mnożąc obustronnie przez $x$ dostajemy ```{math} b(x) = x\,a'(x) = \sum_{n=1}^{\infty} n\,a_n\,x^{n} = \sum_{n=0}^{\infty} n\,a_n\,x^{n} ``` (wyraz dla $n=0$ znika, bo mnoży się przez $n=0$). To jest dokładnie funkcja tworząca ciągu $(n\,a_n)_{n\in\nn_0} .$ ::: ::::{exercise} :class: [exercise] Znajdźmy funkcję tworzącą ciągu $(n)_{n\in\nn_0} .$ :::: :::{solution-without-reference} :class: [solution] dropdown Ciąg $(n)$ to ciąg $(n\cdot a_n)$ dla ciągu stałego $a_n=1$, którego funkcją tworzącą jest $a(x)=\dfrac1{1-x} .$ Korzystając w {prf:ref}`rem-05-diff` mamy ```{math} x\,a'(x) = x\cdot\frac{d}{dx}\Paren{\frac1{1-x}} = x\cdot\frac{1}{(1-x)^2} = \frac{x}{(1-x)^2}. ``` Zatem funkcją tworzącą ciągu $(n)_{n\in\nn_0}$ jest $\dfrac{x}{(1-x)^2} .$ ::: ## Liczby Catalana :::{narration} Przypomnijmy definicję liczb Catalana. ::: :::{prf:definition} :label: def-05-catalan **Liczby Catalana** {index}`liczba Catalana` $(C_n)_{n\in \nn_0}$ definiujemy rekurencyjnie przyjmując $C_0 = 1$ oraz ```{math} C_{n+1} = \sum_{i=0}^{n} C_i\, C_{n-i}, \qquad n\in \nn_0. ``` ::: :::{prf:theorem} :label: thm-05-catalan-closed Dla każdego $n\in \nn_0$ ```{math} C_n = \frac{1}{n+1}\binom{2n}{n}. ``` ::: ```{code-cell} sage :tags: [remove-input, hide-output] show(plot( [(1+sqrt(1-4*x))/(2*x), (1-sqrt(1-4*x))/(2*x)], (x, 0, 0.25), thickness=3, detect_poles='show', legend_label=[r'$\frac{1+\sqrt{1-4x}}{2x}$',r'$\frac{1-\sqrt{1-4x}}{2x}$'], color='automatic' ), transparent=True, frame=False) ``` :::{proof} :class: [proof] Niech $\displaystyle C(x) = \sum_{n=0}^{\infty} C_n x^n .$ Ponieważ $(C_{n+1})$ jest splotem ciągu $(C_n)$ ze sobą, jego funkcją tworzącą jest $C^2(x) .$ Z drugiej strony ze wzoru na przesunięcie ({prf:ref}`thm-05-slownik`) otrzymujemy ```{math} C^2(x) & = \sum_{n=0}^{\infty}\Paren{\sum_{i=0}^n C_i C_{n-i}} x^n \\ & = \sum_{n=0}^{\infty} C_{n+1}\,x^n \\ & = \frac{C(x)-C_0}{x} = \frac{C(x)-1}{x}. ``` Mnożąc obustronnie przez $x$ i porządkując, otrzymujemy równanie kwadratowe względem $C(x)$: $$ x\, C^2(x) - C(x) + 1 = 0, $$ którego pierwiastki są równe $$ C(x) = \frac{1\pm\sqrt{1-4x}}{2x}. $$ Zauważmy, że $C(0) = C_0 = 1$ jest liczbą skończoną oraz $$ \lim_{x \to 0^+} \frac{1-\sqrt{1-4x}}{2x} & = 1 \\ \lim_{x \to 0^+} \frac{1+\sqrt{1-4x}}{2x} & = +\infty . $$ Zatem ```{math} C(x) = \frac{1-\sqrt{1-4x}}{2x}. ``` Przypomnijmy rozwinięcie funkcji $\sqrt{1-4x}$ z {numref}`m-lec-04-ex-01`: ```{math} \sqrt{1-4x} = 1 - 2 \cdot \sum_{n=1}^{\infty} \frac{1}{n} \binom{2n-2}{n-1} x^n \, , ``` z którego łatwo otrzymujemy, że ```{math} 1 - \sqrt{1-4x} = 2 \cdot \sum_{n=1}^{\infty} \frac{1}{n} \binom{2n-2}{n-1} x^n \, . ``` Podstawiając to do wzoru na $C(x)$ otrzymujemy ```{math} C(x) & = \frac{1-\sqrt{1-4x}}{2x} \\ & = \frac{1}{2x}\cdot 2\sum_{n=1}^{\infty}\frac 1 n \binom{2n-2}{n-1}x^n \\ & = \sum_{n=1}^{\infty}\frac{1}{n}\binom{2n-2}{n-1}x^{n-1} \\ & = \sum_{n=0}^{\infty} \frac{1}{n+1}\binom{2n}{n}x^{n}. ``` To kończy dowód. ::: ::::{exercise} :label: mat1-05-ex-03 :class: [exercise] Korzystając ze wzoru jawnego ({prf:ref}`thm-05-catalan-closed`) wyprowadźmy rekurencyjną zależność ```{math} C_{n+1} = \frac{2(2n+1)}{n+2}\, C_n. ``` :::: :::{solution-without-reference} :class: [solution] dropdown Ze wzoru jawnego otrzymujemy ```{math} \frac{C_{n+1}}{C_n} & = \frac{\dfrac{1}{n+2}\binom{2n+2}{n+1}}{\dfrac1{n+1}\binom{2n}{n}} \\ & = \frac{n+1}{n+2}\cdot\frac{\binom{2n+2}{n+1}}{\binom{2n}{n}}. ``` Ponieważ ```{math} \binom{2n+2}{n+1} & = \frac{(2n+2)!}{(n+1)!\,(n+1)!} \\ & = \frac{(2n+2)(2n+1)}{(n+1)^2}\cdot\frac{(2n)!}{n!\,n!} \\ & = \frac{(2n+2)(2n+1)}{(n+1)^2}\binom{2n}{n}, ``` to ```{math} \frac{C_{n+1}}{C_n} & = \frac{n+1}{n+2}\cdot\frac{(2n+2)(2n+1)}{(n+1)^2} \\ & = \frac{(2n+2)(2n+1)}{(n+2)(n+1)} \\ & = \frac{2(n+1)(2n+1)}{(n+2)(n+1)} \\ & = \frac{2(2n+1)}{n+2}. ``` Stąd $C_{n+1} = \dfrac{2(2n+1)}{n+2}\,C_n .$ :::