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

Доказывается это очень просто. Будем изображать возможный выбор первого элемента пары (a,b) в виде ствола дерева

(см. рис. 6.1), а возможный выбор второго элемента пары – в виде ветки, растущей из верхнего конца ствола (см. рис. 6.2).

Рис. 6.1

Рис. 6.2

Тогда выбору упорядоченной пары вида (a,b) будет соответствовать маршрут от «подножия» одного из k деревьев до верхушки ствола и затем по одной из m веток до самого верха. Нетрудно видеть, что всего таких маршрутов будет

m + m + … + m = m∙k (1)

(слева в (1) k слагаемых). Маршруты мы считаем различными, если они не совпадают хотя бы в одной из своих частей.

Возможна ситуация, когда, например, b11= b21, но в этом случае нам приходится сравнивать маршруты (a1, b11) и (a2, b21), а они различны, ибо a1 ≠ a2 по предположению.

Правило произведения легко обобщается на случай, когда требуется сосчитать число возможных способов выбрать упорядоченную тройку элементов или, более общо, упорядоченный набор из n элементов.

Применим теперь правило произведения к решению простейшей задачи. Пусть города А и В связаны сетью дорог, как показано на рис. 6.3.

Ехать из А в В можно только по направлениям, указанным стрелками (так что мы, по существу, имеем дело с ориентированным графом). Спрашивается, сколькими способами можно доехать из А в В? Нетрудно видеть, что выбор первого участка маршрута (до развилки) можно осуществить пятью способами, после чего выбрать второй участок пути всегда (т.е. при любом выборе первого участка) можно тремя способами. Таким образом, применимо правило произведения, и общее количество способов, которыми можно добраться из А в В, равно 5∙3 = 15.

Поставим теперь следующий вопрос: а сколькими способами можно вернуться из В в А? (Разрешается ехать только против направления стрелок на рис. 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» указывает на (минимальное) количество точек, с помощью которых мы однозначно задаем маршрут.