Основные правила комбинаторики

Правило произведения. Пусть имеем декартово произведение двух множеств {a,b,c} {1,2,3,4}. Число элементов, которого равно произведению числа элементов первого множества на число элементов второго множества, в дано случае это будет 3 4 = 12. В общем случае можно сформулировать правило произведения:

Если требуется выполнить последовательно k независимых операций, и каждая может быть выполнена n_i (i =1,2,,k) способами, то общее число исходов равно их произведению n = n₁ n₂... n_k.

Число элементов декартова произведения (мощность) n сомножителей равно произведению числа элементов (мощности) каждого из этих сомножителей.