Funkcja tworząca (funkcja generują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 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 Ciąg jedynek i ciąg liczb naturalnych 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 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 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
Po przekształceniu otrzymamy:
Wielomian ma dwa pierwiastki Funkcję można więc zapisać w następujący sposób:
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 Kombinacja liniowa:
Przesunięcie:
Mnożenie przez liczbę:
Mnożenie: gdzie Różniczkowanie:
Całkowanie:
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 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 Funkcja tworząca ciągu liczb Stirlinga I rodzaju:
Funkcja tworząca ciągu liczb Stirlinga II rodzaju:
Wykładnicza funkcja tworząca ciągu liczb Bernoulliego:
Zobacz też funkcja tworząca momenty kumulanta
Przypisy
Bibliografia Ronald L. Graham, Donald Knuth, Oren Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN, Warszawa 2002, , rozdział 7. Herbet S. Wilf, generatingfunctionology (Second Edition), Academic Press, 1994, .
Linki zewnętrzne Funkcje tworzące (materiały dydaktyczne MIMUW na studia informatyczne I stopnia) Karol Gryszka, Ułamki Fibonacciego [PDF], deltami.edu.pl [dostęp 2021-02-10] – artykuł o funkcjach tworzących m.in. ciągu Fibonacciego Bogdan Chlebus, Wstęp do matematyki dyskretnej [PostScript], rozdział 6. i 7. Oskar Skibski, Funkcje Tworzące [w:] Matematyka Dyskretna, kanał autorski na YouTube, 16 marca 2020 [dostęp 2026-01-17] – nagranie w ramach kursu, Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego (MIM UW). Generating function , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-12-06].
T Kategoria:Szeregi funkcyjne