Matematyka dyskretna , studia zaoczne
zestaw 5
1. Ile jest sposobów rozmieszczenia n rozróżnialnych kul w k rozróżnialnych szufladach, przy
czym:
a. Rozmieszczenia sÄ… dowolne.
b. Rozmieszczenia są takie, że w każdej komórce jest co najwyżej jedna kula.
c. Rozmieszczenia są takie, że w każdej komórce jest co najmniej jedna kula.
2. Ile jest sposobów rozmieszczenia n nierozróżnialnych kul w k rozróżnialnych szufladach, przy
czym:
a. Rozmieszczenia sÄ… dowolne.
b. Rozmieszczenia są takie, że w każdej komórce jest co najwyżej jedna kula.
c. Rozmieszczenia są takie, że w każdej komórce jest co najmniej jedna kula.
3. Wyznaczyć liczbę wszystkich funkcji:
na
a) f :{ð1,2,3,4,5}ð ®ð {ð1,2,3}ð b) f :{ð1,2,3,4,5}ð ®ð {ð1,2,3}ð
1-ð1 na
c) f : {ð1,2,3,4,5}ð ®ð {ð1,2,3}ð d) f :{ð1,2,3,4,5}ð ®ð {ð1,2,3}ð
1-ð1
1-ð1 na
e) f : {ð1,2,3}ð ®ð {ð1,2,3,4,5}ð f) f :{ð1,2,3}ð ®ð {ð1,2,3,4,5}ð
na na
g) f :{ð1,2,3}ð ®ð {ð1,2,3,4,5}ð h) f :{ð1,2,3}ð ®ð {ð1,2,3}ð
1-ð1 1-ð1
4. Na ile sposobów można wybrać trzy liczby spośród 1, 2, ...,30 w ten sposób, żeby ich suma była
parzysta
5. Do windy zatrzymującej się na 8-mu piętrach wsiadły trzy osoby. Obliczyć na ile sposobów osoby
te mogły
a) opuścić windę
b) wysiąść na różnych piętrach
c) wyjść z windy na 8-mym piętrze
6. 10 osób przesłało sobie życzenia świąteczne e-mailem. Ile przesłano razem wszystkich listów
7. Na ile sposobów 20 identycznych przedmiotów można rozmieścić w 5-ciu rozróżnialnych
szufladach, tak żeby żadna szuflada nie była pusta.
8. Niech
1 2 3 4 5 6 7 8 9 10 11 12
f =
śą źą
2 10 4 5 12 9 11 7 6 1 8 3
1 2 3 4 5 6 7 8 9 10 11 12
g =
śą źą
2 1 10 6 12 7 8 9 11 3 4 5
a) rozłóż te permutacje na iloczyn cyki niezależnych i przedstaw cykle za pomocą grafu
b) określ typy tych permutacji i podaj ile permutacji S jest tego samego typu
12
c) wyznacz permutacjÄ™ f-1 oraz g-1 i f-1g-1
d) określ znak permutacji f-1g-1
9. Wypisz wszystkie permutacje w S , w taki sposób, żeby dwa sąsiednie wyrazy różniły się
4
transpozycjÄ….
Zastosuj następujący algorytm generowania permutacji przez minimalną liczbę transpozycji
sąsiednich elementów:
Idea:
Jeśli mamy już skonstruowany ciąg permutacji elementów {2, ..., n} wtedy ciąg permutacji
elementów {1, 2,...,n} otrzymujemy wstawiając element 1 na wszystkie możliwe sposoby do każdej
permutacji elementów 2,...,n. Ogólnie element 1 przesuwamy między pierwszą i ostatnią pozycję na
przemian do tyłu i do przodu (n-1)! razy