Kombinatoryka - reguła mnożenia
Iloczyn kartezjański
Iloczyn kartezjański zbiorów \$A\$ i \$B\$, to zbiór zawierający pary uporządkowane \$(a;b)\$, gdzie element \$a\in A\$ oraz \$b\in B\$.
\[ A\times B = \{ (a;b) : a\in A \ \text{oraz} \ b\in B \} \]Parę uporządkowaną traktujemy jako element w którym kolejność ma znaczenie.
Niech będą zbiory:
\$M = \{ a, b, c \}\$
\$N = \{ 10, 20, 30, 40 \}\$
Weźmy zbiór składający się z iloczynu kartezjańskiego \$M\times N\$:
\[\begin{aligned} M\times N = \{ &(a;10), (a;20), (a;30), (a;40) \\ &(b;10), (b;20), (b;30), (b;40) \\ &(c;10), (c;20), (c;30), (c;40) \} \end{aligned} \]Na każdy element ze zbioru \$M\$ przypada element ze zbioru \$N\$. Razem jest \$3*4=12\$ elementów zbioru.
Zauważ, że w zbiorze \$M\times N\$ nie ma np. elementu \$(30; b)\$. Iloczyn kartezjański nie jest przemienny. To jest \$M\times N \neq N\times M\$.
Weźmy zbiór składający się z iloczynu kartezjańskiego \$N\times M\$:
\[\begin{aligned} N\times M = \{ &(10;a), (20; a), (30;a), (40;a) \\ &(10;b), (20; b), (30;b), (40;b) \\ &(10;c), (20; c), (30;c), (40;c) \} \end{aligned} \]Reguła mnożenia
Dla dwóch zbiorów skończonych \$A\$ i \$B\$ zachodzi.
\[ |A\times B| = |A| * |B| \]Własność ta mówi, że ilość przyporządkowań każdemu elementowi ze zbioru \$A\$ elementu ze zbioru \$B\$ jest równa:
\[ \text{ilość elementów w A} * \text{ilość elementów w B} \]Musimy znaleźć wszystkie możliwe pary \$(chłopiec;dziewczyna)\$ albo \$(dziewczyna;chłopiec)\$.
\$D\$ - zbiór dziewcząt
\$C\$ - zbiór chłopców
\$|D| = 12\$
\$|C| = 9\$
Ilość wszystkich możliwych par chłopców i dziewcząt wynosi.
\[\begin{aligned} |C\times D| &= |C| * |D| \\ &= 9*12 = 108 \end{aligned} \]Odp.Wszystkich możliwych par chłopców i dziewcząt jest \$108\$.
Kolejność wylosowania elementów w poszczególnych rzutach ma znaczenie. Na przykład dwa wyniki poniżej różnią się od siebie.
\[ (Orzeł, Reszka, Orzeł) \neq (Reszka, Reszka, Orzeł) \]\$A = \{ O, R \}\$ - zbiór możliwych losowań w jednym rzucie
Ilość wszystkich możliwych wyników losowania:
\[\begin{aligned} |A\times A\times A| &= |A| * |A| * |A| \\ &= 2*2*2 = 8 \end{aligned} \]Odp. Wszystkich możliwych wyników jest \$8\$.
Kolejność wylosowania elementów w poszczególnych rzutach ma znaczenie. Na przykład dwa wyniki poniżej różnią się od siebie.
\[ (3,5, 1) \neq (1,5,3) \]\$A = \{ 1, 2, 3, 4, 5, 6\}\$ - zbiór możliwych losowań w jednym rzucie
Ilość wszystkich możliwych wyników losowania:
\[\begin{aligned} |A\times A\times A| &= |A| * |A| * |A| \\ &= 6*6*6 = 6^3 \end{aligned} \]Odp. Wszystkich możliwych wyników jest \$6^3\$.
Kolejność ustawiania osób ma znaczenie. Możemy je ustawić w ciąg taki jak poniżej.
\[ (osoba1, osoba2, osoba3, osoba4, osoba5) \]
Przy czym osoby nie mogą się powtarzać.
\$A_5\$ - zbiór wszystkich pięciu osób
\$A_4\$ - zbiór osób bez jednej wybranej z \$A_5\$
\$A_3\$ - zbiór osób bez jednej wybranej z \$A_4\$
\$A_2\$ - zbiór osób bez jednej wybranej z \$A_3\$
\$A_1\$ - zbiór osób bez jednej wybranej z \$A_2\$
Ilość wszystkich możliwych ustawień osób:
\[\begin{aligned} |A_5\times A_4\times A_3\times A_2\times A_1| &= |A_5| * |A_4| * |A_3| * |A_2| * |A_1| \\ &= 5*4*3*2*1=120 \end{aligned} \]Odp. Wszystkich możliwych ustawień osób jest \$120\$.
Miejsca parkingowe mogą być różnie rozlokowane, ale wybór konkretnego miejsca ma znaczenie.
Będziemy mieć ciąg pięciu elementów. Położenie w ciągu odpowiada miejscu parkingowemu.
\[ (samochód1, samochód2, samochód3, samochód4, samochód5) \]
Przy czym samochody nie mogą się powtarzać.
\$A_8\$ - zbiór wszystkich ośmiu samochodów
\$A_7\$ - zbiór samochodów bez jednego wybranego z \$A_8\$
\$A_6\$ - zbiór samochodów bez jednego wybranego z \$A_7\$
\$A_5\$ - zbiór samochodów bez jednego wybranego z \$A_6\$
\$A_4\$ - zbiór samochodów bez jednego wybranego z \$A_5\$
Ilość wszystkich możliwych ustawień samochodów:
\[\begin{aligned} & = |A_8\times A_7\times A_6\times A_5\times A_4| \\ & = 8*7*6*5*4 \\ & = 6720 \end{aligned} \]Odp. Wszystkich możliwych ustawień samochodów jest \$6720\$.