Откуда мы знаем, что такое точка?

Поставим теперь следующий вопрос: а сколькими способами можно вернуться из В в А? (Разрешается ехать только против направления стрелок на рис. 6.3).

Рис. 6.3

Из рис. 6.3 очевидно, что правило произведения «в обратную сторону» не работает. Тем не менее, понятно, что каждому маршруту из А в В соответствует в точности один маршрут из В в А (мы увидим этот маршрут, если «прокрутим киноленту» в обратном направлении). Значит, вернуться из В в А можно по-преж-

нему 15-ю способами.

Любопытно, что в задачах о маршрутах возникает ситуация, в которой подсчет числа вариантов по-прежнему можно проводить по правилу произведения, но выбор «упорядоченной пары элементов» уже не столь очевиден, как раньше.

А именно, пусть на этот раз города А и В связаны сетью дорог, изображенной на рис. 6.4.

Рис. 6.4

Понятно, что в качестве упорядоченной пары (a, b) здесь следует брать пару: (малый начальный участок маршрута, малый конечный участок маршрута).

Выбор такой пары, очевидно, полностью определяет сам маршрут из А в В, и общее количество маршрутов из А в В вычисляется по правилу произведения и равно 2∙3 = 6. Число маршрутов из В в А тем самым также равно шести.

Возможны еще более любопытные конфигурации дорог между А и В, к которым по-прежнему применимо правило произведения для подсчета числа возможных маршрутов из А в В (и, соответственно, из В в А). Пример такой конфигурации приведен на рис. 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+k∙m.