Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Не путать с комбинаторностью .
«Комбинаторный» перенаправляется сюда. Для комбинаторной логики в информатике см. Комбинаторную логику .

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

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

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

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

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

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

История [ править ]

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

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

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

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

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

Подходы и разделы комбинаторики [ править ]

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

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

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

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

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

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

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

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

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

Теория графов [ править ]

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

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

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

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

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

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

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

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

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

Диаграмма Хассе из Powerset из {х, у, г} упорядочены по включению .
Основная статья: Теория порядка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Комбинаторная биология
  • Комбинаторная химия
  • Комбинаторный анализ данных
  • Комбинаторная теория игр
  • Комбинаторная теория групп
  • Список тем комбинаторики
  • Филогенетика
  • Метод полиномов в комбинаторике

Заметки [ править ]

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

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

  • Бьёрнер, Андерс; и Стэнли, Ричард П .; (2010); Комбинаторный сборник
  • Бона, Миклош; (2011); Прогулка по комбинаторике (3-е издание) . ISBN 978-981-4335-23-2 , 978-981-4460-00-2 
  • Грэм, Рональд Л .; Groetschel, Мартин; и Ловас, Ласло; ред. (1996); Справочник по комбинаторике , тома 1 и 2. Амстердам, Нидерланды, и Кембридж, Массачусетс: Elsevier (Северная Голландия) и MIT Press. ISBN 0-262-07169-X 
  • Линднер, Чарльз С .; и Роджер, Кристофер А .; ред. (1997); Теория дизайна , CRC-Press; 1-й. издание (1997). ISBN 0-8493-3986-3 . 
  • Риордан, Джон (2002) [1958], Введение в комбинаторный анализ , Dover, ISBN 978-0-486-42536-8
  • Райзер, Герберт Джон (1963), комбинаторная математика , The Carus Mathematical Monographs (# 14), The Mathematical Association of America
  • Стэнли, Ричард П. (1997, 1999); Перечислительная комбинаторика , тома 1 и 2 , Cambridge University Press . ISBN 0-521-55309-1 , 0-521-56069-1 
  • van Lint, Jacobus H .; и Уилсон, Ричард М .; (2001); Курс комбинаторики , 2-е издание, Cambridge University Press. ISBN 0-521-80340-3 

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

  • "Комбинаторный анализ" , Энциклопедия математики , EMS Press , 2001 [1994]
  • Комбинаторный анализ - статья в Encyclopædia Britannica Eleventh Edition
  • Комбинаторика , статья MathWorld со множеством ссылок.
  • Комбинаторика , с портала MathPages.com .
  • Гиперкнига комбинаторики , сборник ссылок на математические статьи.
  • «Две культуры математики» В. Т. Гауэрса, статья о решении проблем и построении теории.
  • «Словарь терминов комбинаторики»
  • Список программ комбинаторики и баз данных