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