Комбинаторика
Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( Июль 2022 г. ) |
Часть серии о | ||
Математика | ||
---|---|---|
Математический портал | ||
Комбинаторика — область математики , в первую очередь занимающаяся счётом как средством и целью получения результатов, а также определёнными свойствами конечных структур . Она тесно связана со многими другими областями математики и имеет множество приложений — от логики до статистической физики и от эволюционной биологии до информатики .
Комбинаторика хорошо известна широтой решаемых ею задач. Комбинаторные задачи возникают во многих областях чистой математики , особенно в алгебре , теории вероятностей , топологии и геометрии . [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]
Конечная геометрия [ править ]
Конечная геометрия — это изучение геометрических систем, имеющих только конечное число точек. структуры, аналогичные тем, которые встречаются в непрерывных геометриях ( евклидова плоскость , вещественное проективное пространство Основными изучаемыми объектами являются и т. д.), но определенные комбинаторно. Эта область представляет собой богатый источник примеров теории дизайна . Не следует путать ее с дискретной геометрией ( комбинаторной геометрией ).
Теория порядка [ править ]
Теория порядка — это изучение частично упорядоченных множеств , как конечных, так и бесконечных. Он обеспечивает формальную основу для описания таких утверждений, как «это меньше того» или «это предшествует этому». Различные примеры частичных порядков встречаются в алгебре , геометрии, теории чисел, а также в комбинаторике и теории графов. Известные классы и примеры частичных порядков включают решетки и булевы алгебры .
Теория матроидов [ править ]
Теория матроидов абстрагирует часть геометрии . Он изучает свойства множеств (обычно конечных множеств) векторов векторного пространства , не зависящих от конкретных коэффициентов в отношении линейной зависимости . Не только структура, но и перечислительные свойства принадлежат теории матроидов. Теория матроидов была представлена Хасслером Уитни и изучалась как часть теории порядка. Теперь это независимая область исследований, имеющая ряд связей с другими частями комбинаторики.
Экстремальная комбинаторика [ править ]
Экстремальная комбинаторика изучает, насколько большой или маленькой может быть совокупность конечных объектов ( числ , графов , векторов , множеств и т. д.), если она должна удовлетворять определенным ограничениям. Большая часть экстремальной комбинаторики касается классов множеств систем ; это называется экстремальной теорией множеств. Например, в наборе из n элементов каково наибольшее число из k -элементов подмножеств , которые могут попарно пересекаться друг с другом? Каково наибольшее число подмножеств, из которых ни одно не содержит другого? На последний вопрос отвечает теорема Спернера , которая положила начало большей части экстремальной теории множеств.
Типы вопросов, рассматриваемых в этом случае, касаются максимально возможного графа, удовлетворяющего определенным свойствам. Например, самый большой граф без треугольников с 2n вершинами — это полный двудольный граф Kn ,n . Зачастую даже точно найти экстремальный ответ f ( n ) слишком сложно и можно дать лишь асимптотическую оценку .
Теория Рамсея — еще одна часть экстремальной комбинаторики. Он утверждает, что любая достаточно большая конфигурация будет содержать некоторый порядок. Это расширенное обобщение принципа «ячейки» .
Вероятностная комбинаторика [ править ]
В вероятностной комбинаторике вопросы бывают следующего типа: какова вероятность определенного свойства случайного дискретного объекта, например случайного графа ? Например, каково среднее количество треугольников в случайном графе? Вероятностные методы также используются для определения существования комбинаторных объектов с определенными заданными свойствами (для которых может быть трудно найти явные примеры) путем наблюдения за тем, что вероятность случайного выбора объекта с этими свойствами больше 0. Этот подход (часто называемый как вероятностный метод ) оказался весьма эффективным в приложениях к экстремальной комбинаторике и теории графов. Тесно связанной областью является исследование конечных цепей Маркова , особенно на комбинаторных объектах. Здесь снова используются вероятностные инструменты для оценки времени смешивания . [ нужны разъяснения ]
Вероятностная комбинаторика, которую часто связывают с Полом Эрдешем , который проделал новаторскую работу по этому вопросу, традиционно рассматривалась как набор инструментов для изучения проблем в других частях комбинаторики. Недавно эта область выросла и стала независимой областью комбинаторики.
Алгебраическая комбинаторика [ править ]
Алгебраическая комбинаторика — это область математики , которая использует методы абстрактной алгебры , особенно теории групп и теории представлений , в различных комбинаторных контекстах и, наоборот, применяет комбинаторные методы к задачам алгебры . Алгебраическую комбинаторику стали рассматривать более широко как область математики, в которой взаимодействие комбинаторных и алгебраических методов особенно сильно и значимо. Таким образом, комбинаторные темы могут носить перечислительный характер или включать в себя матроиды , многогранники , частично упорядоченные множества или конечную геометрию . С алгебраической стороны, помимо теории групп и представлений, теория решеток и коммутативная алгебра распространены .
Комбинаторика слов [ править ]
Комбинаторика слов имеет дело с формальными языками . Она возникла независимо в рамках нескольких разделов математики, включая теорию чисел , теорию групп и теорию вероятностей . Он имеет приложения к перечислительной комбинаторике, фрактальному анализу , теоретической информатике , теории автоматов и лингвистике . Хотя многие приложения являются новыми, классическая Хомского-Шютценбергера, иерархия классов формальных грамматик пожалуй, является самым известным результатом в этой области.
Геометрическая комбинаторика [ править ]
Геометрическая комбинаторика связана с выпуклой и дискретной геометрией . Например, он спрашивает, сколько граней каждого измерения может иметь выпуклый многогранник . Важную роль играют также метрические свойства многогранников, например, теорема Коши о жесткости выпуклых многогранников. Также рассматриваются специальные многогранники, такие как пермутоэдры , ассоциэдры и многогранники Биркгофа . Комбинаторная геометрия — историческое название дискретной геометрии.
Она включает в себя ряд подобластей, таких как полиэдральная комбинаторика (изучение граней выпуклых многогранников ), выпуклая геометрия (изучение выпуклых множеств , в частности комбинаторика их пересечений) и дискретная геометрия , которая, в свою очередь, имеет множество приложений к вычислительной геометрии. . Изучение правильных многогранников , архимедовых тел и чисел целования также является частью геометрической комбинаторики. Также рассматриваются специальные многогранники, такие как пермутоэдр , ассоциэдр и многогранник Биркгофа .
Топологическая комбинаторика [ править ]
Комбинаторные аналоги понятий и методов топологии используются для изучения раскраски графов , справедливого деления , разбиений , частично упорядоченных множеств , деревьев решений , задач ожерелья и дискретной теории Морса . Ее не следует путать с комбинаторной топологией , которая является старым названием алгебраической топологии .
Арифметическая комбинаторика [ править ]
Арифметическая комбинаторика возникла в результате взаимодействия теории чисел , комбинаторики, эргодической теории и гармонического анализа . Речь идет о комбинаторных оценках, связанных с арифметическими операциями (сложение, вычитание, умножение и деление). Аддитивная теория чисел (иногда также называемая аддитивной комбинаторикой) относится к частному случаю, когда задействованы только операции сложения и вычитания. Одним из важных методов арифметической комбинаторики является эргодическая теория динамических систем .
Бесконечная комбинаторика [ править ]
Бесконечная комбинаторика, или комбинаторная теория множеств, представляет собой распространение идей комбинаторики на бесконечные множества. Это часть теории множеств , области математической логики , но использует инструменты и идеи как из теории множеств, так и из экстремальной комбинаторики. Некоторые из изучаемых вещей включают непрерывные графы и деревья , расширения теоремы Рамсея и аксиому Мартина . Последние разработки касаются комбинаторики континуума . [22] и комбинаторика о потомках особых кардиналов. [23]
Джан-Карло Рота использовал название «непрерывная комбинаторика». [24] для описания геометрической вероятности , поскольку существует множество аналогий между счетом и измерением .
Связанные поля [ изменить ]
Комбинаторная оптимизация [ править ]
Комбинаторная оптимизация — это исследование оптимизации дискретных и комбинаторных объектов. Это началось как часть комбинаторики и теории графов, но теперь рассматривается как раздел прикладной математики и информатики, связанный с исследованием операций , теорией алгоритмов и теорией сложности вычислений .
Теория кодирования [ править ]
Теория кодирования началась как часть теории дизайна с ранних комбинаторных конструкций кодов, исправляющих ошибки . Основная идея предмета – разработка эффективных и надежных методов передачи данных. Сейчас это большая область исследований, часть теории информации .
Дискретная и вычислительная геометрия [ править ]
Дискретная геометрия (также называемая комбинаторной геометрией) также возникла как часть комбинаторики, с ранними результатами по выпуклым многогранникам и целующимся числам . С появлением приложений дискретной геометрии к вычислительной геометрии эти две области частично объединились и стали отдельной областью исследования. Сохраняется множество связей с геометрической и топологической комбинаторикой, которую сами по себе можно рассматривать как результат ранней дискретной геометрии.
Комбинаторика и динамические системы [ править ]
Комбинаторные аспекты динамических систем — еще одна развивающаяся область. Здесь динамические системы могут быть определены на комбинаторных объектах. См. например граф динамической системы .
Комбинаторика и физика [ править ]
Растет взаимодействие между комбинаторикой и физикой , особенно статистической физикой . Примеры включают точное решение модели Изинга и связь между моделью Поттса, с одной стороны, и хроматическими полиномами и полиномами Тутте , с другой стороны.
См. также [ править ]
Примечания [ править ]
- ^ Бьорнер и Стэнли, стр. 2.
- ^ Ловаш, Ласло (1979). Комбинаторные задачи и упражнения . Северная Голландия. ISBN 978-0821842621 . Архивировано из оригинала 16 апреля 2021 г. Проверено 23 марта 2021 г.
По моему мнению, комбинаторика сейчас выходит из этой ранней стадии.
- ^ Пак, Игорь. «Что такое комбинаторика?» . Архивировано из оригинала 17 октября 2017 года . Проверено 1 ноября 2017 г.
- ^ Райзер 1963 , стр. 2.
- ^ Мирский, Леон (1979), «Рецензия на книгу» (PDF) , Бюллетень Американского математического общества , Новая серия, 1 : 380–388, doi : 10.1090/S0273-0979-1979-14606-8 , заархивировано (PDF) из оригинал 26 февраля 2021 г. , получено 4 февраля 2021 г.
- ^ Рота, Джан Карло (1969). Дискретные мысли . Биркхаузер. п. 50. дои : 10.1007/978-0-8176-4775-9 . ISBN 978-0-8176-4775-9 .
...комбинаторная теория стала матерью нескольких наиболее активных разделов современной математики, которые стали независимыми... Типичным... случаем этого является алгебраическая топология (ранее известная как комбинаторная топология).
- ^ Ачерби, Ф. (2003). «На плечах Гиппарха» . Архив истории точных наук . 57 (6): 465–502. дои : 10.1007/s00407-003-0067-0 . S2CID 122758966 . Архивировано из оригинала 23 января 2022 г. Проверено 12 марта 2021 г.
- ^ Стэнли, Ричард П .; «Гиппарх, Плутарх, Шредер и Хаф», American Mathematical Monthly 104 (1997), вып. 4, 344–350.
- ^ Хабзигер, Лоран; Казарян, Максим; Ландо, Сергей (1998). «О втором номере Плутарха». Американский математический ежемесячник . 105 (5): 446. дои : 10.1080/00029890.1998.12004906 .
- ^ Нетц, Р.; Ачерби, Ф.; Уилсон, Н. «На пути к реконструкции желудка Архимеда» . Скиамвс . 5 : 67–99. Архивировано из оригинала 16 апреля 2021 г. Проверено 12 марта 2021 г.
- ^ Хогендейк, Ян П. (1986). «Арабские следы утраченных произведений Аполлония» . Архив истории точных наук . 35 (3): 187–253. дои : 10.1007/BF00357307 . ISSN 0003-9519 . JSTOR 41133783 . S2CID 121613986 . Архивировано из оригинала 18 апреля 2021 г. Проверено 26 марта 2021 г.
- ^ Хаксли, Г. (1967). «Окитокион» . Греческие, римские и византийские исследования . 8 (3): 203. Архивировано из оригинала 16 апреля 2021 г. Проверено 26 марта 2021 г.
- ^ О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. , «Комбинаторика» , Архив истории математики MacTutor , Университет Сент-Эндрюс
- ^ Путтасвами, Тумкур К. (2000). «Математические достижения древнеиндийских математиков». В Селин, Хелейн (ред.). Математика в разных культурах: история незападной математики . Нидерланды: Kluwer Academic Publishers. п. 417. ИСБН 978-1-4020-0260-1 . Архивировано из оригинала 16 апреля 2021 г. Проверено 15 ноября 2015 г.
- ^ Биггс, Норман Л. (1979). «Корни комбинаторики» . История Математики . 6 (2): 109–136. дои : 10.1016/0315-0860(79)90074-0 .
- ^ Майстров Л.Е. (1974), Теория вероятностей: исторический очерк , Академическое издательство, с. 35, ISBN 978-1-4832-1863-2 , заархивировано из оригинала 16 апреля 2021 г. , получено 25 января 2015 г. (Перевод русского изд. 1967 г.)
- ^ Уайт, Артур Т. (1987). «Звонок косетов». Американский математический ежемесячник . 94 (8): 721–746. дои : 10.1080/00029890.1987.12000711 .
- ^ Уайт, Артур Т. (1996). «Фабиан Стедман: первый теоретик групп?». Американский математический ежемесячник . 103 (9): 771–778. дои : 10.1080/00029890.1996.12004816 .
- ^ См. Журналы по комбинаторике и теории графов , заархивированные 17 февраля 2021 г. в Wayback Machine.
- ^ Сандерс, Дэниел П.; Сравнение двухзначных MSC. Архивировано 31 декабря 2008 г. на Wayback Machine.
- ^ Стинсон 2003 , стр.1
- ^ Андреас Бласс , Комбинаторные кардинальные характеристики континуума , Глава 6 в Справочнике по теории множеств, под редакцией Мэтью Формана и Акихиро Канамори , Springer, 2010
- ^ Эйсуорт, Тодд (2010), Форман, Мэтью; Канамори, Акихиро (ред.), «Наследники сингулярных кардиналов» , Справочник по теории множеств , Дордрехт: Springer Нидерланды, стр. 1229–1350, doi : 10.1007/978-1-4020-5764-9_16 , ISBN 978-1-4020-4843-2 , получено 27 августа 2022 г.
- ^ « Непрерывная и проконечная комбинаторика » (PDF) . Архивировано (PDF) из оригинала 26 февраля 2009 г. Проверено 3 января 2009 г.
Ссылки [ править ]
- Бьёрнер, Андерс; и Стэнли, Ричард П.; (2010); Комбинаторный сборник
- Бона, Миклош; (2011); Прогулка по комбинаторике (3-е изд.) . ISBN 978-981-4335-23-2 , 978-981-4460-00-2
- Грэм, Рональд Л.; Гротшель, Мартин; и Ловас, Ласло; ред. (1996); Справочник по комбинаторике , тома 1 и 2. Амстердам, Нидерланды, и Кембридж, Массачусетс: Elsevier (Северная Голландия) и MIT Press. ISBN 0-262-07169-X
- Линднер, Чарльз К.; и Роджер, Кристофер А.; ред. (1997); Теория дизайна , ЦРК-Пресс. ISBN 0-8493-3986-3 .
- Риордан, Джон (2002) [1958], Введение в комбинаторный анализ , Дувр, ISBN 978-0-486-42536-8
- Райзер, Герберт Джон (1963), Комбинаторная математика , Математические монографии Каруса (№ 14), Математическая ассоциация Америки
- Стэнли, Ричард П. (1997, 1999); Перечислительная комбинаторика , тома 1 и 2 , издательство Кембриджского университета . ISBN 0-521-55309-1 , 0-521-56069-1
- Стинсон, Дуглас Р. (2003), Комбинаторные планы: конструкции и анализ , Нью-Йорк: Springer, ISBN 0-387-95487-2
- ван Линт, Якобус Х.; и Уилсон, Ричард М.; (2001); Курс комбинаторики , 2-е изд., Издательство Кембриджского университета. ISBN 0-521-80340-3
Внешние ссылки [ править ]
- «Комбинаторный анализ» , Математическая энциклопедия , EMS Press , 2001 [1994]
- Комбинаторный анализ - статья в одиннадцатом издании Британской энциклопедии.
- Комбинаторика , статья MathWorld со множеством ссылок.
- Комбинаторика с портала MathPages.com .
- Гиперкнига по комбинаторике , сборник ссылок на статьи по математике.
- «Две культуры математики» , У. Т. Гауэрс, статья о решении проблем и построении теории.
- «Глоссарий терминов по комбинаторике». Архивировано 17 августа 2017 г. на Wayback Machine.
- Список программного обеспечения и баз данных для комбинаторики