To tylko jedna z 38 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Matematyka Dyskretna Jarosław Grytczuk 1 O trudnej sztuce liczenia 1.1 Zasada Mno˙zenia Jolanta K. (imi ˛e i inicjał fikcyjne) wybiera si ˛e na koncert charytaty- wny. Jak zwykle w takich wypadkach staje przed kolosalnym problemem wyboru kreacji oraz zestawu dodatków: kapelusza, torebki i butów. Po krótkiej dyskusji z m ˛e˙zem, który zawsze doradza jej w tych sprawach, okazało si ˛e, ˙ze w gr ˛e wchodz ˛ a 3 kapelusze, 6 torebek i 4 pary butów. Ile jest wszystkich mo˙zliwych sposobów zestawienia tych dodatków? Po chwili namysłu Jolanta K. zdobywa absolutn ˛ a pewno´s´c, wszys- tkich mo˙zliwo´sci jest 72. W istocie, do ka˙zdego z 3 kapeluszy mo˙zna dobra´c jedn ˛ a z 6 torebek, co daje 3 · 6 = 18 par (kapelusz, torebka). Teraz, do ka˙zdego z tych 18 układów mo˙ze jeszcze dobra´c jedn ˛ a z 4 par butów, co daje 18 · 4 = 72 zestawy (kapelusz, torebka, buty). Liczba wszystkich mo˙zliwo´sci jest wi ˛ec równa iloczynowi 3 · 6 · 4. Ile spo´sród nich zaspokoi wyrafinowany gust Jolanty–to ju˙z zupełnie inna historia. Powy˙zszy przykład jest ilustracj ˛ a ogólnej zasady, któr ˛ a formułujemy nast ˛epuj ˛ aco. Twierdzenie 1 (Zsada Mno˙zenia) Niech A1, A2, ..., An b ˛ ed ˛ a zbiorami sko´ nczonymi. Wówczas liczba ci ˛ agów (a1, a2, ..., an), gdzie ai ∈ Ai, i = 1, 2, ..., n, wynosi |A1| · |A2| · ... · |An| . Powy˙zsza zasada pozwala na ”przeliczanie” wielu fundamentalnych struktur pojawiaj ˛ acych si ˛e w kombinatoryce. Oto kilka najprostszych sytuacji, w których jej zastosowanie daje natychmiastowy efekt. Ci ˛ agiem binarnym nazywamy ci ˛ ag zło˙zony z zer i jedynek (ogólniej, z elementów dwojakiego rodzaju). Ile jest ci ˛ agów binarnych długo´sci k? 1 Wniosek 2 Mamy 2k ci ˛ agów binarnych długo´sci k. Ogólniej, istnieje nk ci ˛ agów długo´sci k na zbiorze n symboli. Dowód. Wystarczy zastosowa´c Zasad ˛e Mno˙zenia przyjmuj ˛ ac A1 = A2 = ... = An = {0, 1, ..., n − 1}. Jedna z torebek Jolanty posiada zamek szyfrowy. Szyfr jest ci ˛ agiem czterech cyfr ze zbioru {1, 2, ..., 9}. Niestety Jola pami ˛eta tylko, ˙ze ˙zadna cyfra nie była w nim powtórzona. Ile mo˙zliwo´sci w najgorszym razie b ˛edzie musiała sprawdzi´c aby otworzy´c torebk ˛e? Pierwsza cyfra szyfru mo˙ze by´c ka˙zd ˛ a z 9 mo˙zliwych. Za drugim razem mamy ju˙z do wyboru tylko 8 cyfr, poniewa˙z nie mo˙zemy powtórzy´c tej, która stoi na pierwszym miejscu. Za trzecim razem wybieramy ju˙z tylko jedn ˛
... zobacz całą notatkę
Komentarze użytkowników (0)