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

Z Studia Informatyczne
< Matematyka dyskretna 1
Wersja z dnia 17:25, 23 sie 2006 autorstwa Arek (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zliczanie obiektów

Ćwiczenie ex zlicz zlotowka

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

Wskazówka
Rozwiązanie

Ćwiczenie ex zlicz obs78

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \sum_{n=0}^{\infty}f_{n,k,\left( l \right)}x^n &=\prod_{j=1}^{l}\frac{1-x^{j\left( k+1 \right)}}{1-x^j}\\ &=\left( 1+x+\ldots+x^k \right)\cdot\ldots\cdot\left( 1+x^l+\ldots+x^{lk} \right). \endaligned}
Wskazówka
Rozwiązanie

Ćwiczenie ex zlicz tw9

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 ex zlicz sumy

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 ex zlicz drzewa

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

Wskazówka
Rozwiązanie

Ćwiczenie ex movement po szachownicy Catalan

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 ex zlicz drzewa

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