Комбинаторика

13

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

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

Но дело совсем не так просто — вариантов слишком много. Конечно, если надо предсказать только счет, с которым окончится матч века, то достаточно послать 81 письмо: игральс 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$ способами.

*) Две пары, получающие друг из друга перестановкой элементов, считаются различными, например пара (1, 4) считается не совпадающей с парой (4,1).

14

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

$$(a_1, b_1), \dots, (a_1, b_n),$$
$$(a_m, b_1), \dots, (a_m, b_n).$$

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

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

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

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

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

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

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

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

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

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

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

15

Рис. 1. Пусть множество $N$ состоит из четырех элементов: коня, слона, ферзя и ладьи.

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

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

Таким образом, задача о числе исходов залывва свелась к следующей: сколько последовательностей длины 5 можно счётить из цифр 0 и 1? Ответ на эту задачу дает правильное произведение: поскольку на каждом месте последовательности у нас выбор из двух возможностей, то общее число исходов равно $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$ элементов подмножества вытаскивают сразу и никакого разумного порядка для них установить нельзя.

18

Рис. 5. Существует $P_4=4!=24$ перестановки элементов множества $N$.

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

Число $k$-слов без повторений из $n$ элементов обозначают $A_n^k$. Из правила произведения сразу вытекает, что

$$A_n^k=n(n-1)\dots(n-k+1).$$

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

*) Такие $k$-слов называются размешениями без повторений.

Значит, общее число способов действительное выражается формулой (3).

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

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

$$P_n=n!$$

6. Перестановки с повторениями. Мы уже знаем, что из $n$ «букв» можно