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

Не путать с комбинаторностью .
«Комбинаторный» перенаправляется сюда. Чтобы узнать о комбинаторной логике в информатике, см. Комбинаторную логику .
Часть серии о
Математика
Области
Связь с науками
Математический портал

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

Комбинаторика хорошо известна широтой решаемых ею задач. Комбинаторные задачи возникают во многих областях чистой математики , особенно в алгебре , теории вероятностей , топологии и геометрии . [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]

Конечная геометрия [ править ]

Основная статья: Конечная геометрия

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

Теория порядка [ править ]

Диаграмма Хассе набора степеней {x,y,z}, упорядоченного по включению .
Основная статья: Теория порядка

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

Теория матроидов [ править ]

Основная статья: Теория матроидов

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

Экстремальная комбинаторика [ править ]

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

Экстремальная комбинаторика изучает, насколько большой или маленькой может быть совокупность конечных объектов ( числ , графов , векторов , множеств и т. д.), если она должна удовлетворять определенным ограничениям. Большая часть экстремальной комбинаторики касается классов множеств систем ; это называется экстремальной теорией множеств. Например, в наборе из n элементов каково наибольшее число из k -элементов подмножеств , которые могут попарно пересекаться друг с другом? Каково наибольшее число подмножеств, из которых ни одно не содержит другого? На последний вопрос отвечает теорема Спернера , которая положила начало большей части экстремальной теории множеств.

Типы вопросов, рассматриваемых в этом случае, касаются максимально возможного графа, удовлетворяющего определенным свойствам. Например, самый большой граф без треугольников с 2n вершинами — это полный двудольный граф Kn ,n . Зачастую даже точно найти экстремальный ответ f ( n ) слишком сложно и можно дать лишь асимптотическую оценку .

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

Вероятностная комбинаторика [ править ]

Самоизбегающее блуждание по графу с квадратной сеткой .
Основная статья: Вероятностный метод

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

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

Алгебраическая комбинаторика [ править ]

Диаграмма Юнга целочисленного разбиения (5, 4, 1).
Основная статья: Алгебраическая комбинаторика

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

Комбинаторика слов [ править ]

Построение бесконечного слова Туэ–Морса .
Основная статья: Комбинаторика слов

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

Геометрическая комбинаторика [ править ]

Икосаэдр ​ .
Основная статья: Геометрическая комбинаторика

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

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

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

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

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

Арифметическая комбинаторика [ править ]

Основная статья: Арифметическая комбинаторика

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

Бесконечная комбинаторика [ править ]

Основная статья: Бесконечная комбинаторика

Бесконечная комбинаторика, или комбинаторная теория множеств, представляет собой распространение идей комбинаторики на бесконечные множества. Это часть теории множеств , области математической логики , но использует инструменты и идеи как из теории множеств, так и из экстремальной комбинаторики. Некоторые из изучаемых вещей включают непрерывные графы и деревья , расширения теоремы Рамсея и аксиому Мартина . Последние разработки касаются комбинаторики континуума . [22] и комбинаторика о потомках особых кардиналов. [23]

Джан-Карло Рота использовал название «непрерывная комбинаторика». [24] для описания геометрической вероятности , поскольку существует множество аналогий между счетом и измерением .

Связанные поля [ изменить ]

Целующиеся сферы связаны как с теорией кодирования , так и с дискретной геометрией .

Комбинаторная оптимизация [ править ]

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

Теория кодирования [ править ]

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

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

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

Комбинаторика и динамические системы [ править ]

Комбинаторные аспекты динамических систем — еще одна развивающаяся область. Здесь динамические системы могут быть определены на комбинаторных объектах. См. например граф динамической системы .

Комбинаторика и физика [ править ]

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

См. также [ править ]

Примечания [ править ]

  1. ^ Бьорнер и Стэнли, стр. 2.
  2. ^ Ловаш, Ласло (1979). Комбинаторные задачи и упражнения . Северная Голландия. ISBN  978-0821842621 . Архивировано из оригинала 16 апреля 2021 г. Проверено 23 марта 2021 г. По моему мнению, комбинаторика сейчас выходит из этой ранней стадии.
  3. ^ Пак, Игорь. «Что такое комбинаторика?» . Архивировано из оригинала 17 октября 2017 года . Проверено 1 ноября 2017 г.
  4. ^ Райзер 1963 , стр. 2.
  5. ^ Мирский, Леон (1979), «Рецензия на книгу» (PDF) , Бюллетень Американского математического общества , Новая серия, 1 : 380–388, doi : 10.1090/S0273-0979-1979-14606-8 , заархивировано (PDF) из оригинал 26 февраля 2021 г. , получено 4 февраля 2021 г.
  6. ^ Рота, Джан Карло (1969). Дискретные мысли . Биркхаузер. п. 50. дои : 10.1007/978-0-8176-4775-9 . ISBN  978-0-8176-4775-9 . ...комбинаторная теория стала матерью нескольких наиболее активных разделов современной математики, которые стали независимыми... Типичным... случаем этого является алгебраическая топология (ранее известная как комбинаторная топология).
  7. ^ Ачерби, Ф. (2003). «На плечах Гиппарха» . Архив истории точных наук . 57 (6): 465–502. дои : 10.1007/s00407-003-0067-0 . S2CID   122758966 . Архивировано из оригинала 23 января 2022 г. Проверено 12 марта 2021 г.
  8. ^ Стэнли, Ричард П .; «Гиппарх, Плутарх, Шредер и Хаф», American Mathematical Monthly 104 (1997), вып. 4, 344–350.
  9. ^ Хабзигер, Лоран; Казарян, Максим; Ландо, Сергей (1998). «О втором номере Плутарха». Американский математический ежемесячник . 105 (5): 446. дои : 10.1080/00029890.1998.12004906 .
  10. ^ Нетц, Р.; Ачерби, Ф.; Уилсон, Н. «На пути к реконструкции желудка Архимеда» . Скиамвс . 5 : 67–99. Архивировано из оригинала 16 апреля 2021 г. Проверено 12 марта 2021 г.
  11. ^ Хогендейк, Ян П. (1986). «Арабские следы утраченных произведений Аполлония» . Архив истории точных наук . 35 (3): 187–253. дои : 10.1007/BF00357307 . ISSN   0003-9519 . JSTOR   41133783 . S2CID   121613986 . Архивировано из оригинала 18 апреля 2021 г. Проверено 26 марта 2021 г.
  12. ^ Хаксли, Г. (1967). «Окитокион» . Греческие, римские и византийские исследования . 8 (3): 203. Архивировано из оригинала 16 апреля 2021 г. Проверено 26 марта 2021 г.
  13. ^ О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. , «Комбинаторика» , Архив истории математики MacTutor , Университет Сент-Эндрюс
  14. ^ Путтасвами, Тумкур К. (2000). «Математические достижения древнеиндийских математиков». В Селин, Хелейн (ред.). Математика в разных культурах: история незападной математики . Нидерланды: Kluwer Academic Publishers. п. 417. ИСБН  978-1-4020-0260-1 . Архивировано из оригинала 16 апреля 2021 г. Проверено 15 ноября 2015 г.
  15. ^ Биггс, Норман Л. (1979). «Корни комбинаторики» . История Математики . 6 (2): 109–136. дои : 10.1016/0315-0860(79)90074-0 .
  16. ^ Майстров Л.Е. (1974), Теория вероятностей: исторический очерк , Академическое издательство, с. 35, ISBN  978-1-4832-1863-2 , заархивировано из оригинала 16 апреля 2021 г. , получено 25 января 2015 г. (Перевод русского изд. 1967 г.)
  17. ^ Уайт, Артур Т. (1987). «Звонок в косеты». Американский математический ежемесячник . 94 (8): 721–746. дои : 10.1080/00029890.1987.12000711 .
  18. ^ Уайт, Артур Т. (1996). «Фабиан Стедман: первый теоретик групп?». Американский математический ежемесячник . 103 (9): 771–778. дои : 10.1080/00029890.1996.12004816 .
  19. ^ См. Журналы по комбинаторике и теории графов , заархивированные 17 февраля 2021 г. в Wayback Machine.
  20. ^ Сандерс, Дэниел П.; Сравнение двухзначных MSC. Архивировано 31 декабря 2008 г. на Wayback Machine.
  21. ^ Стинсон 2003 , стр.1
  22. ^ Андреас Бласс , Комбинаторные кардинальные характеристики континуума , Глава 6 в Справочнике по теории множеств, под редакцией Мэтью Формана и Акихиро Канамори , Springer, 2010
  23. ^ Эйсуорт, Тодд (2010), Форман, Мэтью; Канамори, Акихиро (ред.), «Наследники сингулярных кардиналов» , Справочник по теории множеств , Дордрехт: Springer Нидерланды, стр. 1229–1350, doi : 10.1007/978-1-4020-5764-9_16 , ISBN  978-1-4020-4843-2 , получено 27 августа 2022 г.
  24. ^ « Непрерывная и проконечная комбинаторика » (PDF) . Архивировано (PDF) из оригинала 26 февраля 2009 г. Проверено 3 января 2009 г.

Ссылки [ править ]

Внешние ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Combinatorics&oldid=1216877841"