§ 2. Комбинаторные задачи. Продолжение

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

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

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

Другое общее правило имеет следующий вид:

если некоторый выбор может быть сделан различными способами, а другой выбор различными способами (отличными от предыдущих), то общее число способов, которыми можно осуществить какой-нибудь один из этих выборов, равен сумме

Это правило также применялось нами в предыдущем параграфе (см. пример 8).

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

Пример 1. Во взводе 5 сержантов и 50 солдат. Сколькими способами можно составить наряд из одного сержанта и трех солдат?

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

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

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

стей; после того как один солдат уже вызван, для выбора второго остается 49 возможностей, а для выбора третьего — лишь 48. Таким образом, применяя правило умножения, находим, что всего для выбора трех солдат в определенном порядке число возможностей равно произведению На этом и заканчивается первая часть решения, но отнюдь не все решение.

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

Остается, следовательно, определить, в каком числе случаев будет получаться один и тот же наряд. Это можно подсчитать, решая в каком-то смысле обратную задачу: каким числом способов можно расставить в шеренгу трех солдат уже выбранного наряда. Очевидно, что это число равно требуемому. Но это число легко под считать, пользуясь обычным приемом: чтобы поставить какого-либо солдата на первое место, есть три различные возможности, на второе место остается два солдата и на третье — только один Поэтому общее число возможных перестановок трех солдат в шеренге равно

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

Число различных нарядов из одного сержанта и трех солдат равно теперь

Пример 2. Сколько членов, содержащих две буквы, получится после раскрытия скобок в выражении

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

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

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

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

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

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

Пример 4. В классе мест. Каким числом способов можно рассадить в нем учеников

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

Представим себе, что ученики входят в класс по одному. Тогда для первого из них имеется возможностей выбрать место. После того как первый выбрал какое-то место, для второго остается возможностей. Далее, для третьего будет различных возможностей и т. д. Искомое число способов рассадить всех учеников выразится произведением

Найдем последний сомножитель этого произведения. Его можно определить по-разному, например так: каждый сомножитель на единицу меньше предыдущего и получается вычитанием из числа, на единицу меньшего, чем номер сомножителя. Поэтому сомножитель с номером получается вычитанием из числа , то есть равен

Можно рассуждать и иначе: после того как все ученики рассядутся, в классе должно остаться свободных мест. Перед входом последнего ученика свободных мест было на 1 больше, то есть . Таково же число возможностей для выбора мест последним учеником, то есть последний сомножитель в произведении.

Итак, искомое число различных способов рассадить учеников на местах равно произведению последовательных целых чисел от до включительно:

Пример 5. В комнате имеется пять лампочек. Сколько существует различных способов освещения?

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

своей простоте, потребует сравнительно длинных рассуждений и вычислений.

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

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

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

Пример 6. Чему равен коэффициент при и при в выражении после раскрытия скобок.

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

Выражение можно рассматривать как произведение 88 скобок; из каждой нужно выбрать в качестве множителя одно из слагаемых: либо а, либо Если мы ищем коэффициент при то нужно определить, каким числом способов можно выбрать из 88 букв а и ровно шесть букв а. Но именно этот вопрос мы решали в примере 7 предыдущего параграфа, когда нужно было определить число различных аккордов из 6 нот.

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

Шесть букв а можно разместить на 88 возможных местах числом способов, равным произведению

если выбрать эти буквы в определенном порядке. Поскольку порядок выбора букв нам безразличен, то каждая комбинация

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

Число возможных способов переставлять между собой шесть букв на шести местах, как мы уже видели, равно 6! Поэтому число различных способов выбрать шесть букв а из 88, а значит, и коэффициент при члене в разложении равно

Легко догадаться, что коэффициент при равен тому же числу. Соответствующее рассуждение уже приводилось в примере 4: способов выбрать по 82 буквы а из 88 равно столько же, сколько способов выбрать по 6, так как каждой группе по 6 букв соответствует определенная группа по 82 буквы, состоящая из оставшихся 82 мест. Но мы можем и не обращаться к этому рассуждению, рассматривая для члена не выбор букв а, наоборот, выбор шести букв Отсюда снова вытекает, что коэффициенты при одинаковы.

Упражнения

(см. скан)