[DM 04]

[1/04] Ile różnych słów n-literowych można utworzyć z alfabetu składającego się z k liter pod warunkiem, że każda litera występuje w słowie

(a) co najwyżej raz (zał. n ≤ k)

(b) dokładnie raz (zał. n = k)

(c) co najmniej raz (zał. n ≥ k)

(b) dokładnie dwa razy (zał. n = 2k)

[2/04] Jest k sal egzaminacyjnych. W każdej sali miejsca są ponumerowane i zajmowane przez wchodzących studentów kolejno (najpierw miejsce nr 1, potem nr 2, itd.). W każdej sali liczba miejsc jest większa niż n. Na ile sposobów można rozmieścić n studentów w tych salach przyjmując, że dwa rozmieszczenia uznajemy za różne, jeżeli:

(a) chociaż jeden student w pierwszym przypadku siedzi w innej sali lub ma miejsce z innym numerem niż w drugim

(b) chociaż jeden student w pierwszym przypadku siedzi w innej sali niż w drugim

(c) chociaż dwóch studentów w pierwszym przypadku siedzi w tej samej sali, a w drugim w różnych salach

[3/04] W każdej załodze jest jeden kapitan, jeden sternik i trzech majtków.

Na ile sposobów można utworzyć 3 załogi z 15 żeglarzy jeżeli zakładamy, że dwa podziały są różne gdy:

(a) istnieje chociaż jeden żeglarz, który w pierwszym przypadku ma inną funkcję, niż w drugim

(b) istnieje dwóch żeglarzy, którzy w pierwszym przypadku są w jednej załodze, a w drugim w różnych załogach

(c) istnieje chociaż jeden żeglarz, który w pierwszym przypadku jest kapitanem, a w drugim nie

(d) istnieje chociaż jeden żeglarz, który w pierwszym przypadku ma innego kapitana niż w drugim

[4/04] Na ile sposobów można posadzić 2n (n ≥ 2) gości przy okrągłym stole (środki krzeseł tworzą wielokąt foremny) jeżeli przyjmujemy, że dwa rozsadzenia są różne gdy:

(a) istnieje chociaż jeden gość mający w pierwszym przypadku inny zbiór sąsiadów (osoba po lewej + osoba po prawej) niż w drugim

(b) istnieje chociaż jeden gość mający w pierwszym przypadku inną osobą przed sobą niż w drugim

(c) istnieje chociaż jeden gość mający innego sąsiada po prawej

[5/04] Każdy student otrzymuje jedną z czterech ocen 2, 3, 4, 5. Skala ocen jest tak dobierana, że każdą z ocen otrzymuje co najmniej jeden student.

Na ile sposobów może się zakończyć egzamin, w którym bierze udział n studentów jeżeli dwie listy wyników uznajemy za różne gdy:

(a) jest inny rozkład ocen (liczby dwójek, trójek, czwórek, piątek)

(b) istnieje chociaż jeden student, który w pierwszym przypadku otrzymał inną ocenę niż w drugim

[6/04] W każdej z dwóch drużyn brydżowych jest 8 zawodników. Przy każdym stoliku dwie osoby z pierwszej drużyny grają przeciwko dwom osobom z drugiej. Na ile sposobów można zorganizować rozgrywki przy czterech stolikach, jeżeli dwa rozsadzenia uznajemy za różne gdy:

(a) istnieje osoba, która w pierwszym przypadku ma innego partnera niż w drugim

(b) istnieje osoba, która w pierwszym przypadku ma chociaż jednego innego przeciwnika, niż w drugim

(c) istnieje osoba, która w pierwszym przypadku siedzi przy innym stoliku niż w drugim

[7/04] Wyznacz liczbę

(a) wszystkich ciągów skończonych

(b) wszystkich ciągów skończonych długości k,

o wartościach naturalnych takich, że suma wszyst­kich wyrazów wynosi n.

[8/04] Wujek Scrooge ma n jednakowych cukierków, którymi chce obdarować swoich k siostrzeńców tak, aby każdy z nich otrzymał co najmniej r cukierków (n ≥ kr). Dwa rozdania uważamy za różne, jeżeli chociaż jeden z siostrzeńców w pierwszym rozdaniu otrzymał inną liczbę cukierków niż w drugim. Na ile sposobów Scrooge może rozdać swoje cukierki?

[9/04] kn dzieci dzielimy na k grup po n dzieci, a następnie w każdej grupie wybieramy szefa. Na ile sposobów można dokonać tego podziału, jeżeli przyjmujemy, że dwa podziały są różne jeżeli istnieje chociaż jedno dziecko, które w pierwszym podziale ma innego szefa niż w drugim. Należy przyjąć, że szef jest także szefem samego siebie. Oprócz ogólnego wzoru przedstaw wszystkie przypadki dla k = n = 2.

[10/04] kn dzieci dzielimy na k niepustych (nie koniecznie równolicznych) grup dzieci, a następnie w każdej grupie wybieramy szefa. Na ile sposobów można dokonać tego podziału, jeżeli przyjmujemy, że dwa podziały są różne, jeżeli istnieje chociaż jedno dziecko, które w pierwszym podziale ma innego szefa niż w drugim. Należy przyjąć, że szef jest także szefem samego siebie. Oprócz ogólnego wzoru przedstaw wszystkie przypadki dla k = n = 2.

[11/04] Na ile sposobów można rozmieścić 60 ponumerowanych kul w 30 workach (w worku kule nie są uporządkowane - zmiana położenia kul w pojedynczym worku nie zmienia rozmieszczenia), jeżeli:

1. Worki są rozróżnialne (ponumerowane) i w każdym mieszczą się dokładnie 2 kule

2. Worki są nierozróżnialne i w każdym mieszczą się dokładnie 2 kule

3. Worki są rozróżnialne (ponumerowane) i każdy z nich może pomieścić wszystkie kule

4. Worki są nierozróżnialne, każdy z nich może pomieścić wszystkie kule i żaden worek nie może być pusty

[12/04] Na ile sposobów można rozmieścić 60 ponumerowanych kartek w 30 szufladach (w szufladzie kartki są uporządkowane - zmiana położenia kartki w szufladzie zmienia rozmieszczenie), jeżeli:

1. Szuflady są rozróżnialne (ponumerowane) i w każdej mieszczą się dokładnie 2 kartki

2. Szuflady są nierozróżnialne i w każdej mieszczą się dokładnie 2 kartki

3. Szuflady są rozróżnialne (ponumerowane) i każda z nich może pomieścić wszystkie kartki

4. Szuflady są rozróżnialne, każda z nich musi zawierać dokładnie 0 albo 10 kartek

[13/04] Na ile sposobów można utworzyć n - 2 małżeństwa spośród n (rozróżnialnych) kobiet i n + 2 (rozróżnialnych) mężczyzn?

[14/04] Na ile sposobów można utworzyć n-bitowe słowo (n ≥ 13) zawierające dokładnie 5 jedynek (i n - 5 zer), w którym każde dwie jedynki są oddzielone co najmniej dwoma zerami?

[15/04] Dla każdego z powyższych zadań przedstaw:

1. Swoją propozycję notacji opisywania zliczanych przypadków

2. Dla wybranych przez siebie małych parametrów, oblicz liczbę sposobów i jednocześnie przedstaw (używając własnej notacji) wszystkie te sposoby
   np. w zadaniu 1(b), dla parametru n = 3 i standardowej notacji permutacji mielibyśmy: 6 sposobów wyrażonych poprzez:
   (1,2,3)
   (1,3,2)
   (1), (2,3)
   (2), (1,3)
   (3), (1,2)
   (1), (2), (3)

3. Kod programu generujący dla zadanych parametrów wszystkie rozwiązania i zliczający ich liczbę.

maximum record size = 2186 record size = 8708

---