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

редактировать
Раздел дискретной математики

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

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

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

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

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

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

Содержание

  • 1 История
  • 2 Подходы и подполя комбинаторики
    • 2.1 Перечислительная комбинаторика
    • 2.2 Аналитическая комбинаторика
    • 2.3 Теория разделов
    • 2.4 Теория графов
    • 2.5 Теория дизайна
    • 2.6 Конечная геометрия
    • 2.7 Теория порядка
    • 2.8 Теория матроидов
    • 2.9 Экстремальная комбинаторика
    • 2.10 Вероятностная комбинаторика
    • 2.11 Алгебраическая комбинаторика
    • 2.12 Комбинаторика слов
    • 2.13 Геометрическая комбинаторика
    • 2.14 Топологическая комбинаторика
    • 2.15 Арифметическая комбинаторика
    • 2.16 Бесконечная комбинаторика
  • 3 Связанные области
    • 3.1 Комбинаторная оптимизация
    • 3.2 Теория кодирования
    • 3.3 Дискретная и вычислительная геометрия
    • 3.4 Комбинаторика и динамические системы
    • 3.5 Комбинаторика и физика
  • 4 См. Также
  • 5 Примечания
  • 6 Ссылки
  • 7 Exte ные ссылки

История

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

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

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

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

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

Подходы и подполя комбинаторики

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

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

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

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

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

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

A плоское разбиение.

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

теорией графов

графом Петерсена.

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

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

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

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

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

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

Диаграмма Хассе из powerset из {x, y, z}, упорядоченных по включению.

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

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

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

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

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

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

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

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

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

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

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

Диаграмма Юнга разбиения (5,4,1).

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

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

Построение бесконечного слова Туэ – Морса.

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

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

икосаэдр.

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

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

Разделение ожерелья двумя разрезами.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. Также

  • icon Портал математики

Примечания

Литература

  • Бьёрнер, Андерс; и Стэнли, Ричард П.; (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
  • Lindner, Charles C.; и Роджер, Кристофер А.; ред. (1997); Теория дизайна, CRC-Press; 1-й. издание (1997). ISBN 0-8493-3986-3.
  • Риордан, Джон (2002) [1958], Введение в комбинаторный анализ, Дувр, 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

Внешние ссылки

Последняя правка сделана 2021-05-15 06:21:06
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте