Matematyka dyskretna 1/Ćwiczenia 8: Funkcje tworzące w zliczaniu obiektów kombinatorycznych
Z Studia Informatyczne
< Matematyka dyskretna 1
Przejdź do nawigacjiPrzejdź do wyszukiwaniaWersja z dnia 15:04, 3 paź 2021 autorstwa Luki (dyskusja | edycje) (Zastępowanie tekstu - "<div class="thumb t(.*)"><div style="width:(.*)px;"> <flash>file=(.*)\.swf\|width=(.*)\|height=(.*)<\/flash> <div\.thumbcaption>(.*)<\/div><\/div> <\/div>" na "$4x$5px|thumb|$1|$6")
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