Matematyka dyskretna 1/Wykład 8: Funkcje tworzące w zliczaniu obiektów kombinatorycznych

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Obiekty kombinatoryczne często są zadane w sposób rekurencyjny. Tak zadawaliśmy np. drzewa binarne. Nawet, gdy obiekty nie są zadane w sposób rekurencyjny, to ich liczba (uzależniona np. od rozmiaru lub innego parametru) spełnia pewne zależności rekurencyjne. Często rozwikłanie takich zależności i wyprowadzenie wzoru na postać zwartą jest skomplikowane. W tym wykładzie zobaczymy jak w wielu przypadkach funkcje tworzące mogą być pomocne w zliczaniu różnych obiektów kombinatorycznych.

Zliczanie drzew

Drzewo binarne to dowolny obiekt powstały zgodnie z regułami:

  • jest drzewem binarnym,
  • jeśli i są drzewami binarnymi to też jest drzewem binarnym.

Węzeł wewnętrzny drzewa binarnego jest zdefiniowany rekurencyjnie:

  • drzewo nie ma węzłów wewnętrznych,
  • węzłami wewnętrznymi drzewa są wszystkie węzły wewnętrzne drzew i a także nowy węzeł łączący drzewa i .

Liczba Catalana to liczba drzew binarnych o węzłach wewnętrznych.

Plik:Genfunc catalan.mp4
Wszystkie pełne drzewa binarne o 3 węzłach wewnętrznych
Drzewo T posiadające lewe poddrzewo T_l oraz prawe poddrzewo Tr

Przykład

Drzewa binarne są modelem dla tzw. wyrażeń nawiasowych, czyli termów z jednym działaniem binarnym i jedną zmienną . Wyrażenia takie są zdefiniowane poprzez:

  • zmienna jest wyrażeniem nawiasowym,
  • jeśli i są wyrażeniami nawiasowymi, to też jest wyrażeniem nawiasowym.
Węzły wewnętrzne wyrażenia nawiasowego, to podtermy nie będące zmiennymi.

Obserwacja 8.1

Liczby Catalana spełniają zależność rekurencyjną:



Dowód

Pojedynczy wierzchołek jest jedynym pełnym drzewem binarnym bez węzłów wewnętrznych, a więc . Każde drzewo o co najmniej jednym wierzchołku wewnętrznym rozkłada się jako , dla pewnych jednoznacznie wyznaczonych poddrzew . Poddrzewo nazywamy lewym, a prawym podrzewem drzewa .

Niech teraz

  • będzie rodziną wszystkich drzew binarnych o węzłach wewnętrznych, oraz
  • będzie rodziną wszystkich drzew, których lewe i prawe poddrzewo mają odpowiednio oraz węzłów wewnętrznych.

Zachodzi więc:


Ponadto, jeśli drzewo o wierzchołkach wewnętrznych posiada lewe poddrzewo o wierzchołkach wewnętrznych oraz prawe poddrzewo o węzłów wewnętrznych to . Zatem rodzina wszystkich drzew o wewnętrznych wierzchołkach rozbija się na rozłączną sumę



W konsekwencji otrzymujemy:



End of proof.gif

Wniosek 8.2

Funkcja tworząca dla ciągu liczb Catalana spełnia



Dowód

Używając zależności rekurencyjnej z Obserwacji 8.1 otrzymujemy:



skąd natychmiast:



Warunek eliminuje rozwiązanie , a zatem



End of proof.gif

Twierdzenie 8.3

Liczby Catalana wyrażają się wzorem



Dowód

Twierdzenie o rozwinięciu funkcji w szereg daje



Podstawiając powyższe rozwinięcie do wzoru na otrzymanego we Wniosku 8.2 po dokonaniu kilku prostych przekształceń otrzymujemy:



czyli



Iloczyn po wymnożeniu przez przyjmuje postać



Mnożąc więc teraz ten iloczyn otrzymujemy:



Tym samym dostajemy



End of proof.gif

Używając ostatniego Twierdzenia, można określic asymptotyczne zachowanie liczb Catalana.

Wniosek 8.4

Asymptotyczne zachowanie liczb Catalana dane jest przez



tzn.



W praktyce często pojawia się konieczność zliczania drzew z uwagi na ich wysokość. Odpowiada to zliczaniu termów z uwagi na zagłębienie.

Wysokość drzewa określona jest rekurencyjnie jako:

  • ,
  • .

Obserwacja 8.5

Liczba drzew binarnych o wysokości co najwyżej wyraża się równaniem rekurencyjnym



Dowód

Niech będzie rodziną pełnych drzew binarnych o wysokości co najwyżej . Wtedy . Oczywiście , a więc . Jedynym drzewem w , które nie jest rozkładalne na lewe i prawe poddrzewo jest drzewo . Każde więc drzewo jest postaci , gdzie poddrzewa oraz są wysokości co najwyżej , tzn. . Dowolne więc drzewo z wyznacza jednoznacznie parę drzew z . Odwzorowanie to jest bijekcją, więc



skąd natychmiast dostajemy naszą zależność rekurencyjną.

End of proof.gif
Plik:Zliczanie drzewa wys.svg
Drzewa o wysokości co najwyżej 2

Wniosek 8.6

Dla mamy:

Dowód

Dowód przeprowadzimy indukcyjnie ze względu na . Dla mamy , oraz Niech więc i załóżmy dla indukcji, że

Wtedy:

skąd natychmiast:

End of proof.gif

Zliczanie podziałów liczby na sumy

Przypomnijmy, że przez oznaczyliśmy liczbę podziałów liczby na dokładnie składników. Wtedy oznacza liczbę wszystkich możliwych podziałów liczby na sumę.

Przykład

Policzmy wszystkie sposoby przedstawienia liczby za pomocą sumy dodatnich liczb naturalnych.



gdzie oraz są dodatnimi liczbami naturalnymi. Oto one



tzn. .

Funkcja tworząca podziału liczby na sumy to szereg



Ponadto funkcja tworząca podziału liczby na sumy złożone wyłącznie z liczb oznaczać będziemy przez



gdzie to liczba podziałów liczby na sumę gdzie oraz .

Przykład

Pierwszy przykład w wykładzie o funkcjach tworzących dotyczył możliwości rozmiany kwoty za pomocą jednocentówek, pięciocentówek, dziesięciocentówek, ćwierćdolarówek oraz półdolarówek. Rozważaliśmy więc tam funkcję tworzącą .

Obserwacja 8.7



Dowód

Niech będzie liczbą rozkładów liczby na sumę złożoną wyłącznie ze składników równych . Oczywiście jeśli dzieli , to istnieje dokładnie jedna suma . Jeśli natomiast nie jest podzielne przez , to taki rozkład nie istnieje, tak więc



Otrzymujemy w ten sposób



która to funkcja zwija się do



End of proof.gif

Obserwacja 8.8



Dowód

Załóżmy, że splot



jest przedstawiony jako szereg . Wtedy oczywiście jest sumą wszystkich jednomianów postaci , dla których . Współczynnik więc jest liczbą wszystkich ciągów takich, że



tzn. jest liczbą rozkładów liczby na sumy o składnikach ze zbioru , a zatem jest -tym współczynnikiem funkcji tworzącej .

End of proof.gif

Przykład

Niech . Współczynnik to liczba iloczynów postaci równych , a zarazem liczba podziałów liczby na sumy złożone ze składników oraz . Każdemu iloczynowi odpowiada jeden podział. Na przykład , gdzie pochodzi z oraz pochodzi z , odpowiada sumie . Poniżej zaznaczono w funkcji tworzącej jednomiany oraz



Odpowiadają one zaznaczonemu rozkładowi na liście wszystkich rozkładów liczby :



Przykład

W funkcji tworzącej



współczynnik jest liczbą podziałów liczby na sumy postaci



czyli liczbą sposobów na jakie można rozmienić centów przy użyciu jednocentówek, pięciocentówek, dziesięciocentówek, ćwierćdolarówek oraz półdolarówek. Otrzymaliśmy więc rozwiązanie przykładu o rozmienianiu monet. Funkcja tworząca jest w poznanej już postaci równej



Widzieliśmy już, że ogólnie



Twierdzenie 8.9[L. Euler]

Funkcja tworząca podziału liczby na sumy jest przedstawialna jako



Dowód

Niech rozwija się w szereg , a formalny nieskończony splot



zwija się do szeregu formalnego



Oczywiście przy liczeniu z czynników , gdzie , jedynie jednomian odgrywa rolę, gdyż jednomiany z dają zbyt duże potęgi. A zatem . Ponieważ żaden składnik w rozkładzie nie może przekraczać , mamy , skąd natychmiast , co kończy dowód.

End of proof.gif

Funkcje tworzące dla liczb Stirlinga oraz liczb Bella

Twierdzenie 8.10

Funkcja tworząca



dla cyklowych liczb Stirlinga ma postać zwartą



Dowód

Cyklowe liczby Stirlinga spełniają następującą zależność rekurencyjną



Po podstawieniu tych zależności w rozwinięciu funkcji tworzącej otrzymujemy



Iterując powyższą równość otrzymujemy:



co kończy dowód.

End of proof.gif

Twierdzenie 8.11

Funkcja tworząca



dla podziałowych liczb Stirlinga ma postać zwartą



Dowód

Podziałowe liczby Stirlinga spełniają następującą zależność rekurencyjną



Po podstawieniu tych zależności w rozwinięciu funkcji tworzącej otrzymujemy:



skąd natychmiast:



Iterując powyższą równość otrzymujemy:



co kończy dowód.

End of proof.gif

Czasem, dla liczenia współczynników funkcji tworzącej wygodnie użyć jest rachunku różniczkowego i rozwinięcia funkcji w szereg Taylora. Dlatego dla ciągu obok funkcji tworzącej



rozważa się też tzw. wykładniczą funkcję tworzącą, tzn. wyrażenie postaci



Twierdzenie 8.12

Wykładnicza funkcja tworząca



dla liczb Bell'a ma postać zwartą



Dowód

Liczby Bella spełniają następującą zależność rekurencyjną



Pochodna szeregu to



Dzieląc obustronnie przez zależność rekurencyjną dla liczb Bella otrzymujemy



Prawa strona tej równości jest współczynnikiem przy splotu funkcji z . Otrzymujemy więc równość End of proof.gif


     (2)


której rozwiązaniem przyjmującym wartość jest



Faktycznie, po podstawieniu rozwiązania do równości (2) uzyskujemy: