Funkcja tworząca

Funkcja tworząca (funkcja generująca) $G(x)$ dla ciągu $(g_{n})=(g_{0},g_{1},g_{2},\ldots )$ jest zdefiniowana jako

$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 $|x|<1.$

Funkcją tworzącą ciągu kolejnych liczb naturalnych $(1,2,3,\ldots )$ 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 ${\tbinom {n}{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 Fibonacciego określony jest wzorem rekurencyjnym

${\begin{cases}F_{0}=0\\F_{1}=1\\F_{n}=F_{n-1}+F_{n-2}{\mbox{ dla }}n\geq 2.\end{cases}}$

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

$F(x)=\sum _{n=0}^{\infty }F_{n}x^{n}=F_{0}x^{0}+\sum _{n=1}^{\infty }F_{n}x^{n}=\sum _{n=1}^{\infty }F_{n}x^{n}.$

Zauważmy, że

$F(x)=\sum _{n=1}^{\infty }F_{n}x^{n}=F_{1}x^{1}+\sum _{n=2}^{\infty }(F_{n-1}+F_{n-2})x^{n}.$

teraz wyciągnijmy $x$ w odpowiedniej potędze przed znak sumy i otrzymamy

$F(x)=F_{1}x+x\sum _{n=2}^{\infty }(F_{n-1}x^{n-1})+x^{2}\sum _{n=2}^{\infty }(F_{n-2}x^{n-2}),$

a jak już zauważyliśmy $\sum _{n=0}^{\infty }F_{n}x^{n}=\sum _{n=1}^{\infty }F_{n}x^{n},$ stąd mamy

$F(x)=F_{1}x+x\sum _{n=1}^{\infty }(F_{n}x^{n})+x^{2}\sum _{n=0}^{\infty }(F_{n}x^{n})=x+xF(x)+x^{2}F(x).$

Po przekształceniu otrzymamy:

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

Wielomian $1-x-x^{2}$ ma dwa pierwiastki $x_{1}={\tfrac {-{\sqrt {5}}-1}{2}},x_{2}={\tfrac {{\sqrt {5}}-1}{2}}.$ Funkcję $F(x)$ można więc zapisać w następujący sposób:

$F(x)={\frac {x}{({\tfrac {x}{x_{1}}}-1)({\tfrac {x}{x_{2}}}-1)}},$

Przyjmując $\lambda _{1}={\tfrac {1}{x_{1}}},\lambda _{2}={\tfrac {1}{x_{2}}}$ otrzymujemy po uprzednim rozkładzie na ułamki proste:

$F(x)={\frac {x}{(1-\lambda _{1}x)(1-\lambda _{2}x)}}={\frac {1}{\sqrt {5}}}\left({\frac {1}{1-\lambda _{1}x}}-{\frac {1}{1-\lambda _{2}x}}\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})={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right).$

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 A(x)=\sum \limits _{n=0}^{\infty }(ca_{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:

$(A(x))'=\sum \limits _{n=0}^{\infty }na_{n}x^{n-1}$

• Całkowanie:

$\int \limits _{0}^{x}A(t)\;dt=\sum \limits _{n=1}^{\infty }{\frac {1}{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 Bernoulliego:

$\sum _{n\geqslant 0}B_{n}{\frac {x^{n}}{n!}}={\frac {x}{e^{x}-1}}$

Zobacz też

• funkcja tworząca momenty
• kumulanta

Bibliografia

• Ronald L. Graham, Donald Knuth, Oren Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN, Warszawa 2002, ISBN 83-01-13906-4, rozdział 7.
• Herbet S. Wilf, generatingfunctionology (Second Edition), Academic Press, 1994, 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 [PostScript], rozdział 6. i 7.
• Karol Gryszka, Ułamki Fibonacciego [PDF], deltami.edu.pl [dostęp 2021-02-10] – artykuł o funkcjach tworzących m.in. ciągu Fibonacciego