Jump to content

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

(Перенаправлено из Комбинаторной математики )

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

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

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

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

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: eb2eb84cf8cadfdaf3798df367879321__1712057520
URL1:https://arc.ask3.ru/arc/aa/eb/21/eb2eb84cf8cadfdaf3798df367879321.html
Заголовок, (Title) документа по адресу, URL1:
Combinatorics - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)