Глава VII. КОМБИНАТОРИКА

§ 1. Комбинаторные задачи

Среди различных задач, которые приходится решать математикам, встречаются такие, где нужно ответить на вопрос: каким числом различных способов можно осуществить требуемое? Такие задачи принято называть комбинаторными задачами. Для решения таких задач созданы общие методы и выведены готовые формулы. Однако для того чтобы лучше ознакомиться с методами их решения, мы начнем не с общих методов и готовых формул, а с рассмотрения конкретных примеров.

Пример 1. Каким числом способов можно обить 12 различных стульев, если есть 12 образцов обивочного материала, причем каждый материал имеется в любом количестве?

Решение. Поскольку имеется 12 различных образцов обивочного материала, то один стул можно обить двенадцатью различными способами. То же самое справедливо и для второго стула, так как каждый обивочный материал имеется в любом количестве. Но каждый способ обивки первого стула можно соединить с любым способом обивки второго, так что число различных способов обивки двух стульев равно .

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

Итак, для двух различных стульев мы получили различных способов их обивки. Очевидно, что для каждого следующего стула остается в силе приведенное выше рассуждение: для каждого стула существует двенадцать возможных способов обивки, и каждый способ обивки данного стула можно соединить с любым

способом обивки предыдущих. Отсюда следует, что для трех стульев число различных способов обивки составляет 123, для четырех и т. д. Для двенадцати стульев это число составляет .

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

Решение. Представим себе, что гости входят в комнату по одному. Первому из входящих гостей предоставляется выбор из 12 различных стульев, т. е. 12 возможностей, как и в предыдущем примере. Однако уже для следующего гостя остаются не те же двенадцать возможностей, что и для первого, а всего лишь одиннадцать, поскольку один из стульев оказывается уже занятым. По-прежнему каждое место, занятое первым гостем, может комбинироваться с любым другим местом, занятым вторым; поэтому общее число различных способов, с помощью которых можно рассадить двух гостей, равно

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

Пример 3. В отделении 12 солдат. Каким числом способов можно составить наряд из двух человек, если один из них должен быть назначен старшим?

Решение этой задачи очень похоже на решение предыдущей. Действительно, если назначить сначала старшего по наряду, то для его выбора у нас имеется 12 различных возможностей: каждый солдат отделения может быть назначен старшим наряда. После того как старший наряда назначен, вторым в наряд может быть назначен любой из оставшихся одиннадцати. Как и во всех предыдущих случаях, общее число различных нарядов составляет

Пример 4. Какое число различных парных нарядов можно назначить из 12 солдат отделения, если не требуется назначать старшего по наряду?

Решение. Легко понять, что число таких нарядов должно быть меньше, чем в предыдущем примере. Действительно, наряды — Иванов (старший) и Петров или Петров (старший) и Иванов — различны, тогда как, если не требуется назначать старшего, эти два солдата в обоих случаях составляют один и тот же наряд. Каждый парный наряд без старшего можно превратить в два различных наряда

ряда со старшим. Поэтому число различных парных нарядов со старшим в два раза больше, чем нарядов без старших. Отсюда следует, что интересующее нас в данном примере число различных парных нарядов из 12 солдат отделения в два раза меньше, чем получено в предыдущем примере, т. е. равно

Пример 5. Клавиатура пианино состоит из 88 клавиш. Сколько различных музыкальных фраз можно составить из 6 нот, допуская повторения одних и тех же нот в одной фразе?

Решение. Как и в примере 1, в качестве первой ноты для музыкальной фразы можно взять любую из 88 нот, т. е. для первой ноты мы имеем 88 возможностей. Так как повторения допускаются, то для второй ноты мы снова имеем те же 88 возможностей, и поэтому музыкальных фраз из двух нот существует . Продолжая рассуждения, как в примере 1, найдем, что число различных музыкальных фраз из 6 нот составляет

Пример 6. Сколько различных музыкальных фраз можно составить из 6 нот, если не допускать в одной фразе повторений уже встречавшихся звуков?

Решение этой задачи так же отличается от решения предыдущей, как решение задачи примера 2 от примера 1. Действительно, при составлении произвольной музыкальной фразы для первой ноты мы имеем по-прежнему 88 возможностей. Для второй ноты число возможностей уменьшится уже до 87, так как нота, использованная первой, не должна больше употребляться. После того как выбрана вторая нота, для третьей остается уже только 86 возможностей. Теперь ясно, что общее число различных музыкальных фраз из 6 нот без повторений равно произведению .

Пример 7. Сколько существует различных аккордов из шести нот?

Решение. Аккорд отличается от музыкальной фразы тем, что все ноты, в него входящие, звучат одновременно. Отсюда следует, что все ноты аккорда должны быть различными. Кроме того, различные музыкальные фразы могут приводить к одному и тому же аккорду, если они состоят из одних и тех же нот, но расположенных в фразе в различном порядке. Поэтому, подобно примеру 4, так как число различных музыкальных фраз уже известно, нам остается определить, сколько различных музыкальных фраз могут «склеиваться» в один и тот же аккорд, или, наоборот, сколько различных фраз получается из одного и того же аккорда.

Мы приходим, таким образом, к задаче, аналогичной рассмотренной в примере 6: имеется аккорд из шести различных нот,

сколько различных музыкальных фраз можно из него составить? В качестве первой ноты для составляемой музыкальной фразы можно взять любую из входящих в аккорд нот, то есть мы имеем для нее шесть различных возможностей. Для второй ноты остается уже только пять возможностей, для третьей — четыре и т. д.

Теперь уже ясно, что число различных музыкальных фраз, которые можно получить из одного аккорда из шести нот, равно Это означает, что 6! различных музыкальных фраз склеиваются в один и тот же аккорд, так что число возможных аккордов будет в 61 раз меньше, чем число различных музыкальных фраз. Итак, мы получаем, что число различных возможных аккордов из 6 нот равно:

Пример 8. Из города А в город В ведет дорог, а в город дорог. В город из города В ведет дорог, а из города дорог. Города В и С дорогами не соединяются. Сколько различных автобусных маршрутов можно провести между городами А и

Решение. Число автобусных маршрутов определяется числом различных дорог между городами. Всего из города А выходит дорог, а в город входит дорог. Мы не можем, однако, сказать, что общее число дорог равно произведению этих чисел, так как здесь невозможно комбинировать любую дорогу, выходящую из А, с любой дорогой, входящей в Если же рассматривать отдельно дороги, проходящие через В или через С, то такая комбинация возможна.

Рассмотрим всевозможные маршруты, идущие из А в D через В. Из А в В ведет дорог, а из В в дорог. Каждую из таких дорог, выходящих из А, можно комбинировать с любой дорогой, входящей в поэтому общее число различных маршрутов, как и во всех предыдущих задачах, получается перемножением числа возможностей и равно Следовательно, число различных маршрутов, идущих из А в через В, равно

Аналогично подсчитывается число различных маршрутов, идущих из А в D через С; оно равно Далее, мы замечаем, что всякий автобусный маршрут, соединяющий города А и должен проходить или через В, или через С, и, значит, он должен входить либо в число маршрутов, идущих через В, либо в число маршрутов, идущих через С. Общее число различных маршрутов равна тогда сумме