Комбинаторика — это область математики , в первую очередь занимающаяся счётом как средством и целью получения результатов, а также определёнными свойствами конечных структур . Она тесно связана со многими другими областями математики и имеет множество приложений — от логики до статистической физики и от эволюционной биологии до информатики .
Комбинаторика хорошо известна широтой решаемых ею задач. Комбинаторные проблемы возникают во многих областях чистой математики , особенно в алгебре , теории вероятностей , топологии и геометрии , [1] , а также во многих областях ее применения. Многие комбинаторные вопросы исторически рассматривались изолированно, давая специальное решение проблемы, возникающей в некотором математическом контексте. Однако в конце двадцатого века были разработаны мощные общетеоретические методы, превратившие комбинаторику в самостоятельную ветвь математики. [2] Одной из старейших и наиболее доступных частей комбинаторики является теория графов , которая сама по себе имеет многочисленные естественные связи с другими областями. Комбинаторика часто используется в информатике для получения формул и оценок при анализе алгоритмов .
Математика , изучающего комбинаторику , называют комбинатористом .
Полный объем комбинаторики не является общепринятым. [3] По мнению Х. Дж. Райзера , определение предмета затруднено, поскольку оно пересекает множество математических подразделений. [4] Поскольку область можно описать типами задач, которые она решает, комбинаторика занимается:
Леон Мирский сказал: «Комбинаторика — это ряд взаимосвязанных исследований, которые имеют что-то общее, но в то же время сильно расходятся по своим целям, методам и степени согласованности, которую они достигли». [5] Одним из способов определения комбинаторики, возможно, является описание ее подразделений с их проблемами и методами. Именно этот подход используется ниже. Однако существуют и чисто исторические причины включения или невключения некоторых тем в сферу комбинаторики. [6] Хотя в первую очередь речь идет о конечных системах, некоторые комбинаторные вопросы и методы могут быть распространены на бесконечные (в частности, счетные ), но дискретные условия.
Основные комбинаторные понятия и перечислительные результаты появились во всем древнем мире . Индийский врач Сушрута утверждает в «Сушрута-самхите» , что из 6 различных вкусов можно составить 63 комбинации, принимаемые по одному, по два за раз и т. д., вычисляя таким образом все 2 6 − 1 возможностей. Греческий историк Плутарх обсуждает спор между Хрисиппом (3 век до н.э.) и Гиппархом (2 век до н.э.) о довольно деликатной перечислительной проблеме, которая, как позже было показано, связана с числами Шредера-Гиппарха . [7] [8] [9] Ранее, в «Остомахионе» , Архимед (3-й век до н. э.), возможно, рассматривал количество конфигураций мозаичной головоломки , [ 10] в то время как комбинаторные интересы, возможно, присутствовали в утраченных работах Аполлония . [11] [12]
В средние века комбинаторику продолжали изучать, в основном за пределами европейской цивилизации . Индийский математик Махавира ( ок. 850 г. ) предоставил формулы для числа перестановок и комбинаций , [13] [14] , и эти формулы, возможно, были знакомы индийским математикам еще в VI веке нашей эры. [15] Философ и астроном раввин Авраам ибн Эзра ( ок. 1140 ) установил симметрию биномиальных коэффициентов , а замкнутая формула была получена позднее талмудистом и математиком Леви бен Герсоном (более известным как Герсонид), в 1321 году. [16] ] Арифметический треугольник — графическая диаграмма, показывающая отношения между биномиальными коэффициентами — был представлен математиками в трактатах, датируемых еще 10 веком, и в конечном итоге стал известен как треугольник Паскаля . Позже, в средневековой Англии , кампанология предоставила примеры того, что сейчас известно как гамильтоновы циклы в некоторых графах Кэли при перестановках. [17] [18]
В эпоху Возрождения , вместе с остальной математикой и естественными науками , комбинаторика пережила второе рождение. Работы Паскаля , Ньютона , Якоба Бернулли и Эйлера стали основополагающими в развивающейся области. В новое время работы Дж. Дж. Сильвестра (конец 19 века) и Перси Мак-Магона (начало 20 века) помогли заложить основу перечислительной и алгебраической комбинаторики . В то же время возрос интерес к теории графов , особенно в связи с проблемой четырех цветов .
Во второй половине 20 века комбинаторика бурно развивалась, что привело к созданию десятков новых журналов и конференций по этой теме. [19] Частично рост стимулировали новые связи и приложения к другим областям, начиная от алгебры до теории вероятностей, от функционального анализа до теории чисел и т. д. Эти связи стирают границы между комбинаторикой и частями математики и теоретической информатики, но в то же время привело к частичной фрагментации поля.
Перечислительная комбинаторика является наиболее классической областью комбинаторики и концентрируется на подсчете количества определенных комбинаторных объектов. Хотя подсчет количества элементов в множестве является довольно широкой математической задачей , многие проблемы, возникающие в приложениях, имеют сравнительно простое комбинаторное описание. Числа Фибоначчи — это основной пример задачи перечислительной комбинаторики. Двенадцатикратный способ обеспечивает единую основу для подсчета перестановок , комбинаций и разделов .
Аналитическая комбинаторика занимается перечислением комбинаторных структур с использованием инструментов комплексного анализа и теории вероятностей . В отличие от перечислительной комбинаторики, которая для описания результатов использует явные комбинаторные формулы и производящие функции , аналитическая комбинаторика направлена на получение асимптотических формул .
Теория разбиений изучает различные проблемы перечисления и асимптотики, связанные с целочисленными разбиениями , и тесно связана с q-рядами , специальными функциями и ортогональными полиномами . Первоначально это была часть теории чисел и анализа , теперь она считается частью комбинаторики или независимой областью. Он включает в себя биективный подход и различные инструменты анализа и аналитической теории чисел и имеет связи со статистической механикой . Разделы можно графически визуализировать с помощью диаграмм Юнга или диаграмм Феррера . Они встречаются в ряде разделов математики и физики , включая изучение симметричных многочленов и симметрической группы , а также в теории представлений групп в целом.
Графы являются фундаментальными объектами комбинаторики. Рассмотрение теории графов варьируется от перечисления (например, количества графов на n вершинах с k ребрами) до существующих структур (например, гамильтоновых циклов) и алгебраических представлений (например, если задан граф G и два числа x и y , то полином T G ( x , y ) имеет комбинаторную интерпретацию?). Хотя между теорией графов и комбинаторикой существует очень сильная связь, иногда их рассматривают как отдельные предметы. [20] Хотя комбинаторные методы применимы ко многим задачам теории графов, эти две дисциплины обычно используются для поиска решений различных типов задач.
Теория дизайна — это исследование комбинаторных проектов , которые представляют собой коллекции подмножеств с определенными свойствами пересечения . Блочные конструкции представляют собой комбинаторные конструкции особого типа. Эта область является одной из старейших частей комбинаторики, например, в задаче Киркмана о школьнице , предложенной в 1850 году. Решением проблемы является частный случай системы Штейнера , системы которой играют важную роль в классификации конечных простых групп . Эта область имеет дальнейшую связь с теорией кодирования и геометрической комбинаторикой.
Теория комбинаторного планирования может быть применена к области планирования экспериментов . Некоторые из основных теорий комбинаторных планов возникли в работе статистика Рональда Фишера по планированию биологических экспериментов. Современные приложения также можно найти в широком спектре областей, включая конечную геометрию , планирование турниров , лотереи , математическую химию , математическую биологию , проектирование и анализ алгоритмов , создание сетей , групповое тестирование и криптографию . [21]
Конечная геометрия — это изучение геометрических систем , имеющих только конечное число точек. Основными изучаемыми объектами являются структуры, аналогичные тем, которые встречаются в непрерывных геометриях ( евклидова плоскость , вещественное проективное пространство и т. д.), но определенные комбинаторно. Эта область представляет собой богатый источник примеров теории дизайна . Не следует путать ее с дискретной геометрией ( комбинаторной геометрией ).
Теория порядка — это изучение частично упорядоченных множеств , как конечных, так и бесконечных. Он обеспечивает формальную основу для описания таких утверждений, как «это меньше того» или «это предшествует этому». Различные примеры частичных порядков встречаются в алгебре , геометрии, теории чисел, а также в комбинаторике и теории графов. Известные классы и примеры частичных порядков включают решетки и булевы алгебры .
Теория матроидов абстрагирует часть геометрии . Он изучает свойства множеств (обычно конечных множеств) векторов векторного пространства , не зависящих от конкретных коэффициентов в отношении линейной зависимости . Не только структура, но и перечислительные свойства принадлежат теории матроидов. Теория матроидов была представлена Хасслером Уитни и изучалась как часть теории порядка. Теперь это независимая область исследований, имеющая ряд связей с другими частями комбинаторики.
Экстремальная комбинаторика изучает, насколько большой или маленькой может быть совокупность конечных объектов ( числ , графов , векторов , множеств и т. д.), если она должна удовлетворять определенным ограничениям. Большая часть экстремальной комбинаторики касается классов систем множеств ; это называется экстремальной теорией множеств. Например, каково наибольшее число подмножеств из k - элементов в наборе из n элементов, которые могут попарно пересекаться друг с другом? Каково наибольшее число подмножеств, из которых ни одно не содержит другого? На последний вопрос отвечает теорема Спернера , которая положила начало большей части экстремальной теории множеств.
Типы вопросов, рассматриваемых в этом случае, касаются максимально возможного графа, удовлетворяющего определенным свойствам. Например, самый большой граф без треугольников с 2n вершинами — это полный двудольный граф Kn ,n . Зачастую даже точно найти экстремальный ответ f ( n ) слишком сложно и можно дать лишь асимптотическую оценку .
Теория Рамсея — еще одна часть экстремальной комбинаторики. Он утверждает, что любая достаточно большая конфигурация будет содержать некоторый порядок. Это расширенное обобщение принципа «ячейки» .
В вероятностной комбинаторике вопросы бывают следующего типа: какова вероятность определенного свойства случайного дискретного объекта, например случайного графа ? Например, каково среднее количество треугольников в случайном графе? Вероятностные методы также используются для определения существования комбинаторных объектов с определенными заданными свойствами (для которых может быть трудно найти явные примеры) путем наблюдения за тем, что вероятность случайного выбора объекта с этими свойствами больше 0. Этот подход (часто называемый как вероятностный метод ) оказался весьма эффективным в приложениях к экстремальной комбинаторике и теории графов. Тесно связанной областью является исследование конечных цепей Маркова , особенно на комбинаторных объектах. Здесь снова используются вероятностные инструменты для оценки времени смешивания . [ нужны разъяснения ]
Вероятностная комбинаторика, которую часто связывают с Полом Эрдешем , который проделал новаторскую работу по этому вопросу, традиционно рассматривалась как набор инструментов для изучения проблем в других частях комбинаторики. Недавно эта область выросла и стала независимой областью комбинаторики.
Алгебраическая комбинаторика — это область математики , которая использует методы абстрактной алгебры , особенно теории групп и теории представлений , в различных комбинаторных контекстах и, наоборот, применяет комбинаторные методы к задачам алгебры . Алгебраическую комбинаторику стали рассматривать более широко как область математики, в которой взаимодействие комбинаторных и алгебраических методов особенно сильно и значимо. Таким образом, комбинаторные темы могут носить перечислительный характер или включать в себя матроиды , многогранники , частично упорядоченные множества или конечную геометрию . С алгебраической стороны, помимо теории групп и представлений, распространены теория решеток и коммутативная алгебра .
Комбинаторика слов имеет дело с формальными языками . Она возникла независимо в рамках нескольких разделов математики, включая теорию чисел , теорию групп и теорию вероятностей . Он имеет приложения к перечислительной комбинаторике, фрактальному анализу , теоретической информатике , теории автоматов и лингвистике . Хотя многие приложения являются новыми, классическая иерархия классов формальных грамматик Хомского-Шютценбергера , пожалуй, является самым известным результатом в этой области.
Геометрическая комбинаторика связана с выпуклой и дискретной геометрией . Например, он спрашивает, сколько граней каждого измерения может иметь выпуклый многогранник . Важную роль играют также метрические свойства многогранников, например, теорема Коши о жесткости выпуклых многогранников. Также рассматриваются специальные многогранники, такие как пермутоэдры , ассоциэдры и многогранники Биркгофа . Комбинаторная геометрия — историческое название дискретной геометрии.
Она включает в себя ряд подобластей, таких как полиэдральная комбинаторика (изучение граней выпуклых многогранников ), выпуклая геометрия (изучение выпуклых множеств , в частности комбинаторика их пересечений) и дискретная геометрия , которая, в свою очередь, имеет множество приложений к вычислительной геометрии. . Изучение правильных многогранников , архимедовых тел и чисел целования также является частью геометрической комбинаторики. Также рассматриваются специальные многогранники, такие как пермутоэдр , ассоциэдр и многогранник Биркгофа .
Комбинаторные аналоги понятий и методов топологии используются для изучения раскраски графов , справедливого деления , разбиений , частично упорядоченных множеств , деревьев решений , задач ожерелья и дискретной теории Морса . Ее не следует путать с комбинаторной топологией , которая является старым названием алгебраической топологии .
Арифметическая комбинаторика возникла в результате взаимодействия теории чисел , комбинаторики, эргодической теории и гармонического анализа . Речь идет о комбинаторных оценках, связанных с арифметическими операциями (сложение, вычитание, умножение и деление). Аддитивная теория чисел (иногда называемая аддитивной комбинаторикой) относится к особому случаю, когда задействованы только операции сложения и вычитания. Одним из важных методов арифметической комбинаторики является эргодическая теория динамических систем .
Бесконечная комбинаторика, или комбинаторная теория множеств, представляет собой распространение идей комбинаторики на бесконечные множества. Это часть теории множеств , области математической логики , но использует инструменты и идеи как из теории множеств, так и из экстремальной комбинаторики. Некоторые из изучаемых вещей включают непрерывные графы и деревья , расширения теоремы Рамсея и аксиому Мартина . Последние разработки касаются комбинаторики континуума [ 22] и комбинаторики потомков сингулярных кардиналов. [23]
Джан-Карло Рота использовал название « непрерывная комбинаторика» [24] для описания геометрической вероятности , поскольку между счётом и мерой существует множество аналогий .
Комбинаторная оптимизация — это исследование оптимизации дискретных и комбинаторных объектов. Это началось как часть комбинаторики и теории графов, но теперь рассматривается как раздел прикладной математики и информатики, связанный с исследованием операций , теорией алгоритмов и теорией сложности вычислений .
Теория кодирования началась как часть теории дизайна с ранних комбинаторных конструкций кодов, исправляющих ошибки . Основная идея предмета – разработка эффективных и надежных методов передачи данных. Сейчас это большая область исследований, часть теории информации .
Дискретная геометрия (также называемая комбинаторной геометрией) также возникла как часть комбинаторики с ранними результатами по выпуклым многогранникам и целующимся числам . С появлением приложений дискретной геометрии к вычислительной геометрии эти две области частично объединились и стали отдельной областью исследования. Сохраняется множество связей с геометрической и топологической комбинаторикой, которую сами можно рассматривать как результат ранней дискретной геометрии.
Комбинаторные аспекты динамических систем — еще одна развивающаяся область. Здесь динамические системы могут быть определены на комбинаторных объектах. См., например , граф динамической системы .
Растет взаимодействие между комбинаторикой и физикой , особенно статистической физикой . Примеры включают точное решение модели Изинга и связь между моделью Поттса, с одной стороны, и хроматическими полиномами и полиномами Тутта, с другой стороны.
По моему мнению, комбинаторика сейчас выходит из этой ранней стадии.
...комбинаторная теория стала матерью нескольких наиболее активных разделов современной математики, которые стали независимыми... Типичным... случаем этого является алгебраическая топология (ранее известная как комбинаторная топология).