Применим теперь правило произведения к решению простейшей задачи. Пусть города А и В связаны сетью дорог, как показано на рис. 6.3.
Ехать из А в В можно только по направлениям, указанным стрелками (так что мы, по существу, имеем дело с ориентированным графом). Спрашивается, сколькими способами можно доехать из А в В? Нетрудно видеть, что выбор первого участка маршрута (до развилки) можно осуществить пятью способами, после чего выбрать второй участок пути всегда (т.е. при любом выборе первого участка) можно тремя способами. Таким образом, применимо правило произведения, и общее количество способов, которыми можно добраться из А в В, равно 5∙3 = 15.
Поставим теперь следующий вопрос: а сколькими способами можно вернуться из В в А? (Разрешается ехать только против направления стрелок на рис. 6.3).
Из рис. 6.3 очевидно, что правило произведения «в обратную сторону» не работает. Тем не менее, понятно, что каждому маршруту из А в В соответствует в точности один маршрут из В в А (мы увидим этот маршрут, если «прокрутим киноленту» в обратном направлении). Значит, вернуться из В в А можно по-преж-
нему 15-ю способами.
Любопытно, что в задачах о маршрутах возникает ситуация, в которой подсчет числа вариантов по-прежнему можно проводить по правилу произведения, но выбор «упорядоченной пары элементов» уже не столь очевиден, как раньше.
А именно, пусть на этот раз города А и В связаны сетью дорог, изображенной на рис. 6.4.
Понятно, что в качестве упорядоченной пары (a, b) здесь следует брать пару: (малый начальный участок маршрута, малый конечный участок маршрута).
Выбор такой пары, очевидно, полностью определяет сам маршрут из А в В, и общее количество маршрутов из А в В вычисляется по правилу произведения и равно 2∙3 = 6. Число маршрутов из В в А тем самым также равно шести.
Возможны еще более любопытные конфигурации дорог между А и В, к которым по-прежнему применимо правило произведения для подсчета числа возможных маршрутов из А в В (и, соответственно, из В в А). Пример такой конфигурации приведен на рис. 6.5.
В ситуации, изображенной на рис. 6.5, маршрут из А в В лучше всего задавать упорядоченной парой точек вида (a, b), которую удается подобрать так, что она однозначно определяет выбранный маршрут. Нетрудно видеть, что после того как выбрана первая точка упорядоченной пары (т.е. выбрана точка a1, a2,
Рассмотрим еще один пример, когда маршрут из А в В определяется выбором упорядоченной тройки точек вида (a, b, c), расположенных на сети дорог (см. рис. 6.6).
Первая координата упомянутой упорядоченной тройки точек может быть выбрана двумя способами (a1 или a2). После того как этот выбор сделан вторая координата рассматриваемой упорядоченной тройки точек может быть выбрана тремя способами (b1
Удобно ввести символ П3
Предположим теперь, что города А и В связывают две непересекающиеся системы дорог, относящиеся, например, к классам