Funkcja tworząca

szereg formalny, w którym współczynniki przy poszczególnych potęgach odpowiadają elementom danego ciągu indeksowanego liczbami naturalnymi

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

 

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[1]:

 

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

edytuj
 
  • 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:
 
 

Zobacz też

edytuj

Przypisy

edytuj
  1. a b Wojciech Broniowski, Matematyka dyskretna, wyd. II: Wykłady z przykładami w języku Python, Wojciech Broniowski, 18 sierpnia 2021, s. 12-14, ISBN 978-83-962099-1-7 [dostęp 2023-08-19] (pol.).

Bibliografia

edytuj

Linki zewnętrzne

edytuj