Комбинаторика - это область математики, которая в первую очередь занимается счетом как средством и как целью получения результатов, так и определенными свойствами конечных структур . Он тесно связан со многими другими областями математики и имеет множество приложений, от логики до статистической физики , от эволюционной биологии до информатики и т. Д.
Не все согласны с полным объемом комбинаторики. [1] По словам Х. Дж. Райзера , определение предмета затруднено, потому что оно пересекает очень много математических подразделов. [2] Поскольку область может быть описана типами проблем, которые она решает, комбинаторика занимается:
- перечисление (подсчет) из указанных структур, иногда называемых механизмов или конфигураций в самом общем смысле, связанный с конечными системами,
- существование таких структур , которые удовлетворяют определенные заданные критерии,
- строительство этих сооружений, возможно , во многих отношениях, и
- оптимизация , поиск «лучшей» структуры или решения среди нескольких возможностей, будь то «наибольший», «наименьший» или удовлетворяющий какому-либо другому критерию оптимальности .
Леон Мирский сказал: «Комбинаторика - это набор взаимосвязанных исследований, которые имеют что-то общее, но при этом сильно различаются по своим целям, методам и степени согласованности, которой они достигли». [3] Один из способов определить комбинаторику - это, возможно, описать ее подразделения с их проблемами и методами. Это подход, который используется ниже. Однако есть и чисто исторические причины для включения или исключения некоторых тем под зонтиком комбинаторики. [4] Хотя в первую очередь они касаются конечных систем, некоторые комбинаторные вопросы и методы могут быть расширены до бесконечной (в частности, счетной ), но дискретной ситуации.
Комбинаторика хорошо известна широким спектром задач, которые она решает. Комбинаторные проблемы возникают во многих областях чистой математики , в частности , в алгебре , теории вероятностей , топологии и геометрии , [5] , а также в его многочисленных областей применения. Многие комбинаторные вопросы исторически рассматривались изолированно, давая специальное решение проблемы, возникающей в некотором математическом контексте. Однако в конце двадцатого века были разработаны мощные и общетеоретические методы, превратившие комбинаторику в самостоятельный раздел математики. [6]Одна из старейших и наиболее доступных частей комбинаторики - теория графов , которая сама по себе имеет многочисленные естественные связи с другими областями. Комбинаторика часто используется в информатике для получения формул и оценок при анализе алгоритмов .
Математик , который изучает комбинаторику называется combinatorialist .
История [ править ]
Основные комбинаторные концепции и результаты перечисления появились во всем античном мире . В VI веке до нашей эры древний индийский врач Сушрута утверждает в « Сушрута-самхите», что можно составить 63 комбинации из 6 различных вкусов, взятых по одному, по два за раз и т. Д., Таким образом вычисляя все 2 6 - 1 возможности. Греческий историк Плутарх обсуждает спор между Хрисиппом (3 век до н.э.) и Гиппархом (2 век до н.э.) относительно довольно деликатной проблемы перечисления, которая, как позже было показано, связана с числами Шредера-Гиппарха . [7] [8][9] Ранее в Стомахионе , Архимед (третий век до н.э.)возможнорассмотрел ряд конфигураций плиточных головоломок , [10] в то время как комбинаторные интересывозможноприсутствовали в утерянных произведениях Аполлония . [11] [12]
В средние века комбинаторика продолжала изучаться, в основном за пределами европейской цивилизации . Индийский математик Махавира (с. 850) , при условии формулы для числа перестановок и комбинаций , [13] [14] , и эти формулы могут быть знакомы индийских математиков уже в 6 - м веке CE. [15] философ и астроном рабби Авраама ибн Эзры (с. 1140) установили симметрию биномиальных коэффициентов , в то время как замкнутая формула была получена позднее в талмудистаи математик Леви бен Герсон (более известный как Герсонид) в 1321 году. [16] Арифметический треугольник - графическая диаграмма, показывающая отношения между биномиальными коэффициентами - был представлен математиками в трактатах, датируемых еще 10 веком, и в конечном итоге будет стали известны как треугольник Паскаля . Позже, в средневековой Англии , кампанология предоставила примеры того, что сейчас известно как гамильтоновы циклы в некоторых графах Кэли на перестановках. [17] [18]
В эпоху Возрождения , вместе с остальной математикой и науками , комбинаторика пережила второе рождение. Работы Паскаля , Ньютона , Якоба Бернулли и Эйлера стали основополагающими в новой области. В наше время работы Дж. Дж. Сильвестра (конец 19 века) и Перси Мак-Магона (начало 20 века) помогли заложить основы перечислительной и алгебраической комбинаторики . В то же время теория графов также вызвала бурный интерес, особенно в связи с проблемой четырех цветов .
Во второй половине 20 века комбинаторика стала быстро развиваться, что привело к созданию десятков новых журналов и конференций по этой теме. [19] Частично рост был вызван новыми связями и приложениями в других областях, от алгебры до теории вероятностей, от функционального анализа до теории чисел и т. Д. Эти связи стирают границы между комбинаторикой и частями математики и теоретической информатики. но в то же время привело к частичной фрагментации поля.
Подходы и разделы комбинаторики [ править ]
Перечислительная комбинаторика [ править ]
Перечислительная комбинаторика - это наиболее классическая область комбинаторики, которая концентрируется на подсчете количества определенных комбинаторных объектов. Хотя подсчет количества элементов в наборе - довольно обширная математическая задача , многие проблемы, возникающие в приложениях, имеют относительно простое комбинаторное описание. Числа Фибоначчи - это основной пример проблемы перечислительной комбинаторики. Двенадцатикратный способ обеспечивает единую основу для подсчета подстановок , комбинаций и разделы .
Аналитическая комбинаторика [ править ]
Аналитическая комбинаторика касается перечисления комбинаторных структур с использованием инструментов комплексного анализа и теории вероятностей . В отличие от перечислительной комбинаторики, которая использует явные комбинаторные формулы и производящие функции для описания результатов, аналитическая комбинаторика направлена на получение асимптотических формул .
Теория разделов [ править ]
Теория разбиения изучает различные проблемы перечисления и асимптотики, связанные с целочисленными разбиениями , и тесно связана с q-рядами , специальными функциями и ортогональными многочленами . Первоначально он был частью теории чисел и анализа , но теперь считается частью комбинаторики или самостоятельной области. Он включает в себя биективный подход и различные инструменты анализа и аналитической теории чисел и связан со статистической механикой .
Теория графов [ править ]
Графы - фундаментальные объекты комбинаторики. Соображения теории графов варьируются от перечисления (например, количества графов на n вершинах с k ребрами) до существующих структур (например, гамильтоновых циклов) до алгебраических представлений (например, учитывая граф G и два числа x и y , выполняет ли Tutte многочлен T G ( x , y ) имеют комбинаторную интерпретацию?). Хотя между теорией графов и комбинаторикой существует очень сильная связь, их иногда считают отдельными предметами. [20] Хотя комбинаторные методы применимы ко многим задачам теории графов, эти две дисциплины обычно используются для поиска решений различных типов проблем.
Теория дизайна [ править ]
Теория дизайна - это исследование комбинаторных планов , которые представляют собой коллекции подмножеств с определенными свойствами пересечения . Блочные конструкции - это комбинаторные конструкции особого типа. Эта область - одна из старейших частей комбинаторики, например , проблема школьницы Киркмана, предложенная в 1850 году. Решение проблемы является частным случаем системы Штейнера, системы которой играют важную роль в классификации конечных простых групп . Эта область связана с теорией кодирования и геометрической комбинаторикой.
Конечная геометрия [ править ]
Конечная геометрия - это изучение геометрических систем, имеющих только конечное число точек. Структуры, аналогичные тем, которые встречаются в непрерывных геометриях ( евклидова плоскость , реальное проективное пространство и т. Д.), Но определенные комбинаторно, являются основными изучаемыми объектами. Эта область предоставляет богатый источник примеров по теории дизайна . Не следует путать с дискретной геометрией ( комбинаторной геометрией ).
Теория порядка [ править ]
Теория порядка - это изучение частично упорядоченных множеств , как конечных, так и бесконечных. Различные примеры частичных порядков появляются в алгебре , геометрии, теории чисел, а также в комбинаторике и теории графов. Известные классы и примеры частичных порядков включают решетки и булевы алгебры .
Теория матроидов [ править ]
Теория матроидов абстрагирует часть геометрии . Он изучает свойства наборов (обычно конечных наборов) векторов в векторном пространстве, которые не зависят от конкретных коэффициентов в отношении линейной зависимости . Не только структура, но и перечислительные свойства принадлежат теории матроидов. Теория матроидов была введена Хасслером Уитни и изучалась как часть теории порядка. Теперь это независимая область исследований, имеющая ряд связей с другими частями комбинаторики.
Экстремальная комбинаторика [ править ]
Экстремальная комбинаторика изучает экстремальные вопросы о системах множеств . Типы вопросов, рассматриваемых в этом случае, касаются максимально возможного графа, удовлетворяющего определенным свойствам. Например, наибольший граф без треугольников с 2n вершинами - это полный двудольный граф K n, n . Часто бывает слишком сложно даже найти точный экстремальный ответ f ( n ), и можно дать только асимптотическую оценку .
Теория Рамсея - еще одна часть экстремальной комбинаторики. В нем говорится, что любая достаточно большая конфигурация будет содержать некоторый порядок. Это продвинутое обобщение принципа «ящика» .
Вероятностная комбинаторика [ править ]
В вероятностной комбинаторике вопросы относятся к следующему типу: какова вероятность определенного свойства для случайного дискретного объекта, такого как случайный граф ? Например, каково среднее количество треугольников в случайном графе? Вероятностные методы также используются для определения существования комбинаторных объектов с определенными заданными свойствами (для которых может быть трудно найти явные примеры), просто наблюдая, что вероятность случайного выбора объекта с этими свойствами больше 0. Этот подход ( часто упоминаются как в вероятностном методе ) доказала свою высокую эффективность в применении к экстремальной комбинаторике и теориям графов. Близким направлением является изучение конечных цепей Маркова., особенно на комбинаторных объектах. Здесь снова используются вероятностные инструменты для оценки времени перемешивания .
Вероятностная комбинаторика, которую часто связывают с Полом Эрдёшем , который проделал новаторскую работу по этому вопросу, традиционно рассматривалась как набор инструментов для изучения проблем в других частях комбинаторики. Однако с ростом приложений для анализа алгоритмов в информатике , а также классической теории вероятностей, аддитивной теории чисел и вероятностной теории чисел , эта область недавно превратилась в независимую область комбинаторики.
Алгебраическая комбинаторика [ править ]
Алгебраическая комбинаторика - это область математики, которая использует методы абстрактной алгебры , особенно теорию групп и теорию представлений , в различных комбинаторных контекстах и, наоборот, применяет комбинаторные методы к задачам алгебры . Алгебраическая комбинаторика постоянно расширяет свои возможности как по темам, так и по методам, и может рассматриваться как область математики, в которой взаимодействие комбинаторных и алгебраических методов особенно сильно и существенно.
Комбинаторика слов [ править ]
Комбинаторика слов занимается формальными языками . Он возник независимо в нескольких разделах математики, включая теорию чисел , теорию групп и вероятность . Он имеет приложения к перечислительной комбинаторике, фрактальному анализу , теоретической информатике , теории автоматов и лингвистике . Хотя многие приложения являются новыми, классическая иерархия классов формальных грамматик Хомского – Шютценбергера, возможно, является самым известным результатом в этой области.
Геометрическая комбинаторика [ править ]
Геометрическая комбинаторика связана с выпуклой и дискретной геометрией , в частности с полиэдральной комбинаторикой . Например, он спрашивает, сколько граней каждого измерения может иметь выпуклый многогранник . Метрические свойства многогранников также играют важную роль, например теорема Коши о жесткости выпуклых многогранников. Также рассматриваются специальные многогранники, такие как пермутоэдры , ассоциэдры и многогранники Биркгофа . Комбинаторная геометрия - это старомодное название дискретной геометрии.
Топологическая комбинаторика [ править ]
Комбинаторные аналоги концепций и методов в топологии используются для изучения раскраски графов , справедливого деления , разбиений , частично упорядоченных множеств , деревьев решений , задач ожерелья и дискретной теории Морса . Не следует путать ее с комбинаторной топологией, которая является более старым названием алгебраической топологии .
Арифметическая комбинаторика [ править ]
Арифметическая комбинаторика возникла в результате взаимодействия теории чисел , комбинаторики, эргодической теории и гармонического анализа . Речь идет о комбинаторных оценках, связанных с арифметическими операциями (сложение, вычитание, умножение и деление). Аддитивная теория чисел (иногда также называемая аддитивной комбинаторикой) относится к частному случаю, когда задействованы только операции сложения и вычитания. Один важный методом в арифметической комбинаторике является эргодической теорией о динамических системах .
Бесконечная комбинаторика [ править ]
Бесконечная комбинаторика или комбинаторная теория множеств - это расширение идей комбинаторики на бесконечные множества. Это часть теории множеств , области математической логики , но в ней используются инструменты и идеи как из теории множеств, так и из экстремальной комбинаторики.
Джан-Карло Рота использовал название непрерывной комбинаторики [21] для описания геометрической вероятности , поскольку существует много аналогий между счетом и мерой .
Связанные поля [ править ]
Комбинаторная оптимизация [ править ]
Комбинаторная оптимизация - это исследование оптимизации на дискретных и комбинаторных объектах. Это началось как часть комбинаторики и теории графов, но теперь рассматривается как ветвь прикладной математики и информатики, связанных с исследования операций , теории алгоритмов и теории сложности вычислений .
Теория кодирования [ править ]
Теория кодирования началась как часть теории проектирования с ранних комбинаторных построений кодов с исправлением ошибок . Основная идея предмета - разработать эффективные и надежные методы передачи данных. Сейчас это большая область исследований, часть теории информации .
Дискретная и вычислительная геометрия [ править ]
Дискретная геометрия (также называемая комбинаторной геометрией) также зародилась как часть комбинаторики, с первых результатов по выпуклым многогранникам и числам поцелуев . С появлением приложений дискретной геометрии к вычислительной геометрии эти две области частично объединились и стали отдельной областью исследований. Остается много связей с геометрической и топологической комбинаторикой, которые сами по себе можно рассматривать как продукт ранней дискретной геометрии.
Комбинаторика и динамические системы [ править ]
Комбинаторные аспекты динамических систем - еще одна развивающаяся область. Здесь динамические системы могут быть определены на комбинаторных объектах. См. Например графическую динамическую систему .
Комбинаторика и физика [ править ]
Между комбинаторикой и физикой , особенно статистической физикой, усиливается взаимодействие . Примеры включают точное решение модели Изинга и связь между моделью Поттса, с одной стороны, и хроматическими многочленами и полиномами Тутте, с другой.
См. Также [ править ]
- Комбинаторная биология
- Комбинаторная химия
- Комбинаторный анализ данных
- Комбинаторная теория игр
- Комбинаторная теория групп
- Список тем комбинаторики
- Филогенетика
- Метод полиномов в комбинаторике
Заметки [ править ]
- ↑ Пак, Игорь. "Что такое комбинаторика?" . Проверено 1 ноября 2017 года .
- ^ Ryser 1963 , стр. 2
- ^ Мирский, Leon (1979), "Книжное обозрение" (PDF) , Бюллетень Американского математического общества , Новая серия, 1 : 380-388, DOI : 10,1090 / S0273-0979-1979-14606-8
- ^ Рота, Джан Карло (1969). Дискретные мысли . Birkhaüser. п. 50.
... комбинаторная теория была матерью нескольких наиболее активных разделов современной математики, которые стали независимыми ...
Типичный ... случай этого - алгебраическая топология (ранее известная как комбинаторная топология)
- ^ Бьорнер и Стэнли, с. 2
- ^ Lovász, Ласло (1979). Комбинаторные задачи и упражнения . Северная Голландия. ISBN 9780821842621.
На мой взгляд, комбинаторика выросла из этой ранней стадии.
- ^ Acerbi, F. (2003). «На плечах Гиппарха» . Архив истории точных наук . 57 (6): 465–502. DOI : 10.1007 / s00407-003-0067-0 . S2CID 122758966 .
- ^ Стэнли, Ричард П .; «Гиппарх, Плутарх, Шредер и Хаф», American Mathematical Monthly 104 (1997), нет. 4, 344–350.
- ^ Habsieger, Лоран; Казарян, Максим; Ландо, Сергей (1998). «О втором номере Плутарха». Американский математический ежемесячник . 105 (5): 446. DOI : 10,1080 / 00029890.1998.12004906 .
- ^ Netz, R .; Acerbi, F .; Уилсон, Н. "К реконструкции желудка Архимеда" . Sciamvs . 5 : 67–99.
- ^ Hogendijk, Ян П. (1986). «Арабские следы утраченных произведений Аполлония» . Архив истории точных наук . 35 (3): 187–253. ISSN 0003-9519 .
- ^ Хаксли, Г. (1967). «Окитокион» . Греческие, римские и византийские исследования . 8 (3): 203–203.
- ^ О'Коннор, Джон Дж .; Робертсон, Эдмунд Ф. , «Комбинаторика» , архив истории математики MacTutor , Университет Сент-Эндрюс.
- ^ Puttaswamy, Tumkur К. (2000). «Математические достижения древних индийских математиков». В Селине, Хелайне (ред.). Математика в разных культурах: история незападной математики . Нидерланды: Kluwer Academic Publishers. п. 417. ISBN 978-1-4020-0260-1.
- ^ Биггс, Норман Л. (1979). «Корни комбинаторики». Historia Mathematica . 6 (2): 109–136. DOI : 10.1016 / 0315-0860 (79) 90074-0 .
- ^ Майстров, Л.Е. (1974), Теория вероятностей: исторический очерк , Academic Press, p. 35, ISBN 978-1-4832-1863-2. (Перевод с русского ред. 1967 г.)
- ^ Белый, Артур Т. (1987). "Звонки косеток". Американский математический ежемесячник . 94 (8): 721–746. DOI : 10.1080 / 00029890.1987.12000711 .
- ^ Белый, Артур Т. (1996). «Фабиан Стедман: первый теоретик групп?». Американский математический ежемесячник . 103 (9): 771–778. DOI : 10.1080 / 00029890.1996.12004816 .
- ^ См. Журналы по комбинаторике и теории графов
- ^ Сандерс, Дэниел П .; 2-значный MSC Сравнение архивации 2008-12-31 в Wayback Machine
- ^ Непрерывная и бесконечная комбинаторика
Ссылки [ править ]
- Бьёрнер, Андерс; и Стэнли, Ричард П .; (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 .
- Гиперкнига комбинаторики , сборник ссылок на математические статьи.
- «Две культуры математики» В. Т. Гауэрса, статья о решении проблем и построении теории.
- «Словарь терминов комбинаторики»
- Список программ комбинаторики и баз данных