Kombinatoryka
Kapitoly: Kombinatoryka, Wariacje, Permutacja, Kombinacja, Wariacje z powtórzeniami, Kombinacje z powtórzeniami, Ile jest różnych kodów PIN?, Kalkulator.
Chcesz wiedzieć, ile różnych piątek możesz wybrać z talii 32 kart? Właśnie tego typu problemy rozwiązuje kombinatoryka. Istnieją dwie podstawowe reguły kombinatoryki - suma i iloczyn. Wszystkie inne procedury są jedynie rozszerzeniami tych podstawowych zasad.
Kombinatoryczna reguła sumy
Reguła sumy jest bardzo prosta - mówi nam, że jeśli mamy zbiory A, B, które nie mają wspólnego elementu, to liczba wszystkich możliwych sposobów wyboru jednego elementu z unii A ∪ B jest równa |A| + |B|, czyli sumie rozmiarów zbiorów.
Zacznijmy od lekkiego przykładu. Mamy 6 czerwonych i 8 niebieskich kulek. Wrzućmy te kulki do jednej puli. Ile mamy w sumie możliwości, jeśli wylosujemy jedną kulę? Na początku mieliśmy zbiór kul czerwonych, oznaczmy go jako zbiór A, a następnie zbiór kul niebieskich, oznaczmy go jako B. Zbiory te są rozłączne, tzn. nie mają tej samej kuli. Chcemy wylosować jedną kulę, więc mamy łącznie |A| + |B| = 6 + 8 = 14 możliwości. To wszystko.
Reguła iloczynu kombinatorycznego
Ponownie mamy dwa zbiory, Z i M. Zbiór Z zawiera trzy kobiety, a zbiór M zawiera czterech mężczyzn. Teraz pytamy, ile różnych par muž—žena możemy utworzyć z tych zestawów? Staramy się zawsze brać jedną kobietę i przypisywać jej mężczyznę. Liczymy liczbę wszystkich par w następujący sposób: bierzemy jedną kobietę, Kate, i przypisujemy jej kolejno wszystkich mężczyzn. To daje nam 4 różne pary, ponieważ możemy przypisać jej 4 różnych mężczyzn. To samo robimy z pozostałymi dwiema kobietami, za każdym razem tworząc 4 kolejne pary. I to wszystko, mamy w sumie 4 + 4 + 4 = 12 par.
Co właściwie zrobiliśmy? Pomnożyliśmy rozmiar dwóch zestawów. Mieliśmy 3 panie i 4 panów, więc całkowita liczba par wynosi 3 · 4 = 12. Stąd reguła iloczynu kombinatorycznego. Jeśli więc mamy dwa dowolne zbiory, z których tworzymy pary, po prostu mnożymy liczbę elementów jednego zbioru przez liczbę elementów drugiego zbioru.
Poniżej widać, że jest to prawdą. Poniżej znajdują się wszystkie sposoby, w jakie możemy połączyć w pary 3 kobiety i 4 mężczyzn. Każdy wiersz reprezentuje możliwości dla jednej z kobiet, a każda kolumna reprezentuje możliwości dla jednego z mężczyzn. Mamy więc trzy wiersze i cztery kolumny, co daje łącznie řádky · sloupce możliwości.
$$\begin{eqnarray} &&[Z_1, M_1], [Z_1, M_2], [Z_1, M_3], [Z_1, M_4], \\ &&[Z_2, M_1], [Z_2, M_2], [Z_2, M_3], [Z_2, M_4], \\ &&[Z_3, M_1], [Z_3, M_2], [Z_3, M_3], [Z_3, M_4] \end{eqnarray}$$
Rozwiązane przykłady
- Ile jest różnych liczb dwucyfrowych? Jak wygląda taka dwucyfrowa liczba? Jedna z cyfr występuje na pierwszym miejscu 1, …, 9, podczas gdy na drugim miejscu może znajdować się dodatkowe zero: 0, …, 9 Mamy więc 9 cyfr w pierwszym zestawie i 10 w drugim. Stosujemy regułę iloczynu kombinatorycznego, aby uzyskać ostateczny wynik: 9 · 10 = 90.
- Ile jest różnych liczb trzycyfrowych, w których żadna cyfra nie może wystąpić dwukrotnie? Dziewięć cyfr może być ponownie na pierwszym miejscu, ale liczba nie może zaczynać się od zera. Na drugiej pozycji mogą być wszystkie cyfry, w tym zero, ale nie może być cyfry występującej na pierwszej pozycji, więc odejmujemy jeden od liczby dziesięciu możliwych cyfr (na przykład, jeśli nasza trzycyfrowa liczba zaczyna się właśnie od czterech, jasne jest, że cztery nie może już wystąpić na drugiej pozycji, ponieważ byłaby dwa razy w całej liczbie). Ponownie, wszystkie cyfry mogą znajdować się na trzeciej pozycji, ale cyfra znajdująca się na pierwszej lub drugiej pozycji nie może tam być. Powód jest ponownie ten sam. Jeśli cyfra 4 znajduje się na pierwszym miejscu, a cyfra 7 na drugim, możemy dodać jedną cyfrę z {0, …, 9} ∖ {4, 7} na trzecie miejsce. Teraz wystarczy pomnożyć przez 9 · 9 · 8 = 648. Całkowita liczba kombinacji wynosi 648.
- Rzuć kostką dwa razy z rzędu. Ile różnych wyników możemy uzyskać? Przy pierwszym rzucie możemy uzyskać 6 różnych wyników. Przy drugim rzucie całkowita liczba możliwości wynosi 6 · 6 = 36.
- Rzuć kostką dwa razy z rzędu. Ile różnych wyników możemy uzyskać, jeśli w pierwszym rzucie wyrzucimy liczbę parzystą? W pierwszym rzucie wyrzucono liczbę parzystą, tzn. wyrzucono jedną z liczb 2, 4, 6, co daje łącznie 3 możliwości. W drugim rzucie można wyrzucić dowolną liczbę, więc mamy łącznie 3 · 6 = 18 możliwości.