в
В (и, соответственно, из
В в
А). Пример такой конфигурации приведен на рис. 6.5.
Рис. 6.5
В ситуации, изображенной на рис. 6.5, маршрут из А в В лучше всего задавать упорядоченной парой точек вида (a, b), которую удается подобрать так, что она однозначно определяет выбранный маршрут. Нетрудно видеть, что после того как выбрана первая точка упорядоченной пары (т.е. выбрана точка a1, a2,a3 или a4) выбор второй точки осуществляется одним из четырех способов. Поэтому в полном соответствии с правилом произведения число различных маршрутов из А в В на рис. 6.5 равно 4∙4 = 16.
Рассмотрим еще один пример, когда маршрут из А в В определяется выбором упорядоченной тройки точек вида (a, b, c), расположенных на сети дорог (см. рис. 6.6).
Рис. 6.6
Первая координата упомянутой упорядоченной тройки точек может быть выбрана двумя способами (a1 или a2). После того как этот выбор сделан вторая координата рассматриваемой упорядоченной тройки точек может быть выбрана тремя способами (b1, b2 или b3). Наконец, после того как выбраны первая и вторая координаты упорядоченной тройки (a, b, c), третья координата тоже может быть выбрана одним из трех способов. Итак, по правилу произведения, число маршрутов из А в В на рис. 6.6 равно 2∙3∙3 =18.
Удобно ввести символ П3
(
А,
В) для характеристики маршрутов, связывающих «города»
А и
В на рис. 6.6. Здесь буква Π указывает на то, что общее число маршрутов
при движении из А в В может быть вычислено с помощью правила произведения, индекс «3» указывает на (минимальное) количество точек, с помощью которых мы однозначно задаем маршрут.
Предположим теперь, что города А и В связывают две непересекающиеся системы дорог, относящиеся, например, к классам
П3(
А,
В) и П2(
В,
А) соответственно. Тогда количество маршрутов из
А в
В, относящихся к первой системе, согласно правилу произведения вычисляется по формуле
k∙m∙n, где
k, m, n – количества способов выбрать первую, вторую и третью точки, задающие каждый маршрут из
А в
В. Аналогично, количество маршрутов второй системы вычисляется по формуле
k
∙m, где
k и
m – количества способов выбрать соответственно первую и вторую точки, задающие маршруты второй системы (при движении из
В в
А). Поскольку число маршрутов, принадлежащих любой системе, в конечном итоге не зависит от того, а какую сторону направлено движение, заключаем, что в нашей задаче общее число маршрутов из
А в
В (и тем самым из
В в
А) будет равно
k∙m∙n
