Funkcja tworząca

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Funkcja tworząca dla ciągu jest zdefiniowana jako

.

Ciąg 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 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]

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 -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]

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

Funkcją tworzącą ciągu złożonego z samych jedynek

jest funkcja

.

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 .

Funkcją tworzącą ciągu kolejnych liczb naturalnych jest funkcja

.

Dzieje się tak, gdyż

.

Dwumian Newtona[edytuj]

Funkcją tworzącą dwumianu Newtona (ze względu na , przy ustalonym ) jest

.

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ą

.

Liczby Fibonacciego[edytuj]

Ciąg Fibonacciego określony jest wzorem rekurencyjnym

Niech będzie funkcją tworzącą tego ciągu, wtedy

.

Zauważmy, że

.
teraz wyciągnijmy w odpowiedniej potędze przed znak sumy i otrzymamy
a jak już zauważyliśmy stąd mamy

Zatem

.

Wielomian ma dwa pierwiastki . Funkcję można więc zapisać w następujący sposób:

Wiedząc, że i przyjmując otrzymujemy po uprzednim rozkładzie na ułamki proste:

.

Stąd szukany -ty wyraz można zapisać z pominięciem rekurencji:

.

Operacje związane z funkcjami tworzącymi[edytuj]

  • Kombinacja liniowa:
  • Przesunięcie:
  • Mnożenie przez liczbę:
  • Mnożenie:
, gdzie
  • Różniczkowanie:
  • Całkowanie:


Modyfikacje[edytuj]

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 definiuje się jako funkcję

.

Rozważane są także funkcje tworzące Dirichleta zdefiniowane dla powyższego ciągu jako

.

Przykładowo funkcją tworzącą Dirichleta dla ciągu jest znana funkcja dzeta Riemanna.

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

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

Literatura[edytuj]

Linki zewnętrzne[edytuj]

Zobacz też[edytuj]