Matematyka dyskretna 1/Test 8: Funkcje tworzące w zliczaniu obiektów kombinatorycznych

Z Studia Informatyczne
< Matematyka dyskretna 1
Wersja z dnia 15:02, 18 wrz 2006 autorstwa Rogoda (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

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


-ta liczba Catalana to:


Niech będzie liczbą drzew o wysokości . Wtedy:


Liczba podziałów liczby na sumy złożone jedynie ze składników wynosi:


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


Funkcja tworząca dla cyklowych liczb Stirlinga , ma postać zwartą:


Podziałowe liczby Stirlinga spełniają zależność rekurencyjną:}

, dla

, dla

, dla

żadna z pozostałych odpowiedzi nie jest prawidłowa


Niech , oraz . Funkcja tworząca ma postać zwartą:

żadna z pozostałych odpowiedzi nie jest prawidłowa