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

Предположим теперь, что города А и В связывают две непересекающиеся системы дорог, относящиеся, например, к классам П3(А, В) и П2(В, А) соответственно. Тогда количество маршрутов из А в В, относящихся к первой системе, согласно правилу произведения вычисляется по формуле k∙m∙n, где k, m, n – количества способов выбрать первую, вторую и третью точки, задающие каждый маршрут из А в В. Аналогично, количество маршрутов второй системы вычисляется по формуле k∙m, где k и m – количества способов выбрать соответственно первую и вторую точки, задающие маршруты второй системы (при движении из В в А). Поскольку число маршрутов, принадлежащих любой системе, в конечном итоге не зависит от того, а какую сторону направлено движение, заключаем, что в нашей задаче общее число маршрутов из А в В (и тем самым из В в А) будет равно k∙m∙n+k∙m.

(Заметим, что прямой подсчет числа маршрутов в задачах такого рода может быть весьма трудоемким делом.)

Дальнейшие обобщения предложенного подхода очевидны: рассмотренные системы маршрутов типа Пk (А, В) можно использовать как «строительные блоки» для конструирования более сложных систем.

Замечание. В дальнейшем мы увидим, что правило произведения может успешно применяться в задачах совершенно иного сорта.

7. ОБ ОДНОМ КОМБИНАТОРНОМ

СООТНОШЕНИИ

Опыт преподавания комбинаторики говорит о том, что наглядные геометрические соображения (если, конечно, ими удается воспользоваться) значительно облегчают усвоение материала. Например, важнейший закон комбинаторики – правило произведения – обычно иллюстрируют при помощи «деревьев»[5]. Эта же иллюстрация служит заодно вполне надежным доказательством упомянутого правила.

В этом параграфе приводится геометрическая иллюстрация (также являющаяся одновременно доказательством) другого известного комбинаторного закона – рекуррентного соотношения для числа сочетаний из n элементов по k элементов ():

(1)

Рассмотрим прямоугольник размера m×k, составленный из единичных квадратов (см. рис. 7.1). Нас будет интересовать число маршрутов из нижнего левого угла A в правый верхний угол B (двигаться можно только вверх или вправо по сторонам единичных квадратов). Это число мы обозначим через N(m, k).

Заметим теперь, что попасть в точку B можно только одним из двух способов: либо из точки C, либо из точки D, cледовательно,

N(m,k) = N(m–1,k) + N(m,k–1) (2)

(справедливость этого соотношения геометрически очевидна; при этом существенно то обстоятельство, что двигаться из точки A можно только либо вверх, либо вправо).

Рис. 7.1

Покажем теперь, что геометрически очевидное соотношение (2) это и есть, в сущности, другая (причем более симметричная!) форма записи комбинаторного равенства (1).

Действительно, длина любого маршрута из A в B равна в точности m + k. Пронумеруем теперь шаги произвольно взятого маршрута. Очевидно, что каждый маршрут полностью характеризуется номерами шагов, направленных вверх (этих шагов всего должно быть k штук). Тем самым каждый маршрут однозначно соответствует выбору k чисел из множества{1,2,…, m + k}.

Следовательно,

и мы можем переписать (2) в виде

Полагая здесь n = m + k, приходим к искомому равенству (1).

8. ЧЕМУ РАВЕН НУЛЬ-ФАКТОРИАЛ?

Объясняя студентам – будущим педагогам начальных классов – начала комбинаторики, неизбежно приходится вводить функцию n! («эн-факториал»). С педагогической точки зрения здесь имеется одно довольно узкое место.

Мы полагаем по определению, что

n! = n(n–1)(n–2)·…·2 ·1 при n ≥ 1, (1)

а при n = 1 считаем опять же по определению, что

0! = 1. (2)

Соотношение (1) обычно не вызывает никаких затруднений – здесь все ясно: мы имеем дело с произведением всех натуральных чисел от n до 1. Но откуда берется соотношение (2)? Если не дать разумного, адекватного объяснения, четко указав то место, где действительно используется соглашение (2), то весь материал, связанный с биномиальными коэффициентами, будет воспринят отчасти на веру.

И тут у преподавателя, знакомого, естественно, с Гамма-функцией Эйлера, появляется искушение объяснить происхождение формулы (2) следующим образом.

При n > 1, очевидно, имеем

n! = (n–1)! · n. (3)

Мы хотим сохранить это же самое соотношение при n = 1. Подставляя в (3) n = 1, получаем

1! = 0!·1, (4)

откуда и следует (2).

Однако соотношение (4) нигде в курсе комбинаторики не

используется, и в результате остается непонятным, нельзя ли было положить 0! равным какому-нибудь другому числу, отличному от 1.

Выход из положения здесь, на наш взгляд, такой. Соображения (3), (4) можно (но не обязательно) рассказывать студентам в качестве дополнительного материала, но не стоит давать их непосредственно после формулы (2) для ее «оправдания».