a, b, c), расположенных на сети дорог (см. рис. 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.
(Заметим, что прямой подсчет числа маршрутов в задачах такого рода может быть весьма трудоемким делом.)
Дальнейшие обобщения предложенного подхода очевидны: рассмотренные системы маршрутов типа Пk(А, В) можно использовать как «строительные блоки» для конструирования более сложных систем.
Замечание. В дальнейшем мы увидим, что правило произведения может успешно применяться в задачах совершенно иного сорта.
Опыт преподавания комбинаторики говорит о том, что наглядные геометрические соображения (если, конечно, ими удается воспользоваться) значительно облегчают усвоение материала. Например, важнейший закон комбинаторики – правило произведения – обычно иллюстрируют при помощи «деревьев»[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 можно только либо вверх, либо вправо).
Покажем теперь, что геометрически очевидное соотношение (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) следующим образом.
При n> 1, очевидно, имеем
n! = (n–1)! · n. (3)
Мы хотим сохранить это же самое соотношение при n = 1. Подставляя в (3) n = 1, получаем
1! = 0!·1, (4)
откуда и следует (2).
Однако соотношение (4) нигде в курсе комбинаторики не
используется, и в результате остается непонятным, нельзя ли было положить 0! равным какому-нибудь другому числу, отличному от 1.
Выход из положения здесь, на наш взгляд, такой. Соображения (3), (4) можно (но не обязательно) рассказывать студентам в качестве дополнительного материала, но не стоит давать их непосредственно после формулы (2) для ее «оправдания».
Вместо этого, чтобы оправдать соглашение (2), на наш взгляд, следует сказать, что для того чтобы формулы, которые вскоре появятся, имели единообразный вид при всех n ≥ 0 (а не только при n ≥ 1) нужно, чтобы выражение
(5)
равнялось 1. (Действительно, как известно, каждое выражение вида при 0 <k <n представляет собой число сочетаний из n элементов по k элементов, т.е. число способов выбрать какие-нибудь k элементов из n данных элементов. При k = 0, очевидно, существует только один такой способ – не брать ни одного элемента.)
Поэтому неизбежно принятие соглашения (2). В результате, мы избегаем неприятного порочного круга в задаче: «Сколькими способами можно выбрать 0 элементов из n элементов?»
(Имеется в виду следующий порочный круг: «Число этих способов равно числу сочетаний из n элементов по 0 элементов, т.е. равно выражению (5). Подставляя в (5) определение (2) для 0!, получаем в ответе 1»).
Среди комбинаторных задач имеется серия таких, к которым правило произведения на первый взгляд неприменимо, и оттого эти задачи кажутся начинающему сложными. Однако при помощи простого рассуждения задачи этой серии могут быть переформулированы и затем решены именно с помощью вышеупомянутого правила произведения.
В качестве примера разберем одну из таких задач; прием, которым мы воспользуемся, заслуживает, на наш взгляд, специального рассмотрения на занятиях, посвященных комбинаторике.
Задача 1. Имеется 5 одуванчиков и 19 репейников. Сколькими способами можно составить из них букет, состоящий из трёх одуванчиков и семи репейников?
Решение. Букет, очевидно, представляет собой неупорядоченное множество, элементы которого выбираются из двух других непересекающихся неупорядоченных множеств – множества одуванчиков:
ОД = {ОД1, ОД2,..., ОД5} (1)
и множества репейников:
P = {Р1, Р2,..., Р19}. (2)
Существенно, однако, то, что каждому букету Б можно взаимно-однозначным образом сопоставить упорядоченную пару
Б ↔ ({три одуванчика); {семь репейников}). (3)
Это оказывается возможным только потому, что множества (1) и (2) не пересекаются!
Здесь, как это обычно принято, мы обозначаем неупорядоченные множества, перечисляя их элементы в фигурных скобках, а элементы упорядоченных множеств перечисляем в круглых скобках. Таким образом, элементами упорядоченной пары
({три одуванчика); {семь репейников}) (4)
являются два неупорядоченных множества.
Теперь в силу взаимной однозначности соответствия (3) заключаем, что численность множества Б (т.е. искомое число различных букетов заданного состава) равна численности множества упорядоченных пар вида (4).Тем самым, применяя правило произведения для нахождения этой численности, получаем
Ответ: искомое число способов равно ∙; здесь – число сочетаний из