UNIWERSYTET GDACSKI MATERIAAY DYDAKTYCZNE DO PRZEDMIOTU MATEMATYKA DYSKRETNA kierunek: Informatyka GDACSK 2009 Niniejsze materiały powstały w ramach projektu Uniwersytet Gdański promotorem zasobów nowoczesnej gospodarki zwiększenie liczby absolwentów kierunków przyrodniczych i ścisłych (PRO-GOS) , współfinansowanego przez Europejski Fundusz Społeczny i budżet państwa w ra- mach Programu Operacyjnego Kapitał Ludzki. ż3 Kombinatoryka 3.1 Wariacje z powtórzeniami Twierdzenie 3.1 (Wariacje z powtórzeniami) Liczba ciągów długości k ze zbioru {a, b} wynosi 2k. Liczba ciągów długości k ze zbioru n-elementowego wynosi nk. Liczba funkcji z k-elementowego zbioru A w n-elementowy zbiór wynosi nk. Przykład 3.1. Wypisz wszystkie funkcje f : X Y , gdzie: a) X = {1, 2, 3}, Y = {a, b}; b) X = {a, b}, Y = {1, 2, 3}. Czy można policzyć, ile jest tych funkcji bez ich wypisywania? Odpowiedz 3.1. a) x f1(x) f2(x) f3(x) f4(x) f5(x) f6(x) f7(x) f8(x) 1 a b a a b b a b 2 a a b a b a b b 3 a a a b a b b b Zgodnie z Twierdzeniem 3.1, tych funkcji jest 23 = 8. b) x f1(x) f2(x) f3(x) f4(x) f5(x) f6(x) f7(x) f8(x) f9(x) a 1 2 3 1 2 3 1 2 3 b 1 1 1 2 2 2 3 3 3 Zgodnie z Twierdzeniem 3.1, tych funkcji jest 32 = 9. Przykład 3.2. Mamy 10 różnych piłek i 2 różne pudła. Każdą piłkę wrzucamy do jednego z pudeł. Na ile sposobów można to zrobić? Odpowiedz 3.2. Jako że powyższą sytuację można utożsamić z funkcją f : {p1, p2, . . . , p10} {1, 2}, która każdej z dziesięciu piłek przyporządkowuje numer pudła, liczba rozmieszczeń równa jest liczbie różnych funkcji f. Na mocy Twierdzenia 3.1 liczba ta wynosi 210. 1 Przykład 3.3. Pewna osoba miała przedostać się najkrótszą drogą z punktu A do punktu B (patrz poniższy rysunek), a następnie wrócić z punktu B do punktu A. Szła tylko narysowanymi ulicami. Na ile sposobów mogła wybrać trasę? A ul. Pierwsza ul. Siódma B Odpowiedz 3.3. Wybór najkrótszej drogi, zarówno tej do jak i z , równoważny jest wyborowi którejś z pięciu dróg Druga, Trzecia, Czwarta, Piąta, Szósta. Jako że takiego wyboru dokonujemy dwa razy, liczba możliwości wynosi 52. Istnieje też rozwiązanie bardziej formalne. Zauważmy, że istnieje wzajemna odpowiedniość pomiędzy najkrótszymi drogami do i z , a funkcjami f : {do, z} {Druga, Trzecia, Czwarta, Piąta, Szósta}, a tym samym, na mocy Twierdzenia 3.1, liczba różnych dróg/funkcji wynosi 52. Zadanie 3.4. a) Ile istnieje liczb naturalnych 5-cyfrowych, w których zapisie nie występuje cyfra 0 ? b) Ile istnieje liczb naturalnych 5-cyfrowych? c) Ile istnieje liczb naturalnych 5-cyfrowych takich, w których cyfrą setek jest 5 ? Zadanie 3.5. a) Ile jest funkcji f ze zbioru {1, . . . , n} w zbiór {a, b, c}? b) Ile spośród nich spełnia warunek f(1) = a? c) Ile spośród nich spełnia warunek f(1) = f(2)?
Zadanie 3.6. Ile jest liczb trzycyfrowych w systemie: a) dziesiÄ™tnym, b) dwójkowym, c) trójkowym? Ile jest liczb trzycyfrowych z różnymi cyframi? Zadanie 3.7. Rzucamy 3 razy monetÄ…, a nastÄ™pnie 4 razy kostkÄ… do gry. Ile różnych wyników tego doÅ›wiadczenia możemy uzyskać? (ZakÅ‚adamy, że istotna jest kolejność). Zadanie 3.8. Grupa znajomych przyszÅ‚a do ciastkarni, w której byÅ‚o 8 rodzajów ciastek. Każdy kupiÅ‚ jedno ciastko. Z ilu osób skÅ‚adaÅ‚a siÄ™ grupa, jeżeli wiadomo, że mogÅ‚o być 512 różnych możliwoÅ›ci wyboru? 2 ul.PiÄ…ta ul.Szósta ul.Czwarta ul.Druga ul.Trzecia 3.2 Wariacje bez powtórzeÅ„ Twierdzenie 3.2 (Wariacje bez powtórzeÅ„) Liczba ciÄ…gów bez powtórzeÅ„ dÅ‚ugoÅ›ci k ze zbioru n-elementowego wynosi n · (n - 1) · . . . · ((n - k) + 1). Liczba różnowartoÅ›ciowych funkcji z k-elementowego zbioru A w n-elementowy zbiór wynosi n · (n - 1) · . . . · ((n - k) + 1). PrzykÅ‚ad 3.9. Wypisz wszystkie różnowartoÅ›ciowe funkcje f : X Y , gdzie: (a) X = {1, 2, 3}, Y = {a, b}; (b) X = {a, b}, Y = {1, 2, 3}. Czy można policzyć, ile jest tych funkcji bez ich wypisywania? Odpowiedz 3.9. a) Zauważmy, że nie istnieje różnowartoÅ›ciowa funkcja f : X Y , gdzie X = {1, 2, 3}, Y = {a, b}, gdyż musimy trzem elementom z X przypisać różne wartoÅ›ci, a zatem tych wartoÅ›ci do wyboru powinno być przynajmniej trzy, a mamy do wyboru tylko dwie. Zgodnie z Twierdzeniem 3.2, tych funkcji jest 2 · 1 · 0 = 0. b) x f1(x) f2(x) f3(x) f4(x) f5(x) f6(x) a 1 1 2 2 3 3 b 2 3 1 3 1 2 Zgodnie z Twierdzeniem 3.2, tych funkcji jest 3 · 2 = 6. PrzykÅ‚ad 3.10. W kawiarni, do której przyszÅ‚o 7 osób, byÅ‚o 10 gatunków ciastek. Każdy kupiÅ‚ jedno ciastko, przy czym każdy kupiÅ‚ inne. Na ile sposobów można byÅ‚o kupić ciastka? Odpowiedz 3.10. PowyższÄ… sytuacjÄ™ można utożsamić z różnowartoÅ›ciowÄ… funkcjÄ… f : {o1, o2, . . . , o7} {1, 2, . . . , 10}, która każdej z siedmiu osób przyporzÄ…dkowuje inny rodzaj ciastka. Zatem liczba sposobów równa jest liczbie różnowartoÅ›ciowych funkcji f, a na mocy Twierdzenia 3.2, liczba ta wynosi 10·9·. . . ·4. PrzykÅ‚ad 3.11. Pewna osoba miaÅ‚a przedostać sie najkrótszÄ… drogÄ… z punktu A do punktu B (patrz rysunek poniżej), a nastÄ™pnie wrócić z punktu B do punktu A. SzÅ‚a tylko narysowanymi ulicami. Na ile sposobów mogÅ‚a wybrać trasÄ™, jeÅ›li nie chciaÅ‚a wracać tÄ… samÄ… drogÄ…? A ul. Pierwsza ul. Siódma B 3 ul.PiÄ…ta ul.Szósta ul.Czwarta ul.Druga ul.Trzecia Odpowiedz 3.11. Zauważmy, że istnieje wzajemna odpowiedniość pomiÄ™dzy różnymi najkrót- szymi drogami do i z , a różnowartoÅ›ciowymi funkcjami f : {do, z} {Druga, Trzecia, Czwarta, PiÄ…ta, Szósta}, a tym samym, na mocy Twierdzenia 3.2, liczba różnowartoÅ›ciowych funkcji/tras wynosi 5 · 4 = 20. Zadanie 3.12. a) Ile istnieje liczb naturalnych 5-cyfrowych o nie powtarzajÄ…cych siÄ™ cyfrach takich, w których zapisie nie wystÄ™puje cyfra 0 ? b) Ile istnieje liczb naturalnych 5-cyfrowych o nie powtarzajÄ…cych siÄ™ cyfrach? c) Ile istnieje liczb naturalnych 5-cyfrowych o nie powtarzajÄ…cych siÄ™ cyfrach takich, w których cyfrÄ… setek jest 5 ? Zadanie 3.13. W grupie skÅ‚adajÄ…cej siÄ™ z 3 dziewczÄ…t i 5 chÅ‚opców, urodzonych w tym samym roku, żadna para dziewczÄ…t i żadna para chÅ‚opców nie obchodzi urodzin tego samego dnia roku. Ile jest możliwoÅ›ci wystÄ…pienia takiego zdarzenia ze wzglÄ™du na daty urodzin tych oÅ›miu osób? Zadanie 3.14. Z ilu osób skÅ‚ada siÄ™ grupa, jeżeli wiadomo, że na 5 miejscach osoby te mogÄ… usiąść na 60 sposobów? 3.3 Permutacje Twierdzenie 3.3 (Permutacje) Liczba permutacji (czyli n-elementowych ciÄ…gów bez powtórzeÅ„ o elementach ze zbioru n-elementowego) wynosi n · (n - 1) · . . . · 2 · 1 = n!. PrzykÅ‚ad 3.15. Wypisz wszystkie różnowartoÅ›ciowe funkcje f : X Y , gdzie X = {1, 2, 3}, Y = {a, b, c}. Czy można policzyć, ile jest tych funkcji bez ich wypisywania? Odpowiedz 3.15. x f1(x) f2(x) f3(x) f4(x) f5(x) f6(x) 1 a a b b c c 2 b c a c a b 3 c b c a b a Zgodnie z Twierdzeniem 3.3, tych funkcji jest 3! = 6. PrzykÅ‚ad 3.16. Ile różnych 4-cyfrowych liczb można utworzyć z cyfr 1, 2, 3, 4 tak, aby żadna cyfra w liczbie nie powtarzaÅ‚a siÄ™? Odpowiedz 3.16. Jako że każda 4-cyfrowa liczba o niepowtarzajÄ…cych siÄ™ cyfrach ze zbioru {1, 2, 3, 4} odpowiada 4-elementowemu ciÄ…gowi bez powtórzeÅ„, na mocy Twierdzenia 3.3, liczb tych jest 4! = 24. 4 Zadanie 3.17. a) Ile różnych 5-cyfrowych liczb można utworzyć z cyfr 1, 2, 3, 4, 5 tak, aby żadna cyfra w liczbie nie powtarzaÅ‚a siÄ™? b) Ile różnych 5-cyfrowych liczb można utworzyć z cyfr 1, 2, 3, 4, 5 tak, aby żadna cyfra w liczbie nie powtarzaÅ‚a siÄ™ i aby na miejscu dziesiÄ…tek staÅ‚a 5 lub 4 ? Zadanie 3.18. Rodzina 6-osobowa (rodzice i czworo dzieci) ustawia siÄ™ w szeregu do zdjÄ™cia. Ile różnych fotografii można otrzymać, jeżeli: a) każdy może stać obok każdego, b) rodzice stojÄ… na dwóch koÅ„cach szeregu? Zadanie 3.19. 20-osobowa grupa wsiada do autobusu. Najpierw wsiada 12 paÅ„, a za nimi 8 panów. Ile istnieje różnych możliwoÅ›ci tego zdarzenia? Zadanie 3.20. Ile jest różnych sposobów ustawienia na półce dzieÅ‚a 5-tomowego tak, aby: a) tomy I i II staÅ‚y obok siebie, b) tomy I i II nie staÅ‚y obok siebie? Zadanie 3.21. Na ile sposobów można rozsadzić: a) 3 osoby na 3-osobowej karuzeli, b) 4 osoby na 4-osobowej karuzeli, c) n osób na n-osobowej karuzeli? Uwaga. Dwa rozsadzenia uważamy za różne, jeżeli co najmniej jedna osoba ma co najmniej z jednej strony innego sÄ…siada. Czyli rozsadzenia takie jak na poniższym rysunku sÄ… identyczne (karuzela siÄ™ krÄ™ci). 1 3 2 3 1 2 Zadanie 3.22. Na ile sposobów można rozsadzić przy okrÄ…gÅ‚ym stole: a) 3 osoby, b) 4 osoby, c) n osób? Uwaga. Rozsadzenia przedstawione na powyższym rysunku traktujemy jako różne. Zadanie 3.23. W ilu permutacjach zbioru {1, . . . , 5} jedynka stoi przed dwójkÄ… (niekoniecznie bezpoÅ›rednio)? 5 3.4 Permutacje z powtórzeniami Twierdzenie 3.4 (Permutacje z powtórzeniami) Niech dane bÄ™dzie n elementów, gdzie elementów typu 1 (nierozróżnialnych) jest n1, elementów typu 2 (nierozróżnialnych) jest n2, . . ., elementów typu k (nierozróżnialnych) jest nk. Wówczas liczba sposobów, na które można uporzÄ…dkować te elementy w rzÄ™dzie, wynosi
n n! = . n1, n2, . . . , nk n1! · . . . · nk! PrzykÅ‚ad 3.24. Ile różnych słów można utworzyć z liter sÅ‚owa: a) ULICA, b) MARTA, c) LALKA. Odpowiedz 3.24. MajÄ…c na uwadze z Twierdzenie 3.4 oraz: a) że wszystkie litery w sÅ‚owie ULICA sÄ… różne, otrzymujemy 5!. 5! b) że w sÅ‚owie MARTA sÄ… dwie litery A , otrzymujemy . 2! 5! c) że w sÅ‚owie LALKA mamy dwie litery L i dwie litery A , otrzymujemy . 2!2! Zadanie 3.25. Ile różnych liczb 5-cyfrowych można utworzyć z cyfr 1, 1, 1, 2, 2? Zadanie 3.26. Ile różnych nieparzystych liczb 6-cyfrowych można utworzyć z cyfr 2, 2, 4, 4, 7, 9? Zadanie 3.27. Na ile różnych sposobów można nawlec na sznurek 10 korali: 4 czarne, 4 czerwone i 2 biaÅ‚e, jeÅ›li ustalimy poczÄ…tek i koniec sznurka? A jeÅ›li potraktujemy sznurek jako naszyjnik? 3.5 Kombinacje Twierdzenie 3.5 (Kombinacje) Liczba wyborów k-elementowego podzbioru ze zbioru n-elementowego wynosi
n n! = . k k!(n - k)! Przykład 3.28. Na ile sposobów można podzielić grupę 8-osobową na dwie grupy: 5-osobową i 3-osobową? Na ile sposobów można podzielić grupę 8-osobową na dwie równe grupy? Odpowiedz 3.28. Zauważmy, że wybór trzech osób z ośmiu automatycznie wyznacza wybór pięciu osób z tej samej grupy. samym sposobów podziału grupy 8-osobowej na dwie grupy 8Tym 8 8
(5-osobowÄ… i 3-osobowÄ…) jest = 56. Co wiÄ™cej, powyższa obserwacja implikuje, że = , 3 3 5 n n a w ogólnoÅ›ci = . JeÅ›li natomiast rozważymy wybór czteroosobowej grupy, wówczas k n-k musimy pamiÄ™tać, że temu samemu podziaÅ‚owi odpowiadajÄ… dwa różne wybory grupy, tzn. wybór osób 1, 2, 3, 4 z oÅ›miu i otrzymany podziaÅ‚ jest równoważny wyborowi osób 5, 6, 7, 8, bo podziaÅ‚ 8 1 jest ten sam, zatem rozważanych podziałów jest · = 35. 2 4 Zadanie 3.29. Mamy do wyboru 3 rodzaje chlebów i 4 rodzaje buÅ‚ek. Chcemy kupić 2 różne chleby i 2 różne buÅ‚ki. Na ile sposobów możemy to zrobić? 6 Zadanie 3.30. Na ile sposobów można rozmieÅ›cić 30 książek na 4 półkach tak, aby na pierwszej półce byÅ‚o 10 książek, na drugiej 8, na trzeciej 7, a na czwartej 5? Zadanie 3.31. Z talii 52 kart losujemy 10 kart. Ile istnieje możliwych wyników losowania, w których wylosujemy 2 damy? Zadanie 3.32. Z talii 24 kart wybieramy 5 kart. Ile jest takich wyborów, w których dostaniemy: a) 5 kart w jednym kolorze, b) 1 parÄ™ i 1 trójkÄ™, c) 2 pary różnych figur, d) 2 pary? Zadanie 3.33. Na ile sposobów można utworzyć 5 par z 10 osób? Zadanie 3.34. Na ile sposobów można rozdać 52 karty czterem osobom (po równo)? Zadanie 3.35. Znajdz liczbÄ™ rozdaÅ„ przy grze w brydża, w których każdy z grajÄ…cych otrzyma dokÅ‚adnie jednego asa i jednego króla. Zadanie 3.36. Z ilu osób skÅ‚ada siÄ™ klasa, jeżeli wiadomo, że 2-osobowÄ… delegacjÄ™ można wybrać na 300 sposobów? 3.6 Zadania różne Zadanie 3.37. Ile prostych można przeprowadzić przez 5 punktów, z których żadne 3 nie sÄ… współliniowe? Zadanie 3.38. Ile przekÄ…tnych ma: a) siedmiokÄ…t wypukÅ‚y, b) n-kÄ…t wypukÅ‚y? Zadanie 3.39. Pokoje w mieszkaniu, którego plan przedstawia poniższy rysunek, majÄ… być pomalowane w taki sposób, aby pokoje majÄ…ce wspólne drzwi byÅ‚y pomalowane różnymi kolorami. Na ile sposobów można pomalować mieszkanie majÄ…c do dyspozycji n kolorów? Zadanie 3.40. Wyobrazmy sobie, że poniższy rysunek przedstawia prostokÄ…tnÄ… kratÄ™ ulic 6 × 4. Chcemy przejść ulicami od A do B idÄ…c najkrótszÄ… drogÄ…. Ile jest takich dróg? Uogólnij wynik na kratÄ™ o dowolnych wymiarach n × k. B A 7 Zadanie 3.41. a) Ile rozwiÄ…zaÅ„ ma równanie x1 + x2 + x3 + x4 = 6, gdzie każde xi jest nieujemnÄ… liczbÄ… caÅ‚kowitÄ…? Wskazówka. Rozważyć prostokÄ…tnÄ… kratÄ™ 6 × 4 i najkrótsze drogi z lewego dolnego rogu do prawego górnego rogu. b) Ile rozwiÄ…zaÅ„ ma równanie x1 + x2 + . . . + xk = n, gdzie każde xi jest nieujemnÄ… liczbÄ… caÅ‚kowitÄ…? Zadanie 3.42. Załóżmy, że mamy przedmioty w k różnych typach, że liczba przedmiotów każdego typu jest nieograniczona oraz że przedmioty jednego typu sÄ… nierozróżnialne. Na ile sposobów można wybrać n przedmiotów spoÅ›ród tych k typów przy zaÅ‚ożeniu, że dopuszczalne sÄ… powtórzenia typów i że kolejność wybranych przedmiotów jest nieistotna? Wskazówka. Patrz poprzednie zadanie. Zadanie 3.43. W kolejce do kina stoi n osób. Osoby te sÄ… wpuszczane do kina w k grupach, z których każda skÅ‚ada siÄ™ z jednej lub wiÄ™cej osób. Na ile sposobów można utworzyć tych k grup? Wskazówka. Rozważyć wstawianie bramek pomiÄ™dzy osoby jako podziaÅ‚ na grupy. Zadanie 3.44. Ile rozwiÄ…zaÅ„ ma równanie x1 + x2 + . . . + xk = n, gdzie każde xi jest dodatniÄ… liczbÄ… caÅ‚kowitÄ…? Wskazówka. Patrz poprzednie zadanie. Zadanie 3.45. Zastosować odpowiedz do poprzedniego zadania w celu przedstawienia uzasad- nienia, że liczba rozwiÄ…zaÅ„ równania x1 + x2 + . . . + xk = n, gdzie każde xi jest nieujemnÄ… liczbÄ… n+k-1 caÅ‚kowitÄ…, wynosi . k-1 Wskazówka. Rozważyć podstawienie yi = xi + 1 oraz odpowiednio powstaÅ‚e równanie. Zadanie 3.46. Mamy 30 jednakowych piÅ‚ek, które wrzucamy do różnych 5 pudeÅ‚. Ile jest takich rozmieszczeÅ„, że żadne pudÅ‚o nie jest puste? Zadanie 3.47. Mamy r jednakowych kul i n różnych komórek. Ile jest takich rozmieszczeÅ„ kul w komórkach, że żadna komórka nie jest pusta? Zadanie 3.48. Mamy r jednakowych kul i n różnych komórek. Ile jest wszystkich możliwych rozmieszczeÅ„ kul w komórkach? Zadanie 3.49. W poczekalni u lekarza w rzÄ™dzie z n krzeseÅ‚ siedzi k pacjentów w ten sposób, że żadni dwaj z nich nie znajdujÄ… siÄ™ na sÄ…siednich krzesÅ‚ach. Na ile sposobów może być wybrany odpowiedni zbiór krzeseÅ‚? Zadanie 3.50. Jeżeli na obwodzie koÅ‚a jest rozmieszczonych n punktów i każda para punktów jest poÅ‚Ä…czona liniÄ… prostÄ…, to koÅ‚o dzieli siÄ™ na pewnÄ… liczbÄ™ obszarów. Pokazać, że jeÅ›li żadne n trzy proste nie przetnÄ… siÄ™ wewnÄ…trz koÅ‚a, to liczba obszarów bÄ™dzie równa co najwyżej 1+n+ . 2 8 3.7 WÅ‚asnoÅ›ci n n-1 n-1 PrzykÅ‚ad 3.51. Wykaż, że = + . k k-1 k Odpowiedz 3.51. LewÄ… stronÄ™ równania stanowi ilość wyborów k liczb ze zbioru {1, 2, . . . , n}. Zauważmy, że zbiory k-elementowe można podzielić na te, które zawierajÄ… liczbÄ™ n, oraz te, które n-1 jej nie zawierajÄ…. W pierwszym przypadku, tych zbiorów jest (bo zakÅ‚adajÄ…c, że n należy k-1 do zbioru, pozostaje wybrać k - 1 elementów ze zbioru {1, . . . , k - 1}), w drugim natomiast tych n-1 zbiorów jest (bo wybieramy k liczb ze zbioru {1, 2, . . . , n - 1}). I dokÅ‚adnie suma iloÅ›ci tych k wyborów jest po prawej stronie równania.
n n Zauważmy na koniec, że z definicji zachodzi = dla dowolnych n1 i n2 takich, że n1 n1,n2 n-1 n-1 n-1 n-1 n1 + n2 = n, a zatem, ponieważ = oraz = , powyższą równość n1-1,n2 n1-1 n1,n2-1 n1 możemy zapisać jako
n n - 1 n - 1 = + . a, b a - 1, b a, b - 1 Zadanie 3.52. Niech a, b i c będą liczbami naturalnymi takimi, że a + b + c = n. Wykaż, że
n n - 1 n - 1 n - 1 = + + . a, b, c a - 1, b, c a, b - 1, c a, b, c - 1 n n-1 n-2 k-1 k Przykład 3.53. Udowodnij równość = + + . . . + + . k k-1 k-1 k-1 k-1 Odpowiedz 3.53. Zauważmy, że lewa strona jest z definicji ilością wyborów k liczb ze zbioru {1, 2, . . . , n}. Z drugiej strony, zauważmy, że wśród wszystkich podzbiorów k-elementowych można wyróżnić te, które mają 1 jako najmniejszy element, następnie te, które mają 2 jako najmniejszy element, . . ., i na koniec te, które mają n - k jako najmniejszy element i dokładnie suma ilości tych wyborów jest po prawej stronie równania. n n
Zadanie 3.54. Udowodnij równość = 2n. k k=0 Wskazówka. Rozważyć ilość wszystkich podzbiorów zbioru n-elementowego. n n n n Zadanie 3.55. Udowodnij równość - + - . . . + (-1)n-1 n + (-1)n = 0. 0 1 2 n-1 n Wskazówka. Skorzystać z własności z Przykładu 50. k n m+n
m Zadanie 3.56. Udowodnij równość = . r k-r k r=0 Wskazówka. Rozważyć wybór k osób spośród grupy n kobiet i m mężczyzn. n n n-i n
Zadanie 3.57. Udowodnij równość = 2k . i k-i k i=0 Wskazówka. Rozważyć kolorowanie k spośród n obiektów, mając do dyspozycji dwa kolory. n n 2 2n
Zadanie 3.58. Udowodnij równość = . k n k=0 Wskazówka. Rozważyć wybór n osób spośród grupy n kobiet i n mężczyzn. 9 Zadanie 3.59. Z powyższego zadania możemy wywnioskować, że chcąc wybrać z grupy 2n osób, składającej z n kobiet i n mężczyzn, podzbiór o takiej samej liczbie kobiet i mężczyzn, podzbiór 2n ten może być wybrany na sposobów. Zakładając, że po wybraniu takiego podzbioru chcemy n ustalić ponadto przywódcę wśród mężczyzn i przywódczynię wśród kobiet, wywnioskować, że n n 2 2n-2
k2 = n2 . k n-1 k=1 Wskazówka. Rozważyć wybór grupy z przywódcą. n m n n-k Zadanie 3.60. Udowodnij równość = . m k k m-k Wskazówka. Rozważyć sytuację, w ktorej mamy dokonać wyboru m osobowej delegacji spośród n osób, a następnie w tej delegacji wybrać k-osobowy zarząd. n n
Zadanie 3.61. Udowodnij równość: k = n2n-1. k k=0 Wskazówka. Rozważyć pochodną funkcji (1 + x)n. 3.8 Zasada włączania i wyłączania Twierdzenie 3.6 (Zasada włączania i wyłączania) |A *" B| = |A| + |B| - |A )" B|, |A *" B *" C| = |A| + |B| + |C| - |A )" B| - |A )" C| - |B )" C| + |A )" B )" C|, n
| | = (-1)|I|+1|AI, gdzie AI = Ai. I‚"{1,...,n} i=1 i"I I="
Przykład 3.62. Wyznacz liczbę elementów |A )" B )" C| oraz |C| wiedząc, że |A| = 12, |B| = 10, |A )" B| = 4, |B )" C| = 2, |A )" C| = 2, |A *" B *" C| = 20. Odpowiedz 3.62. Na podstawie zasady włączania-wyłączania otrzymujemy, że |C| + |A )" B )" C| = 6. Zauważmy, że |A )" B )" C| d" |B )" C| = 2, a zatem |A )" B )" C| może byc równe 0, 1 lub 2. Otrzymujemy wtedy, że |C| " {4, 5, 6} . Przykład 3.63. Oblicz, ile liczb mniejszych od 100 jest podzielnych przez 2, 3 lub 5. Odpowiedz 3.63. Niech D oznacza zbiór liczb podzielnych przez 2, T przez 3 i P przez pięć, D )" P zbiór liczb podzielnych przez 2 i 5, itp. Z zasady włączania-wyłączania otrzymujemy, że |D *" T *" P | = 49 + 33 + 19 - 16 - 9 - 6 + 3 = 73. Zadanie 3.64. Wyznacz liczbę elementów |A )" B )" C| oraz |C| wiedząc, że |A| = 10, |B| = 9, |A )" B| = 3, |A )" C| = 1, |B )" C| = 1, |A *" B *" C| = 18. Zadanie 3.65. Ile osób jest w grupie, jeśli wiemy, że 10 zna Francuski, 15 zna Szwedzki, 12 zna Duński? Ponadto spośród nich 5 zna Francuski i Szwedzki, 4 zna Francuski i Duński, a 3 Szwedzki i Duński. Tylko 2 zna wszystkie 3 języki. Zadanie 3.66. Ile osób jest w grupie, jeśli wiemy, że 18 zna Francuski, 11 zna Niemiecki, 15 zna Duński, 13 zna Turecki, Duński i Turecki zna 8, Francuski i Niemiecki zna 9, Turecki i Francuski 10 zna 7, Duński i Francuski zna 8, Niemiecki i Turecki zna 9, Niemiecki i Duński zna 5, Niemiecki i Francuski i Duński zna 3, Niemiecki i Francuski i Turecki zna 4, Francuski i Duński i Turecki zna 3, Niemiecki i Francuski i Turecki i Duński zna 2? Zadanie 3.67. Oblicz, ile liczb mniejszych od 100 nie jest podzielnych przez żadną z liczb 2, 3, 5 lub 7. 3.9 Zasada szufladkowa Dirichleta Przykład 3.68. Pewna grupa ludzi wita się podając sobie ręce. Nikt nie wita się z samym sobą, a żadna para nie wita się więcej niż raz. Pokazać, że będą istniały 2 osoby, które witały się tyle samo razy. Odpowiedz 3.68. Mamy n osób. Możliwe liczby powitań to od 0 do n - 1, przy czym nie jest możliwe, by jednocześnie występowała osoba z 0 i osoba z n - 1 powitaniami. Zatem liczba możliwych różnych ilości powitań jest równa co najwyżej n - 1. Skoro osób jest n, z zasady szufladkowej Dirichleta otrzymujemy tezę. Zadanie 3.69. Paweł ma w szufladzie 200 białych skarpetek i 300 czarnych. Lewe skarpetki są nieodróżnialne od prawych. Niestety Paweł nie potrafi odróżnić koloru białego od czarnego. Ile skarpetek musi on zabrać, aby mieć pewność, że choć dwie będą tego samego koloru? Ile skarpetek musi on zabrać, aby mieć pewność, że choć 10 będzie tego samego koloru? Zadanie 3.70. Pokazać, że wśród 25 studentów zdających egzamin zawsze znajdzie się pięciu, którzy otrzymali tę samą ocenę przy skali ocen: 2, 3, 3+, 4, 4+, 5. Zadanie 3.71. Uzasadnij, że wśród dowolnych 14 liczb naturalnych znajdziemy dwie, które przy dzieleniu przez 13 dają tę samą resztę. Zadanie 3.72. Kabel długości 100cm tniemy dowolnie na 6 części, każda o całkowitej długości. Uzasadnij, że zawsze któraś z części będzie miała długość przynajmniej 17cm. Czy zawsze musi powstać część dłuższa niż 17cm? Zadanie 3.73. Uzasadnij, że wśród dowolnych pięciu punktów należących do wnętrza kwadratu " o boku 2 zawsze są dwa punkty odległe o nie więcej niż 2. Zadanie 3.74. Mając danych 10 dowolnych różnych liczb dodatnich mniejszych od 107 pokazać, że będą istniały dwa rozłączne podzbiory tych liczb, których elementy dają taką samą sumę. Zadanie 3.75. Udowodnić, że wśród dowolnych n+1 liczb całkowitych będzie istniała para liczb różniących się o wielokrotność n. Wskazówka. Mając dane liczby l0, . . . , ln rozważyć n szufladek ponumerowanych 0, 1, . . . , n - 1. Następnie rozważyć każdą z liczb li - l0 i włożyć ją do szufladki odpowiadającej reszcie z dzielenia tej liczby przez n. Zadanie 3.76. Udowodnić, że wśród dowolnych n + 1 liczb całkowitych ze zbioru {1, 2, . . . , 2n} istnieje taka, która jest wielokrotnością innej. Wskazówka. Rozważyć n szuflad ponumerowanych kolejnymi liczbami nieparzystymi 1, 3, . . . , 2n - 1. Każdą z wylosowanych liczb wkładamy do szuflady z numerem m, jeżeli k = 2rm dla jakiegoś r e" 0. 11 3.10 Algorytmy generowania podzbiorów i permutacji Algorytm generowania podzbiorów zbioru {1, . . . , n}. pierwszy podzbiór to "; kolejny podzbiór po podzbiorze A: Ć" znajdujemy największy element nie należący do A, czyli a = max{i " A}; Ć" jeżeli nie ma takiego a, to rozważany podzbiór A jest ostatnim Koniec; Ć" w przeciwnym przypadku, dodajemy a do zbioru A i usuwamy z A wszystkie elementy większe od a. Przykład 3.77. Rozważmy zbór {1, 2, 3, 4, 5, 6} i załóżmy, że wygenerowaliśmy podzbiór A = {1, 2, 3, 6}. Spośród elementów nienależących do A algorytm znajduje największy, czyli a = 5. Wstawiamy 5 do A i usuwamy wszystkie x > 5, czyli tutaj tylko 6, otrzymując {1, 2, 3, 5}. Zadanie 3.78. Wypisz 10 kolejnych podzbiorów zbioru {1, 2, 3, 4, 5, 6}. Zadanie 3.79. Wypisz 10 kolejnych podzbiorów zbioru {1, 2, 3, 4, 5, 6, 7} poczynając od podzbioru {1, 2, 3, 5}. Algorytm generowania k-elementowych podzbiorów {1, . . . , n}. pierwszy podzbiór to {1, . . . , k}; kolejny podzbiór po podzbiorze A = (a1, . . . , ak), gdzie a1 < . . . < ak: Ć" znajdujemy najmniejsze i takie, że ai + 1 " A; Ć" jeżeli ai = an, to rozważany podzbiór A = {n - k + 1, . . . , n} jest ostatnim Koniec; Ć" w przeciwnym przypadku, zwiększamy ai o jeden, a elementy mniejsze od ai zamieniamy na i - 1 najmniejszych kolejnych liczb, tzn. aj := j, dla j < i. Przykład 3.80. Rozważmy zbiór {1, 2, 3, 4, 5, 6, 7) i załóżmy, że wygenerowaliśmy już podzbiór {2, 3, 4, 6}. Algorytm znajduje i = 3, bo ai = 4 i ai + 1 = 5 " {2, 3, 4, 6}. Zatem ai := ai + 1 = 5, a elementy a1, a2 przyjmują odpowiednio wartości 1 i 2. Zatem kolejny podzbiór to {1, 2, 5, 6}. Zadanie 3.81. Wypisz 10 kolejnych 3-elementowych podzbiorów zbioru {1, 2, 3, 4, 5, 6}. Zadanie 3.82. Wypisz 10 kolejnych 5-elementowych podzbiorów zbioru {1, 2, 3, 4, 5, 6, 7}. 12 Algorytm generowania permutacji zbioru {1, . . . , n}. pierwsza permutacja to ai = i, dla 1 e" i e" n, kolejna permutacja po permutacji (a1, . . . , an): Ć" znajdujemy największe j spełniające warunek aj < aj+1 Ć" jeżeli nie ma takiego j, to rozważana permutacja jest permutacją ostatnią Koniec Ć" w przeciwnym przypadku, zamieniamy aj z najmniejszym ak takim, że ak > aj i k > j, a następnie odwracamy porządek elementów aj+1, . . . , an Przykład 3.83. Rozważmy permutację (436521). Algorytm znajduje j = 2 i aj = 3. Mamy: 3 < 6 = a3 i 3 < 5 = a4, zatem zamieniamy a2 z a4. Następnie odwracamy kolejność elementów a3, a4, a5, a6, otrzymując (451236). Zadanie 3.84. Wypisz 10 kolejnych permutacji zbioru {1, 2, 3, 4, 5, 6} poczynając od permutacji (456321). Zadanie 3.85. Wypisz 10 kolejnych permutacji zbioru {1, 2, 3, 4, 5, 6, 7} poczynając od permu- tacji (5463721). 3.11 Permutacje raz jeszcze Na permutację n-elementową można patrzeć jak na dowolną różnowartościową funkcję ze zbioru {1, 2, . . . , n} na ten sam zbiór. Na oznaczenie permutacji Ą używa się zapisu
1 2 . . . n Ą = . Ą(1) Ą(2) . . . Ą(n) Przykładem permutacji jest
1 2 3 4 5 Ą = , 2 5 4 3 1 która jest funkcją przyjmującą następujące wartości: Ą(1) = 2, Ą(2) = 5, Ą(3) = 4, Ą(4) = 3 oraz Ą(5) = 1. Dwie permutacje można składać tak, jak się składa funkcje. Złożenie permutacji Ą1 i Ą2 określone jest wzorem Ą1 ć% Ą2(x) = Ą1(Ą2(x)). Na przykład dla permutacji
1 2 3 4 1 2 3 4 Ą1 = oraz Ą2 = 2 1 4 3 3 1 4 2 ich złożenie Ą = Ą1 ć% Ą2 wynosi
1 2 3 4 Ą = , 4 2 3 1 ponieważ Ą(1) = Ą1(Ą2(1)) = Ą1(3) = 4, Ą(2) = Ą1(Ą2(2)) = Ą1(1) = 2, ponieważ Ą(3) = Ą1(Ą2(3)) = Ą1(4) = 3, oraz Ą(4) = Ą1(Ą2(4)) = Ą1(2) = 1. 13 Zbiór Sn wszystkich permutacji na zbiorze {1, 2, . . . , n} z działaniem złożenia ma następujące własności: a) Złożenie permutacji jest łączne, czyli, dla każdych trzech permutacji Ą1, Ą2 oraz Ą3 zachodzi Ą1 ć% (Ą2 ć% Ą3) = (Ą1 ć% Ą2) ć% Ą3. b) Wśród permutacji istnieje identyczność id, czyli permutacja, która każdemu x z dziedziny przypisuje wartość id(x) = x. Identyczność jest elementem neutralnym operacji składania permutacji, ponieważ dla każdej permutacji Ą zachodzi Ą ć% id = id ć% Ą = Ą. c) Dla każdej permutacji Ą istnieje permutacja odwrotna (funkcja odwrotna) Ą-1 spełniająca warunek Ą ć% Ą-1 = Ą-1 ć% Ą = id. Na przykład dla permutacji
1 2 3 4 1 2 3 4 , . 3 4 1 2 3 4 2 1 14 Zadanie 3.88. Ile jest 6-elementowych permutacji Ą spełniających warunek: a) Ą(2) = 3; b) Ą(2) = 3 oraz Ą(3) = 2? Zadanie 3.89. Wyznacz liczbę permutacji Ą ze zbioru S6, które spełniają Ą2 = id, Ą = id.
Często stosuje się cykliczną notację permutacji. Rozważmy dla przykładu permutację
1 2 3 4 5 Ą = . 2 5 4 3 1 Zauważmy, że Ą(1) = 2, Ą(2) = 5 oraz Ą(5) = 1 mówimy tym samym, że elementy 1, 2 oraz 5 tworzą cykl (1 2 5) długości 3. Analogicznie, mając na uwadze, że Ą(3) = 4 oraz Ą(4) = 3, otrzymujemy cykl (3 4) długości 2. Permutację Ą możemy teraz zapisać jako Ą = (1 2 5) ć% (3 4), albo równoważnie Ą = (1 2 5)(3 4) (tzn. bez znaku operatora ć%). Dowolną permutację Ą zbioru X = {1, . . . , n} możemy rozłożyć na rozłączne cykle w sposób następujący: 1) Wybieramy dowolny element x " X, który nie jest jeszcze w żadnym cyklu. 2) Iterujemy permutację Ą otrzymując kolejno: x, Ą1(x), Ą2(x), Ą3(x), . . . aż do uzyskania Ąj(x) = x, gdzie Ąi(x) = Ą ć% . . ć% Ą(x), i = 1, 2, . . . , j. . i razy
3) Dodajemy do rozkładu cykl x Ą1(x) Ą2(x) Ą3(x) . . . Ąj-1(x) . 4) Jeśli w zbiorze X pozostały jeszcze elementy niepokryte przez żaden cykl, to wracamy do kroku (1) naszej procedury. Jeśli permutacja Ą złożona jest z k rozłącznych cykli, to zapisujemy ją jako Ą = (x1 . . .)(x2 . . .) . . . (xk . . .), gdzie w kolejnych nawiasach są elementy kolejnych cykli zaczynających się odpowiednio od x1, . . . , xk. Należy podkreślić, że nie ma znaczenia kolejność cykli, ani to, od jakiego elementu zaczynamy cykl np. (1 2 5)(3 4) i (3 4)(2 5 1) oznaczają tę samą permutację ważne natomiast są długości cykli i kolejność elementów je tworzących. A dokładnie, zachodzi następujące twierdzenie. Twierdzenie 3.7 (Rozkład permutacji na cykle) Rozkład permutacji na cykle jest jednoznaczny z dokładnością do kolejności cykli i elementów początkowych. 15 Przykład 3.90. Rozważmy permutację
1 2 3 4 5 6 7 8 9 Ą = . 3 4 7 1 5 2 6 9 8 Rozkład Ą na cykle jest następujący: " pierwszy cykl: 1, Ą(1) = 3, Ą(3) = 7, Ą(7) = 6, Ą(6) = 2, Ą(2) = 4, Ą(4) = 1; " drugi cykl: 5, Ą(5) = 5; " trzeci cykl: 8, Ą(8) = 9, Ą(9) = 8. Otrzymujemy ostatecznie Ą = (1 3 7 6 2 4)(5)(8 9). Zadanie 3.91. Niech Ą1 = (1 2 3)(4 5 6)(7 8) oraz Ą2 = (1 3 5 7)(2 6)(4)(8). Wyznacz Ą1 ć% Ą2, 2 3 2 3 -1 Ą2 ć% Ą1, Ą1, Ą1, Ą2, Ą2 oraz Ą1 , i przedstaw je w postaci cyklicznej. Zadanie 3.92. Permutacja Ą " Sn jest nazywana cykliczną, jeśli jest postać w notacji cyklicznej składa się z jednego cyklu długości n. Wykaż, że istnieje dokładnie (n-1)! permutacji cyklicznych w zbiorze Sn. Przykład 3.93. Dwanaście kart ponumerowanych 1, . . . , 12 leży na stole w następujący sposób: 1 2 3 4 5 6 7 8 9 10 11 12 Zbieramy te karty od lewej do prawej, z kolejnych 4 wierszy, a następnie rozkładamy je, ale tym razem z góry na dół, w kolejnych 3 kolumnach. 1 5 9 2 6 10 3 7 11 4 8 12 Ile razy musimy powtórzyć powyższą operację, aby otrzymać pierwotne ułożenie kart? Odpowiedz 3.93. Niech Ą będzie permutacją, która określa zmianę ułożenia kart, a dokładnie, mamy Ą(i) = j, jeśli karta j pojawia się na pozycji zajmowanej uprzednio przez kartę i. Wówczas notacja cykliczna Ą jest postaci (1)(2 5 6 10 4)(3 9 11 8 7)(12). Cykle (1) oraz (12) oznaczają, że karty 1 i 12 zawsze pozostają na swoim miejscu. Jako że pozostałe cykle mają długość 5, dokładnie ta liczba powtórnych przełożeń kart wystarczy, aby znalazły się one w swoim pierwotnym ułożeniu. (Zauważmy także, że Ą5 = id.) Zadanie 3.94. Rozwiąż powyższy problem z kartami przy założeniu, że dostępnych jest 20 kart i rozważamy ułożenie postaci: 5 wierszy po 4 karty. Typem permutacji Ą nazywamy wektor (c1, c2, . . . , cn), gdzie ci jest liczbą cykli długości i w rozkładzie Ą na cykle. Zazwyczaj typ permutacji zapisuje się jako [1c12c2 . . . ncn], przy czym często pomija się te wartości, dla których ci = 0. 16 Przykład 3.95. Permutacja Ą = (1 3 7 6 2 4)(5)(8 9) ma jeden cykl długości 1, jeden cykl długości 2 oraz jeden cykl długości 6, a więc jest typu [112161]. Transpozycja to permutacja typu [1n-221]. Innymi słowy, transpozycja dokonuje tylko jednego przestawienia dwóch elementów. Przykład 3.96. Dla permutacji Ą " S7
1 2 3 4 5 6 7 Ä„ = 1 2 6 4 5 3 7 mamy Ä„ = (1)(2)(3 6)(4)(5)(7) = (2 5), a wiÄ™c Ä„ jest typu [1521], co oznacza, że Ä„ jest transpozycjÄ…. Twierdzenie 3.8 Dowolny cykl z Sn jest zÅ‚ożeniem n - 1 transpozycji. Ponieważ, na mocy twierdzenia 3.7, dowolna permutacja może być rozÅ‚ożona na cykle, zatem z powyższego twierdzenia wynika, że każda permutacja jest zÅ‚ożeniem transpozycji. W szczególnoÅ›ci, każda permutacja typu [1c12c2 . . . ncn] ma rozkÅ‚ad na co najwyżej c2 + 2c3 + . . . + (n - 1)cn transpozycji. PrzykÅ‚ad 3.97. Jak Å‚atwo sprawdzić, permutacja cykliczna Ä„ = (1 2 3) " S5 jest zÅ‚ożeniem transpozycji Ä1 = (1 3) oraz Ä2 = (1 2). x 1 2 3 4 5 Ä1 3 2 1 4 5 Ä2 2 1 3 4 5 x 1 2 3 4 5 Ä1 ć% Ä2 2 3 1 4 5 W ogólnoÅ›ci zachodzi: (x1 x2 x3 . . . xk-1 xk) = (x1 xk)(x1 xk-1) . . . (x1 x3)(x1 x2). Permutacja jest parzysta, gdy jest zÅ‚ożeniem parzystej liczby transpozycji, w przeciwnym wypadku jest nieparzysta. Znak sign(Ä„) permutacji Ä„ to sign(Ä„) = (-1)r, gdzie r jest liczbÄ… transpozycji, na które można rozÅ‚ożyć Ä„. PrzykÅ‚ad 3.98. Rozłóż podanÄ… permutacjÄ™ Ä„ " S9 na cykle i transpozycje. Wyznacz typ tej permutacji. Czy permutacja Ä„ jest parzysta?
1 2 3 4 5 6 7 8 9 Ą = . 3 6 4 5 1 2 9 7 8 Odpowiedz 3.98. Rozłóżmy najpierw permutację Ą na cykle: " cykl pierwszy: (1 3 4 5); " cykl drugi: (2 6); 17 " cykl trzeci: (7 9 8). A zatem Ą = (1 3 4 5)(2 6)(7 9 8), a tym samym Ą jest typu [213141]. Aby przedstawić teraz Ą jako złożenie transpozycji, najpierw rozkładamy każdy z cykli, zgodnie ze sposobem podanym wyżej: " (1 3 4 5) = (1 5)(1 4)(1 3). " (2 6) bez zmian. " (7 9 8) = (7 8)(7 9). A zatem otrzymujemy, że Ą = (1 5)(1 4)(1 3)(2 6)(7 8)(7 9) i Ą jest permutacją parzystą. Zadanie 3.99. Permutacje Ą1, Ą2 " S7 zadane tabelami:
1 2 3 4 5 6 7 1 2 3 4 5 6 7 Ą1 = Ą2 = 3 4 6 5 7 1 2 4 7 3 5 1 6 2 rozłóż na cykle i transpozycje. Wyznacz typy tych permutacji. Zadanie 3.100. Rozłóż podaną permutację Ą " S14 na cykle i transpozycje. Wyznacz typ tej permutacji. Czy permutacja Ą jest nieparzysta?