Комбинато́рика (Комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисление элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей, и имеет широкий спектр применения, например в информатике и статистической физике.
Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».
Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.
Примеры комбинаторных конфигураций и задач[]
Для формулировки и решения комбинаторных задач используют различные модели комбинаторных конфигураций. Примерами комбинаторных конфигураций являются:
- Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества.
- Перестановкой из n элементов (обычно чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.
- Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
- Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел.
- Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.
Примерами комбинаторных задач являются:
- Сколькими способами можно разместить n предметов по m ящикам так, чтобы выполнялись заданные ограничения?
- Сколько существует функций из m-элементного множества в n-элементное, удовлетворяющих заданным ограничениям?
- Сколько существует различных перестановок из 52 игральных карт?
- Ответ: 52! (52 факториал) то есть 80658175170943878571660636856403766975289505440883277824000000000000 или примерно 8.0658 × 1067.
- При игре в кости бросаются две кости и выпавшие очки складываются, сколько существует комбинаций, таких, что сумма очков на верхних гранях равна двенадцати?
- Решение: Каждый возможный исход соответствует функции (аргумент функции - это номер кости, значение - очки на верхней грани). Очевидно, что лишь 6+6 даёт нам нужный результат 12. Таким образом существует лишь одна функция, ставящая в соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего одна комбинация, такая, что сумма очков на верхних гранях равна двенадцати.
Разделы комбинаторики[]
Перечислительная комбинаторика[]
Перечислительная комбинаторика (или исчисляющая комбинаторика) рассматривает задачи о перечислении или подсчёте количества различных конфигураций (например, перестановок) образуемых элементами конечных множеств, на которые могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.
Количество конфигураций, образованных несколькими манипуляциями над множеством, подсчитывается согласно правилам сложения и умножения.
Типичным примером задач данного раздела является подсчёт количества перестановок (см. выше). Число перестановок n-элементного множества равно факториалу числа n, то есть n!. Другой пример — известная Задача о письмах.
Структурная комбинаторика[]
К данному разделу относятся некоторые вопросы теории графов, а также теории матроидов.
Экстремальная комбинаторика[]
Примером этого раздела может служить следующая задача: какова наибольшая размерность графа, удовлетворяющего определённым свойствам.
Теория Рамсея[]
Теория Рамсея изучает наличие регулярных структур в случайных конфигурациях элементов. Примером утверждения из теории Рамсея может служить следующее:
- в группе из 6 человек всегда можно найти трёх человек, которые либо попарно знакомы друг с другом, либо попарно незнакомы.
В терминах структурной комбинаторики это же утверждение формулируется так:
- в любом графе с 6 вершинами найдётся либо клика, либо независимое множество размера 3.
Вероятностная комбинаторика[]
Этот раздел отвечает на вопросы вида: какова вероятность присутствия определённого свойства у заданного множества.
Топологическая комбинаторика[]
Аналоги комбинаторных концепций и методов используются и в топологии, при изучении дерева принятия решений, частично упорядоченных множеств, раскрасок графа и др.
См. также[]
- Оптимизация
Литература[]
- Ерош И. Л. Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 c.
- Андерсон Джеймс Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. — М.: «Вильямс», 2006. — С. 960. — ISBN 0-13-086998-8
- Р. Стенли Перечислительная комбинаторика = Enumerative Combinatorics. — М.: «Мир», 1990. — С. 440. — ISBN 5-03-001348-2
- Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980. — 476 с.
- Риордан Дж. Введение в комбинаторный анализ. — пер. с англ.. — М.: 1963.
- Раизер Г. Дж. Комбинаторная математика. — пер. с англ.. — М.: 1966.
- Липский В. Комбинаторика для программиста. — М.: Мир, 1988. — 213 с.
- Виленкин Н.Я. Популярная комбинаторика. — М.: Наука, 1975.
- Райгородский А. М. Линейно-алгебраические и вероятностные методы в комбинаторике. — Летняя школа «Современная математика». — Дубна: 2006.
Ссылки[]
- Теория вероятностей. 3. Элементы комбинаторики
- Белешко Д. Комбинаторика. 2004.
- http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%B8%D0%BA%D0%B0 Википедия. Комбинаторика
![]() |
Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её. |