Funkcja tworząca

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Ciąg jedynek i ciąg liczb naturalnych[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

  • 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

\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}}
\sum_{n\geqslant 0} B_n\frac{x^n}{n!}=\frac{x}{e^x-1}

Literatura[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]

Zobacz też[edytuj | edytuj kod]