Funkcja tworząca

Funkcja tworząca $G(x)\!$ dla ciągu $\{g_n\} = g_0, g_1, g_2, \ldots\;\;\;$ jest zdefiniowana przez

$G(x)=\sum_{n=0}^\infty g_n x^n$.

Ciąg $\{ g_n\}$ może być w szczególnym przypadku ciągiem liczbowym (wartości są liczbami naturalnymi, jak to się dzieje, gdy odpowiada on zliczaniu obiektów kombinatorycznych, rzeczywistymi, zespolonymi) jednak w ogólności jego wartości mogą być inne (np. funkcje).

Tymczasem jednomiany $x^n$ mogą być rozpatrywane jako wyrazy pierścienia szeregu formalnego (gdy interesują nas wyłącznie algebraiczne właściwości funkcji tworzącej) albo liczby (rzeczywiste lub zespolone).

Zastosowania

Funkcje tworzące wykorzystywane są w wielu różnych działach matematyki. Jednym z najważniejszych ich zastosowań jest przydatność do rozwiązywania równań rekurencyjnych. Bardzo dobrym przykładem stosowanych technik jest wyprowadzenie wzoru na $n$-ty wyraz ciągu Fibonacciego.

Częstym zastosowaniem funkcji tworzących jest zliczanie pewnych obiektów kombinatorycznych. Klasyczną metodą jest ułożenie najpierw równania rekurencyjnego na zliczane obiekty, a potem rozwiązanie go z użyciem funkcji tworzących. Przykładem takiego rozumowania jest m.in. wyprowadzenie wzoru na liczby Catalana.

Funkcje tworzące stosuje się również do opisu szeregów funkcji, np. wielomianów Hermite'a.

Przykłady

Ciąg jedynek i ciąg liczb naturalnych

Funkcją tworzącą ciągu złożonego z samych jedynek

$\left( 1,1,1,\ldots\right)$

jest funkcja

$G(x)=\sum_{n=0}^\infty x^n=\frac{1}{1-x}$.

Przykład ten jest ilustracją bardzo ważnego założenia w teorii funkcji tworzących, mianowicie - ze względu na to, że szeregi w funkcjach tworzących są tylko szeregami formalnymi, to aspekt zbieżności jest z tego punktu widzenia nieistotny. Powyższy szereg jest zbieżny tylko dla niektórych $x\in\mathbb R$ (lub $x\in\mathbb C$).

Funkcją tworzącą ciągu kolejnych liczb naturalnych $\langle 1,2,3,\ldots\rangle$ jest funkcja

$G(x)=\sum_{n=0}^\infty (n+1)x^n=\frac{1}{(1-x)^2}$.

Dzieje się tak, gdyż

$\sum_{n=0}^\infty (n+1)x^n= \sum_{n=0}^\infty \frac{d}{dx}x^{n+1} = \frac{d}{dx} \sum_{n=0}^\infty x^{n+1} = \frac{d}{dx} \left( \frac{x}{1-x} \right) = \frac{1}{(1-x)^2}$.

Dwumian Newtona

Funkcją tworzącą dwumianu Newtona $n \choose k$ (ze względu na $k\!$, przy ustalonym $n\!$) jest

$G_n(x)=(1+x)^n\!$.

Można rozważać funkcje tworzące od dwóch zmiennych. W szczególności potraktujmy powyższe wyrażenia jako ciąg, z którego chcemy uzyskać funkcję tworzącą

$G(x,y)=\sum_{n=0}^\infty (1+x)^n y^n = \frac{1}{1-y(1+x)}$.

Liczby Fibonacciego

Ciąg liczb Fibonacciego określony jest wzorem rekurencyjnym

$\begin{cases}F_0=0\\F_1=1\\F_{n+2}=F_{n+1}+F_n\end{cases}$

Niech $F(x)\!$ będzie funkcją tworzącą tego ciągu, wtedy

$F(x)=\sum_{n=0}^\infty F_n x^n$.

Zauważmy, że

$F(x)=\sum_{n=0}^\infty F_n x^n=x+\sum_{n=2}^\infty (F_{n-2}+F_{n-1})x^n=x+x^2F(x)+xF(x)$.

Zatem

$F(x)=\frac{x}{1-x-x^2}$.

Niech $\lambda_1=\frac{1+\sqrt 5}{2}$ i $\lambda_2=\frac{1-\sqrt 5}{2}$ będą odwrotnościami dwóch pierwiastków równania $1-x-x^2=0\!$ (tj. mianownika F(x)).

Zatem mamy

$F(x)=\frac{x}{1-x-x^2}=\frac{x}{(1-\lambda_1x)(1-\lambda_2x)}=\frac{1}{\sqrt 5} \left ( \frac{1}{1-\lambda_1x}-\frac{1}{1-\lambda_2x} \right )$

$=\frac{1}{\sqrt 5} \left ( \sum_{n=0}^\infty x^n \lambda_1^n-\sum_{n=0}^\infty x^n \lambda_2^n \right ) =\sum_{n=0}^\infty \left ( \frac{1}{\sqrt 5}(\lambda_1^n-\lambda_2^n) \right ) x^n$.

Stąd szukany $n\!$-ty wyraz można zapisać z pominięciem rekurencji:

$F_n=\frac{1}{\sqrt 5}(\lambda_1^n-\lambda_2^n)$.

Operacje związane z funkcjami tworzącymi

• Kombinacja liniowa:

$\alpha \sum\limits_{n=0}^{\infty} a_n x^n + \beta \sum\limits_{n=0}^{\infty} b_n x^n = \sum\limits_{n=0}^{\infty} (\alpha a_n + \beta b_n) x^n$

• Przesunięcie:

$x^m \sum\limits_{n=0}^{\infty} a_n x^n = \sum\limits_{n=m}^{\infty} a_{n-m} x^n$

• Mnożenie przez liczbę:

$c \cdot G(x) = \sum\limits_{n=0}^{\infty} (c a_n) x^n, \; c \in \mathbb{C}$

• Mnożenie:

$\sum\limits_{n=0}^{\infty} a_n x^n \cdot \sum\limits_{n=0}^{\infty} b_n x^n = \sum\limits_{n=0}^{\infty} c_n x^n$, gdzie $c_n =\sum\limits_{k=0}^n a_k b_{n-k}$

• Różniczkowanie:

$(G(x))' = \sum\limits_{n=0}^{\infty} n a_n x^{n-1}$

• Całkowanie:

$\int\limits_0^x G(t) \; dt = \sum\limits_{n=1}^{\infty} {1 \over n} a_{n-1} x^n$

Modyfikacje

Czasem okazuje się, że wygodniejsze do rozważania są pewne modyfikacje funkcji tworzących. Jedną z bardziej znanych są wykładnicze funkcje tworzące. Wykładniczą funkcję tworzącą dla ciągu liczb $\left( g_0,g_1,g_2,\ldots\right)$ definiuje się jako funkcję

$G(x)=\sum_{n=0}^\infty g_n\frac{x^n}{n!}$.

Rozważane są także funkcje tworzące Dirichleta zdefiniowane dla powyższego ciągu jako

$G(x)=\sum_{n=1}^\infty \frac{g_n}{n^x}$.

Przykładowo funkcją tworzącą Dirichleta dla ciągu $\left( 1,1,1,\ldots\right)$ jest znana funkcja dzeta Riemanna.

Funkcje tworzące znanych ciągów

• Funkcja tworząca ciągu liczb Stirlinga I rodzaju:

$\sum_{n\geqslant 0} \left[\begin{matrix}n\\m\\\end{matrix}\right]x^n=\frac{x^m}{(1-x)(1-2x)\ldots(1-mx)}$

• Funkcja tworząca ciągu liczb Stirlinga II rodzaju:

$\sum_{n\geqslant 0} \left\{ \begin{matrix}n\\m\\\end{matrix} \right\}x^n=x(x+1)\ldots(x+m-1)=x^{\bar{m}}$

• Wykładnicza funkcja tworząca ciągu liczb Bella:

$\sum_{n\geqslant 0} B_n\frac{x^n}{n!}=\frac{x}{e^x-1}$

Literatura

• Ronald L. Graham, Donald Knuth, Oren Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN, Warszawa, 2002 r. ISBN 83-01-13906-4, rozdział 7
• Herbet S. Wilf, generatingfunctionology (Second Edition) (1994) Academic Press. ISBN 0-12-751956-4.

Linki zewnętrzne

• Funkcje tworzące (materiały dydaktyczne MIMUW na studia informatyczne I stopnia)
• Bogdan Chlebus, Wstęp do matematyki dyskretnej, rozdział 6. i 7.
• Dowód indukcyjny wzoru Bineta dla ciągu Fibonacciego

Zobacz też

• funkcja tworząca momenty
• kumulanta