Комбинаторика - Combinatorics - Wikipedia

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

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

Не все согласны с полным объемом комбинаторики.[1] В соответствии с Х. Дж. Райзер, определение предмета затруднено, потому что оно пересекает так много математических подразделений.[2] Поскольку область может быть описана по типам проблем, которые она решает, комбинаторика занимается

  • то перечисление (подсчет) определенных структур, иногда называемых компоновками или конфигурациями в очень общем смысле, связанных с конечными системами,
  • то существование таких структур, которые удовлетворяют определенным заданным критериям,
  • то строительство этих структур, возможно, разными способами, и
  • оптимизация, найти «лучшую» структуру или решение среди нескольких возможностей, будь то «наибольший», «наименьший» или удовлетворяющий какой-либо другой критерий оптимальности.

Леон Мирский сказал: «комбинаторика - это ряд взаимосвязанных исследований, которые имеют что-то общее, но при этом широко расходятся по своим целям, методам и степени согласованности, которой они достигли».[3] Один из способов определить комбинаторику - это, возможно, описать ее подразделения с их проблемами и методами. Это подход, который используется ниже. Однако есть и чисто исторические причины для включения или исключения некоторых тем под зонтиком комбинаторики.[4] Хотя в основном они связаны с конечными системами, некоторые комбинаторные вопросы и методы могут быть расширены до бесконечности (в частности, счетный ) но дискретный параметр.

Комбинаторика хорошо известна широтой решаемых ею проблем. Комбинаторные проблемы возникают во многих областях чистая математика, особенно в алгебра, теория вероятности, топология, и геометрия,[5] а также во многих областях его применения. Многие комбинаторные вопросы исторически рассматривались изолированно, что давало для этого случая решение проблемы, возникающей в некотором математическом контексте. Однако в конце двадцатого века были разработаны мощные и общетеоретические методы, превратившие комбинаторику в самостоятельный раздел математики.[6] Одна из старейших и наиболее доступных частей комбинаторики - это теория графов, который сам по себе имеет многочисленные естественные связи с другими областями. Комбинаторика часто используется в информатике для получения формул и оценок в анализ алгоритмов.

А математик кто изучает комбинаторику, называется комбинатор.

История

Пример изменить звонок (с шестью колокольчиками), один из самых ранних нетривиальных результатов теория графов.
Основная статья: История комбинаторики

Основные комбинаторные концепции и результаты перечисления появлялись в древний мир. В VI веке до нашей эры древний индийский врач Сушрута утверждает в Сушрута Самхита что 63 комбинации могут быть составлены из 6 разных вкусов, взятых по одной, по две за раз и т. д., таким образом вычисляются все 26 - 1 возможность. Греческий историк Плутарх обсуждает спор между Хрисипп (3 век до н.э.) и Гиппарх (2 век до н.э.) довольно деликатной задачи перечисления, которая, как позже было показано, связана с Числа Шредера – Гиппарха.[7][8] в Остомахион, Архимед (3 век до н.э.) считает мозаика.

в Средний возраст комбинаторика продолжала изучаться, в основном за пределами Европейская цивилизация. В Индийский математик Махавира (ок. 850) предоставил формулы для количества перестановки и комбинации,[9][10] и эти формулы могли быть знакомы индийским математикам еще в VI веке нашей эры.[11] В философ и астроном Раввин Авраам ибн Эзра (ок. 1140 г.) установил симметрию биномиальные коэффициенты, а замкнутая формула была получена позже талмудист и математик Леви бен Герсон (более известный как Герсонид), в 1321 г.[12]Арифметический треугольник - графическая диаграмма, показывающая отношения между биномиальными коэффициентами - был представлен математиками в трактатах, датируемых еще 10 веком, и в конечном итоге стал известен как Треугольник Паскаля. Позже Средневековая Англия, кампанология предоставил примеры того, что сейчас известно как Гамильтоновы циклы в определенных Графики Кэли по перестановкам.[13][14]

Вовремя эпоха Возрождения вместе с остальной математикой и науки Комбинаторика пережила второе рождение. Работы Паскаль, Ньютон, Джейкоб Бернулли и Эйлер стал основополагающим в новой области. В наше время произведения J.J. Сильвестр (конец 19 века) и Перси МакМахон (начало 20 века) помогли заложить фундамент для перечислительный и алгебраическая комбинаторика. Теория графов в то же время вызвали всплеск интереса, особенно в связи с четырехцветная проблема.

Во второй половине 20 века комбинаторика стала быстро развиваться, что привело к созданию десятков новых журналов и конференций по этой теме.[15] Частично рост был вызван новыми связями и приложениями в других областях, от алгебры до вероятности, от функциональный анализ к теория чисел и т. д. Эти связи стирают границы между комбинаторикой и частями математики и теоретической информатики, но в то же время приводят к частичной фрагментации этой области.

Подходы и разделы комбинаторики

Перечислительная комбинаторика

Пять бинарные деревья на трех вершины, пример Каталонские числа.
Основная статья: Перечислительная комбинаторика

Перечислительная комбинаторика - это наиболее классическая область комбинаторики, которая концентрируется на подсчете количества определенных комбинаторных объектов. Хотя подсчет количества элементов в наборе - довольно широкая математическая проблема, многие проблемы, возникающие в приложениях, имеют относительно простое комбинаторное описание. Числа Фибоначчи является основным примером проблемы перечислительной комбинаторики. В двенадцатикратный путь обеспечивает единую основу для подсчета перестановки, комбинации и перегородки.

Аналитическая комбинаторика

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

Аналитическая комбинаторика касается перечисления комбинаторных структур с помощью инструментов из комплексный анализ и теория вероятности. В отличие от перечислительной комбинаторики, которая использует явные комбинаторные формулы и производящие функции для описания результатов аналитическая комбинаторика направлена ​​на получение асимптотические формулы.

Теория раздела

А плоская перегородка.
Основная статья: Теория раздела

Теория разделов изучает различные перечислительные и асимптотические проблемы, связанные с целые разделы, и тесно связан с q-серия, специальные функции и ортогональные многочлены. Первоначально входил в состав теория чисел и анализ, теперь он считается частью комбинаторики или самостоятельной области. Он включает биективный подход и различные инструменты для анализа и аналитическая теория чисел и имеет связи с статистическая механика.

Теория графов

Граф Петерсена.
Основная статья: Теория графов

Графы - фундаментальные объекты комбинаторики. Соображения теории графов варьируются от перечисления (например, количества графов на п вершины с k ребер) к существующим структурам (например, гамильтоновым циклам) к алгебраическим представлениям (например, заданному графу грамм и два числа Икс и у, делает ли Полином Тутте Тграмм(Икс,у) имеют комбинаторную интерпретацию?). Хотя между теорией графов и комбинаторикой существует очень сильная связь, их иногда считают отдельными предметами.[16] Хотя комбинаторные методы применимы ко многим задачам теории графов, эти две дисциплины обычно используются для поиска решений различных типов проблем.

Теория дизайна

Основная статья: Комбинаторный дизайн

Теория дизайна - это исследование комбинаторные конструкции, которые представляют собой наборы подмножеств с определенными пересечение характеристики. Блочные конструкции комбинаторные конструкции особого типа. Эта область - одна из старейших частей комбинаторики, например, в Проблема школьницы Киркмана предложен в 1850 году. Решение проблемы - частный случай Система Штейнера, какие системы играют важную роль в классификация конечных простых групп. Район имеет дальнейшие связи с теория кодирования и геометрическая комбинаторика.

Конечная геометрия

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

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

Теория порядка

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

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

Теория матроидов

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

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

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

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

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

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

Вероятностная комбинаторика

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

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

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

Алгебраическая комбинаторика

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

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

Комбинаторика слов

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

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

Геометрическая комбинаторика

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

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

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

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

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

Арифметическая комбинаторика

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

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

Бесконечная комбинаторика

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

Бесконечная комбинаторика или комбинаторная теория множеств - это расширение идей комбинаторики на бесконечные множества. Это часть теория множеств, площадь математическая логика, но использует инструменты и идеи как из теории множеств, так и из экстремальной комбинаторики.

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

Связанные поля

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

Комбинаторная оптимизация

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

Теория кодирования

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

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

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

Комбинаторика и динамические системы

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

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

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

Смотрите также

Примечания

  1. ^ Пак, Игорь. "Что такое комбинаторика?". Получено 1 ноября 2017.
  2. ^ Райзер 1963, п. 2
  3. ^ Мирский, Леон (1979), «Книжное обозрение» (PDF), Бюллетень (новая серия) Американского математического общества, 1: 380–388, Дои:10.1090 / S0273-0979-1979-14606-8
  4. ^ Рота, Джан Карло (1969). Дискретные мысли. Birkhaüser. п. 50. ... комбинаторная теория была матерью нескольких наиболее активных разделов современной математики, которые стали независимыми ... Типичный ... случай этого - алгебраическая топология (ранее известная как комбинаторная топология)
  5. ^ Бьёрнер и Стэнли, стр. 2
  6. ^ Ловас, Ласло (1979). Комбинаторные задачи и упражнения. Северная Голландия. ISBN  9780821842621. На мой взгляд, комбинаторика выросла из этой ранней стадии.
  7. ^ Стэнли, Ричард П.; «Гиппарх, Плутарх, Шредер и Хаф», Американский математический ежемесячный журнал 104 (1997), нет. 4, 344–350.
  8. ^ Habsieger, Laurent; Казарян, Максим; Ландо, Сергей (1998). «О втором номере Плутарха». Американский математический ежемесячник. 105 (5): 446. Дои:10.1080/00029890.1998.12004906.
  9. ^ О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф., «Комбинаторика», Архив истории математики MacTutor, Сент-Эндрюсский университет.
  10. ^ Путтасвами, Тумкур К. (2000). «Математические достижения древних индийских математиков». В Селине, Хелайне (ред.). Математика в разных культурах: история незападной математики. Нидерланды: Kluwer Academic Publishers. п. 417. ISBN  978-1-4020-0260-1.
  11. ^ Биггс, Норман Л. (1979). «Корни комбинаторики». Historia Mathematica. 6 (2): 109–136. Дои:10.1016/0315-0860(79)90074-0.
  12. ^ Майстров, Л. (1974), Теория вероятностей: исторический очерк, Academic Press, стр. 35, ISBN  978-1-4832-1863-2. (Перевод с русского ред. 1967 г.)
  13. ^ Уайт, Артур Т. (1987). "Звонки косеток". Американский математический ежемесячник. 94 (8): 721–746. Дои:10.1080/00029890.1987.12000711.
  14. ^ Белый, Артур Т. (1996). «Фабиан Стедман: первый теоретик групп?». Американский математический ежемесячник. 103 (9): 771–778. Дои:10.1080/00029890.1996.12004816.
  15. ^ Видеть Журналы по комбинаторике и теории графов
  16. ^ Сандерс, Дэниел П .; 2-значный MSC сравнение В архиве 2008-12-31 на Wayback Machine
  17. ^ Непрерывная и бесконечная комбинаторика

Рекомендации

внешняя ссылка