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 - "\mathscr{" na "\mathcal{")
Linia 20: Linia 20:
  
  
<center><math>\displaystyle \begin{align} P_{5,10}\!\left( x \right)&=P_{5}\!\left( x \right)\cdotP_{10}\!\left( x \right),\\
+
<center><math>\displaystyle \begin{align} P_{5,10}\!\left( x \right)&=P_{5}\!\left( x \right)\cdot P_{10}\!\left( x \right),\\
P_{5,10,20}\!\left( x \right)&=P_{5,10}\!\left( x \right)\cdotP_{20}\!\left( x \right),\\
+
P_{5,10,20}\!\left( x \right)&=P_{5,10}\!\left( x \right)\cdot P_{20}\!\left( x \right),\\
P_{5,10,20,50}\!\left( x \right)&=P_{5,10,20}\!\left( x \right)\cdotP_{50}\!\left( x \right).
+
P_{5,10,20,50}\!\left( x \right)&=P_{5,10,20}\!\left( x \right)\cdot P_{50}\!\left( x \right).
 
\end{align}</math></center>
 
\end{align}</math></center>
  

Wersja z 22:34, 10 cze 2020

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

Niech

  • będzie rodziną ścieżek z punktu do punktu przechodzących poniżej prostej opisanej funkcją , czyli zawierających punkty ze zbioru ,
  • będzie szukaną liczbą ścieżek.

Dla ścieżki niech będzie pierwszym punktem prostej na ścieżce .

Oznacza to, że odwiedzone pozycje pomiędzy punktami oraz były poniżej prostej . Ścieżkę można więc rozłożyć na dwie ścieżki:

  • ścieżkę z punktu do poniżej prostej , oraz
  • ścieżkę z punktu do poniżej prostej .

Z kolei para jednoznacznie wyznacza ścieżkę . Rodzina ścieżek, na których punkt jest pierwszym spotkaniem z prostą jest więc równoliczna z produktem . Zachodzi więc



Ponieważ zbiór ścieżek z do jest rozłączną sumą , to



A zatem ciąg przedstawia kolejne liczby Catalana, czyli szukana liczba ścieżek z do , to



Ć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