Виленкин Н. Я.

КомбинаторикаВиленкин Н. Я. Комбинаторика // Квант. — 1971. — № 1. — С. 13‍—‍19.‍‍

Вероятно, каждому читателю «Кванта» знакомо волнение, охватывающее болельщиков перед крупным спортивным соревнованием — будь то чемпионат мира по футболу или «матч века» по шахматам. Даже от тех, кто не совсем точно помнит правила рокировки, можно услышать глубокомысленные замечания вроде «а я бы на первую доску сборной мира поставил не Ларсена, а Портиша». Знатоки и любители шахмат спорят о шансах на победу Смыслова и Кереса, а у любителей футбола дело доходит чуть ли не до драки при обсуждении возможного исхода матча сборных команд Бразилии и Англии.

Очень часто перед такими соревнованиями газеты объявляют конкурс знатоков, предлагая угадать как исход соревнования в целом (предсказать, кому достанется «Золотая богиня», или счёт, с которым сборная СССР по шахматам победит сборную мира), так и исходы отдельных состязаний. На первый взгляд есть совсем простой способ победить в таком конкурсе: послать в редакцию столько писем, сколько есть теоретически возможных исходов соревнования, и в каждом письме дать один из вариантов. Хоть одно письмо попадёт в цель!

Но дело совсем не так просто — вариантов слишком много. Конечно, если надо предсказать только счёт, с которым окончится матч века, то достаточно послать 41 письмо: игралось 40 партий, и сборная СССР могла набрать любое число очков от 0 (брр…) до 40 (вот было бы здорово!). Но если требуется ещё указать исход матча на каждой доске (хотя бы предсказать, кто в нём победит), то число возможных вариантов растёт катастрофически.

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

1. Правила суммы и произведения

В основе решения комбинаторных задач лежат два простых правила — правило суммы и правило произведения.

Правило суммы. Если в нашем распоряжении $m$‍‍ способов выбрать элемент $a$‍‍ и (независимо от них) $n$‍‍ способов выбрать элемент $b$‍,‍ то выбор «или $a$‍‍ или $b$‍‍» можно сделать $m+n$‍‍ способами.

Например, если на тарелке лежат 5 яблок и 9 груш, то выбор яблока или груши можно сделать 14 способами — выбрать либо одно из 5 яблок, либо одну из 9 груш.

Несколько сложнее правило произведения. В нём речь идёт о выборе пары элементов $(a, b)$‍‍ ‍.

Правило произведения. Если в нашем распоряжении $m$‍‍ способов выбрать элемент $a$‍‍ и $n$‍‍ способов выбрать элемент $b$‍,‍ то пару $(a, b)$‍‍ можно выбрать $mn$‍‍ способами.

Таким образом, если на блюде лежат 5 яблок и 9 груш, то пару (яблоко, груша) можно выбрать $5 \cdot 9 = 45$‍‍ способами.

Чтобы убедиться в справедливости правила произведения, обозначим все способы выбора элемента $a$‍‍ через $a_1, \ldots, a_m$‍,‍ а все способы выбора элемента $b$‍‍ — через $b_1, \ldots, b_n$‍.‍ Тогда все пары, которые можно составить из этих элементов, располагаются в следующую таблицу из $m$‍‍ строк и $n$‍‍ столбцов:

$$ (a_1, b_1), \ldots, (a_1, b_n), $$ $$ (a_m, b_1), \ldots, (a_m, b_n). $$ рисунок или нет

В этой таблице как раз $mn$‍‍ пар.

Заметим, что иногда выбор бывает более сложным — надо сначала выбрать элемент $a$‍,‍ а потом, в зависимости от этого выбора, элемент $b$‍.‍ Но если элемент $a$‍‍ можно выбрать $m$‍‍ способами, а после каждого такого выбора элемент $b$‍‍ можно выбрать $n$‍‍ способами, то число различных пар $(a, b)$‍‍ опять равно $mn$‍.‍ Докажите это сами.

Конечно, может случиться, что нам надо сделать не два, а несколько выборов. В этом случае надо перемножить числа вариантов для каждого выбора. Иными словами, верно следующее правило.

Если элемент $a_1$‍‍ можно выбрать $n_1$‍‍ способами, элемент $a_2$‍‍ — $n_2$‍‍ способами, элемент $a_k$‍‍ — $n_k$‍‍ способами, то набор $(a_1, \ldots, a_k)$‍‍ можно выбрать $n_1 \ldots n_k$‍‍ способами (при этом наборы, отличающиеся друг от друга только порядком элементов, считаются различными).

Теперь мы уже можем решить задачу о числе возможных исходов матча века. На каждой доске могло быть 3 исхода: победа, ничья и поражение. Так как число досок равно 10, то различных исходов могло быть $3^{10} = 59 \, 049$‍.‍ А если надо предсказать не только исход каждого поединка, но и его счёт, то получится ответ $9^{10}$‍.‍

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

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

Конечно, «слова» здесь имеют иной смысл, чем в филологии — допускаются такие «слова», как абвео или абаба. Но слова типа ссора, пресс, аахен не допускаются — в них есть две идущие подряд одинаковые буквы.

Чтобы решить этот пример, будем выбирать буквы одну за другой — сначала первую, потом вторую, третью, четвёртую, пятую. Первую букву можно выбрать 33 способами — ведь в нашем распоряжении все 33 буквы русского алфавита. А вот вторую букву можно выбрать лишь 32 способами — ведь она должна отличаться от первой. 32 способами можно выбрать и третью букву — она должна отличаться от второй; четвёртую и пятую буквы тоже можно выбрать 32 способами. А всего получается $$ 33 \cdot 32 \cdot 32 \cdot 32 \cdot 32 = 34 \, 603 \, 008 $$ различных слов, удовлетворяющих поставленному условию.

2. k-подмножества

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

Эти задачи формулируются на языке теории множеств. Если читатель не знаком с тем, что такое «множество», «элемент множества», «пересечение множеств», «объединение множеств», отсылаем его к литературе, список которой приведён в конце статьи. Впрочем, мы будем пользоваться лишь простейшими понятиями теории множеств, которые теперь будут изучаться в 4-м и 5-м классах средней школы, а в качестве примера мы возьмём множество из четырёх элементов и будем изображать его подмножества и слова, составленные из элементов этого множества.

Решим следующую задачу. 5 студентов сдают зачёт по плаванию. Зачёт сдан, если студент проплывает 100 метров (время любое). Если же студента приходится вылавливать, то зачёт не сдан. Сколькими способами может окончиться заплыв?

Возможны различные случаи. Может случиться, что все студенты окажутся хорошими пловцами, а может случиться, что всех пятерых придётся спасать. Общее число исходов можно сосчитать так. Расположим всех студентов в каком-то порядке, скажем по алфавиту: Андреев, Борисов, Володин, Григорьев, Дмитриев. Для каждого из них есть две возможности — либо он сдаёт зачёт, либо нет. В первом случае поставим в соответствие этому студенту цифру 1, а во втором — цифру 0. Тогда исход заплыва выразится последовательностью длины 5 из нулей и единиц. Например, последовательность 0, 1, 1, 0, 1 означает, что достаточно хорошо плавают только Борисов, Володин и Дмитриев. А если зачёт сдаст только Григорьев, то отчёт об исходе соревнований будет иметь такой вид: 0, 0, 0, 1, 0. Последовательность 0, 0, 0, 0, 0 означает, что ни один студент не достиг финиша.

Таким образом, задача о числе всех исходов заплыва свелась к следующей: сколько последовательностей длины 5 можно составить из цифр 0 и 1? Ответ на эту задачу даётся правилом произведения: поскольку на каждом месте последовательности у нас выбор из двух возможностей, то общее число исходов равно $2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 32$‍.‍ Итак, имеется 32 возможных исхода заплыва.

В разобранной задаче нам надо было узнать, сколько подмножеств можно составить из множества $N: \{Андреев, Борисов, Володин, Григорьев, Дмитриев\}$‍.‍

При этом допускалось и пустое подмножество, а также подмножество, совпадающее со всем множеством $N$‍.‍ Ответ оказался равным $32 = 2^5$‍.‍ Точно так же доказывается, что если множество $N$‍‍ содержит $n$‍‍ элементов, то оно имеет $2^n$‍‍ подмножеств. Этот же результат можно доказать, воспользовавшись математической индукцией.

В олимпийских играх поступают так: в финал выходят двое лучших. Выясним, сколько исходов могут иметь соревнования в этом случае. Математически задача формулируется так: сколькими способами можно выбрать 2 элемента из множества, содержащего 5 элементов? Легко проверить, что это можно сделать 10 способами (выпишите сами все эти способы). Но такой метод «прямого перебора» годится лишь при малом числе участников. Хотелось бы иметь формулу, позволяющую сразу давать ответ на вопрос. Итак, нам надо решить следующую задачу.

Сколько $k$‍‍-подмножеств содержится в множестве $N$‍‍ из $n$‍‍ элементов?

Здесь мы для краткости говорим «$k$‍‍-подмножество» вместо «подмножество, содержащее $k$‍‍ элементов».

Выбор подмножества из данного множества $N$‍‍ можно наглядно представить себе следующим образом. Элементы множества $N$‍‍ сложим в мешок, а затем запустим в этот мешок руку и вытащим подмножество. Разумеется, все $k$‍‍ элементов подмножества вытаскиваются сразу и никакого разумного порядка для них установить нельзя.

Рисунок 2

Обозначим число $k$‍‍-подмножеств в множестве из $n$‍‍ элементов через $C_n^k$‍‍ ‍.

Числа $C_n^k$‍‍ (их называют биномиальными коэффициентами) обладают целым рядом любопытных свойств. О многих из них было рассказано в статье Д. Б. Фукса и М. Б. Фукса «Арифметика биномиальных коэффициентов» («Квант», № 6, 1970). В этой статье было доказано, что $$ C_n^k = C_{n-1}^k + C_{n-1}^{k-1}, \tag{1} $$ и с помощью метода математической индукции получена формула для $C_n^k$‍:‍ $$ C_n^k = \frac{n!}{k!(n-k)!} . \tag{2} $$ ‍

Оба утверждения были выведены из равенства: $$ (1+x)^n = C_n^0 + C_n^1x + C_n^2x^2 + ... + C_n^nx^n, $$ но их можно доказать и комбинаторными рассуждениями.

Чтобы доказать, например, равенство $(1)$‍,‍ зафиксируем один элемент $a$‍‍ из $N$‍‍ и разобьём все $k$‍‍-подмножества в $N$‍‍ на два класса: содержащие $a$‍‍ и не содержащие $a$‍.‍ Проверьте, что число подмножеств первого класса равно $C_{n-1}^{k-1}$‍,‍ а число подмножеств второго класса равно $C_{n-1}^k$‍.‍ Так как каждое $k$‍‍-подмножество принадлежит либо первому, либо второму классу, общее число всех $k$‍‍-подмножеств равно $C_n^k$‍,‍ то равенство $(1)$‍‍ доказано.

Чтобы вывести формулу $(2)$‍,‍ выясним сначала, как получаются $k$‍‍-подмножества из $(k-1)$‍‍-подмножеств. Ясно, что для этого надо к $(k-1)$‍‍-подмножествам присоединить не входящие в них элементы. Так как всё множество $N$‍‍ содержит $n$‍‍ элементов, то в данное $(k-1)$‍‍-подмножество не входит $n - (k-1)$‍‍ элементов. Значит, из каждого $(k-1)$‍‍-подмножества можно получить $n - k+1$‍‍ различных $k$‍‍-подмножеств. Но одно и то же $k$‍‍-подмножество может быть получено из различных $(k-1)$‍‍-подмножеств — мы не знаем, какой из $k$‍‍ элементов оказался присоединённым в последнюю очередь. Иными словами, любое $k$‍‍-подмножество может быть получено $k$‍‍ различными способами из $(k-1)$‍‍-подмножеств. Поэтому общее число $k$‍‍-подмножеств в $k$‍‍ раз меньше, чем $(n-k+1) C_{n}^{k-1}$‍.‍ Итак, $$ C_n^k = \frac{n-k+1}{k} C_n^{k-1}. $$

Пользуясь этой формулой и методом математической индукции, легко доказать и формулу $(2)$‍.‍

3. k-слова

Снова возьмём в руки мешок с элементами множества $N$‍,‍ но на этот раз будем вытаскивать элементы не сразу, а по очереди. Сначала вынем один элемент, обозначим его $a_1$‍,‍ запишем и положим обратно в мешок. Потом вытащим второй элемент (может случиться, что нам снова попадётся тот же самый элемент $a_1$‍),‍ запишем его и т. д. После $k$‍‍ выборов у нас получится запись вида $(a_1, \ldots, a_k)$‍,‍ где $a_1, \ldots, a_k$‍‍ — какие-то элементы из множества $N$‍.‍ Такую запись мы назовём словом длины $k$‍‍ или $k$‍‍-словом (иначе её называют кортежем), составленным из элементов множества $N$‍.‍

Два $k$‍‍-слова считаются совпадающими, если у них одинаковые первые элементы, одинаковые вторые элементы, одинаковые $k$‍‍-е элементы.

С $k$‍‍-словами мы часто встречаемся на практике. Например, десятичные записи чисел — это «слова», составленные из 10 цифр, обычные слова — это «слова», составленные из русских букв, фразы — это «слова», составленные из русских слов. Решим следующую задачу.

Дано множество $N$‍,‍ состоящее из $n$‍‍ элементов. Сколько $k$‍‍-слов можно составить из элементов этого множества?

Поскольку первый элемент можно выбрать $n$‍‍ способами, второй тоже $n$‍‍ способами, $\ldots$‍,‍ $k$‍‍-ый тоже $n$‍‍ способами, то $k$‍‍-слово можно выбрать $n^k$‍‍ способами.

Окончательно: из $n$‍‍ элементов можно составить $n^k$‍‍ слов длины $k$‍.‍

Многие комбинаторные задачи решаются по этому правилу. Найдём, например, сколькими способами можно разделить $k$‍‍ различных предметов между $n$‍‍ людьми. Для этого расположим элементы в каком-то порядке и над каждым предметом укажем, кому он предназначается. Например, запись

Таблица

показывает, что первому участнику раздела достанутся $1$‍‍-й, $2$‍‍-й, $6$‍‍-й, $10$‍‍-й предметы, второму — $4$‍‍-й, $5$‍‍-й, $7$‍‍-й, а третьему — $3$‍‍-й, $8$‍‍-й, $9$‍‍-й предметы.

Мы видим, что каждый способ раздела задаётся $k$‍‍-словом (где $k$‍‍ — число предметов) из $n$‍‍ элементов (номеров участников раздела). Значит, число способов раздела равно $n^k$‍.‍

4. k-слова без повторений

Опять возьмём в руки мешок, в который сложены элементы множества $N$‍‍ и начнём вытаскивать из него один за другим элементы этого множества. Но на этот раз не будем возвращать эти элементы в мешок, а выложим их в ряд. После $k$‍‍ выборов у нас снова появится $k$‍‍-слово $(a_1, \ldots, a_k)$‍,‍ но на этот раз среди элементов $a_1, \ldots, a_k$‍‍ нет повторяющихся‍. По-другому можно сказать, что $k$‍‍-слова без повторений — это упорядоченные $k$‍‍-подмножества множества $N$‍.‍

Число $k$‍‍-слов без повторений из $n$‍‍ элементов обозначают $A_n^k$‍.‍ Из правила произведения сразу вытекает, что $$ A_n^k = n \, (n - 1) \dots (n - k + 1). \tag{3} $$

В самом деле, первый элемент можно выбрать $n$‍‍ способами, второй — только $n - 1$‍‍ способами, ведь взять уже выбранный элемент нельзя. Третий элемент можно выбрать $n - 2$‍‍ способами, $\ldots$‍,‍ $k$‍‍-ый — $(n - k + 1)$‍‍ способами. Значит, общее число способов действительно выражается формулой $(3)$‍.‍

Например, если из 10 членов комиссии надо назначить председателя, его заместителя и секретаря, то это можно сделать $10 \cdot 9 \cdot 8 = 720$‍‍ способами.

5. Перестановки

Если из мешка вытаскиваются и выкладываются в ряд один за другим все элементы множества $N$‍‍ (и ни один элемент не возвращается обратно), то в конце концов все элементы множества $N$‍‍ окажутся расположенными в некотором порядке. В этом случае говорят о перестановках без повторений из $n$‍‍ элементов. Таким образом, перестановка из $n$‍‍ элементов — это $n$‍‍-слово без повторений из $n$‍‍ элементов. Полагая в формуле $(3)$‍‍ $k = n$‍,‍ получаем, что число перестановок из $n$‍‍ элементов равно $n!$‍.‍ Его обозначают символом $P_n$‍.‍ Итак, $$ P_n = n! $$

6. Перестановки с повторениями

Мы уже знаем, что из $n$‍‍ «букв» можно составить $n^k$‍‍ слов длины $k$‍.‍ Некоторые из них отличаются друг от друга своим составом, а другие — только порядком элементов. Соберём все слова, имеющие один и тот же состав, а именно такие, в которые входят $k_1$‍‍ раз первая буква, $k_2$‍‍ раз вторая буква, ... $k_n$‍‍ раз $n$‍‍-я буква (мы считаем, что «буквы» в «алфавите» расположены в каком-то порядке). Ясно, что $k = k_1 + k_2 + ... + k_n$‍.‍ Число «слов» в этом подмножестве обозначим через $P(k_1, ..., k_n)$‍.‍ Мы докажем сейчас, что $$ P(k_1, k_2, ..., k_n) = \frac{k!}{k_1!k_2!...k_n!}. \tag{4} $$

Для этого заметим, что буквы, входящие в данное слово, можно переставлять друг с другом $k!$‍‍ способами. Но не все из этих способов изменяют слово. Например, слово баллада не изменяется при перестановке второй и пятой или третьей и четвёртой букв (в первом случае переставляются между собой две буквы а, а во втором — две буквы л). Подсчитаем число перестановок букв, не изменяющих слово состава $(k_1, k_2, ..., k_n)$‍.‍ Легко видеть, что число таких перестановок равно $k_1! k_2! ... k_n!$‍‍ (например, для слова баллада число таких перестановок равно $3! \cdot 2!$‍‍ — мы можем переставлять друг с другом $3!$‍‍ способами буквы а и $2!$‍‍ способами буквы л; буквы б и д входят лишь один раз). Поэтому, чтобы сосчитать число перестановок с повторениями, надо $k!$‍‍ разделить на $k_1! k_2! ... k_n!$‍‍ Формула $(4)$‍‍ доказана.

Найдём, например, сколько различных слов получается при перестановке букв слова метаматематика. В это слово входят 3 буквы м, 2 буквы е, 3 буквы т, 4 буквы а, 1 буква и и 1 буква к, а всего 14 букв. Значит, число перестановок букв этого слова равно $$ P(3, 2, 3, 4, 1, 1) = \frac{14!}{3! \, 2! \, 3! \, 4! \, 1! \, 1!} = 50 \, 450 \, 400. $$

С помощью формулы для перестановок с повторениями можно получить новое доказательство формулы $(2)$‍.‍ Мы уже знаем, что каждое подмножество множества $N$‍‍ можно зашифровать с помощью нулей и единиц. Если множество $N$‍‍ содержит $n$‍‍ элементов, а подмножество — $k$‍‍ элементов, то получим $k$‍‍ единиц и $n - k$‍‍ нулей. Значит, в множестве из $n$‍‍ элементов есть столько же $k$‍‍-подмножеств, сколько перестановок можно сделать из $k$‍‍ единиц и $n - k$‍‍ нулей. Таким образом, $$ C_n^k = P(k, n - k) = \frac{n!}{k! \, (n - k)!}. $$

Задачи

1. Пусть $p_1, ..., p_k$‍‍ — различные простые числа. Сколько делителей имеет число $$ q = p_1^{\alpha_1} p_2^{\alpha_2} \ldots p_k^{\alpha_k}, $$ где $\alpha_1, \ldots, \alpha_k$‍‍ — некоторые натуральные числа (включая делители 1 и $q$‍)?‍
2. Сколькими способами можно переставить между собой буквы слова перешеек так, чтобы четыре буквы е не шли подряд?
3. Сколькими способами можно переставить буквы в слове камелия так, чтобы не менялся порядок гласных букв?
4. Сколькими способами можно переставить буквы слова огород так, чтобы три буквы о не стояли рядом?
5. Найдите сумму всех трёхзначных чисел, которые можно записать с помощью цифр $1, 2, 3, 4$‍‍ (любую из цифр можно использовать несколько раз).
6. Найдите сумму четырёхзначных чисел, которые получаются при всевозможных перестановках цифр $1, 2, 3, 4$‍.‍
7. Решите ту же задачу для цифр $1, 2, 2, 5$‍.‍
8. С помощью комбинаторных рассуждений докажите тождества:
   1. а) $C_n^0 + C_n^1 + ... + C_n^n = 2^n$‍;‍
   2. б) $C_n^k C_{n-k}^{m-k} = C_m^k C_{n}^{m}$‍.‍

оформить надлежащим образом литературу

Литература

1. Н. Я. Виленкин, Р. С. Гутер и др. Алгебра, «Просвещение», 1968.
2. Н. Я. Виленкин, Рассказы о множествах, «Наука», 1969.
3. Н. Я. Виленкин, Комбинаторика, «Наука», 1969.
4. Дополнительные главы по курсу математики 7‍—‍8 классов для факультативных занятий. Сборник статей, составитель К. П. Сикорский. «Просвещение», М., 1969.
5. Б. В. Гнеденко, И. Г. Журбенко, Теория вероятностей и комбинаторика. «Математика в школе», 1968, № 2, 3.