Часть VII · Случай и данные Глава 45 из 60
Комбинаторика
Вечер настольных игр: кости, карты, фишки, шляпы и гости. Научимся считать варианты, не выписывая их, и увидим, что в достаточно большой компании какой-то порядок возникает сам собой.
Опирается на: 44 · Дзета-функция и эллиптические кривые
Вы научитесь
- считать варианты правилами суммы и произведения, не выписывая их
- отличать перестановки, размещения и сочетания и считать их по формулам
- раскрывать скобки в степени двучлена и делить одинаковые предметы между людьми
- доказывать принципом Дирихле, что нужное совпадение обязательно найдётся
Прошлая глава закончилась вопросом «сколькими способами может выпасть…?». Начнём с игральных костей: с задач о них началась и сама наука о шансах. Около 1620 года Галилео Галилей написал короткую заметку о том, как выпадают очки на трёх костях. Считается, что вопрос задал ему покровитель, великий герцог Тосканский. Игроки, бросавшие три кости, заметили странное: сумма $10$ выпадает чаще, чем $9$. А ведь обе суммы складываются шестью способами.
Проверьте сами. Девятка: $1 + 2 + 6$, $1 + 3 + 5$, $1 + 4 + 4$, $2 + 2 + 5$, $2 + 3 + 4$, $3 + 3 + 3$. Десятка: $1 + 3 + 6$, $1 + 4 + 5$, $2 + 2 + 6$, $2 + 3 + 5$, $2 + 4 + 4$, $3 + 3 + 4$. Шесть и шесть. Откуда перевес?
Эта глава устроена как вечер настольных игр. За каждым столом своя игра: кости, рассадка гостей, раздача карт, фишки, шляпы в гардеробе. И за каждым столом один и тот же вопрос: сколько всего вариантов? Выписать их все чаще всего невозможно — их миллионы. Будем учиться считать, не перебирая.
Кости великого герцога
Галилей заметил то, что ускользнуло от игроков: кости различимы, даже если выглядят одинаково. Покрасьте их мысленно в три цвета, красный, синий и зелёный. Тогда «$1 + 2 + 6$» — это не один исход, а шесть: единица может оказаться на любой из трёх костей, двойка — на любой из двух оставшихся, шестёрка — на последней. Всего $3 \cdot 2 \cdot 1 = 6$ способов. А «$1 + 4 + 4$» выпадает лишь тремя способами: важно только, на какой кости единица. «$3 + 3 + 3$» — единственным.
Сложим честно. У девятки $6 + 6 + 3 + 3 + 6 + 1 = 25$ исходов, у десятки $6 + 6 + 3 + 6 + 3 + 3 = 27$. Всех исходов у трёх костей $6 \cdot 6 \cdot 6 = 216$, и все они равновозможны. Выходит, десятка выпадает в $27$ случаях из $216$, девятка — в $25$. Разница в два исхода, меньше процента, но за сотни вечеров у игорного стола игроки её почувствовали.
Ошибка «считать разложения вместо исходов» долго переживала Галилея. По известному рассказу, Лейбниц считал, что на двух костях суммы $11$ и $12$ выпадают одинаково часто: каждая, мол, получается одним способом, $5 + 6$ и $6 + 6$. На деле у одиннадцати два исхода, $(5, 6)$ и $(6, 5)$, а у двенадцати один.
Два правила
Вся глава стоит на двух правилах, которыми мы уже пользовались, не называя их: на правиле суммы и на правиле произведения.
Если выбрать можно или один из $m$ вариантов, или один из $n$ других, и общих вариантов у двух групп нет, то всего вариантов $m + n$.
Пронумеруем варианты первой группы числами от $1$ до $m$, а варианты второй — числами от $m + 1$ до $m + n$. Раз общих вариантов нет, каждый вариант получил ровно один номер, и каждый номер от $1$ до $m + n$ достался ровно одному варианту. Значит, вариантов столько же, сколько номеров, — $m + n$. Если бы у групп был общий вариант, он получил бы два номера и был бы посчитан дважды; поэтому условие «общих вариантов нет» в правиле обязательно.
Пусть выбор делается в $k$ шагов: на первом шаге есть $n_1$ вариантов, на втором — $n_2$ вариантов при любом выборе на первом, на третьем — $n_3$ при любых выборах на первых двух, и так далее. Тогда всего вариантов $n_1 \cdot n_2 \cdots n_k$.
Изобразим выбор деревом. Из корня выходят $n_1$ ветвей — варианты первого шага. На рисунке первый шаг — выбор одной из трёх игр, $n_1 = 3$.
Из конца каждой ветви выходят $n_2$ новых ветвей — варианты второго шага. Именно здесь работает условие правила: их число одно и то же, какую бы ветвь первого шага мы ни выбрали. У каждой игры по четыре вида печенья, $n_2 = 4$.
Полный выбор — это путь от корня до листа, и разным выборам соответствуют разные листья. Листья разбиты на $n_1$ групп, в каждой по $n_2$ листьев. Сложив группы по правилу суммы, получаем $n_2 + n_2 + \ldots + n_2 = n_1 \cdot n_2$ листьев. На рисунке $3 \cdot 4 = 12$.
Если шагов больше, к каждому листу приставляем $n_3$ новых ветвей (здесь — три вида сока), и число листьев снова умножается: $n_1 n_2 \cdot n_3$. Каждый следующий шаг умножает число листьев на своё число вариантов, поэтому после $k$ шагов их $n_1 \cdot n_2 \cdots n_k$.
На полке пять карточных игр и три настольные. Взять одну игру можно $5 + 3 = 8$ способами: это правило суммы. К игре нужен ещё перекус: четыре вида печенья и три вида сока. Печенье и сок выбираются $4 \cdot 3 = 12$ способами, а игра с печеньем и соком — $8 \cdot 4 \cdot 3 = 96$ способами. Это правило произведения.
Условие «при любом выборе» легко пропустить. Сколько трёхзначных чисел записывается разными цифрами? Первая цифра — любая, кроме нуля: девять вариантов. Вторая — любая, кроме первой: снова девять (ноль теперь разрешён). Третья — любая, кроме двух уже занятых: восемь. Какие именно цифры свободны, зависит от первых шагов, а сколько их — нет. Поэтому правило работает.
Сколько существует трёхзначных чисел, у которых все три цифры разные?
Первая цифра — от $1$ до $9$: девять вариантов. Вторая — любая из десяти, кроме первой: девять. Третья — любая, кроме двух занятых: восемь. По правилу произведения $9 \cdot 9 \cdot 8 = 648$.
Правило суммы тоже требует внимательности. Если группы пересекаются, общие варианты посчитаются дважды. Как с этим справляться, мы увидим за столом со шляпами.
Кто где сядет
Шесть гостей рассаживаются на шесть стульев вдоль стола. На первый стул может сесть любой из шести, на второй — любой из пяти оставшихся, на третий — из четырёх. Последнему гостю достаётся последний стул. Всего $6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720$ рассадок. Если гости захотят каждый вечер садиться по-новому, им хватит почти на два года.
Перестановка $n$ различных предметов — любой их порядок в ряд. Произведение $1 \cdot 2 \cdot 3 \cdots n$ называют факториалом числа $n$ и пишут $n!$ (читается «эн факториал»).
$n$ различных предметов можно расставить в ряд ровно $n!$ способами.
Расстановка — это выбор в $n$ шагов: какой предмет встанет на первое место, какой на второе, и так далее. На первое место годится любой из $n$ предметов. На второе — любой из $n - 1$ оставшихся; какие именно остались, зависит от первого шага, но их всегда $n - 1$. На третье место остаётся $n - 2$ вариантов, и так до последнего места, куда встаёт единственный оставшийся предмет. Условие правила произведения выполнено на каждом шаге, поэтому расстановок $n \cdot (n - 1) \cdot \ldots \cdot 2 \cdot 1 = n!$.
Факториал растёт стремительно. Колоду из $52$ карт можно перетасовать $52!$ способами, а это число из $68$ цифр, примерно $8 \cdot 10^{67}$. Если бы все восемь миллиардов жителей Земли тасовали по колоде в секунду с самого Большого взрыва, они получили бы около $3{,}5 \cdot 10^{27}$ колод. Это ничтожная доля всех порядков. Почти наверняка колода, которую вы хорошо перетасуете сегодня вечером, лежит в порядке, в каком не лежала ни одна колода в истории.
Теперь вернёмся к костям. Почему «$1 + 4 + 4$» выпадает тремя способами, а не шестью? Расставим на три кости набор $\{1, 4, 4\}$. Если бы четвёрки различались (скажем, одна красная, другая синяя), способов было бы $3! = 6$. Но переставив две четвёрки между собой, мы не получим ничего нового, поэтому каждый исход посчитан дважды: $3!/2! = 3$.
Так же считаются «слова» из букв с повторами. Из букв слова МАМА получается $\frac{4!}{2! \cdot 2!} = 6$ слов: ММАА, МАМА, МААМ, АММА, АМАМ, ААММ. В слове КОМБИНАТОРИКА тринадцать букв, и четыре из них встречаются дважды (К, О, И, А). Переставляя их, можно получить $\frac{13!}{2!\cdot 2! \cdot 2! \cdot 2!} = 389\,188\,800$ разных «слов».
Сколько разных «слов» (не обязательно осмысленных) получается, если переставлять буквы слова АНАНАС?
Всего шесть букв: А три раза, Н два раза, С один раз. Если бы все буквы различались, было бы $6! = 720$ перестановок. Три буквы А между собой переставляются $3! = 6$ способами, две Н — $2! = 2$ способами, и эти перестановки слова не меняют. Ответ: $\frac{720}{6 \cdot 2} = 60$.
Пьедестал
В турнире по шашкам восемь участников, и нас интересует только тройка призёров: кто золото, кто серебро, кто бронза. Золото может взять любой из восьми, серебро — любой из семи оставшихся, бронзу — любой из шести. Пьедесталов $8 \cdot 7 \cdot 6 = 336$.
Размещение из $n$ по $k$ — упорядоченный выбор $k$ различных предметов из $n$: важно и кто выбран, и в каком порядке. Их число обозначают $A_n^k$ (так пишут в российских учебниках; в англоязычных чаще встречается $P(n, k)$).
Упорядоченно выбрать $k$ различных предметов из $n$ можно $A_n^k = n(n - 1)\cdots(n - k + 1) = \dfrac{n!}{(n - k)!}$ способами.
Первое место занимает любой из $n$ предметов, второе — любой из $n - 1$ оставшихся, и так далее; $k$-е место — любой из $n - (k - 1) = n - k + 1$ оставшихся. По правилу произведения способов $n(n - 1)\cdots(n - k + 1)$: это произведение $k$ множителей. Чтобы записать его через факториалы, домножим и разделим его на $(n - k)! = (n - k)(n - k - 1)\cdots 1$. В числителе получится произведение всех чисел от $n$ до $1$, то есть $n!$, откуда $A_n^k = \frac{n!}{(n - k)!}$.
Раздача
Из тех же восьми игроков надо выбрать троих в команду на командный турнир. Капитана и порядка нет: команда «Аня, Боря, Вика» — та же, что «Вика, Аня, Боря». Каждую команду из трёх человек можно поставить на пьедестал $3! = 6$ способами, так что пьедесталов вшестеро больше, чем команд. Команд $336 / 6 = 56$.
Сочетание из $n$ по $k$ — выбор $k$ предметов из $n$ без учёта порядка. Число сочетаний называют биномиальным коэффициентом и обозначают $\binom{n}{k}$ (читается «из $n$ по $k$»). В российских учебниках пишут также $C_n^k$.
Выбрать $k$ предметов из $n$ без учёта порядка можно $\dbinom{n}{k} = \dfrac{n!}{k!\,(n - k)!}$ способами.
Посчитаем упорядоченные выборы — пьедесталы — двумя способами. С одной стороны, их $A_n^k = \frac{n!}{(n - k)!}$. С другой стороны, пьедестал можно выбрать в два шага: сначала неупорядоченную команду из $k$ человек (это $\binom{n}{k}$ вариантов), затем её порядок на пьедестале (это $k!$ вариантов при любой команде — число перестановок $k$ человек). По правилу произведения пьедесталов $\binom{n}{k} \cdot k!$. Приравниваем: $\binom{n}{k} \cdot k! = \frac{n!}{(n - k)!}$, и делим обе части на $k!$.
За карточным столом эта формула отвечает на все вопросы о раздачах. В покере игрок получает пять карт из $52$, и разных раздач $\binom{52}{5} = 2\,598\,960$. Ровно четыре из них — флеш-рояль (туз, король, дама, валет и десятка одной масти), поэтому он приходит примерно раз на шестьсот пятьдесят тысяч раздач. В лотерее «6 из 45» комбинаций $\binom{45}{6} = 8\,145\,060$: один билет угадывает все шесть чисел с шансом один на восемь миллионов.
Сколькими способами из пяти человек можно выбрать двоих дежурных?
Порядок не важен, значит, это сочетания: $\binom{5}{2} = \frac{5 \cdot 4}{2} = 10$. Если бы нужны были старший и помощник, ответ был бы $A_5^2 = 20$.
В конце вечера каждый из десяти гостей пожал руку каждому другому. Сколько всего было рукопожатий?
Рукопожатие — это пара гостей без учёта порядка: $\binom{10}{2} = \frac{10 \cdot 9}{2} = 45$. Можно рассуждать иначе: каждый пожал $9$ рук, это $10 \cdot 9 = 90$, но каждое рукопожатие так посчитано дважды, с обеих сторон. Эта мысль вернётся в следующей главе.
Ладья идёт домой
На пустой шахматной доске ладья стоит в углу a1 и хочет попасть в противоположный угол h8. Ходит она по одной клетке, вправо или вверх. Сколько у неё путей?
Любой такой путь состоит из четырнадцати ходов: семи «вправо» и семи «вверх». Путь целиком определяется тем, какие семь ходов из четырнадцати будут «вверх». Значит, путей $\binom{14}{7} = 3432$.
Есть и второй способ посчитать, без формулы. В каждую клетку ладья приходит либо слева, либо снизу. Поэтому число путей до клетки равно сумме чисел путей до её соседа слева и соседа снизу. Вдоль нижнего края и левого края путь один. Заполняя доску этим правилом, мы получим таблицу, которую удобнее повернуть на сорок пять градусов. Выйдет треугольник, где каждое число — сумма двух над ним.
При $1 \le k \le n - 1$ выполняется равенство $\dbinom{n}{k} = \dbinom{n - 1}{k - 1} + \dbinom{n - 1}{k}$.
Путь ладьи из угла $S$ в клетку $T$ состоит из $n$ ходов, $k$ из них — вверх, остальные — вправо. Путь целиком задаётся тем, какие $k$ ходов из $n$ направлены вверх, поэтому путей в $T$ ровно $\binom{n}{k}$. На рисунке $n = 5$, $k = 2$.
Посмотрим на последний ход. Если он сделан вверх, ладья пришла в $T$ из клетки прямо под ней. До этой клетки она сделала $n - 1$ ходов, из них вверх — $k - 1$. Таких путей $\binom{n - 1}{k - 1}$ (клетка существует, потому что $k \ge 1$), и каждый продолжается в $T$ единственным ходом.
Если последний ход сделан вправо, ладья пришла из клетки слева от $T$. До неё $n - 1$ ходов, и вверх среди них все $k$. Таких путей $\binom{n - 1}{k}$ (клетка существует, потому что $k \le n - 1$).
Последний ход бывает либо вверх, либо вправо, но не то и другое сразу. Значит, две группы путей не пересекаются и вместе дают все пути в $T$. По правилу суммы $\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}$; на рисунке $10 = 4 + 6$. Заполняя так клетку за клеткой, мы получаем числа всей доски — это и есть треугольник Паскаля, повёрнутый на $45°$.
Треугольник Паскаля — таблица, в $n$-й строке которой стоят числа $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. Строки нумеруют с нуля; по краям стоят единицы, каждое внутреннее число равно сумме двух соседних над ним.
В треугольнике Паскаля спрятано больше, чем кажется. Раскрасим нечётные числа, а чётные оставим незакрашенными. Первые строки выглядят невинно, но в тридцати двух строках проступает узор из треугольников в треугольниках — тот самый, который польский математик Вацлав Серпинский описал в 1915 году.
Почему возникает узор? Нас интересует только чётность, а при сложении чётностей $1 + 1$ даёт чётное. Строка номер $2^m$ (например, $16$ или $32$) состоит из двух единиц по краям и одних чётных чисел между ними. Дальше каждая из двух единиц порождает под собой точную копию верхушки треугольника, а между копиями остаётся пустота. Отсюда и самоподобие. Посчитать нечётные числа тоже можно: при удвоении числа строк их становится втрое больше (три копии), так что в первых $2^m$ строках их ровно $3^m$. В тридцати двух строках $528$ чисел, а нечётных среди них $3^5 = 243$ — меньше половины, и с каждым удвоением строк доля нечётных падает.
Вдоль пологих диагоналей числа складываются в $1, 1, 2, 3, 5, 8, 13, \ldots$ — в числа Фибоначчи. А сумма чисел в $n$-й строке равна $2^n$: $1 + 4 + 6 + 4 + 1 = 16$. Причину мы увидим, когда начнём подбрасывать монеты.
Орёл и решка
Бросим монету четыре раза. Исходов $2^4 = 16$, и каждый записывается словом из букв О и Р, например ОРРО. Сколько исходов, в которых ровно два орла? Столько, сколькими способами можно выбрать два места из четырёх под буквы О: $\binom{4}{2} = 6$. Сгруппируем все шестнадцать исходов по числу орлов: $1$ исход без орлов, $4$ с одним, $6$ с двумя, $4$ с тремя и $1$ с четырьмя. Это четвёртая строка треугольника, а сумма $16 = 2^4$ — все исходы.
Та же строка появляется, когда раскрываешь скобки в $(a + b)^4$, и это не совпадение.
Для любых чисел $a$, $b$ и любого натурального $n$
$$(a + b)^n = \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k} = b^n + \binom{n}{1} a b^{n - 1} + \binom{n}{2} a^2 b^{n - 2} + \ldots + a^n.$$$(a + b)^n$ — произведение $n$ одинаковых скобок. По распределительному закону, раскрыв скобки, мы получим сумму всех произведений, где из каждой скобки взято одно слагаемое: $a$ или $b$. Каждое такое произведение запишем словом из $n$ букв — например, $abba$ означает: из первой скобки взяли $a$, из второй $b$, из третьей $b$, из четвёртой $a$. Слов $2^n$ (по два варианта на каждую скобку); на рисунке $n = 4$, слов $16$.
Произведение, записанное словом, зависит только от того, сколько в слове букв $a$. Если их $k$, то букв $b$ — $n - k$, и произведение равно $a^k b^{n - k}$: от перестановки множителей оно не меняется. Разложим слова по столбцам так, чтобы в одном столбце было одинаковое число букв $a$.
Сколько слов в столбце с $k$ буквами $a$? Слово определяется тем, на каких $k$ местах из $n$ стоят буквы $a$, а таких выборов $\binom{n}{k}$. При $n = 4$ получаем $1, 4, 6, 4, 1$ — четвёртую строку треугольника Паскаля.
Собираем одинаковые слагаемые: столбец с $k$ буквами $a$ даёт $\binom{n}{k} a^k b^{n - k}$. Складывая столбцы от $k = 0$ до $k = n$, получаем формулу бинома. При $n = 4$: $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$.
$\dbinom{n}{0} + \dbinom{n}{1} + \ldots + \dbinom{n}{n} = 2^n$.
Подставим $a = b = 1$ в бином Ньютона: слева получится $(1 + 1)^n = 2^n$, а справа, поскольку все степени единицы равны единице, — сумма $\binom{n}{0} + \binom{n}{1} + \ldots + \binom{n}{n}$. Можно убедиться и без формулы: обе части считают все исходы $n$ бросков монеты. Слева — все сразу, по правилу произведения; справа — группами, по числу выпавших орлов, по правилу суммы.
Раскройте скобки в выражении $(x + 2)^5$. Какой коэффициент будет при $x^3$?
Чтобы получить $x^3$, из трёх скобок берём $x$, из двух оставшихся — двойки. Выбрать три скобки из пяти можно $\binom{5}{3} = 10$ способами, и каждый раз двойки дают множитель $2^2 = 4$. Коэффициент $10 \cdot 4 = 40$.
Фишки и перегородки
Новая игра начинается с раздачи. В коробке десять одинаковых фишек, игроков четверо, и раздать фишки можно как угодно: кому-то может не достаться ни одной. Сколько способов? Фишки одинаковые, поэтому важно только, сколько их у каждого. Раздача — это четвёрка чисел, например $(3, 0, 5, 2)$, с суммой $10$.
Выписывать раздачи по одной долго. Хитрость в том, чтобы превратить каждую раздачу в строку из фишек и перегородок.
$n$ одинаковых предметов можно разложить между $k$ получателями (кому-то может не достаться ничего) ровно $\dbinom{n + k - 1}{k - 1}$ способами.
Раздача — это набор чисел $(x_1, x_2, \ldots, x_k)$: сколько предметов досталось каждому получателю. Все $x_i \ge 0$, и их сумма равна $n$. На рисунке $n = 10$, $k = 4$ и раздача $(3, 0, 5, 2)$.
Выложим раздачу в строку: фишки первого получателя, перегородка, фишки второго, перегородка, … фишки последнего. Перегородок $k - 1$, фишек $n$, всего в строке $n + k - 1$ мест. Второму игроку не досталось ничего — в строке это две перегородки подряд.
Обратно: любую строку из $n$ фишек и $k - 1$ перегородок можно прочитать как раздачу — считаем фишки до первой перегородки, между первой и второй, и так далее до конца. Из строки получается ровно та раздача, из которой строка сделана, и наоборот. Значит, раздач ровно столько же, сколько строк.
Строка целиком задаётся тем, какие $k - 1$ мест из $n + k - 1$ заняты перегородками, а на остальных местах стоят фишки. Таких выборов $\binom{n + k - 1}{k - 1}$. На рисунке $\binom{13}{3} = 286$.
Раздач $\binom{n + k - 1}{k - 1}$. Если каждому положено хотя бы по одному предмету, раздадим сначала по одному, а оставшиеся $n - k$ — как угодно: по доказанному это $\binom{(n - k) + k - 1}{k - 1} = \binom{n - 1}{k - 1}$ способов.
Эта формула закрывает и историю с костями. Сколько вообще разных «наборов очков» у трёх костей, если кости не различать? Это раздача трёх одинаковых «костей» по шести значениям граней: $\binom{3 + 6 - 1}{5} = \binom{8}{5} = 56$. Пятьдесят шесть наборов против $216$ исходов. Игроки, которые думали наборами, считали в неправильных единицах: наборы неравновозможны, а исходы равновозможны.
Все приёмы, которые мы собрали, стоит потренировать. Главный вопрос в каждой задаче один и тот же: важен ли порядок и могут ли предметы повторяться. Если попадётся задача, в которой никак не удаётся разобраться, её разберёт по шагам решатель.
Спорим?
Пока за соседним столом раздают фишки, здесь заключают пари, которые нельзя проиграть. «Спорим, что среди нас тринадцати есть двое, родившиеся в одном месяце?» Месяцев двенадцать, людей тринадцать. Даже если первые двенадцать родились в разных месяцах, тринадцатому деваться некуда.
Это рассуждение называют принципом Дирихле; в русской традиции его рассказывают про кроликов и клетки.
Если $n + 1$ кролика рассажены по $n$ клеткам, то в какой-то клетке сидят хотя бы два кролика. В общем виде: если $N$ предметов разложены по $n$ ящикам, то в каком-то ящике их не меньше $N / n$.
Докажем от противного. Предположим, что в каждой клетке сидит не больше одного кролика. На рисунке $n = 4$ клетки и $5$ кроликов.
Тогда кроликов не больше, чем клеток: по одному в каждой — это ровно $n$ кроликов, а если какие-то клетки пусты, то и меньше. Но кроликов $n + 1$, на одного больше.
Противоречие: лишнему кролику некуда деться, и он окажется в уже занятой клетке. Значит, предположение неверно — в какой-то клетке сидят хотя бы два кролика.
Общий вид доказывается так же. Если бы в каждом из $n$ ящиков лежало меньше $N / n$ предметов, то всего их было бы меньше $n \cdot \frac{N}{n} = N$. А их ровно $N$ — противоречие.
Звучит как пустяк, и доказательство действительно короткое. Трудность в другом: понять, что в задаче кролики, а что клетки. Немецкий математик Петер Густав Лежён Дирихле пользовался этим рассуждением в теории чисел в XIX веке, по-немецки оно так и называется, «принцип ящиков». В главе о дробях он уже работал: при делении уголком остатков меньше, чем шагов, поэтому какой-то остаток повторится и цифры пойдут по кругу.
Чуть смелее: в Москве наверняка живут два человека с одинаковым числом волос на голове. Волос у человека порядка ста тысяч и заведомо меньше миллиона, а москвичей больше тринадцати миллионов. Ящики — возможные числа волос, от нуля до миллиона, предметы — москвичи. Кого именно имеет в виду это пари, неизвестно никому, но проиграть его невозможно.
В тёмном ящике перемешаны десять чёрных и десять белых носков. Сколько носков нужно вытащить не глядя, чтобы среди них наверняка нашлась пара одного цвета?
Цвета — это ящики, их два. Три носка по двум ящикам: в каком-то окажутся два. А вот чтобы наверняка вытащить пару именно чёрных, понадобится $12$ носков.
Ещё одно пари, которое пригодится в следующей главе.
В любой компании из двух и более человек найдутся двое, у которых внутри этой компании одинаковое число знакомых.
Пусть людей $n$. Знакомых в компании у каждого от $0$ до $n - 1$: это $n$ возможных чисел, $n$ ящиков — как раз по числу людей, так что принцип Дирихле напрямую не срабатывает. Но ящики «$0$» и «$n - 1$» не могут быть заняты одновременно: если кто-то знаком со всеми остальными, то каждый знаком хотя бы с ним, и ни у кого нет нуля знакомых. Значит, занято не больше $n - 1$ ящиков, а людей $n$. По принципу Дирихле двое оказались в одном ящике: у них одинаковое число знакомых.
Тринадцать
В 1708 году французский математик Пьер Ремон де Монмор разобрал в своей книге об азартных играх карточную игру «Тринадцать». Банкомёт открывает карты одной масти по одной и вслух считает: «туз, два, три, …, король». Если хоть раз открытая карта совпадёт с названной, выигрывает банкомёт. Если за тринадцать карт совпадений не было — выигрывает игрок. Кому выгодна игра?
Та же задача в гардеробе: $n$ гостей сдали шляпы, а гардеробщик возвращает их наугад. Какова вероятность, что никто не получил свою шляпу? Чтобы ответить, нужно научиться вычитать пересечения.
Начнём с разминки. Сколько чисел от $1$ до $100$ делятся на $2$, на $3$ или на $5$? Чётных $50$, кратных трём $33$, кратных пяти $20$. Но в сумме $50 + 33 + 20 = 103$ числа вроде $6$ посчитаны дважды, а число $30$ даже трижды. Вычтем кратные шести ($16$), десяти ($10$) и пятнадцати ($6$): получится $71$. Однако числа, кратные тридцати, мы сначала трижды прибавили, а потом трижды вычли — они пропали. Вернём их: $71 + 3 = 74$.
Формула включений и исключений считает, сколько предметов попало хотя бы в одну из нескольких групп: сложить размеры групп, вычесть попарные пересечения, прибавить тройные, вычесть четверные — и так далее, чередуя знаки.
Для любых трёх конечных групп $A$, $B$, $C$
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.$$Здесь $|X|$ — число предметов в группе $X$, $A \cup B$ — все, кто хотя бы в одной из групп, $A \cap B$ — те, кто сразу в обеих.
Круги $A$, $B$, $C$ делят всех, кто в них попал, на семь частей. Посчитаем, сколько раз каждый предмет учтён в сумме $|A| + |B| + |C|$: предмет из одного круга — один раз, из двух кругов — два раза, из всех трёх — три раза. Эти числа написаны на рисунке.
Вычтем $|A \cap B| + |A \cap C| + |B \cap C|$. Предмет, лежащий ровно в двух кругах, входит ровно в одно из этих пересечений: было $2$, стало $1$. Предмет из всех трёх кругов входит во все три пересечения: было $3$, стало $0$. Предметов из одного круга вычитание не касается.
Прибавим $|A \cap B \cap C|$. Это касается только центральной части: было $0$, стало $1$.
Теперь каждый предмет, попавший хотя бы в один круг, учтён ровно один раз, а предметы вне кругов — ни разу. Значит, правая часть равна $|A \cup B \cup C|$.
Теперь шляпы. Нам нужно сосчитать перестановки, при которых никто не получил свою шляпу.
Беспорядок — перестановка, в которой ни один предмет не остался на своём месте. Число беспорядков из $n$ предметов обозначают $D_n$.
$D_n = n! \left(1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \dfrac{1}{3!} + \ldots + \dfrac{(-1)^n}{n!}\right)$.
Идея: проверить, сколько раз правая часть учитывает каждую перестановку, и убедиться, что беспорядки она учитывает по одному разу, а остальные перестановки — ни разу.
Раскроем скобку: правая часть равна $\sum_{j = 0}^{n} (-1)^j \frac{n!}{j!}$, а $\frac{n!}{j!} = \binom{n}{j}(n - j)!$. Число $\binom{n}{j}(n - j)!$ считает пары «набор из $j$ гостей и перестановка, в которой каждый из них получил свою шляпу»: набор выбираем $\binom{n}{j}$ способами, выбранным отдаём их шляпы, а остальные $n - j$ шляп раздаём как угодно — $(n - j)!$ способами.
Возьмём перестановку, в которой свою шляпу получили ровно $m$ гостей. В $j$-м слагаемом она учтена столько раз, сколько у неё наборов из $j$ гостей, получивших своё, — $\binom{m}{j}$ раз. Со знаками она учтена $\binom{m}{0} - \binom{m}{1} + \binom{m}{2} - \ldots + (-1)^m \binom{m}{m}$ раз. По биному Ньютона при $a = -1$, $b = 1$ эта сумма равна $(1 - 1)^m$, то есть $0$ при $m \ge 1$ и $1$ при $m = 0$. Значит, правая часть считает ровно те перестановки, где совпадений нет, по одному разу: это $D_n$.
Разделим на $n!$ и получим вероятность, что никто не получил свою шляпу: $1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \ldots$ Если продолжать этот ряд без конца, он сходится к $\frac{1}{e} \approx 0{,}3679$, где $e \approx 2{,}718$ — то самое число из главы об экспоненте. Уже при шести гостях вероятность отличается от предела меньше чем на одну тысячную. Число гостей почти ничего не меняет: у шестерых, у тринадцати и у тысячи шанс «никто не получил своё» около $37\,\%$.
Так что игра «Тринадцать» выгодна банкомёту: он выигрывает с вероятностью $1 - \frac{D_{13}}{13!} \approx 0{,}632$, почти в двух случаях из трёх. Монмор нашёл общий ответ к 1713 году, во втором издании книги, вместе с Николаем Бернулли.
Скобки и торт
У старого калькулятора есть странность: он умеет перемножать только два числа за раз. Чтобы вычислить $a \cdot b \cdot c \cdot d$, ему нужно указать порядок скобками. Вариантов пять: $((ab)c)d$, $(a(bc))d$, $(ab)(cd)$, $a((bc)d)$, $a(b(cd))$. Для пяти множителей вариантов $14$, для шести $42$.
За соседним столом режут торт в форме правильного шестиугольника. Резать можно только по диагоналям, от угла к углу, так чтобы разрезы не пересекались, и в итоге получились одни треугольники. Сколько способов? Тоже $14$. Совпадение не случайно.
Числа Каталана $C_0, C_1, C_2, \ldots = 1, 1, 2, 5, 14, 42, 132, 429, \ldots$ считают расстановки скобок в произведении $n + 1$ множителей и разрезания выпуклого $(n + 2)$-угольника на треугольники. (У буквы здесь один индекс; не путайте с $C_n^k$.)
Правильных слов из $n$ открывающих и $n$ закрывающих скобок (в которых каждая скобка закрывается после того, как открылась) ровно $\dfrac{1}{n + 1}\dbinom{2n}{n}$.
Запишем слово как ломаную: «(» — шаг вверх, «)» — шаг вниз. Слово правильное ровно тогда, когда ломаная из $2n$ шагов, начав на уровне $0$, ни разу не опускается ниже нуля (иначе какая-то «)» закрывает то, что не открывалось) и кончается на нуле. Всего ломаных с $n$ шагами вверх и $n$ вниз $\binom{2n}{n}$: столько способов выбрать места для «(».
Плохая ломаная хоть раз опускается ниже нуля, то есть касается уровня $-1$. Отметим первое такое касание.
Отразим часть ломаной после первого касания относительно уровня $-1$: каждый шаг вверх станет шагом вниз и наоборот. Раньше ломаная кончалась на $1$ выше линии $-1$, теперь кончается на $1$ ниже — на уровне $-2$. В ней стало $n - 1$ шагов вверх и $n + 1$ вниз.
Обратно, любая ломаная с $n - 1$ шагами вверх и $n + 1$ вниз кончается на уровне $-2$, а значит, по дороге обязательно касается уровня $-1$. Отразив её хвост после первого касания, получим плохую ломаную, и это действие отменяет предыдущее. Поэтому плохих ломаных столько же, сколько ломаных с концом на $-2$: $\binom{2n}{n + 1}$. При $n = 4$ всего ломаных $70$, плохих $56$, хороших $14$.
Хороших ломаных $\binom{2n}{n} - \binom{2n}{n + 1}$. Сравнив факториалы, видим $\binom{2n}{n + 1} = \frac{(2n)!}{(n + 1)!\,(n - 1)!} = \binom{2n}{n} \cdot \frac{n}{n + 1}$, поэтому хороших $\binom{2n}{n}\left(1 - \frac{n}{n + 1}\right) = \frac{1}{n + 1}\binom{2n}{n}$.
Расстановок скобок в произведении $n + 1$ множителей, разрезаний выпуклого $(n + 2)$-угольника на треугольники и правильных слов из $n$ пар скобок одинаково много — по $C_n$.
Идея: все три семейства собираются из меньших по одному и тому же правилу. Обозначим их размеры через $P_n$, $T_n$ и $W_n$ и положим $P_0 = T_0 = W_0 = 1$: один множитель, «двуугольник» (просто отрезок) и пустое слово устроены единственным образом. Покажем, что каждая из трёх последовательностей удовлетворяет правилу $X_{n + 1} = X_0 X_n + X_1 X_{n - 1} + \ldots + X_n X_0$. Тогда они совпадают: начальные значения равны, а каждое следующее одинаково вычисляется из предыдущих.
Скобки. В произведении $n + 2$ множителей последнее умножение перемножает левую часть из $i + 1$ множителей на правую из $n + 1 - i$, где $i$ от $0$ до $n$. Скобки внутри частей расставляются независимо, поэтому при данном $i$ вариантов $P_i \cdot P_{n - i}$ (правило произведения), а всего — сумма по $i$ (правило суммы).
Разрезания. Опустим одну сторону $(n + 3)$-угольника вниз. Над ней стоит ровно один треугольник разрезания: сторона принадлежит ровно одному треугольнику. Его верхняя вершина делит остаток на левый многоугольник с $i + 2$ вершинами и правый с $n + 2 - i$ вершинами, и они режутся независимо: $T_i \cdot T_{n - i}$ вариантов. Если подписать стороны, кроме нижней, буквами, этот треугольник и есть последнее умножение «(всё слева) · (всё справа)» — именно это соответствие показывает виджет.
Слова. В правильном слове из $n + 1$ пар первая «(» закрывается какой-то «)». Между ними стоит правильное слово $X$ из $i$ пар, после — правильное слово $Y$ из $n - i$ пар: всё слово имеет вид «( $X$ ) $Y$». Слова $X$ и $Y$ выбираются независимо: $W_i \cdot W_{n - i}$ вариантов.
Шесть гостей
Последняя игра вечера — о самих гостях. Возьмём любых шестерых. Утверждается, что среди них обязательно найдутся трое, попарно знакомые друг с другом, или трое, попарно незнакомые. Каких бы гостей вы ни пригласили.
Среди любых шести человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых. Для пяти человек это уже неверно.
Нарисуем гостей точками и соединим каждую пару отрезком: оранжевым, если они знакомы, синим, если нет. Возьмём одного гостя, Аню. От неё идут пять отрезков двух цветов, и по принципу Дирихле (пять отрезков, два цвета, $5 / 2 > 2$) хотя бы три из них одного цвета. Пусть это оранжевые отрезки к Боре, Вике и Гоше; если одинаковых синих, рассуждение то же с заменой цветов.
Посмотрим на три отрезка между Борей, Викой и Гошей. Если хотя бы один из них оранжевый — скажем, Боря–Вика, — то Аня, Боря и Вика попарно знакомы: оранжевый треугольник.
Если же ни один из них не оранжевый, то все три синие: Боря, Вика и Гоша попарно незнакомы — синий треугольник. Третьего не дано, поэтому одноцветный треугольник найдётся всегда.
Для пяти человек утверждение неверно. Рассадим их за круглым столом, и пусть знакомы только соседи. Знакомства образуют оранжевый пятиугольник, незнакомства — синюю пятиконечную звезду, и ни в одной из этих фигур нет треугольника.
Это частный случай теоремы, которую доказал английский математик Фрэнк Рамсей. Статья вышла в 1930 году, в год его ранней смерти: Рамсею было двадцать шесть.
Число Рамсея $R(m, n)$ — наименьшее число людей, среди которых обязательно найдутся $m$ попарно знакомых или $n$ попарно незнакомых. Мы только что доказали, что $R(3, 3) = 6$. Но почему такое число вообще существует для любых $m$ и $n$?
Для любых натуральных $m$ и $n$ число $R(m, n)$ существует, и $R(m, n) \le R(m - 1, n) + R(m, n - 1)$.
Идея та же, что с шестью гостями: выбрать одного человека и разделить остальных на его знакомых и незнакомых. Доказываем индукцией по $m + n$ (о ней — в главе о последовательностях). База: если $m = 1$ или $n = 1$, то $R = 1$ — один человек уже образует «группу из одного».
Шаг. Пусть $m, n \ge 2$ и для пар $(m - 1, n)$ и $(m, n - 1)$ числа $A = R(m - 1, n)$ и $B = R(m, n - 1)$ уже существуют. Возьмём компанию из $A + B$ человек и выберем в ней Аню. Остальные $A + B - 1$ человек делятся на её знакомых и незнакомых. Знакомых хотя бы $A$ или незнакомых хотя бы $B$: иначе всего было бы не больше $(A - 1) + (B - 1) = A + B - 2$ человек (принцип Дирихле).
Если знакомых Ани не меньше $A$, среди них есть $m - 1$ попарно знакомых — тогда вместе с Аней их $m$ — или $n$ попарно незнакомых, и в обоих случаях всё доказано. Если незнакомых не меньше $B$, среди них есть $m$ попарно знакомых или $n - 1$ попарно незнакомых — и вместе с Аней их $n$. Значит, в любой компании из $A + B$ человек нужная группа есть, и $R(m, n) \le A + B$; взяв $A = R(m - 1, n)$ и $B = R(m, n - 1)$, получаем неравенство теоремы. Для $m = n = 3$: $R(2, 3) = 3$ (среди трёх человек либо какие-то двое знакомы, либо все трое попарно незнакомы), так что $R(3, 3) \le 3 + 3 = 6$ — ровно то, что показала задача о гостях.
На основе этой теоремы в 1969 году американский криптограф Густавус Симмонс придумал игру для двоих, которую назвал Sim. Шесть точек, пятнадцать отрезков. Игроки по очереди красят отрезки, каждый своим цветом, и кто первым замкнёт треугольник своего цвета, тот проиграл. Ничьей не бывает: когда отрезки кончатся, одноцветный треугольник обязательно будет, а значит, кто-то замкнул его раньше.
В 1974 году перебор на компьютере показал, что при безошибочной игре Sim всегда выигрывает тот, кто ходит вторым. Но запомнить его стратегию человеку не под силу, поэтому играть интересно.
Точные значения чисел Рамсея известны лишь для совсем маленьких компаний. $R(4, 4) = 18$ установили в 1955 году. Про $R(5, 5)$ до сих пор известно только, что оно не меньше $43$ и не больше $46$; верхнюю оценку доказали в 2024 году с помощью огромного компьютерного перебора. Пал Эрдёш, по рассказу его соавтора Джоэла Спенсера, шутил так: если инопланетяне потребуют назвать $R(5, 5)$ под угрозой уничтожения Земли, нужно бросить на задачу все компьютеры и всех математиков. А если потребуют $R(6, 6)$, разумнее попытаться уничтожить инопланетян.
Комбинаторика умеет не только считать варианты, но и доказывать, что нужный вариант обязательно найдётся. В достаточно большой системе полного беспорядка не бывает: какой-то порядок в ней возникает сам собой.
Куда дальше
После вечера гости выходят прогуляться. Город Кёнигсберг XVIII века стоял на реке Прегель, которая огибала два острова. Берега и острова соединяли семь мостов. Горожане любили задачу: пройти по городу так, чтобы по каждому мосту пройти ровно один раз.
Маршрутов, в которых мосты идут в разном порядке, конечное число, и их можно перебрать: мы теперь умеем считать. Но перебор ничего не объяснит, а задача требует объяснения: почему не получается и как быть с другим городом, где мостов тридцать. Леонард Эйлер нашёл ответ, для которого не нужно перебирать ничего. Для этого ему пришлось забыть о расстояниях, форме берегов и ширине реки и оставить только точки и связи между ними, как мы сделали с шестью гостями. Так появились графы — о них следующая глава.