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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Размещением из 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 или примерно 8,0658 ⋅ 1067.
  4. При игре в кости бросаются две кости, и выпавшие очки складываются; сколько существует комбинаций, в которых сумма очков на верхних гранях равна двенадцати?
    Решение: Каждый возможный исход соответствует функции (аргумент функции — это номер кости, значение — очки на верхней грани). Очевидно, что лишь 6 + 6 даёт нам нужный результат 12. Таким образом, существует лишь одна функция, ставящая в соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего одна комбинация, при которой сумма очков на верхних гранях равна двенадцати.

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

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

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

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

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

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

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

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

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

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

Теория разбиения изучает различные перечислительные и асимптотические задачи, связанные с разбиением натуральных чисел, и тесно связана с 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 разреза — один из участников получает большую секцию, а другой получает оставшиеся два куска.

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

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

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

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

Инфинитарная комбинаторика[править | править код]

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

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

Связанные области[править | править код]

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

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

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

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

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

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

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

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

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

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

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

Открытые проблемы[править | править код]

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

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

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

Комбинаторика в языкознании[править | править код]

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

См. также[править | править код]

Примечания[править | править код]

  1. Виленкин Н. Я., 1975, с. 19.
  2. O'Connor, John; Edmund Robertson. Abraham de Moivre. The MacTutor History of Mathematics archive (06 2004). Дата обращения: 31 мая 2010. Архивировано 27 апреля 2012 года.
  3. Weisstein, Eric W. Числа Рамсея (англ.) на сайте Wolfram MathWorld.
  4. МАТРИЦЫ АДАМАРА.
  5. Минк X. Перманенты.. — Мир. — 1982. — 211 с.
  6. Рыбников К. А. Введение в комбинаторный анализ. — МГУ, 1972. — С. 96. — 308 с.
  7. Рыбников К. А. Введение в комбинаторный анализ.. — МГУ, 1972. — С. 110. — 308 с.
  8. Капитонова Ю. В., Кривой С. Л., Летичевский А. А. Лекции по дискретной математике. — СПб: БХВ-Петербург, 2004. — С. 530. — 624 с. — ISBN 5-94157-546-7.

Литература[править | править код]

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