У будь-якій комбінаторній задачі в тій чи іншій мірі фігурує так зване правило множення.
Приклад
З міста А до міста В веде п різних доріг, з міста В до міста С веде т різних шляхів. Скількома способами можна здійснити подорож з міста А в місто С?
Відповідь очевидна: n • m, бо обравши один з n можливих шляхів з міста А в місто B, ми матимемо т різних продовжень подорожі з В в С.
Міркування, які були проведені при розв’язанні задачі, доводять справедливість такого простого правила, яке називають правилом множення або основним принципом комбінаторики.
Якщо деякий вибір А можна здійснити N способами, а для кожного з цих способів другий вибір В можна здійснити т способами, то вибір А і В (у вказаному порядку) можна здійснити n - т способамиЗадача 1. На вершину гори веде 8 доріг.
а) Скількома способами турист може піднятися на гору і спуститися вниз?
б) Скількома способами турист може піднятися на гору і спуститися вниз, якщо підйом і спуск здійснюються різними шляхами?
а) Відповідь: 8 х 8 = 64. б)Відповідь: 8 х 7 = 56.
Сформулюємо тепер правило множення в загальному вигляді. Нехай треба виконати одна за одною "к" дій. Якщо першу дію можна здійснити п способами, другу дію (після того, як здійснена перша)
— n2 способами, третю дію (після того, як здійснені попередні дві) — n3 способами, і так до k-тої дії, яку можна здійснити nk, способами, то загальне число способів здійснення дій дорівнює
n1 x n2 x...x nk
