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ń.
Jeżeli mamy n kolejnych decyzji do podjęcia, z których każdą i-tą (1\le i\le n) decyzję można podjąć na k_i sposobów, to liczba wszystkich możliwych sekwencji (wyników n-etapowego wyboru) wynosi:
Jeżeli pewien wybór można dokonać na n sposobów, a inny, niezależny wybór na m sposobów, to liczba wszystkich możliwych sposobów dokonania jednego z tych wyborów wynosi:
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 podejmujemy na m sposobów: X_1,X_2,\ldots,X_m.
drugą decyzję Y podejmujemy na n sposobów: 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.
.png)
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ąć.
.png)