Я много лет читаю курсы по комбинаторике и графам для студентов-математиков и computer scientists (как это по-русски, компьютерных научников?), раньше в Академическом университете, а теперь в СПбГУ. Программа у нас построена так, что эти темы проходят как часть «теоретической информатики» (другие темы в ней — алгоритмы, сложность, языки и грамматики). Не могу сказать, насколько это оправдано метафизически или исторически: всё же комбинаторные объекты (графы, системы множеств, перестановки, клетчатые фигуры и др.) начали изучали задолго до появления компьютеров, и сейчас последние хотя и важная, но далеко не единственная причина интереса к ним. Но так посмотреть на самых спецов по комбинаторике и по theoretical computer science — это удивительно часто одни и те же люди: Ловас, Алон, Семереди, Разборов и далее. Наверно, есть на то свои причины. На моих уроках часто очень нетривиальные решения сложных задач предлагают чемпионы олимпиадного программирования (их перечислять не буду, кому любопытно посмотрите топ codeforces.) В общем, думаю, что некоторые вещи из комбинаторики могут быть интересны сообществу. Говорите, если что так или не так.
Пусть вам надо построить случайную перестановку чисел от 1 до , чтобы все перестановки были равновероятны. Это можно сделать многими способами: например, сначала выбрать случайно первый элемент, потом из оставшихся второй и так далее. А можно поступить иначе: выбрать случайно точки в отрезке , и посмотреть как они упорядочены. Заменяя наименьшее из чисел на 1, второе на 2 и так далее получаем случайную перестановку. Легко видеть, что все перестановок равновероятны. Можно и не в отрезке выбирать точки, а, например, среди чисел от 1 до . Тут возможны совпадения (для отрезка тоже возможны, но с нулевой вероятностью, так что нас они не волнуют) — с ними можно бороться по-разному, например, дополнительно переупорядочивая совпадающие числа. Или взять N побольше, чтобы вероятность совпадения была маленькой (хорошо известен случай, когда , а есть число учеников в вашем классе, и речь о совпадении двух дней рождения.) Вариация этого метода: отметить случайно точек в единичном квадрате и посмотреть, как упорядочены их ординаты относительно абсцисс. Другая вариация: отметить в отрезке точку и посмотреть, как упорядочены длины отрезочков, на которые он разбился. Ключевой момент в этих подходах — независимость испытаний, по результатам которых строится случайная перестановка. Андрей Николаевич Колмогоров говорил, что теория вероятностей это теория меры плюс независимость — и это подтвердит всякий кто имел дело с вероятностью.
Покажу, как это помогает, на примере формулы крюков для деревьев:
Пусть — подвешенное за корень дерево с вершинами, растущее вниз как на картинке. Наша цель — вычислить число нумераций вершин дерева числами от 1 до таких, что для каждого ребра число в его верхней вершине больше чем в нижней. Одна из таких нумераций приведена на средней картинке. Ответ формулируется с помощью размеров крюков . Крюком вершины назовём поддерево, растущее из этой вершины, а его размером просто число вершин в нём. Длины крюков написаны на правой картинке рядом с соответствующими вершинами. Так вот, число нумераций равно делить на произведение размеров крюков, так для нашего примера
Можно доказывать ту формулу по-разному, например индукцией по числу вершин, но наш взгляд на случайные перестановки позволяет провести доказательство вообще без вычислений. Оно лучше не только элегантностью, но и тем что хорошо обобщается на более тонкие вопросы о нумерациях с предписанными неравенствами, но об этом не сейчас. Так вот, возьмём n различных вещественных чисел и расставим их случайно в вершины дерева, в каждую по одному числу, все перестановок равновероятны. Какова вероятность того, что для каждого ребра число в верхней вершине ребра больше числа в его нижней вершине? Ответ: , и от набора чисел он не зависит. А раз не зависит, то давайте считать числа тоже выбранными случайно — для определённости, в отрезке . Вместо того, чтобы сначала случайно выбирать числа, а потом случайно расставлять их в вершины дерева, мы можем просто случайно и независимо выбрать число в каждой вершине: их перестановка окажется случайной автоматически. Таким образом, это вероятность того, что для случайных независимых чисел , выбранных по одному для каждой вершины дерева , выполняются все неравенства вида для всех рёбер , — верхняя вершина ребра, а — нижняя. Сформулируем эти условия в равносильном виде, но немного иначе: для каждой вершины должно происходить такое событие — обозначу его
: число — максимальное среди всех чисел в вершинах поддерева-крюка .
Заметим, что это вероятность события . В самом деле, в крюке имеется вершин и максимальное по крюку число сопоставлено каждой из них с равной вероятностью . Таким образом, формула крюков может быть сформулировано так: вероятность того, что происходят сразу все события , равна произведению вероятностей этих событий. Причин на то может быть много разных, но тут работает первая, приходящая в голову: эти события независимы. Чтобы это понять, посмотрим, например, на событие (соответствующее корню). Оно состоит в том, что число в корне больше всех остальных чисел в вершинах, а прочие события касаются сравнений между собой чисел, написанных не в корне. То есть касается числа и множества чисел в остальных вершинах, а все остальные события — порядка чисел в вершинах, отличных от корня. Как мы уже обсуждали, «порядок» и «множество» независимы, поэтому событие не зависит от прочих. Спускаясь далее по дереву, получим, что все эти события независимы, откуда и следует требуемое.
Обычно формулой крюков называют формулу для нумераций не вершин в дереве, а клеток в диаграмме Юнга
, возрастающих в направлениях координатных осей, и крюки там больше похоже на крюки чем для деревьев. Но эта формула доказывается сложнее и заслуживает отдельного поста.
Раз уж пришлось к слову, не могу не рассказать о модели случайной диаграммы Юнга. Диаграмма Юнга это вот такая фигура из единичных квадратиков, длины её строк возрастают снизу вверх, а длины столбцов слева направо. Количество диаграмм Юнга площади обозначается , эта важная функция ведёт себя интересно и необычно: например, она растёт быстрее любого многочлена, но медленнее любой экспоненты. Поэтому, в частности, генерировать случайную диаграмму Юнга (если мы хотим, чтобы все диаграммы площади имели равную вероятность ) дело нетривиальное. Например, если добавлять клеточки по одной, выбирая место добавления случайно, разные диаграммы будут иметь разные вероятности (так, вероятность однострочечной диаграммы получается равной .) Выходит занимательная мера на диаграммах, но не равномерная. Равномерную можно получить так. Возьмём число , для наших целей лучше всего годятся числа в районе . Для каждого
рассмотрим геометрическое распределение на целых неотрицательных числах со средним (то есть вероятность числа равна ). Выберем согласно нему случайную величину (есть много способов как это организовать). При больших скорее всего 0. Посмотрим на диаграмму Юнга, в которой строк имеют длину при каждом . Я называю это методом кораблей, потому что общая площадь иногда равна . Если не равна, то повторяем эксперимент. На самом деле равна она достаточно часто, если умно выбрать . Предлагаю читателю самостоятельно доказать, что все диаграммы данной площади равновероятны и оценить число шагов.
Пусть вам надо построить случайную перестановку чисел от 1 до , чтобы все перестановки были равновероятны. Это можно сделать многими способами: например, сначала выбрать случайно первый элемент, потом из оставшихся второй и так далее. А можно поступить иначе: выбрать случайно точки в отрезке , и посмотреть как они упорядочены. Заменяя наименьшее из чисел на 1, второе на 2 и так далее получаем случайную перестановку. Легко видеть, что все перестановок равновероятны. Можно и не в отрезке выбирать точки, а, например, среди чисел от 1 до . Тут возможны совпадения (для отрезка тоже возможны, но с нулевой вероятностью, так что нас они не волнуют) — с ними можно бороться по-разному, например, дополнительно переупорядочивая совпадающие числа. Или взять N побольше, чтобы вероятность совпадения была маленькой (хорошо известен случай, когда , а есть число учеников в вашем классе, и речь о совпадении двух дней рождения.) Вариация этого метода: отметить случайно точек в единичном квадрате и посмотреть, как упорядочены их ординаты относительно абсцисс. Другая вариация: отметить в отрезке точку и посмотреть, как упорядочены длины отрезочков, на которые он разбился. Ключевой момент в этих подходах — независимость испытаний, по результатам которых строится случайная перестановка. Андрей Николаевич Колмогоров говорил, что теория вероятностей это теория меры плюс независимость — и это подтвердит всякий кто имел дело с вероятностью.
Покажу, как это помогает, на примере формулы крюков для деревьев:
Пусть — подвешенное за корень дерево с вершинами, растущее вниз как на картинке. Наша цель — вычислить число нумераций вершин дерева числами от 1 до таких, что для каждого ребра число в его верхней вершине больше чем в нижней. Одна из таких нумераций приведена на средней картинке. Ответ формулируется с помощью размеров крюков . Крюком вершины назовём поддерево, растущее из этой вершины, а его размером просто число вершин в нём. Длины крюков написаны на правой картинке рядом с соответствующими вершинами. Так вот, число нумераций равно делить на произведение размеров крюков, так для нашего примера
Можно доказывать ту формулу по-разному, например индукцией по числу вершин, но наш взгляд на случайные перестановки позволяет провести доказательство вообще без вычислений. Оно лучше не только элегантностью, но и тем что хорошо обобщается на более тонкие вопросы о нумерациях с предписанными неравенствами, но об этом не сейчас. Так вот, возьмём n различных вещественных чисел и расставим их случайно в вершины дерева, в каждую по одному числу, все перестановок равновероятны. Какова вероятность того, что для каждого ребра число в верхней вершине ребра больше числа в его нижней вершине? Ответ: , и от набора чисел он не зависит. А раз не зависит, то давайте считать числа тоже выбранными случайно — для определённости, в отрезке . Вместо того, чтобы сначала случайно выбирать числа, а потом случайно расставлять их в вершины дерева, мы можем просто случайно и независимо выбрать число в каждой вершине: их перестановка окажется случайной автоматически. Таким образом, это вероятность того, что для случайных независимых чисел , выбранных по одному для каждой вершины дерева , выполняются все неравенства вида для всех рёбер , — верхняя вершина ребра, а — нижняя. Сформулируем эти условия в равносильном виде, но немного иначе: для каждой вершины должно происходить такое событие — обозначу его
: число — максимальное среди всех чисел в вершинах поддерева-крюка .
Заметим, что это вероятность события . В самом деле, в крюке имеется вершин и максимальное по крюку число сопоставлено каждой из них с равной вероятностью . Таким образом, формула крюков может быть сформулировано так: вероятность того, что происходят сразу все события , равна произведению вероятностей этих событий. Причин на то может быть много разных, но тут работает первая, приходящая в голову: эти события независимы. Чтобы это понять, посмотрим, например, на событие (соответствующее корню). Оно состоит в том, что число в корне больше всех остальных чисел в вершинах, а прочие события касаются сравнений между собой чисел, написанных не в корне. То есть касается числа и множества чисел в остальных вершинах, а все остальные события — порядка чисел в вершинах, отличных от корня. Как мы уже обсуждали, «порядок» и «множество» независимы, поэтому событие не зависит от прочих. Спускаясь далее по дереву, получим, что все эти события независимы, откуда и следует требуемое.
Обычно формулой крюков называют формулу для нумераций не вершин в дереве, а клеток в диаграмме Юнга
, возрастающих в направлениях координатных осей, и крюки там больше похоже на крюки чем для деревьев. Но эта формула доказывается сложнее и заслуживает отдельного поста.Раз уж пришлось к слову, не могу не рассказать о модели случайной диаграммы Юнга. Диаграмма Юнга это вот такая фигура из единичных квадратиков, длины её строк возрастают снизу вверх, а длины столбцов слева направо. Количество диаграмм Юнга площади обозначается , эта важная функция ведёт себя интересно и необычно: например, она растёт быстрее любого многочлена, но медленнее любой экспоненты. Поэтому, в частности, генерировать случайную диаграмму Юнга (если мы хотим, чтобы все диаграммы площади имели равную вероятность ) дело нетривиальное. Например, если добавлять клеточки по одной, выбирая место добавления случайно, разные диаграммы будут иметь разные вероятности (так, вероятность однострочечной диаграммы получается равной .) Выходит занимательная мера на диаграммах, но не равномерная. Равномерную можно получить так. Возьмём число , для наших целей лучше всего годятся числа в районе . Для каждого
рассмотрим геометрическое распределение на целых неотрицательных числах со средним (то есть вероятность числа равна ). Выберем согласно нему случайную величину (есть много способов как это организовать). При больших скорее всего 0. Посмотрим на диаграмму Юнга, в которой строк имеют длину при каждом . Я называю это методом кораблей, потому что общая площадь иногда равна . Если не равна, то повторяем эксперимент. На самом деле равна она достаточно часто, если умно выбрать . Предлагаю читателю самостоятельно доказать, что все диаграммы данной площади равновероятны и оценить число шагов.
