Funkcja tworząca

Z Wikipedii

Funkcja tworząca $G(x)\!$ dla ciągu $\left( g_0,g_1,g_2,\ldots\right)$ jest zdefiniowana przez

$G(x)=\sum_{n=0}^\infty g_n x^n$ .

Ciąg $\left( g_n\right)$ może być w szczególnym przypadku ciągiem liczbowym (wartości są liczbami naturalnymi jak to sie 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).

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

[edytuj] Przykłady

[edytuj] 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 - nie przejmujemy się zbieżnością szeregów. Szereg taki jest zbieżny tylko dla niektórych $x\in\mathbb R$ (lub $x\in\mathbb C$ ). Niemniej, pomijając ten fakt w teorii funkcji tworzących wcale nie uzyskujemy błędnych rezultatów, a jedynie omijamy pewną teoretyczną przeszkodę.

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}$ .

[edytuj] Dwumian Newtona

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)}$ .

[edytuj] Liczby Fibonacciego

Liczby Fibonacciego określone są wzorami rekurencyjnymi

$\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ą ciągu liczb Fibonacciego, 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ą dwoma pierwiastkami równania $x^2+x-1=0\!$ .

Zatem mamy

$F(x)=\frac{x}{1-x-x^2}=\frac{x}{(1-\lambda_1x)(1-\lambda_2x)}=\frac{1}{\sqrt 5}(\frac{1}{1-\lambda_1x}-\frac{1}{1-\lambda_2x})$

$=\frac{1}{\sqrt 5}(\sum_{n=0}^\infty x^n \lambda_1^n-\sum_{n=0}^\infty x^n \lambda_2^n)$ .

Możemy więc już obliczyć szukany $n\!$ -ty wyraz,

$F_n=\frac{1}{\sqrt 5}(\lambda_1^n-\lambda_2^n)$ .

[edytuj] Modyfikacje

Czasem okazuje się, że wygodniejsze do rozważania są pewne modyfikacji 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.

[edytuj] Funkcje tworzące znanych ciągów

Funkcja tworząca ciągu liczb Stirlinga I rodzaju to $\sum_{n\geq 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 to $\sum_{n\geq 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 Bella to $\sum_{n\geq 0} B_n\frac{x^n}{n!}=\frac{x}{e^x-1}$

[edytuj] Literatura

Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN, Warszawa, 2002 r. ISBN 83-01-13906-4, rozdział 7
Herbet S. Wilf, generatingfunctionology (Second Edition) (1994) Academic Press. ISBN 0-12-751956-4.

[edytuj] Linki zewnętrzne

Funkcje tworzące (materiały dydaktyczne MIMUW na studia informatyczne I stopnia)
Bogdan Chlebus, Wstęp do matematyki dyskretnej, rozdział 6. i 7.

[edytuj] Zobacz też

Kategoria: Funkcje matematyczne

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Funkcja tworząca

Z Wikipedii

Spis treści

[edytuj] Zastosowania

[edytuj] Przykłady

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

[edytuj] Dwumian Newtona

[edytuj] Liczby Fibonacciego

[edytuj] Modyfikacje

[edytuj] Funkcje tworzące znanych ciągów

[edytuj] Literatura

[edytuj] Linki zewnętrzne

[edytuj] Zobacz też

Views

nawigacja

zmiany

dla edytorów

Szukaj

W innych językach