Matematyka dyskretna 1/Ćwiczenia 8: Funkcje tworzące w zliczaniu obiektów kombinatorycznych: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m (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")
 
Linia 361: Linia 361:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
  
<div class="thumb tright"><div style="width:250px;">
+
[[File:Zliczanie catalan N2.svg|250x250px|thumb|right|Przykładowa ścieżka z punktu  <math>\displaystyle \left( 0,0 \right) </math>  do punktu  <math>\displaystyle \left( n,n \right)=\left( 7,7 \right) </math>]]
<flash>file=Zliczanie catalan N2.swf|width=250|height=250</flash>
 
<div.thumbcaption>Przykładowa ścieżka z punktu  <math>\displaystyle \left( 0,0 \right) </math>  do punktu  <math>\displaystyle \left( n,n \right)=\left( 7,7 \right) </math></div></div>
 
</div>
 
  
 
Niech
 
Niech

Aktualna wersja na dzień 15:04, 3 paź 2021

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