Введение

Комбинаторика — это раздел дискретной математики, в основном занимающийся подсчетом, как средством, так и целью получения результатов, а также определенными свойствами конечных структур. Она тесно связана со многими другими областями математики и имеет широкое применение, от логики до статистической физики, от эволюционной биологии до информатики. Комбинаторика известна широтой решаемых ею задач. Комбинаторные задачи возникают во многих областях чистой математики, в частности в алгебре, теории вероятностей, топологии и геометрии, а также в многочисленных областях её применения. Многие комбинаторные вопросы исторически рассматривались изолированно, приводя к ad hoc решению проблемы, возникающей в определенном математическом контексте. Однако во второй половине двадцатого века были разработаны мощные и общие теоретические методы, которые сделали комбинаторику самостоятельным разделом математики. Одной из старейших и наиболее доступных частей комбинаторики является теория графов, которая сама по себе имеет множество естественных связей с другими областями. Комбинаторика часто используется в информатике для получения формул и оценок при анализе алгоритмов. Математик, изучающий комбинаторику, называется комбинатором.

История

Основные комбинаторные понятия и результаты перечисления возникали на протяжении всей истории древнего мира. Индийский врач Сушрута утверждает в «Сушрута Самхите», что из 6 различных вкусов можно составить 63 комбинацию, беря их по одному, по два и так далее, таким образом вычисляя все 2<sup>6</sup> − 1 возможностей. Греческий историк Плутарх обсуждает спор между Хрисиппом (III век до н.э.) и Гиппархом (II век до н.э.) относительно довольно сложной задачи перечисления, которая позднее была связана с числами Шрёдера — Гиппарха. Ранее, в «Остомахионе», Архимед (III век до н.э.) мог рассматривать число конфигураций головоломки, состоящей из плоских фигур, а комбинаторные интересы, возможно, присутствовали в утерянных трудах Аполлония. В Средние века комбинаторика продолжала изучаться, преимущественно за пределами европейской цивилизации. Индийский математик Махавира (ок. 850 г.) привел формулы для числа перестановок и сочетаний, и эти формулы, возможно, были известны индийским математикам уже в VI веке н.э. Философ и астроном раввин Авраам ибн Эзра (ок. 1140 г.) установил симметрию биномиальных коэффициентов, а замкнутая формула была получена позднее талмудистом и математиком Леви бен Герсоном (более известным как Герсонид) в 1321 году. Арифметический треугольник — графическая схема, показывающая взаимосвязи между биномиальными коэффициентами — был представлен математиками в трактатах, датируемых X веком, и впоследствии стал известен как треугольник Паскаля. Позднее, в средневековой Англии, искусство перезвона (кампанология) предоставило примеры того, что сейчас известно как гамильтоновы циклы в некоторых графах Кэли на перестановках. В эпоху Возрождения, вместе с остальной математикой и науками, комбинаторика пережила возрождение. Работы Паскаля, Ньютона, Якоба Бернулли и Эйлера стали основополагающими в формирующейся области. В наше время работы Дж. Дж. Сильвестра (конец XIX века) и Перси Макмаона (начало XX века) помогли заложить основу для перечислительной и алгебраической комбинаторики. Теория графов также вызвала повышенный интерес в то же время, особенно в связи с проблемой четырёх цветов. Во второй половине XX века комбинаторика пережила стремительный рост, что привело к созданию десятков новых журналов и конференций по этой тематике. Отчасти этот рост был обусловлен новыми связями и приложениями в других областях, начиная от алгебры до теории вероятностей, от функционального анализа до теории чисел и т.д. Эти связи размывают границы между комбинаторикой и различными разделами математики и теоретической информатики, но в то же время приводят к некоторой фрагментации области.

Численная комбинаторика

Перечислительная комбинаторика — наиболее классическая область комбинаторики, которая сосредоточена на подсчете числа определенных комбинаторных объектов. Хотя подсчет количества элементов в множестве является достаточно широкой математической задачей, многие задачи, возникающие в приложениях, имеют относительно простое комбинаторное описание. Числа Фибоначчи — это базовый пример задачи в перечислительной комбинаторике. Метод двенадцати способов предоставляет унифицированную основу для подсчета перестановок, сочетаний и разбиений.

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

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

Теория разделов

Теория разбиений изучает различные задачи перечисления и асимптотики, связанные с разбиениями целых чисел, и тесно связана с q-рядами, специальными функциями и ортогональными полиномами. Изначально являясь частью теории чисел и математического анализа, в настоящее время она рассматривается как часть комбинаторики или самостоятельная область. В ней используются биективный подход и разнообразные методы математического анализа и аналитической теории чисел, а также существуют связи со статистической механикой. Разбиения можно графически изображать с помощью диаграмм Янга или диаграмм Феррера. Они встречаются в различных областях математики и физики, включая изучение симметричных многочленов, симметрической группы и, в целом, теории представлений групп.

Теория графов

Графы — фундаментальные объекты в комбинаторике. Исследования в теории графов охватывают широкий спектр вопросов, от перечисления (например, количества графов на n вершинах с k ребрами) до изучения существующих структур (например, гамильтоновых циклов) и алгебраических представлений (например, для заданного графа G и двух чисел x и y, существует ли комбинаторная интерпретация полинома Тютте TG(x, y)?). Несмотря на тесную связь между теорией графов и комбинаторикой, их часто рассматривают как отдельные области. Комбинаторные методы применимы ко многим задачам теории графов, однако эти две дисциплины обычно используются для решения различных типов задач.

Теория дизайна

Теория проектирования — это изучение комбинаторных схем, представляющих собой наборы подмножеств с заданными свойствами пересечения. Блочные схемы являются комбинаторными схемами особого типа. Эта область — одна из старейших в комбинаторике, как, например, в задаче Киркмана о школьницах, предложенной в 1850 году. Решение этой задачи является частным случаем системы Штайнера, которая играет важную роль в классификации конечных простых групп. Данная область также связана с теорией кодирования и геометрической комбинаторикой. Теория комбинаторных схем может применяться в области планирования экспериментов. Основы теории комбинаторных схем берут начало в работах статистика Рональда Фишера по планированию биологических экспериментов. Современные применения также встречаются в широком спектре областей, включая конечную геометрию, составление расписаний турниров, лотереи, математическую химию, математическую биологию, разработку и анализ алгоритмов, сети, групповое тестирование и криптографию.

Конечная геометрия

Конечная геометрия — это изучение геометрических систем, содержащих лишь конечное число точек. Основными объектами исследования являются структуры, аналогичные тем, что встречаются в непрерывных геометриях (евклидовой плоскости, вещественном проективном пространстве и т.п.), но заданные комбинаторно. Эта область является богатым источником примеров для теории проектирования. Её не следует путать с дискретной геометрией (комбинаторной геометрией).

Теория порядка

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

Теория матроидов

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

Экстремальная комбинаторика

Экстремальная комбинаторика изучает, каким может быть максимальный или минимальный размер коллекции конечных объектов (чисел, графов, векторов, множеств и т. д.), если она должна удовлетворять определенным ограничениям. Значительная часть экстремальной комбинаторики посвящена классам систем множеств; это называется экстремальной теорией множеств. Например, в множестве из n элементов, каково наибольшее число k-элементных подмножеств, которые могут пересекаться попарно? Каково наибольшее число подмножеств, ни одно из которых не является подмножеством другого? Ответ на последний вопрос даёт теорема Спернера, которая послужила основой для развития экстремальной теории множеств. Типы вопросов, рассматриваемые в этом контексте, касаются наибольшего графа, удовлетворяющего заданным свойствам. Например, наибольший граф, не содержащий треугольников, на 2n вершинах – это полный двудольный граф Kn,n. Зачастую слишком сложно даже точно определить экстремальное значение f(n), и можно получить лишь асимптотическую оценку. Теория Рамсея – ещё одна область экстремальной комбинаторики. Она утверждает, что любая достаточно большая конфигурация будет содержать некоторую упорядоченность. Это развитое обобщение принципа Дирихле.

Вероятностная комбинаторика

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

Алгебраическая комбинаторика

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

Комбинаторика слов

Комбинаторика слов занимается формальными языками. Она возникла независимо в различных областях математики, включая теорию чисел, теорию групп и теорию вероятностей. Она находит применение в энумеративной комбинаторике, фрактальном анализе, теоретической информатике, теории автоматов и лингвистике. Хотя многие применения относительно новы, классическая иерархия Чомски — Шютценбергера классов формальных грамматик, пожалуй, является наиболее известным результатом в этой области.

Геометрическая комбинаторика

Геометрическая комбинаторика связана с выпуклой и дискретной геометрией. Она изучает, например, сколько граней каждой размерности может иметь выпуклый политоп. Метрические свойства политопов также играют важную роль, например, теорема Коши о жёсткости выпуклых политопов. Рассматриваются также специальные политопы, такие как пермутоэдры, ассоциаэдры и политопы Биркоффа. Комбинаторная геометрия – историческое название дискретной геометрии. Она включает в себя ряд областей, таких как полиэдрическая комбинаторика (изучение граней выпуклых полиэдров), выпуклая геометрия (изучение выпуклых множеств, в частности, комбинаторики их пересечений) и дискретная геометрия, которая, в свою очередь, имеет множество приложений в вычислительной геометрии. Изучение правильных политопов, архимедовых тел и чисел поцелуев также является частью геометрической комбинаторики. Рассматриваются также специальные политопы, такие как пермутоэдр, ассоциаэдр и политоп Биркоффа.

Топологическая комбинаторика

Комбинаторные аналоги понятий и методов топологии применяются для изучения раскраски графов, справедливого распределения, разбиений, частично упорядоченных множеств, деревьев решений, задач с бусами и дискретной теории Морса. Это не следует путать с комбинаторной топологией, которая является устаревшим названием алгебраической топологии.

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

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

Бесконечная комбинаторика

Бесконечная комбинаторика, или комбинаторная теория множеств, — это расширение идей комбинаторики на бесконечные множества. Она является частью теории множеств, области математической логики, но использует инструменты и идеи как из теории множеств, так и из экстремальной комбинаторики. Среди изучаемых вопросов — непрерывные графы и деревья, обобщения теоремы Рамсея и аксиома Мартина. Недавние достижения связаны с комбинаторикой континуума и комбинаторикой на преемниках сингулярных кардиналов. Джан Карло Рота использовал термин «непрерывная комбинаторика» для описания геометрической вероятности, поскольку существует множество аналогий между подсчетом и мерой.

Комбинаторная оптимизация

Комбинаторная оптимизация – это область, изучающая оптимизацию на дискретных и комбинаторных объектах. Возникнув как часть комбинаторики и теории графов, она теперь рассматривается как ветвь прикладной математики и информатики, тесно связанная с исследованиями операций, теорией алгоритмов и теорией вычислительной сложности.

Теория кодирования

Теория кодирования возникла как часть теории проектирования, с ранними комбинаторными построениями кодов, исправляющих ошибки. Главная идея этой области – разработка эффективных и надежных методов передачи данных. В настоящее время это обширная область исследований, являющаяся частью теории информации.

Дискретная и вычислительная геометрия

Дискретная геометрия (также называемая комбинаторной геометрией) возникла как часть комбинаторики, с первыми результатами, касающимися выпуклых многогранников и чисел касаний. С появлением применений дискретной геометрии в вычислительной геометрии эти две области частично объединились и сформировали отдельное направление исследований. Сохраняется множество связей с геометрической и топологической комбинаторикой, которые сами можно рассматривать как развитие ранней дискретной геометрии.

Комбинаторика и динамические системы

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

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

Взаимодействие между комбинаторикой и физикой, в особенности статистической физикой, становится все более интенсивным. Примерами служат точное решение модели Изинга и связь между моделью Поттса, с одной стороны, и хроматическим и полиномами Тютте – с другой.