(Заметим, что прямой подсчет числа маршрутов в задачах такого рода может быть весьма трудоемким делом.)
Дальнейшие обобщения предложенного подхода очевидны: рассмотренные системы маршрутов типа Пk (А, В) можно использовать как «строительные блоки» для конструирования более сложных систем.
Замечание. В дальнейшем мы увидим, что правило произведения может успешно применяться в задачах совершенно иного сорта.
Опыт преподавания комбинаторики говорит о том, что наглядные геометрические соображения (если, конечно, ими удается воспользоваться) значительно облегчают усвоение материала. Например, важнейший закон комбинаторики – правило произведения – обычно иллюстрируют при помощи «деревьев»[5]. Эта же иллюстрация служит заодно вполне надежным доказательством упомянутого правила.
В этом параграфе приводится геометрическая иллюстрация (также являющаяся одновременно доказательством) другого известного комбинаторного закона – рекуррентного соотношения для числа сочетаний из n элементов по k элементов
Рассмотрим прямоугольник размера 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 можно только либо вверх, либо вправо).
Покажем теперь, что геометрически очевидное соотношение (2) это и есть, в сущности, другая (причем более симметричная!) форма записи комбинаторного равенства (1).
Действительно, длина любого маршрута из A в B равна в точности m + k. Пронумеруем теперь шаги произвольно взятого маршрута. Очевидно, что каждый маршрут полностью характеризуется номерами шагов, направленных вверх (этих шагов всего должно быть k штук). Тем самым каждый маршрут однозначно соответствует выбору k чисел из множества{1,2,…, m + k}.
Следовательно,
и мы можем переписать (2) в виде
Полагая здесь n = m + k, приходим к искомому равенству (1).
Объясняя студентам – будущим педагогам начальных классов – начала комбинаторики, неизбежно приходится вводить функцию n! («эн-факториал»). С педагогической точки зрения здесь имеется одно довольно узкое место.
Мы полагаем по определению, что
n! = n(n–1)(n–2)·…·2 ·1 при n ≥ 1, (1)
а при n = 1 считаем опять же по определению, что
0! = 1. (2)
Соотношение (1) обычно не вызывает никаких затруднений – здесь все ясно: мы имеем дело с произведением всех натуральных чисел от n до 1. Но откуда берется соотношение (2)? Если не дать разумного, адекватного объяснения, четко указав то место, где действительно используется соглашение (2), то весь материал, связанный с биномиальными коэффициентами, будет воспринят отчасти на веру.
И тут у преподавателя, знакомого, естественно, с Гамма-функцией Эйлера, появляется искушение объяснить происхождение формулы (2) следующим образом.