4.2 Podstawowe reguły kombinatoryczne (basic counting methods)

Podstawowe reguły kombinatoryczne, które wykorzystuje się w rachunku prawdopodobieństwa do wyznaczania liczebności przestrzeni zdarzeń elementarnych (\(|S|\) lub \(|\Omega|\)):

1. reguła sumy,
2. reguła mnożenia,
3. permutacje (nPk).
4. kombinacje (nCk).

4.2.1 Reguła sumy

Jeśli pierwsze zadanie można wykonać na \(n1\) sposobów (\(n1\) opcji), podczas gdy drugie zadanie można wykonać na \(n2\) sposoby, a dwa zadania nie mogą być wykonane jednocześnie, to wykonanie któregokolwiek z zadań można wykonać na dowolny z \(n1 + n2\) sposobów.

Ćwiczenie: Wydział przyzna darmowy komputer studentowi lub profesorowi CS (informatyki). Ile jest różnych opcji, jeśli jest 530 studentów i 15 profesorów?

Przykład: Bruce chce każdego dnia spróbować innego posiłku. Ile czasu zajmuje mu jednorazowe spróbowanie każdego posiłku? W menu jest 9 rodzajów pizzy i 6 rodzajów makaronów.

W sumie jest 9 + 6 = 15 rodzajów posiłków. Tak więc Bruce potrzebuje 15 dni.

Rozszerzmy regułę sumy na dowolną liczbę zestawów:

Jeśli \(A_1, \ldots, A_n\) są rozłączne parami, to \(| A_1 \cup \ldots \cup A_n | = | A_1 | + | A_2 | + \ldots + | A_n |\).

4.2.1.1 Zasada włączenia-wykluczenia

Co jeśli zestawy nie są rozłączne? Np. Kierunki matematyczne i CS (informatyki), gdzie niektórzy specjalizują się w obu? Najpierw rozważ dwa zbiory. Jeśli \(A\) i \(B\) są dowolnymi zbiorami (niekoniecznie rozłącznymi), to \(| A \cup B | = | A | + | B | - | A \cap B |\).

Zasada włączenia-wykluczenia wyraża fakt, że suma rozmiarów obu zbiorów może być zbyt duża, ponieważ niektóre elementy mogą być liczone dwukrotnie. Elementy liczone podwójnie to te, które znajdują się na przecięciu dwóch zestawów, a liczba jest korygowana przez odjęcie rozmiaru przecięcia.

Przykład. Załóżmy, że ankieta obejmująca 100 osób zapyta, czy mają kota lub psa jako zwierzaka. Wyniki są następujące: 55 osób odpowiedziało tak dla kota, 58 tak dla psa, a 20 osób odpowiedziało tak zarówno dla kota, jak i psa. Ile osób ma kota lub psa? - Rozwiązanie: Ponieważ 55 ma kota, a 58 psa, na początku możesz pomyśleć, że 55 + 58 = 113 mają jedno lub drugie.

To rozumowanie pomija fakt, że niektórzy ludzie - 20 - mają jedno i drugie zwierzę, a my policzyliśmy te osoby dwukrotnie, dodając 55 i 58. Aby poprawić naszą odpowiedź, mysimy odjąć od tej sumy liczbę 20: 55 + 58 - 20 = 93 mieć kota lub psa. To jest przykład zasady włączenia-wykluczenia.

Zasada jest wyraźniej widoczna w przypadku trzech zbiorów, co dla zbiorów A, B i C daje

\(|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|\)

Źródło: Wikipedia.org

4.2.2 Reguła iloczynu

Jeśli daną czynność wykonujemy w dwóch etapach; na pierwszym etapie mamy n możliwości, a na drugim etapie m sposobów wykonania tej czynności, to cała czynność może być wykonana n * m sposobów.

Ogólniej, jeśli jakaś czynność składa się z kilku etapów (np. wieloetapowy eksperyment losowy składający się z losowań z populacji n osób do próby), na pierwszym etapie mamy \(k_1\) możliwości, na drugim \(k_2, ...,\) na n-tym etapie \(k_n\) możliwości, to wtedy łączna liczba sposobów wykonania czynności (np. łączna liczba możliwych prób) jest równa \(k = k_1 \times k_2 \times ... \times k_n\)

Dla przykładu, jeśli rzucamy dwa razy monetą, to łączna liczba wyników jest równa 4. Gdy rzucamy dwa razy kostką sześcienną, to łączna liczba wyników jest równa 36.

Przykład. W New Hampshire tablice rejestracyjne składają się z dwóch liter, po których następowały 3 cyfry. Ile jest możliwych tablic rejestracyjnych?

Odpowiedź: 26 opcji dla pierwszej litery, 26 dla drugiej, 10 opcji dla pierwszej liczby, drugiej liczby i trzeciej liczby:

262 × 103 = 676000

W przykładach niżej zakładamy, że alfabet ma 26 liter [wyłączamy polskie znaki diakrytyczne]

Ćwiczenie. Ile można utworzyć tablic rejestracyjnych formatu: [3 cyfry | 2 litery]? Składowe nie mogą się powtarzać, pierwsza cyfra różna od zera.

Przykład. Ile jest możliwych tablic rejestracyjnych w formacie - 3 litery i następnie 3 cyfry: \(26 \times 26 \times 26 \times 10 \times 10 \times 10\).

Przykład. Power set, zbiór potęgowy. Jaka jest liczba podzbiorów zestawu elementów \(n\)? To jest \(2 ^n\). Każdy podzbiór odpowiada ciągowi bitów o długości \(n\), gdzie \(1\) na pozycji \(k\) oznacza, że \(k\)-ty element znajduje się w podzbiorze.

Przykład . Ile jest możliwych 4-cyfrowych kodów PIN? Można to rozwiązać jako \(10 · 10 · 10 · 10 = 104 = 10000\). Tak więc istnieje jedna na dziesięć tysięcy szans, że złodziej może odgadnąć Twój kod PIN (losowo).

Rozważmy silniejszy przypadek, w którym musisz użyć każdej cyfry dokładnie raz, więc kod PIN ma dokładnie 10 różnych cyfr. Ile istnieje takich kodów PIN?

Mamy 10 wyborów dla pierwszej cyfry, 9 wyborów dla drugiej cyfry i tak dalej, aż mamy tylko 2 wybory dla dziewiątej cyfry i 1 dla dziesiątej cyfry. Oznacza to, że istnieje 362880 możliwych numerów PIN w tym scenariuszu. Mamy:

\[10 \times 9 \times \ldots \times 2 \times 1 = \prod_{i = 1}^{n = 10} i = 362880\]

Ogólniej:

\[N! = N \times (N − 1) \times (N − 2) \times \ldots \times 3 \times 2 \times 1 = \prod_{j=1}^n j\]

\(N!\) Jest odczytywane jako „N silnia". Należy pamiętać, że \(0! = 1\), ponieważ istnieje jeden sposób na uporządkowanie 0 obiektów.

Wiemy z absolutną pewnością, że \(1! = 1, (n = 1)\). W ten sposób otrzymujemy:

Wiemy, że \(n! = n \times (n-1)!\), wynika z tego, że \(1! = 1 \times (1-1)!\), Wynika z tego, że \(1! = 1 \times 0!\), Więc musi być \(0! = 1\).

Aby równanie było prawdziwe, musimy wymusić zerową silnię równą 1. W przeciwnym razie \(1! \neq 1\) co prowadzi do sprzeczności.

4.2.3 Reguła iloczynu (2)

Załóżmy, że tworzymy 10-cyfrowy kod PIN, ale teraz przynajmniej jedna cyfra musi zostać powtórzona przynajmniej raz. Ile istnieje takich kodów PIN? Niektóre przykłady tego kodu PIN to 1111111111, 01234556788 lub 9876598765, ale lista jest długa!

W tym przypadku dobrym podejściem może być policzenie, ile PINów nie spełnia tej właściwości i następnie odjęcie uzyskanej liczby od łącznej liczby kodów PIN. Ta strategia nazywa się liczeniem uzupełniającym (ang. complementary counting), ponieważ liczymy wielkość dopełnienia zbioru będącego przedmiotem zainteresowania. Liczba możliwych 10-cyfrowych kodów PIN, bez żadnych zastrzeżeń, wynosi \(10^{10}\) (z reguły iloczynu mnożąc przez siebie 10 wyborów dla każdej z 10 pozycji). Stwierdziliśmy powyżej, że 10-cyfrowe kody PIN bez powtórzeń mają 10! możliwości (każda cyfra używana dokładnie raz). Weź pod uwagę, że 10-cyfrowe kody PIN z co najmniej jednym powtórzeniem będą wszystkimi innymi możliwościami. Problem można rozwiązać obliczając różnicę wszystkich możliwych 10-cyfrowych PIN-ów i tych bez powtórzeń. To znaczy: \(10^{10} - 10!\)

4.2.4 Permutacje bez powtórzeń (bez zwracania)

Wzór pozwalający wyznaczyć liczbę \(P_r^n\) r-permutacji bez powtórzeń ze zbioru n-elementów jest następujący

\[P_r^n = \frac{n!}{(n-r)!}\]

przy czym \(n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1\), oraz \(0! = 1\).

Ile jest dwuelementowych permutacji bez powtórzeń ze zbioru \(S = \{R, O\}\)?

Odpowiedź:

\[P_2^2 = \frac{2!}{(2-2)!} = 2! = 1 \times 2 = 2\]

Zbiór permutacji jest następujący: \(\{(R,O), (O, R)\}\). Zbiór ten liczy dwa elementy - \(|\{(R,O), (O, R)\}| = 2\).

Pamiętaj, że zbiór pusty \(\emptyset\) jest podzbiorem każdego zbioru, ale \(|\emptyset| = |\{\}| = 0\).

4.2.5 Kombinacje bez powtórzeń (bez zwracania)

Wzór pozwalający wyznaczyć liczbę \(C_x^n\) x-kombinacji bez powtórzeń ze zbioru n-elementów jest następujący:

\[C_x^n = \binom{n}{x} = \frac{n!}{(n-x)!x!}\]

Ile można utworzyć 6-kombinacji (6-elementowych zbiorów) ze zbioru liczb 1, …, 49?

\[C_6^{49} = \binom{49}{6} = \frac{49!}{(49-6)!6!} = 13 983816\]

Ile jest równe prawdopodobieństwo wylosowania dowolnego zbioru 6 liczb (kolejność jest bez znaczenia) ze zbioru 49 liczb?

\[P(\text{6-elementowy zbiór różnych liczb ze zbioru 49 liczb}) = \frac{\binom{6}{6}}{13983816} = 1/13983816\]

Ile jest dwuelementowych kombinacji bez powtórzeń ze zbioru \(S = \{R, O\}\)?

Odpowiedź:

\[C_2^2 = \frac{2!}{(2-2)!2!} = 2!/2! = 1\]

Zbiór kombinacji jest następujący: \(\{\{0, 1\}\}\) - jest to zbiór jednoelementowy.

4.2.6 Permutacje z powtórzeniami (elementy mogą się powtarzać)

Wzór na liczbę \(P_r^n\) r-permutacji (elementy mogą się powtarzać) z zbioru n-elementów jest jest następujący:

\[P_r^n = n^r\]

Liczba trójelementowych permutacji ze zbioru dwuelementowego jest równa \(2^3 = 8\).

\(S = \{ (R, R, R), (R, R, O), (R, O, O), (O, O, O), (O, O, R), (O, R, R), (O, R, O), (R, O, R) \}\).

4.2.7 Kombinacje z powtórzeniami

Teraz przechodzimy od permutacji z powtórzeniami do kombinacji z powtórzeniami. Niech \(S\) będzie zbiorem \(\{A, B, C \}\). Ten zbiór ma trzy kombinacje dwuelementowe. Oznacza to, że istnieją trzy sposoby, aby wybrać dwa różne elementy \(S\), gdzie kolejność nie ma znaczenia. Poniżej przedstawiono trzy \(2\)-kombinacje ze zbioru \(S\).

\[\{\{ A, B \}, \{ A, C \}, \{ B, C \}\}\]

Załóżmy, że nie musimy wybierać różnych elementów z \(S\), ale możemy wybierać wielokrotnie ten sam element. Wynikowe zbiory nazywane są \(r\)-kombinacjami z powtórzeniami ze zbioru \(S\). Poniżej wymienione jest sześć kombinacji dwuelementowych z powtórzeniami z \(S\).

\[\{\{ A, B \}, \{ A, C \}, \{ B, C \}, \{ A, A \}, \{ B, B \}, \{ C, C \}\}\]

Ściśle mówiąc, są to multizbiory, a nie zbiory, ponieważ element może występować wielokrotnie.

4.2.7.1 Obliczanie \(r\)-kombinacji z powtórzeniami

Liczba \(r\)-kombinacji z powtórzeniami ze zbioru elementów \(n\) wynosi

\[\binom{n + r - 1}{r}\]

W powyższym przykładzie znaleźliśmy sześć sposobów wyboru dwóch elementów ze zbioru \(S = \{A, B, C\}\) z dozwolonymi powtórzeniami. Oczywiście twierdzenie mówi, że liczba kombinacji 2 w zestawie 3-elementowym wynosi \(\binom{3 + 2 - 1}{2} = 6\).

Dla porównania, pamiętaj, że liczba zwykłych kombinacji \(r\) zestawu elementów \(n\) wynosi \(\binom{n}{r}\). Każda zwykła kombinacja \(r\) jest również poprawną \(r\)-kombinacją z powtórzeniami.