Правило прямого произведения

Пусть А и В – конечные множества, и , тогда

Определение: Если элемент можно выбрать m способами и если элемент

можно выбрать n способами, то выбор пары в указанном порядке можно осуществить способами. В этом случае говорят, что выбор элементов множества А не зависит от способа выбора элементов множества В. Пусть теперь X₁,X₂,…,X_k – произвольные множества, . Тогда

.

Пример:

Найти число маршрутов из пункта М в пункт N через пункт К, если из М в К ведут 5 дорог, а из К в N – 3 дороги.

Решение: Введём два множества: – дороги из М в K, – дороги из K в N можно представить парой (s_i,t_j) где i=1,2,3,4,5; j=1,2,3. Значит, – это множество всех дорог из М в N, количество которых равно .