Reguła mnożenia

Reguła mnożenia to zasada w kombinatoryce, która pozwala obliczyć liczbę wszystkich możliwych sposobów wykonania sekwencji działań, gdy każde z działań może być zrealizowane na określoną liczbę sposobów, a wynik jednego działania nie wpływa na możliwości kolejnych działań.

Twierdzenie 1

Reguła mnożenia

Jeżeli mamy $n$ n kolejnych decyzji do podjęcia, z których każdą $i-$ i-tą $(1\le i\le n)$ (1\le i\le n) decyzję można podjąć na $k_i$ k_i sposobów, to liczba wszystkich możliwych sekwencji (wyników $n-$ n-etapowego wyboru) wynosi:

\prod_{i=1}^{n}k_i=k_1\cdot k_2\cdot\ldots k_n

(0)

Twierdzenie 2

Reguła dodawania

Jeżeli pewien wybór można dokonać na $n$ n sposobów, a inny, niezależny wybór na $m$ m sposobów, to liczba wszystkich możliwych sposobów dokonania jednego z tych wyborów wynosi:

n+m

(0)

W kombinatoryce w celu zobrazowania możliwych wyników możemy posłużyć się tabelką lub drzewem. Załóżmy, że mamy do podjęcia dwu-etapową decyzję:

pierwszą decyzję $X$ X podejmujemy na $m$ m sposobów: $X_1,X_2,\ldots,X_m$ X_1,X_2,\ldots,X_m.
drugą decyzję $Y$ Y podejmujemy na $n$ n sposobów: $Y_1,Y_2,\ldots,Y_n$ Y_1,Y_2,\ldots,Y_n.

Wszystkie możliwe do podjęcia wynikowe decyzje możemy zilustrować za pomocą tabeli gdzie każda z komórek zawiera parę będącą kombinacją pierwszej oraz drugiej decyzji.

Alternatywnie, możemy przedstawić wyniki na drzewie , w którym każdy odcinek nazywamy krawędzią tego drzewa, punkty w których te krawędzie się spotykają - wierzchołkami. Dodatkowo, każdy ciąg krawędzi od czubka drzewa aż po sam jego dół nazywamy gałęzią która składa się z tylu krawędzi, ile decyzji musimy podjąć.