Funkcja tworząca

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Funkcje tworzące)

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

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

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

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

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

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

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

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

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

Linki zewnętrzne[edytuj | edytuj kod]