6218157046

3 Kombinatoryka

[Wyjaśnienie podstawowej zasady mnożenia] Rozpatrujemy grę: rzut kostką, a potem rzut monetą. Ile jest możliwych wyników? [Drzewo gry]

Twierdzenie. Jeżeli zostaje wykonanych N doświadczeń jedno po drugim, w których jest możliwe odpowiednio rii, U2,..., różnych wyników, to w całym doświadczeniu możemy uzyskać

ni ■ 7i2 • ⁿ3 •■ riN

□

różnych wyników.

Przykład

(a)    W grze: rzut kostką—rzut monetą mamy 6 możliwych wynków rzutu kostką i 2 możeliwe wyniki rzutu monetą, a więc w całej grze jest możliwe 6-2 = 12 różnych wyników.

(b)    Grupy studneckie na WZ mają oznaczenie: litera—dwie cyfry (jeżeli pierwszą jest 0 to zwyczajowo nie piszemy jej). Ile grup można w ten sposób oznaczyć? Litera może być jedną z 26, a cyfra jedną z 10, zatem różnych oznaczeń jest 26 • 10 • 10 = 2600.

(c)    W grupie Cli jest 23 studentów, C12 22, C13 - 25, C14 - 23. Ile różnych reprezentacji pojednym przedstawicielu z każdej grupy można utworzyć? Można utworzyć

n(C\l) ■ n(C12) • tz(C13) ■ n(CU) = 23 • 22 • 25 ■ 23 = 290950

reprezentacji.

□

Permutacje

Permutacja n elementowa to ciąg wszystkich elementów z n elementowego zbioru. Na przykład jeżeli rozpatrujemy litery A, B i C to ABC, BAC są przykładami permutacji. Wszystkich permutacji tych liter jest 6:

ABC, ACB, BAC, BCA, CAB, CBA.

Liczbę wszystkich permutacji n elementowych można wyznaczyć korzystając z zasady mnożenia. Najpier wybieramy jedne elment - można to zrobić na n sposobów. Potem wybieramy drugi element - można to zrobić na Ti — 1 sposobów, bo tyle elementów w zbiorze pozostało (elementy w permutacji nie mogą się powtarzać). Czyli mamy ti ■ (ti — 1) wyborów dwóch elementów. Trzeci element można wybrać na 71 — 2 sposobów (bo dwa elementy już zostały zabrane), czyli mamy 71(71 — l)(n — 2) możliwośic wyboru 3 elementów. Analogicznie dalej otrzymamy, że n elementów (czyli wszystkie) można wybrać na

P_n = n(n — l)(n — 2)... 2 • 1 = n!

sposobów.

Przykład

(a) Wszystkich permutacji trech liter jest P₃ = 3 • 2 • 1 = 6.