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

(перенаправлено с «Комбинаторный анализ»)

Комбинато́рика (иногда называемая комбинаторным анализом) — раздел математики, посвящённый решению задач, связанных с выбором и расположением элементов некоторого (чаще всего конечного) множества в соответствии с заданными правилами. Каждое такое правило определяет некоторую выборку из элементов исходного множества, которая называется комбинаторной конфигурацией. Простейшими примерами комбинаторных конфигураций[1][2] являются перестановки, сочетания и размещения[⇨].

Типичные задачи[1] комбинаторики[⇨]:

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

Комбинаторика тесно связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей, теорией чисел и другими[⇨]. Она применяется в самых различных областях знаний (например, в генетике, информатике, статистике, статистической физике, лингвистике).

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

Примеры комбинаторных конфигураций и задачПравить

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

  • Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества.
  • Перестановкой из n элементов (например чисел 1, 2, … n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.
  • Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
  • Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел.
  • Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.

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

  1. Сколько имеется способов разместить n предметов по m ящикам, чтобы выполнялись заданные ограничения?
  2. Сколько существует функций   из m-элементного множества в n-элементное, удовлетворяющих заданным ограничениям?
  3. Сколько существует различных перестановок из 52 игральных карт?
    Ответ: 52! (52 факториал), то есть: 80 658 175 170 943 880 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000,
или примерно  
  1. При игре в кости бросаются две кости, и выпавшие очки складываются; сколько существует комбинаций, в которых сумма очков на верхних гранях равна двенадцати?
    Решение: Каждый возможный исход соответствует функции   (аргумент функции — это номер кости, значение — очки на верхней грани). Очевидно, что лишь 6 + 6 даёт нам нужный результат 12. Таким образом, существует всего одна комбинация, при которой сумма очков на верхних гранях равна двенадцати.

ИсторияПравить

Древность и средние векаПравить

Основные комбинаторные понятия и вычислительные результаты появились в древнем мире. Классическая задача комбинаторики: «сколько есть способов извлечь m элементов из N возможных» упоминается ещё в сутрах древней Индии (начиная примерно с IV века до н. э.)[3]. Индийские математики, видимо, первыми открыли биномиальные коэффициенты и их связь с биномом Ньютона[3]. Во II веке до н. э. индийцы знали, что сумма всех биномиальных коэффициентов степени n равна  .

Комбинаторные мотивы можно заметить в символике китайской «Книги Перемен» (V век до н. э.). По мнению её авторов, всё в мире комбинируется из различных сочетаний мужского и женского начал, а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небо[4]. Историки отмечают также комбинаторные проблемы в руководствах по игре в Го и другие игры. Большой интерес математиков многих стран с древних времён неизменно вызывали магические квадраты.

Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематическое изложение ими этих вопросов, если оно и существовало, до нас не дошло. Хрисипп (III век до н. э.) и Гиппарх (II век до н. э.) подсчитывали, сколько следствий можно получить из 10 аксиом; методика подсчёта нам неизвестна, но у Хрисиппа получилось более миллиона, а у Гиппарха — более 100000[5]. Аристотель при изложении своей логики безошибочно перечислил все возможные типы трёхчленных силлогизмов. Аристоксен рассмотрел различные чередования длинных и коротких слогов в стихотворных размерах.[5] Какие-то комбинаторные правила пифагорейцы, вероятно, использовали при построении своей теории чисел и нумерологии (совершенные числа, фигурные числа, пифагоровы тройки и др.).

В Средние века комбинаторика также продолжала развиваться, в основном, за пределами европейской цивилизации. В XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями. Другой индийский математик, Махавира[en] (середина IX века), опубликовал формулы для числа перестановок и сочетаний, причём эти формулы, возможно, были знакомы индийским математикам еще в VI веке н. э. Философ и астроном рабби Авраам ибн Эзра (около 1140 года) подсчитал число размещений с перестановками в огласовках имени Бога[6]. Он же установил симметрию биномиальных коэффициентов. Точную формулу для них обнародовал позже талмудист и математик Леви бен Гершом (более известный как Герсонид) в 1321 году.

Несколько комбинаторных задач содержит «Книга абака» (Фибоначчи, XIII век). Например, он поставил задачу найти наименьшее число гирь, достаточное для взвешивания любого товара весом от 1 до 40 фунтов.

Новое времяПравить

Блез Паскаль много занимался биномиальными коэффициентами и открыл простой способ их вычисления: «треугольник Паскаля». Позднее выяснилось, что этот способ был уже известен на Востоке (примерно с X века) и он назывался арифметическим треугольником. Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого треугольника. Арифметический треугольник представляет собой графическую диаграмму, показывающую отношения между биномиальными коэффициентами. Позже, в средневековой Англии, кампанология[en] предоставила примеры того, что теперь известно как гамильтоновы циклы в графах Кэли на перестановках.

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

Сам термин «комбинаторика» придумал Лейбниц, он считается основоположником современной комбинаторики. В 1666 году (ему было тогда 20 лет) опубликовал книгу «Рассуждения о комбинаторном искусстве». Правда, термин «комбинаторика» Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику[7]. Ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике.

В этот же период формируется терминология новой науки. Термин «сочетание» (combination) впервые встречается у Паскаля (1653, опубликован в 1665 году). Термин «перестановка» (permutation) употребил в указанной книге Якоб Бернулли (хотя эпизодически он встречался и раньше). Бернулли использовал и термин «размещение» (arrangement).

После появления математического анализа обнаружилась тесная связь комбинаторных и ряда аналитических задач. Абрахам де Муавр и Джеймс Стирлинг нашли формулы для аппроксимации факториала[8].

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

Кроме перестановок и сочетаний, Эйлер изучал разбиения, а также сочетания и размещения с условиями.

Современное состояниеПравить

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

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

В начале XX века началось развитие комбинаторной геометрии: были доказаны теоремы Радона, Хелли, Юнга, Бляшке, а также строго доказана изопериметрическая теорема. На стыке топологии, анализа и комбинаторики были доказаны теоремы Борсука — Улама и Люстерника — Шнирельмана[en]. Во второй четверти XX века были поставлены проблема Борсука и проблема Нелсона — Эрдёша — Хадвигера. В 1940-х годах оформилась теория Рамсея. Отцом современной комбинаторики считается Пал Эрдёш, который ввёл в комбинаторику вероятностный анализ. Внимание к конечной математике и, в частности, к комбинаторике значительно повысилось со второй половины XX века, когда появились компьютеры. Сейчас это чрезвычайно содержательная и быстроразвивающаяся область математики.

Методы и разделы комбинаторикиПравить

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

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

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

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

Числа Фибоначчи являются типичным примером задачи в перечислительной комбинаторике, а также известная Задача о письмах. Двенадцатеричный путь обеспечивает единую структуру для подсчета перестановок, сочетаний и разбиений.

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

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

 
Плоское разбиение

Теория разбиенияПравить

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

 
Граф Петерсена

Теория графовПравить

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

Теория схемПравить

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

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

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

 
Диаграмма Хассе, булеан — {x, y,z} упорядоченный по включению

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

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

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

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

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

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

Теория РамсеяПравить

Теория Рамсея — это еще одна часть экстремальной комбинаторики. Она утверждает, что любая достаточно большая конфигурация будет содержать некоторый порядок и изучает наличие регулярных структур в случайных конфигурациях элементов. Это расширенное обобщение принципа Дирихле («принцип голубей и ящиков»). Примером утверждения из теории Рамсея может служить следующее:

в группе из 6 человек всегда можно найти трёх человек, которые либо попарно знакомы друг с другом, либо попарно незнакомы.

В терминах структурной комбинаторики это же утверждение формулируется так:

в любом графе с 6 вершинами найдётся либо клика, либо независимое множество размера 3.
 
Самоустраняющаяся прогулка по решетке

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

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

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

 
Диаграмма Юнга формы (5, 4, 1)

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

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

 
Демонстрация создания последовательности Морса — Туэ.

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

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

Комбинаторная геометрияПравить

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

 
Пример ожерелья, разделённого на k = 2 (то есть между двумя участниками дележа) и t = 2 (то есть два типа бусин, имеется 8 красных и 6 зелёных). Показаны 2 разреза — один из участников получает большую секцию, а другой получает оставшиеся два куска.

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

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

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

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

Инфинитарная комбинаторикаПравить

Инфинитарная комбинаторика (англ.) — применение идей и методов комбинаторики к бесконечным (в том числе, несчётным) множествам. Это часть теории множеств, область математической логики, но использует инструменты и идеи как теории множеств, так и экстремальной комбинаторики.

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

Связанные областиПравить

 
Контактное расположение сфер связанно как теория кодирования с дискретной геометрией

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

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

Теория кодированияПравить

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

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

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

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

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

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

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

Открытые проблемыПравить

Комбинаторика (в частности, теория Рамсея) содержит много известных открытых проблем, подчас с весьма несложной формулировкой. Например, неизвестно, при каком наименьшем   в любой группе из   человек найдутся 5 человек, либо попарно знакомых друг с другом, либо попарно незнакомых (хотя известно, что 49 человек достаточно).[9]

А также есть и другие нерешённые задачи или не доказанные гипотезы:

  • Гипотеза Адамара (1893): для каждого натурального  , делящегося на 4, существует вещественная матрица Адамара порядка  . Пояснение: известно, что делимость на 4 является лишь необходимым условием существования матрицы Адамара. Существуют различные методы построения вещественных матриц Адамара порядка   для некоторых бесконечных серий натуральных чисел, делящихся на 4, однако они не позволяют доказать гипотезу Адамара. Наименьшим порядком, кратным 4, для которого матрица Адамара неизвестна, является  [10].
  • Существование конечной проективной плоскости натурального порядка, не являющегося степенью простого числа.
  • Гипотеза Эрдёша — Реньи. Если   — фиксированное целое число  , то   для   из  . Здесь   — перманент матрицы   — множество всех   — матриц порядка   c   единицами в каждой строке и каждом столбце[11].
  • Числа Рамсея   для случая   почти не изучены[12].
  • Задача нахождения минимума перманента дважды стохастической матрицы в общем случае не решена[13].
  • Не известны необходимые и достаточные условия, при которых существует общая трансверсаль для трёх семейств подмножеств[14].

Комбинаторика в языкознанииПравить

Комбинаторика (языкознание) — это свойство единиц языка и соответствующих им единиц речи вступать в синтагматические отношения, то есть в отношения сочетаемости.

ПримечанияПравить

  1. 1 2 Сачков В. Н. Комбинаторный анализ // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1979. — Т. 2. — С. 974—979. — 1104 с.
  2. БРЭ.
  3. 1 2 Amulya Kumar Bag. Binomial theorem in ancient India. Indian J. History Sci., 1:68-74, 1966.
  4. Виленкин Н. Я., 1975, с. 7.
  5. 1 2 Виленкин Н. Я., 1975, с. 9.
  6. Краткий комментарий к Исход, 3:13.
  7. Виленкин Н. Я., 1975, с. 19.
  8. O'Connor, John; Edmund Robertson. Abraham de Moivre. The MacTutor History of Mathematics archive. Дата обращения: 31 мая 2010. Архивировано 27 апреля 2012 года.
  9. Weisstein, Eric W. Числа Рамсея (англ.) на сайте Wolfram MathWorld.
  10. МАТРИЦЫ АДАМАРА.
  11. Минк X. Перманенты.. — Мир. — 1982. — 211 с.
  12. Рыбников, 1972, с. 96.
  13. Рыбников, 1972, с. 110.
  14. Капитонова Ю. В., Кривой С. Л., Летичевский А. А. Лекции по дискретной математике. — СПб.: БХВ-Петербург, 2004. — С. 530. — 624 с. — ISBN 5-94157-546-7.

ЛитератураПравить

СсылкиПравить