combinatorics.md

Ликбез по комбинаторике

Статья не затрагивает теоирию чисел и линейную алгебру.

Воможно, поможет почитать про нахождение обратного.

[Конкретная математика](http://sereja.me/f/discrete_math_knuth.pdf Грэхэма, Кнута и Паташика.

Рекуррентные задачи

Ханойские башни

123

Задача Иосифа

Иосиф Флавий (лат. Flavius Josephus) — знаменитый историк первого векf. По легенде, он бы не дожил до известности если бы не его математические способности.

Во время еврейсDuring the Jewish-Roman war, he was among a band of 41 Jewish rebels trapped in a cave by the Romans. Preferring suicide to capture, the rebels decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. But Josephus, along with an unindicted co-conspirator, wanted none of this suicide nonsense; so he quickly calculated where he and his friend should stand in the vicious circle.

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

В англоязычном мире называется Pigeonhole principle и говорит о голубях, но суть не меняется.

Принцип кажется очевидным, однако его применение очевидно не всегда. Рассмотрим несколько примеров.

Задача. Дан квадрат $2 \times 2$ и $5$ точек внутри него. Доказать, что среди них найдется две такие, что расстояние между ними $\leq \sqrt 2$.

Решение. Рассмотрим $4$ квадратика $1 \times 1$. По принципу Дирихле найдётся квадратик, внутри или на границе которого 2 точки. Эти точки — искомые.

Примеры посложнее:

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

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

• Пример из реального мира: любой алгоритм сжатия без потери данных не может гарантировать сжатие для всех возможных входных файлов.

Задача про покемонов.

Бином Ньютона

Поли=много, Би=два. nomen = название.

$$ (a + b)^n $$

Коэффициенты при разложении имеют огромную роль в комбинаторике.

В России их обозначают как , во всем остальном мире — как .

Сильно раздражает, что нет даже единого мнения, где $n$, а где $k$.

Биномиальные коэффициенты

Алгоритм Евклида

Решето

Треугольник Паскаля

Можно заметить

Сочетания

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

Соответственно, если элементы могут повторяться, то набор называется размещением без повторений, или просто размещением.

Сочетанием из $n$ элементов по $k$ называется набор $k$ элементов этого множества, при том что наборы, отличающиеся только порядком следования элементов, считаются одинаковыми (этим сочетание отличается от размещения).

Аналогично, сочетания бывают с повторениями и без.

Читается как «цэ из $n$ по $k$».

Как это считать

int t[maxn];

int bp (int a, int n) {
    int ans = 1;
    while (n) {
        if (n&1) ans = ans*a % mod;
        a = a*a % mod;
        n >>= 1;
    }
    return ans;
}

int inv (int x) {
    return bp(x, mod-2);
}

int c (int n, int k) {
    return t[n]*inv(t[k]) % mod * inv(t[n-k]) % mod;
}

t[0] = 1;
for (int i = 1; i < maxn; i++)
    t[i] = i*t[i-1] % mod;

Разложения

Шары и перегородки.

Автор не запоминает эту формулу и не пытается проделать алгебру в уме, а просто определяет вспомогательную функцию:

int d(int n, int k) {
    return c(n + k - 1, k - 1);
}

Известные равенства

$$ \sum_k \binom{r}{m+k}\binom{s}{n-k} = \binom{r+s}{m+n} $$

$$ \sum_k \binom{l}{m+k} \binom{s}{n+k} = \binom{l+s}{l-m+n} $$

$$ \sum_k \binom{l}{m+k}\binom{s+k}{n} (-1)^k = (-1)^{l+m} \binom{s-m}{n-l} $$

$$ \sum_{k \leq l} \binom{l-k}{m}\binom{s}{k-n} (-1)^k = (-1)^{l+m} \binom{s-m-l}{l-m-n} $$

$$ \sum_{0 \leq k \leq l} \binom{l-k}{m}\binom{q+k}{n} = \binom{l+q+1}{m+n+1} $$

Hockey stick identity

«Равенство хоккейной клюшки».

Правильные скобочные последовательности

Диаграмма Юнга

Числа Каталана

Числа Каталана — числовая последовательность, встречающаяся в удивительном числе комбинаторных задач. Например, $n$-ное число Каталана равно числу:

• …корректных скобочных последовательностей, состоящих из $n$ открывающих и $n$ закрывающих скобок.

• …корневых бинарных деревьев с n+1 листьями (если вершины не пронумерованы).

• …разбиений выпуклого многоугольника непересекающимися диагоналями на треугольники $(n+2)$-угольника (это называется триангуляцией).

• …способов соединить $2n$ точек на окружности $n$ непересекающимися хордами.

• …разбиений отрезка из $n$ элементов на непрерывные блоки.

• …путей из точки $(0,0)$ в точку $(n,n)$ в квадратной решётке размером $n \times n$, не поднимающихся над главной диагональю.

Первые несколько чисел Каталана, начиная с нулевого:

$$ 1, 1, 2, 5, 14, 42, 132, 429, 1430, … $$

Числа Каталана можно считать квадратичной динамикой. Пусть $k$-тое число Каталана, $C_k$, равно количеству правильных скобочных последовательностей длины $2k$, то есть из $k$ пар скобок. Последовательность начинается с открывающей скобки, и этой скобке соответствует какая-то закрывающая. Можно перебрать её место (все нечетные при нумерации с нуля позиции), и для каждого варианта последовательность разделится на две правильные скобочные последовательности — до закрывающей скобки (из $k$ пар скобок) и после (из $(n-1-k)$ пар).

Получается следующая рекуррентная формула:

$$ C_n = \sum_{k = 0}^{n-1} C_k C_{n-1-k} $$

Аналитическая формула

Но не нужно, потому что есть аналитическая формула, которую мы сейчас докажем:

$$ C_n = \dfrac{1}{n+1} \dbinom {2n} {n} $$

Эту формулу проще всего вывести из задачи о монотонных путях —. Общее количество монотонных путей в решётке размером n \times n равно C_{2n}^{n}. Теперь посчитаем количество монотонных путей, пересекающих диагональ. Рассмотрим какой-либо из таких путей, и найдём первое ребро, которое стоит выше диагонали. Отразим относительно диагонали весь путь, идущий после этого ребра. В результате получим монотонный путь в решётке (n-1) \times (n+1). Но, с другой стороны, любой монотонный путь в решётке (n-1) \times (n+1) обязательно пересекает диагональ, следовательно, он получен как раз таким способом из какого-либо (причём единственного) монотонного пути, пересекающего диагональ, в решётке n \times n. Монотонных путей в решётке (n-1) \times (n+1) имеется C_{2n}^{n-1}. В результате получаем формулу:

Все $C_4 = 14$ путей на квадрате $4 \times 4$:

$$ C_n = C_{2n}^{n} - C_{2n}^{n-1} = \frac{1}{n+1} C[...] $$

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

Перестановки как граф

Граф, у которого

Наибольшая общая подпоследовательность двух перестановок.

Ничего не мешает нам переименовать объекты так, что в первой они будут идти по порядку.

Генерация комбинаторных объектов

Обратная задача

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

Принцип включений-исключений

Это бывает полезно при подсчете площадей многомерных фигур через префиксные суммы.

Куда дальше, или полезные незатронутые темы

Если вам зачем-то понадобилось.

Лемма бернсайда.

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

Линейные рекурренты.

Теория чисел.

Частично упорядоченные множества и теорема Дилуорса.

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

Разные отдельные факты на границе комбинаторики и теории графов.

Комбинаторика, которая находится на границе с теорией вероятностей.