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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zliczanie obiektów

Ćwiczenie 1

Na ile sposobów można rozmienić 1zł używając jedynie monet: 5gr, 10gr, 20gr, 50gr.

Wskazówka
Rozwiązanie

Ćwiczenie 2

Niech będzie liczbą podziałów liczby na sumę składników nie większych od , przy czym składników o tej samej wartości jest co najwyżej . Pokaż, że dla ustalonego funkcja tworząca ciągu , wyraża się wzorem



Wskazówka
Rozwiązanie

Ćwiczenie 3

Niech będzie liczbą podziałów liczby na składniki wykorzystujących co najwyżej składników o tej samej wartości. Pokaż, że dla ustalonego funkcja tworząca ciągu , wyraża się wzorem



Wskazówka
Rozwiązanie

Ćwiczenie 4

Używając funkcji tworzących pokaż, że liczba podziałów liczby składająca się z liczb nieparzystych jest równa liczbie podziałów na różne składniki.

Wskazówka
Rozwiązanie

Ćwiczenie 5

Policz ile jest drzew binarnych o węzłach, a ile o szerokości nie większej niż .

Wskazówka
Rozwiązanie

Ćwiczenie 6

Będziemy poruszać się po punktach zbioru w ten sposób, że w jednym ruchu z punktu można się przejść jedynie do lub , czyli możliwy jest ruch w "prawo" o lub w "górę" o . Policz na ile sposobów można przejść z punktu do punktu poruszając się zgodnie z powyższymi zasadami jedynie po punktach ze zbioru .

Wskazówka
Rozwiązanie

Ćwiczenie 7

Policz ile jest słów złożonych z liter o długości , w których nie występuje podsłowo .

Wskazówka
Rozwiązanie