Комбинаторика - Combinatorics
Комбинаторика - это область математики, которая в первую очередь занимается счетом как средством и целью получения результатов, а также определенными свойствами конечных структур . Он тесно связан со многими другими областями математики и имеет множество приложений, от логики до статистической физики , от эволюционной биологии до информатики и т. Д.
Не все согласны с полным объемом комбинаторики. По словам Х. Дж. Райзера , определение предмета сложно, потому что оно пересекает так много математических подразделений. Поскольку область может быть описана типами проблем, которые она решает, комбинаторика занимается:
- перечисление (подсчет) из указанных структур, иногда называемых механизмов или конфигураций в самом общем смысле, связанный с конечными системами,
- существование таких структур , которые удовлетворяют определенные заданные критерии,
- строительство этих сооружений, возможно , во многих отношениях, и
- оптимизация : поиск «лучшей» структуры или решения среди нескольких возможностей, будь то «наибольшая», «наименьшая» или удовлетворяющая какому-либо другому критерию оптимальности .
Леон Мирский сказал: «Комбинаторика - это набор взаимосвязанных исследований, которые имеют что-то общее, но при этом сильно различаются по своим целям, методам и степени согласованности, которой они достигли». Один из способов определить комбинаторику - это, возможно, описать ее подразделения с их проблемами и методами. Это подход, который используется ниже. Однако есть и чисто исторические причины для включения или исключения некоторых тем под зонтиком комбинаторики. Хотя в первую очередь они связаны с конечными системами, некоторые комбинаторные вопросы и методы могут быть расширены до бесконечных (в частности, счетных ), но дискретных условий .
Комбинаторика хорошо известна широтой решаемых ею проблем. Комбинаторные проблемы возникают во многих областях чистой математики , особенно в алгебре , теории вероятностей , топологии и геометрии , а также во многих областях ее приложений. Многие комбинаторные вопросы исторически рассматривались изолированно, давая специальное решение проблемы, возникающей в некотором математическом контексте. Однако в конце двадцатого века были разработаны мощные и общетеоретические методы, превратившие комбинаторику в самостоятельный раздел математики. Одна из старейших и наиболее доступных частей комбинаторики - теория графов , которая сама по себе имеет многочисленные естественные связи с другими областями. Комбинаторика часто используется в информатике для получения формул и оценок при анализе алгоритмов .
Математик , который изучает комбинаторику называется combinatorialist .
История
![](https://upload.wikimedia.org/wikipedia/commons/thumb/0/0b/Plain-bob-minor_2.png/150px-Plain-bob-minor_2.png)
Основные комбинаторные концепции и результаты перечисления появились во всем античном мире . В VI веке до нашей эры древний индийский врач Сушрута утверждает в « Сушрута-самхите», что можно составить 63 комбинации из 6 различных вкусов, взятых по одному, по два за раз и т. Д., Таким образом вычисляя все 2 6 - 1 возможности. Греческий историк Плутарх обсуждает спор между Хрисиппом (3 век до н.э.) и Гиппархом (2 век до н.э.) относительно довольно деликатной проблемы перечисления, которая, как позже было показано, связана с числами Шредера-Гиппарха . Раньше, в Остомахионе , Архимед (3 век до н.э.) мог учитывать количество конфигураций мозаичной головоломки , в то время как комбинаторные интересы, возможно, присутствовали в утерянных работах Аполлония .
В средние века комбинаторика продолжала изучаться, в основном за пределами европейской цивилизации . Индийский математик Махавир (с. 850) , при условии формулы для числа перестановок и комбинаций , и эти формулы могут быть знакомы с индийскими математиками еще в 6 веке н.э.. Философ и астроном Рав Авраам ибн Эзра (с. 1140) установили симметрию биномиальных коэффициентов , в то время как замкнутая формула была получена позднее в талмудиста и математик Леви бен Герсон (более известный как Герсонид), в 1321 арифметической-треугольник в графическая диаграмма, показывающая отношения между биномиальными коэффициентами, была представлена математиками в трактатах, датируемых еще 10 веком, и в конечном итоге стала известна как треугольник Паскаля . Позже, в средневековой Англии , кампанология предоставила примеры того, что сейчас известно как гамильтоновы циклы в некоторых графах Кэли на перестановках.
В эпоху Возрождения , вместе с остальной математикой и науками , комбинаторика пережила второе рождение. Работы Паскаля , Ньютона , Якоба Бернулли и Эйлера стали основополагающими в новой области. В наше время работы Дж. Дж. Сильвестра (конец 19 века) и Перси Мак-Магона (начало 20 века) помогли заложить основы перечислительной и алгебраической комбинаторики . В то же время теория графов также вызвала бурный интерес, особенно в связи с проблемой четырех цветов .
Во второй половине 20-го века комбинаторика стала быстро развиваться, что привело к созданию десятков новых журналов и конференций по этой теме. Частично этот рост был вызван новыми связями и приложениями в других областях, от алгебры до теории вероятностей, от функционального анализа до теории чисел и т. Д. Эти связи стирают границы между комбинаторикой и частями математики и теоретической информатики, но на самом деле В то же время привело к частичной фрагментации поля.
Подходы и разделы комбинаторики
Перечислительная комбинаторика
Перечислительная комбинаторика - это наиболее классическая область комбинаторики, которая концентрируется на подсчете количества определенных комбинаторных объектов. Хотя подсчет количества элементов в наборе - довольно обширная математическая задача , многие проблемы, возникающие в приложениях, имеют относительно простое комбинаторное описание. Числа Фибоначчи - это основной пример проблемы перечислительной комбинаторики. Двенадцатикратный способ обеспечивает единую основу для подсчета подстановок , комбинаций и разделы .
Аналитическая комбинаторика
Аналитическая комбинаторика касается перечисления комбинаторных структур с использованием инструментов комплексного анализа и теории вероятностей . В отличие от перечислительной комбинаторики, которая использует явные комбинаторные формулы и производящие функции для описания результатов, аналитическая комбинаторика направлена на получение асимптотических формул .
Теория разделов
Теория разбиения изучает различные проблемы перечисления и асимптотики, связанные с целочисленными разбиениями , и тесно связана с q-рядами , специальными функциями и ортогональными многочленами . Первоначально он был частью теории чисел и анализа , но теперь считается частью комбинаторики или самостоятельной области. Он включает в себя биективный подход и различные инструменты анализа и аналитической теории чисел и связан со статистической механикой .
Теория графов
Графы - фундаментальные объекты комбинаторики. Соображения теории графов варьируются от перечисления (например, количества графов на n вершинах с k ребрами) до существующих структур (например, гамильтоновых циклов) до алгебраических представлений (например, учитывая граф G и два числа x и y , выполняет ли Tutte многочлен T G ( x , y ) имеют комбинаторную интерпретацию?). Хотя между теорией графов и комбинаторикой существует очень сильная связь, их иногда считают отдельными предметами. Хотя комбинаторные методы применимы ко многим задачам теории графов, эти две дисциплины обычно используются для поиска решений различных типов проблем.
Теория дизайна
Теория дизайна - это исследование комбинаторных планов , которые представляют собой коллекции подмножеств с определенными свойствами пересечения . Блочные конструкции - это комбинаторные конструкции особого типа. Эта область - одна из старейших частей комбинаторики, например , проблема школьницы Киркмана, предложенная в 1850 году. Решение проблемы является частным случаем системы Штейнера, системы которой играют важную роль в классификации конечных простых групп . Эта область связана с теорией кодирования и геометрической комбинаторикой.
Конечная геометрия
Конечная геометрия - это изучение геометрических систем, имеющих только конечное число точек. Структуры, аналогичные тем, которые встречаются в непрерывных геометриях ( евклидова плоскость , реальное проективное пространство и т. Д.), Но определенные комбинаторно, являются основными объектами изучения. Эта область предоставляет богатый источник примеров по теории дизайна . Не следует путать с дискретной геометрией ( комбинаторной геометрией ).
Теория порядка
Теория порядка - это изучение частично упорядоченных множеств , как конечных, так и бесконечных. Различные примеры частичных порядков появляются в алгебре , геометрии, теории чисел, а также в комбинаторике и теории графов. Известные классы и примеры частичных порядков включают решетки и булевы алгебры .
Теория матроидов
Теория матроидов абстрагирует часть геометрии . Он изучает свойства наборов (обычно конечных наборов) векторов в векторном пространстве, которые не зависят от конкретных коэффициентов в отношении линейной зависимости . Не только структура, но и перечислительные свойства принадлежат теории матроидов. Теория матроидов была введена Хасслером Уитни и изучалась как часть теории порядка. Теперь это независимая область исследований, имеющая ряд связей с другими частями комбинаторики.
Экстремальная комбинаторика
Экстремальная комбинаторика изучает экстремальные вопросы о системах множеств . Типы вопросов, рассматриваемых в этом случае, касаются максимально возможного графа, удовлетворяющего определенным свойствам. Например, наибольший граф без треугольников с 2n вершинами - это полный двудольный граф K n, n . Часто бывает слишком сложно даже точно найти экстремальный ответ f ( n ), и можно дать только асимптотическую оценку .
Теория Рамсея - еще одна часть экстремальной комбинаторики. В нем говорится, что любая достаточно большая конфигурация будет содержать некоторый порядок. Это продвинутое обобщение принципа «ящика» .
Вероятностная комбинаторика
В вероятностной комбинаторике вопросы относятся к следующему типу: какова вероятность определенного свойства для случайного дискретного объекта, такого как случайный граф ? Например, каково среднее количество треугольников в случайном графе? Вероятностные методы также используются для определения существования комбинаторных объектов с определенными заданными свойствами (для которых может быть трудно найти явные примеры), просто наблюдая, что вероятность случайного выбора объекта с этими свойствами больше 0. Этот подход ( часто упоминаются как в вероятностном методе ) доказала свою высокую эффективность в применении к экстремальной комбинаторике и теориям графов. Близким направлением является изучение конечных цепей Маркова , особенно на комбинаторных объектах. Здесь снова используются вероятностные инструменты для оценки времени перемешивания .
Вероятностная комбинаторика, которую часто связывают с Полом Эрдёшем , который проделал новаторскую работу по этому вопросу, традиционно рассматривалась как набор инструментов для изучения проблем в других частях комбинаторики. Однако с ростом приложений для анализа алгоритмов в информатике , а также классической теории вероятностей, аддитивной теории чисел и вероятностной теории чисел , эта область недавно превратилась в независимую область комбинаторики.
Алгебраическая комбинаторика
Алгебраическая комбинаторика - это область математики, которая использует методы абстрактной алгебры , особенно теорию групп и теорию представлений , в различных комбинаторных контекстах и, наоборот, применяет комбинаторные методы к задачам алгебры . Алгебраическая комбинаторика постоянно расширяет свои возможности как по темам, так и по методам, и может рассматриваться как область математики, где взаимодействие комбинаторных и алгебраических методов особенно сильно и важно.
Комбинаторика слов
![](https://upload.wikimedia.org/wikipedia/commons/thumb/f/f1/Morse-Thue_sequence.gif/210px-Morse-Thue_sequence.gif)
Комбинаторика слов занимается формальными языками . Он возник независимо в нескольких разделах математики, включая теорию чисел , теорию групп и вероятность . Он имеет приложения к перечислительной комбинаторике, фрактальному анализу , теоретической информатике , теории автоматов и лингвистике . Хотя многие приложения являются новыми, классическая иерархия классов формальных грамматик Хомского – Шютценбергера, возможно, является самым известным результатом в этой области.
Геометрическая комбинаторика
![](https://upload.wikimedia.org/wikipedia/commons/thumb/b/b7/Icosahedron.svg/150px-Icosahedron.svg.png)
Геометрическая комбинаторика связана с выпуклой и дискретной геометрией , в частности с полиэдральной комбинаторикой . Например, он спрашивает, сколько граней каждого измерения может иметь выпуклый многогранник . Метрические свойства многогранников также играют важную роль, например теорема Коши о жесткости выпуклых многогранников. Также рассматриваются специальные многогранники, такие как пермутоэдры , ассоциэдры и многогранники Биркгофа . Комбинаторная геометрия - это старомодное название дискретной геометрии.
Топологическая комбинаторика
![](https://upload.wikimedia.org/wikipedia/commons/thumb/4/47/Collier-de-perles-rouge-vert.svg/150px-Collier-de-perles-rouge-vert.svg.png)
Комбинаторные аналоги концепций и методов в топологии используются для изучения раскраски графов , справедливого деления , разбиений , частично упорядоченных множеств , деревьев решений , задач ожерелья и дискретной теории Морса . Не следует путать ее с комбинаторной топологией, которая является более старым названием алгебраической топологии .
Арифметическая комбинаторика
Арифметическая комбинаторика возникла в результате взаимодействия теории чисел , комбинаторики, эргодической теории и гармонического анализа . Речь идет о комбинаторных оценках, связанных с арифметическими операциями (сложение, вычитание, умножение и деление). Аддитивная теория чисел (иногда также называемая аддитивной комбинаторикой) относится к частному случаю, когда задействованы только операции сложения и вычитания. Один важный методом в арифметической комбинаторике является эргодической теорией о динамических системах .
Бесконечная комбинаторика
Бесконечная комбинаторика или комбинаторная теория множеств - это расширение идей комбинаторики на бесконечные множества. Это часть теории множеств , области математической логики , но в ней используются инструменты и идеи как из теории множеств, так и из экстремальной комбинаторики.
Джан-Карло Рота использовал название непрерывной комбинаторики для описания геометрической вероятности , поскольку существует много аналогий между счетом и мерой .
Связанные поля
Комбинаторная оптимизация
Комбинаторная оптимизация - это исследование оптимизации на дискретных и комбинаторных объектах. Это началось как часть комбинаторики и теории графов, но теперь рассматривается как ветвь прикладной математики и информатики, связанных с исследования операций , теории алгоритмов и теории сложности вычислений .
Теория кодирования
Теория кодирования началась как часть теории проектирования с ранних комбинаторных построений кодов с исправлением ошибок . Основная идея предмета - разработать эффективные и надежные методы передачи данных. Сейчас это большая область исследований, часть теории информации .
Дискретная и вычислительная геометрия
Дискретная геометрия (также называемая комбинаторной геометрией) также зародилась как часть комбинаторики, с первых результатов о выпуклых многогранниках и числах поцелуев . С появлением приложений дискретной геометрии к вычислительной геометрии эти две области частично объединились и стали отдельной областью исследований. Остается много связей с геометрической и топологической комбинаторикой, которые сами по себе можно рассматривать как продукт ранней дискретной геометрии.
Комбинаторика и динамические системы
Комбинаторные аспекты динамических систем - еще одна развивающаяся область. Здесь динамические системы могут быть определены на комбинаторных объектах. См. Например графическую динамическую систему .
Комбинаторика и физика
Между комбинаторикой и физикой , особенно статистической физикой, усиливается взаимодействие . Примеры включают точное решение модели Изинга и связь между моделью Поттса, с одной стороны, и хроматическими многочленами и полиномами Тутте, с другой.
Смотрите также
Примечания
использованная литература
- Бьёрнер, Андерс; и Стэнли, Ричард П .; (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 .
- Гиперкнига комбинаторики , сборник ссылок на математические статьи.
- «Две культуры математики» В. Т. Гауэрса, статья о решении проблем и построении теории.
- «Словарь терминов комбинаторики»
- Список программ комбинаторики и баз данных