Przeczytaj

Reguła mnożenia

Reguła: Reguła mnożenia

Liczba wszystkich możliwych wyników doświadczenia polegającego na wykonaniu po kolei $n$ czynności, z których pierwsza może zakończyć się na jeden z $k_{1}$ sposobów, druga – na jeden z $k_{2}$ sposobów, trzecia – na jeden z $k_{3}$ sposobów i tak dalej do $n$ -tej czynności, która może zakończyć się na jeden z $k_{n}$ sposobów, jest równa

k_{1} \cdot k_{2} \cdot \dots \cdot k_{n}

Dla dowodu zauważmy, że dwie pierwsze czynności możemy wykonać na $k_{1} \cdot k_{2}$ sposobów - wystarczy w tym celu rozumować podobnie, jak w przykładzie opisanym we wprowadzeniu.

Zatem postępując analogicznie, stwierdzamy w kolejnych krokach, że:

trzy pierwsze czynności możemy wykonać na $(k_{1} \cdot k_{2}) \cdot k_{3}$ sposobów,
cztery pierwsze czynności możemy wykonać na $(k_{1} \cdot k_{2} \cdot k_{3}) \cdot k_{4}$ sposobów,
...
wszystkie $n$ czynności możemy wykonać na $(k_{1} \cdot k_{2} \cdot \dots \cdot k_{n - 1}) \cdot k_{n} = k_{1} \cdot k_{2} \cdot \dots \cdot k_{n}$ sposobów.

Przykład 1

Obliczymy, ile jest wszystkich siedmioznakowych kodów, które są zapisane według następujących zasad:

pierwszym znakiem jest wybrana wielka litera alfabetu łacińskiego, czyli jeden z dwudziestu sześciu następujących znaków: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z,
drugim znakiem jest wybrana mała litera alfabetu łacińskiego,
na każdym z czterech kolejnych miejsc (trzecim, czwartym, piątym i szóstym) zapisujemy dowolnie wybraną cyfrę ze zbioru {0, 1, 2, …, 9},
na ostatnim miejscu zapisujemy znak specjalny wybrany z ośmioelementowego zbioru {!, @, #, $, %, +, –, _}.

Tworząc taki kod dokonujemy siedmiu kolejnych wyborów, przy czym:

znak na pierwszym miejscu możemy wybrać na 26 sposobów,
znak na drugim miejscu możemy wybrać na 26 sposobów,
znak na trzecim miejscu możemy wybrać na 10 sposobów,
znak na czwartym miejscu możemy wybrać na 10 sposobów,
znak na piątym miejscu możemy wybrać na 10 sposobów,
znak na szóstym miejscu możemy wybrać na 10 sposobów,
znak na siódmym miejscu możemy wybrać na 8 sposobów.

Korzystając z reguły mnożeniareguła mnożeniareguły mnożenia stwierdzamy, ze wszystkich takich kodów jest

$26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 \cdot 10 \cdot 8 = 54080000$

Przykład 2

Obliczymy, ile jest wszystkich dziewięcioznakowych kodów, które da się zapisać według następujących zasad:

pierwsze trzy znaki to trzy różne wielkie litery alfabetu łacińskiego,
na każdym z czterech kolejnych miejsc (czwartym, piątym, szóstym i siódmym) zapisujemy dowolnie wybraną cyfrę ze zbioru {0, 1, 2, …, 9}, przy czym zapisane cyfry są parami różne,
na ostatnich dwóch miejscach (ósmym i dziewiątym) zapisujemy dwie różne małe litery alfabetu łacińskiego, które są samogłoskami, czyli są wybrane spośród znaków a, e, i, o, u, y.

Tworząc taki kod dokonujemy dziewięciu kolejnych wyborów. Opiszemy te wybory z podziałem na trzy etapy.

(1) Opisujemy najpierw możliwości wyboru trzech pierwszych znaków:

znak na pierwszym miejscu możemy wybrać na 26 sposobów,
niezależnie od wyboru dokonanego za pierwszym razem znak na drugim miejscu możemy wybrać na 25 sposobów (nie możemy powtórzyć litery zapisanej na pierwszym miejscu),
niezależnie od wyboru dokonanego za pierwszym i za drugim razem na trzecim miejscu znak możemy wybrać na 24 sposoby (nie możemy powtórzyć liter zapisanych na dwóch pierwszych miejscach).

Korzystając z reguły mnożeniareguła mnożeniareguły mnożenia obliczamy, że trzy początkowe znaki możemy zapisać na $26 \cdot 25 \cdot 24 = 15600$ sposobów.

(2) Wybór znaków na kolejnych czterech miejscach (czwartym, piątym, szóstym i siódmym) odbywa się następująco:

znak na czwartym miejscu możemy wybrać na 10 sposobów,
niezależnie od wyboru czwartego znaku kolejny, na piątym miejscu, możemy wybrać na 9 sposobów (nie możemy powtórzyć cyfry zapisanej na czwartym miejscu),
niezależnie od wyboru czwartego i piątego znaku kolejny, na szóstym miejscu, możemy wybrać na 8 sposobów (nie możemy powtórzyć cyfr zapisanych na czwartym i na piątym miejscu),
niezależnie od wyboru czwartego, piątego i szóstego znaku kolejny, na siódmym miejscu, możemy wybrać na 7 sposobów (nie możemy powtórzyć żadnej z cyfr zapisanych na trzech poprzednich miejscach).

Korzystając z reguły mnożeniareguła mnożeniareguły mnożenia obliczamy, że znaki na miejscach czwartym, piątym, szóstym i siódmym możemy zapisać na $10 \cdot 9 \cdot 8 \cdot 7 = 5040$ sposobów.

(3) Na koniec opisujemy wybór znaków na ostatnich dwóch miejscach (ósmym i dziewiątym):

znak na ósmym miejscu możemy wybrać na 6 sposobów,
niezależnie od wyboru ósmego znaku kolejny, na dziewiątym miejscu, możemy wybrać na 5 sposobów (nie możemy powtórzyć litery zapisanej na poprzednim miejscu).

Korzystając z reguły mnożeniareguła mnożeniareguły mnożenia obliczamy, że dwa ostatnie znaki możemy zapisać na $6 \cdot 5 = 30$ sposobów.

Ponieważ liczba wyborów w każdym z opisanych powyżej etapów została ustalona, więc, po raz kolejny korzystając z reguły mnożeniareguła mnożeniareguły mnożenia, obliczamy, że wszystkich kodów zapisanych według określonych warunków jest $(26 \cdot 25 \cdot 24) \cdot (10 \cdot 9 \cdot 8 \cdot 7) \cdot (6 \cdot 5) = 15600 \cdot 5040 \cdot 30 = 2358720000$ .

Uwaga. W powyższym przykładzie wykorzystaliśmy reguły mnożeniareguła mnożeniareguły mnożenia w sytuacji, kiedy liczba możliwych sposobów wykonania kolejnej czynności była zależna od tego, jakim wynikiem zakończyły się czynności ją poprzedzające.

Zauważmy więc, że w przypadku, gdy nie jest ustalony zbiór wyników kolejnych czynności, ale umiemy określić liczbę wyników możliwych do uzyskania w kolejnych krokach reguła mnożenia pozostaje w mocy.

Przykład 3

Obliczymy, ile jest wszystkich pięcioznakowych kodów, które są zapisane za pomocą cyfr ze zbioru $\{0, 1, 2, \dots, 9\}$ , według następujących zasad:

dwie pierwsze cyfry są takie same,
trzecia cyfra jest o 2 mniejsza od czwartej,
piąta cyfra jest parzysta.

Zapiszmy wybory kolejnych cyfr jako ciąg $(c_{1}, c_{2}, c_{3}, c_{4}, c_{5})$ , gdzie $c_{i}$ oznacza cyfrę zapisaną w kodzie na miejscu $i = 1, 2, 3, 4, 5$ .

Zauważmy, że:

$c_{1}$ możemy wybrać na 10 sposobów: $c_{1} \in (0, 1, \dots, 9)$ ,
niezależnie od wyboru $c_{1}$ cyfrę $c_{2}$ możemy wybrać na 1 sposób (ma ona być taka sama, jak zapisana na pierwszym miejscu),
ponieważ $c_{3} = c_{4} - 2$ , więc $c_{3} \in (0, 1, \dots, 7)$ , zatem tę cyfrę możemy wybrać na 8 sposobów,
niezależnie od wyboru $c_{3}$ cyfrę $c_{4}$ możemy wybrać na 1 sposób (jest tylko jednak cyfra $c_{4}$ większa o 2 od ustalonej już cyfry $c_{3}$ ),
$c_{5}$ możemy wybrać na 5 sposobów: $c_{5} \in (0, 2, 4, 6, 8)$ .

Korzystając z reguły mnożeniareguła mnożeniareguły mnożenia obliczamy, że liczba wszystkich kodów jest równa $10 \cdot 1 \cdot 8 \cdot 1 \cdot 5 = 400$ .

Przykład 4

Rozpatrzmy wszystkie sześcioznakowe kody, zapisywane za pomocą parami różnych cyfr ze zbioru $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ .

Obliczymy, ile jest wśród nich takich kodów, w których występuje cyfra 7.

Zapiszmy wybory kolejnych cyfr jako ciąg $(c_{1}, c_{2}, c_{3}, c_{4}, c_{5}, c_{6})$ gdzie $c_{i}$ oznacza cyfrę zapisaną w kodzie na miejscu $i = 1, 2, 3, 4, 5, 6$ .

Zauważmy, że ponieważ cyfry w rozpatrywanym kodzie są parami różne, więc cyfrę 7 możemy wstawić na jednym z sześciu miejsc: $c_{1}, c_{2}, c_{3}, c_{4}, c_{5}, c_{6}$ , co możemy zrobić na $6$ sposobów.

Niezależnie od wyboru miejsca dla cyfry 7 pozostałe $5$ cyfr kodu zapisujemy, wybierając miejsca dla kolejnych cyfr, np. od lewej do prawej.

Wtedy:

cyfrę na pierwszym wolnym miejscu możemy wybrać na $9$ sposobów (nie możemy powtórzyć zapisanej już cyfry $7$ ),
cyfrę na drugim wolnym miejscu możemy wybrać na $8$ sposobów (nie możemy powtórzyć żadnej z dwóch już zapisanych cyfr),
cyfrę na trzecim wolnym miejscu możemy wybrać na $7$ sposobów (nie możemy powtórzyć żadnej z trzech już zapisanych cyfr),
cyfrę na czwartym wolnym miejscu możemy wybrać na $6$ sposobów (nie możemy powtórzyć żadnej z czterech już zapisanych cyfr),
cyfrę na piątym wolnym miejscu możemy wybrać na $5$ sposobów (nie możemy powtórzyć żadnej z pięciu już zapisanych cyfr).

Korzystając z reguły mnożeniareguła mnożeniareguły mnożenia obliczamy, że liczba wszystkich kodów określonych w treści zadania jest równa $6 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 = 90720$ .

Uwaga. Powyższe zadanie można rozwiązać korzystając z reguły mnożeniareguła mnożeniareguły mnożenia oraz z reguły dodawaniareguła dodawaniareguły dodawania.

Oznaczmy w tym celu:

$A$ - zbiór wszystkich kodów o parami różnych cyfrach ze zbioru $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ , w których występuje cyfra 7,

$B$ - zbiór wszystkich kodów o parami różnych cyfrach ze zbioru $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ , w których nie występuje cyfra 7.

Zauważmy, że:

zbiory $A$ i $B$ są rozłączne,
zbiór $A \cup B$ to zbiór wszystkich kodów sześciocyfrowych o parami różnych cyfrach ze zbioru $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ .

Zatem na podstawie reguły dodawaniareguła dodawaniareguły dodawania stwierdzamy, że

$|A \cup B| = |A| + |B|$ ,

skąd $|A| = |A \cup B| - |B|$ .

Natomiast na podstawie reguły mnożeniareguła mnożeniareguły mnożenia obliczamy, że:

$|A \cup B| = 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 = 151200$ ,

$|B| = 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 = 60480$ .

Wobec tego

$|A| = 151200 - 60480 = 90720$ .

Oznacza to, że jest $90720$ kodów spełniających warunki zadania.

Słownik

reguła dodawania

jeżeli zbiory $A_{1}, A_{2}, \dots, A_{n}$ są parami rozłączne, to liczba elementów zbioru $A_{1} \cup A_{2} \cup \dots \cup A_{n}$ jest równa sumie liczb elementów każdego ze zbiorów $A_{1}, A_{2}, \dots, A_{n}$ :

$|A_{1} \cup A_{2} \cup \dots \cup A_{n}| = |A_{1}| + |A_{2}| + \dots + |A_{n}|$

reguła mnożenia

liczba wszystkich możliwych wyników doświadczenia polegającego na wykonaniu po kolei $n$ czynności, z których pierwsza może zakończyć się na jeden z $k_{1}$ sposobów, druga – na jeden z $k_{2}$ sposobów, trzecia – na jeden z $k_{3}$ sposobów i tak dalej do $n$ -tej czynności, która może zakończyć się na jeden z $k_{n}$ sposobów, jest równa

$k_{1} \cdot k_{2} \cdot \dots \cdot k_{n}$

Wprowadzenie

Animacja

Słownik