Funkcja tworząca

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

${\displaystyle G(x)=\sum _{n=0}^{\infty }g_{n}x^{n}.}$

Ciąg ${\displaystyle (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 ${\displaystyle 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 ${\displaystyle 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

${\displaystyle \left(1,1,1,\ldots \right)}$

jest funkcja

${\displaystyle 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 ${\displaystyle |x|<1.}$

Funkcją tworzącą ciągu kolejnych liczb naturalnych ${\displaystyle (1,2,3,\ldots )}$ jest funkcja

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

Dzieje się tak, gdyż

${\displaystyle \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 ${\displaystyle {\tbinom {n}{k}}}$ (ze względu na ${\displaystyle k,}$ przy ustalonym ${\displaystyle n}$) jest

${\displaystyle 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ą

${\displaystyle 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

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

Niech ${\displaystyle F(x)}$ będzie funkcją tworzącą tego ciągu, wtedy^[1]

${\displaystyle 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

${\displaystyle 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 ${\displaystyle x}$ w odpowiedniej potędze przed znak sumy i otrzymamy

${\displaystyle 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 ${\displaystyle \sum _{n=0}^{\infty }F_{n}x^{n}=\sum _{n=1}^{\infty }F_{n}x^{n},}$ stąd mamy

${\displaystyle 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^[1]:

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

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

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

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

${\displaystyle 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 ${\displaystyle n}$-ty wyraz można zapisać z pominięciem rekurencji:

${\displaystyle 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:

${\displaystyle \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:

${\displaystyle 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ę:

${\displaystyle c\cdot A(x)=\sum \limits _{n=0}^{\infty }(ca_{n})x^{n},\;c\in \mathbb {C} }$

• Mnożenie:

${\displaystyle \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 ${\displaystyle c_{n}=\sum \limits _{k=0}^{n}a_{k}b_{n-k}}$

• Różniczkowanie:

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

• Całkowanie:

${\displaystyle \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 ${\displaystyle \left(g_{0},g_{1},g_{2},\ldots \right)}$ definiuje się jako funkcję

${\displaystyle 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

${\displaystyle G(x)=\sum _{n=1}^{\infty }{\frac {g_{n}}{n^{x}}}.}$

Przykładowo funkcją tworzącą Dirichleta dla ciągu ${\displaystyle \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:

${\displaystyle \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:

${\displaystyle \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:

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

Zobacz też

• funkcja tworząca momenty
• kumulanta

Przypisy

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