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

Z Studia Informatyczne
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