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

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

Ciąg Fibonacciego określony jest wzorem rekurencyjnym

\begin{cases}F_0=0\\F_1=1\\F_n=F_{n-1}+F_{n-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=\sum_{n=1}^\infty F_n x^n.

Zauważmy, że

F(x)=\sum_{n=1}^\infty F_n x^n=F_1x^1+\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}.

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

F(x)=\frac{x}{x_1x_2(\tfrac{x}{x_1}-1)(\tfrac{x}{x_2}-1)}

Wiedząc, że x_1x_2=1 i 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_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)=\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[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]