Правило прямого произведения
Пусть А и В – конечные множества, и , тогда
Определение: Если элемент можно выбрать m способами и если элемент
можно выбрать n способами, то выбор пары в указанном порядке можно осуществить способами. В этом случае говорят, что выбор элементов множества А не зависит от способа выбора элементов множества В. Пусть теперь X1,X2,…,Xk – произвольные множества, . Тогда
.
Пример:
Найти число маршрутов из пункта М в пункт N через пункт К, если из М в К ведут 5 дорог, а из К в N – 3 дороги.
Решение: Введём два множества: – дороги из М в K, – дороги из K в N можно представить парой (si,tj) где i=1,2,3,4,5; j=1,2,3. Значит, – это множество всех дорог из М в N, количество которых равно .