Funkcje tworzące

Zawartość

5. 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 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.

5.1. Ciągi rekurencyjne#

Definicja 5.1

Ciągiem rekurencyjnym 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 (równania rekurencyjnego), przy zadanych warunkach początkowych.

Przykład 5.1

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.

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

\[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.
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

\[\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.
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

\[\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:

\[\begin{split}\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}\end{split}\]

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\}\):

\[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):

\[C_{n+1} = \sum_{i=0}^{n} C_i\, C_{n-i}, \quad n\in \nn_0.\]

5.2. Funkcja tworząca ciągu#

Definicja 5.2

Funkcją tworzącą ciągu liczbowego \((a_n)_{n\in \nn_0}\) nazywamy (formalny) szereg potęgowy

\[G(x) = \sum_{n=0}^{\infty} a_n x^n.\]

Przykład 5.2

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. \]
Ogólniej, dla ciągu geometrycznego \(a_n = q^n\) (\(q\in\rr\) ustalone) mamy

\[G(x) = \sum_{n=0}^{\infty} q^n x^n = \sum_{n=0}^{\infty} (qx)^n = \frac{1}{1-qx}.\]
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,

\[G(x) = \sum_{n=0}^{\infty} \binom{m}{n} x^n = \sum_{n=0}^{m} \binom{m}{n} x^n = (1+x)^m.\]
Dla ciągu \(a_n = \dfrac{1}{n!}\) mamy

\[G(x) = \sum_{n=0}^{\infty} \frac{x^n}{n!} = e^x.\]
Dla ciągu \(a_n = \dfrac{(-1)^{n+1}}{n}\), \(n\in \nn\) (oraz \(a_0=0\)), mamy

\[G(x) = \sum_{n=1}^{\infty} \frac{(-1)^{n+1}}{n} x^n = \ln(1+x) \quad \text{ dla } -1 < x \leq 1.\]

5.3. Uogólniony wzór dwumianowy Newtona#

Definicja 5.3

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 \(\binom{r}{k}\) dla nieujemnych liczb całkowitych \(k\) nazywamy liczbę:

\[\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.\]

Przykład 5.3

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} .\)

Twierdzenie 5.1 (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:

\[(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\]

Ćwiczenie 5.1

Pokażmy, że

\[\sqrt{1-4x} = 1 - 2 \cdot \sum_{n=1}^{\infty} \frac{1}{n} \binom{2n-2}{n-1} x^n \, .\]

Rozwiązanie

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

\[\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

\[\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

\[\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

\[\begin{split} (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)! \end{split}\]

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

\[\begin{split} \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}. \end{split}\]

Ostatecznie rozwinięcie funkcji \(\sqrt{1-4x}\) przybiera postać

\[\sqrt{1-4x} = 1 - \sum_{n=1}^{\infty} \frac{2}{n} \binom{2n-2}{n-1} x^n \, .\]

5.4. Działania na funkcjach tworzących#

5.4.1. Liniowość i translacja#

Twierdzenie 5.2

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:

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) .\)
Translacja. Dla dowolnego \(k\in\nn\)

\[\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}.\)

Dowód

Bezpośrednio z definicji funkcji tworzącej, współczynnik przy \(x^n\) w \(\alpha G(x)+\beta H(x)\) wynosi

\[\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ć.
(dla \(k=1\)) Mnożąc \(G(x)=\sum_{n=0}^{\infty}a_n x^n\) przez \(x\) i przesuwając wskaźnik sumowania:

\[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)\):

\[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

\[\sum_{n=0}^{\infty} a_{n+1}\,x^n = \frac{G(x)-a_0}{x}.\]

Dla ogólnego \(k\geq 2\) rozumowanie jest analogiczne.

Przykład 5.4

Rozwiążmy rekurencję (tzn. znajdźmy jawny wzór na \(n\)-ty wyraz ciągu \((a_n)\))

\[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\), Tw. 5.2) oraz z liniowości:

\[\begin{split}\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}.\end{split}\]

Ponieważ \(a_0=1\), to po pomnożeniu obustronnie przez \(x\) otrzymamy

\[\begin{split}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)}.\end{split}\]

Rozkład na ułamki proste

\[ \frac{1+2x}{(1-x)(1-2x)} = \frac{4}{1-2x}-\frac{3}{1-x} \]

daje

\[\begin{split}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.\end{split}\]

Zatem \(a_n = 2^{n+2}-3 .\)

Przykład 5.5

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\):

\[\begin{split} 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). \end{split}\]

Ponieważ

\[\begin{split} 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 \end{split}\]

oraz analogicznie

\[ B = \sum_{n=1}^{\infty}\mathcal F_n\, x^n = F(x)-\mathcal F_0 = F(x), \]

otrzymujemy

\[\begin{split} 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}. \end{split}\]

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

\[\begin{split} 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. \end{split}\]

Tym samym, otrzymujemy wzór Bineta

\[ \mathcal F_n = \dfrac{\Paren{\dfrac{1+\sqrt5}2}^{n}-\Paren{\dfrac{1-\sqrt5}2}^{n}}{\sqrt 5}. \]

5.4.2. Splot ciągów#

Definicja 5.4

Splotem 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

\[c_n = \sum_{i=0}^{n} a_i b_{n-i}.\]

Twierdzenie 5.3

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.

Dowód

Zauważmy, że

\[\begin{split} \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} \end{split}\]

Stąd

\[ c_n = \sum_{i=0}^{n} a_i b_{n-i}. \]

Przykład 5.6

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

\[\sum_{n=0}^{\infty} (n+1)x^n = \Paren{\frac{1}{1-x}}^2 = \frac{1}{(1-x)^2}.\]

Ćwiczenie 5.2

Znajdźmy wyraz ogólny ciągu \((a_n)_{n\in\nn_0}\), którego funkcją tworzącą jest

\[f(x) = \frac{2-x}{(1-x)^2(1-2x)}.\]

Rozwiązanie

Mianownik ma podwójny pierwiastek \(x=1\), więc rozkład na ułamki proste ma postać

\[f(x) = \frac{A}{1-x} + \frac{B}{(1-x)^2} + \frac{C}{1-2x}.\]

Mnożąc obustronnie przez \((1-x)^2(1-2x)\):

\[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

\[f(x) = \frac{-3}{1-x} - \frac{1}{(1-x)^2} + \frac{6}{1-2x}.\]

Korzystając z Prz. 5.6, gdzie znaleźliśmy

\[ \dfrac{1}{(1-x)^2}=\sum_{n=0}^{\infty}(n+1)x^n \]

oraz geometrycznych szeregów potęgowych (patrz Prz. 5.2):

\[ \dfrac1{1-x}=\sum_{n=0}^{\infty}x^n, \qquad \dfrac1{1-2x}=\sum_{n=0}^{\infty}2^nx^n, \]

otrzymujemy

\[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 .\)

Stwierdzenie 5.4

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ą

\[s(x) = \frac{a(x)}{1-x}.\]

Dowód

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:

\[\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 (Tw. 5.3) otrzymujemy, że funkcją tworzącą ciągu \((s_n)\) jest

\[a(x)\cdot b(x) = a(x)\cdot\frac{1}{1-x} = \frac{a(x)}{1-x}.\]

Ćwiczenie 5.3

Znajdźmy funkcję tworzącą ciągu liczb trójkątnych

\[T_n = 1+2+\cdots+(n+1) = \binom{n+2}{2} = \frac {n (n+1)} 2, \qquad n\in\nn_0.\]

Rozwiązanie

Zauważmy, że \(T_n\) jest sumą częściową ciągu \((n+1)_{n\in\nn_0}\):

\[T_n = \sum_{i=0}^{n} (i+1).\]

Funkcję tworzącą ciągu \((n+1)_{n\in\nn_0}\) wyznaczyliśmy już w Prz. 5.6 i jest ona równa

\[\frac{1}{(1-x)^2}.\]

Na mocy Stw. 5.4, funkcją tworzącą ciągu sum częściowych \((T_n)_{n\in\nn_0}\) jest

\[\frac{1}{1-x}\cdot\frac{1}{(1-x)^2} = \frac{1}{(1-x)^3}.\]

5.4.3. Różniczkowanie funkcji tworzącej#

Stwierdzenie 5.5

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} .\)

Dowód

Różniczkując \(a(x)\) wyraz po wyrazie otrzymamy

\[a'(x) = \sum_{n=1}^{\infty} n\,a_n\,x^{n-1}.\]

Mnożąc obustronnie przez \(x\) dostajemy

\[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} .\)

Ćwiczenie 5.4

Znajdźmy funkcję tworzącą ciągu \((n)_{n\in\nn_0} .\)

Rozwiązanie

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 Stw. 5.5 mamy

\[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} .\)

5.5. Liczby Catalana#

Narration

Przypomnijmy definicję liczb Catalana.

Definicja 5.5

Liczby Catalana \((C_n)_{n\in \nn_0}\) definiujemy rekurencyjnie przyjmując \(C_0 = 1\) oraz

\[C_{n+1} = \sum_{i=0}^{n} C_i\, C_{n-i}, \qquad n\in \nn_0.\]

Twierdzenie 5.6

Dla każdego \(n\in \nn_0\)

\[C_n = \frac{1}{n+1}\binom{2n}{n}.\]

Dowód

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 (Tw. 5.2) otrzymujemy

\[\begin{split}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}.\end{split}\]

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

\[\begin{split} \lim_{x \to 0^+} \frac{1-\sqrt{1-4x}}{2x} & = 1 \\ \lim_{x \to 0^+} \frac{1+\sqrt{1-4x}}{2x} & = +\infty . \end{split}\]

Zatem

\[C(x) = \frac{1-\sqrt{1-4x}}{2x}.\]

Przypomnijmy rozwinięcie funkcji \(\sqrt{1-4x}\) z Ćw. 5.1:

\[\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

\[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

\[\begin{split}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}.\end{split}\]

To kończy dowód.

Ćwiczenie 5.5

Korzystając ze wzoru jawnego (Tw. 5.6) wyprowadźmy rekurencyjną zależność

\[C_{n+1} = \frac{2(2n+1)}{n+2}\, C_n.\]

Rozwiązanie

Ze wzoru jawnego otrzymujemy

\[\begin{split}\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}}.\end{split}\]

Ponieważ

\[\begin{split}\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},\end{split}\]

to

\[\begin{split}\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}.\end{split}\]

Stąd \(C_{n+1} = \dfrac{2(2n+1)}{n+2}\,C_n .\)