Пусть задано конечное множество Х, такое, что . Тогда объект
из Х может быть выбран n способами. Пусть множества Хi, где
таковы, что
и
, если i¹j. Тогда выполняется равенство
Этот факт в комбинаторике называется Правилом суммы, которое утверждает, что так как объект можно выбрать ni способами из Х (
ÎХiÌХ), то выбор из Х либо
, либо
, либо
можно осуществить n1+n2+…+nk способами.
В другом случае, если мы будем осуществлять выбор упорядоченного набора (кортежа) < ,
,…,
>, где
ÎXi, то очевидно, что такой набор можно осуществить
способами. Это следует из равенства
.
Это так называемое Правило произведения, которое можно проиллюстрировать задачей.
Задача 2.1. Найти число возможных десятичных четырехзначных чисел (не начинающихся, естественно, с нуля).
Решение. Для первого символа (слева) , для остальных символов
,
. Следовательно, число всех возможных комбинаций <a1, a2, a3, a4>, где a1¹0, равно
.