Funkcja tworząca

Funkcja tworząca (funkcja generująca) $G(x)$ dla ciągu $(g_n)=(g_0,g_1,g_2,\dots )$ jest zdefiniowana jako

$G(x)=\sum _{n=0}^{\mathrm{\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

$(1,1,1,\dots )$

jest funkcja

$G(x)=\sum _{n=0}^{\mathrm{\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,\dots )$ jest funkcja

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

Dzieje się tak, gdyż

$\sum _{n=0}^{\mathrm{\infty }}(n+1)x^n=\sum _{n=0}^{\mathrm{\infty }}\frac{d}{dx}{x}^{n+1}=\frac{d}{dx}\sum _{n=0}^{\mathrm{\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 $(\genfrac{}{}{0ex}{}{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}^{\mathrm{\infty }}(1+x{)}^n{y}^n=\frac{1}{1-y(1+x)}.$

Liczby Fibonacciego

Ciąg Fibonacciego określony jest wzorem rekurencyjnym

$\{\begin{array}{c}{F}_0=0\\ F_1=1\\ F_n=F_{n-1}+F_{n-2}\text{ dla }n\ge 2.\end{array}$

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

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

Zauważmy, że

$F(x)=\sum _{n=1}^{\mathrm{\infty }}{F}_n{x}^n=F_1{x}^1+\sum _{n=2}^{\mathrm{\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}^{\mathrm{\infty }}(F_{n-1}{x}^{n-1})+x^2\sum _{n=2}^{\mathrm{\infty }}(F_{n-2}{x}^{n-2}),$

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

$F(x)=F_{1}x+x\sum _{n=1}^{\mathrm{\infty }}(F_n{x}^n)+x^2\sum _{n=0}^{\mathrm{\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=\frac{-\sqrt{5}-1}{2},x_2=\frac{\sqrt{5}-1}{2}.$ Funkcję $F(x)$ można więc zapisać w następujący sposób:

$F(x)=\frac{x}{(\frac{x}{x_1}-1)(\frac{x}{x_2}-1)},$

Przyjmując ${\lambda }_1=\frac{1}{x_1},{\lambda }_2=\frac{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}}(\frac{1}{1-{\lambda }_{1}x}-\frac{1}{1-{\lambda }_{2}x})=\frac{1}{\sqrt{5}}(\sum _{n=0}^{\mathrm{\infty }}{x}^n{\lambda }_1^n-\sum _{n=0}^{\mathrm{\infty }}{x}^n{\lambda }_2^n)=\sum _{n=0}^{\mathrm{\infty }}(\frac{1}{\sqrt{5}}({\lambda }_1^n-{\lambda }_2^n))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(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n).$

Operacje związane z funkcjami tworzącymi

• Kombinacja liniowa:

$\alpha \sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n+\beta \sum _{n=0}^{\mathrm{\infty }}{b}_n{x}^n=\sum _{n=0}^{\mathrm{\infty }}(\alpha a_n+\beta b_n)x^n$

• Przesunięcie:

$x^m\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n=\sum _{n=m}^{\mathrm{\infty }}{a}_{n-m}{x}^n$

• Mnożenie przez liczbę:

$c\cdot A(x)=\sum _{n=0}^{\mathrm{\infty }}(c{a}_n)x^n,c\in ℂ$

• Mnożenie:

$\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n\cdot \sum _{n=0}^{\mathrm{\infty }}{b}_n{x}^n=\sum _{n=0}^{\mathrm{\infty }}{c}_n{x}^n,$ gdzie $c_n=\sum _{k=0}^n{a}_k{b}_{n-k}$

• Różniczkowanie:

$(A(x){)}^{\prime }=\sum _{n=0}^{\mathrm{\infty }}n{a}_n{x}^{n-1}$

• Całkowanie:

$\underset{0}{\overset{x}{\int }}A(t)dt=\sum _{n=1}^{\mathrm{\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 $(g_0,g_1,g_2,\dots )$ definiuje się jako funkcję

$G(x)=\sum _{n=0}^{\mathrm{\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}^{\mathrm{\infty }}\frac{g_n}{n^x}.$

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

Funkcje tworzące znanych ciągów

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

$\sum _{n⩾0}\left[\begin{array}{c}n\\ m\end{array}\right]x^n=\frac{x^m}{(1-x)(1-2x)\dots (1-mx)}$

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

$\sum _{n⩾0}\left\{\begin{array}{c}n\\ m\end{array}\right\}{x}^n=x(x+1)\dots (x+m-1)=x^{\overline{m}}$

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

$\sum _{n⩾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, Szablon:ISBN, rozdział 7.
• Herbet S. Wilf, generatingfunctionology (Second Edition), Academic Press, 1994, Szablon:ISBN.

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.
• Szablon:Otwarty dostęp Karol Gryszka, Ułamki Fibonacciego [PDF], deltami.edu.pl [dostęp 2021-02-10] – artykuł o funkcjach tworzących m.in. ciągu Fibonacciego