Комбинато́рика (Комбинаторный анализ) - раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике).
Термин введен Лейбницем в 1666 г.
Для формулировки и решения комбинаторных задач используют различные модели комбинаторных конфигураций. Примерами комбинаторных конфигураций являются:
- Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества.
- Перестановкой из n элементов (например чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.
- Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
- Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел.
- Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.
Примеры комбинаторных задач:
- Сколькими способами можно разместить n предметов по m ящикам, чтобы выполнялись заданные ограничения?
- Сколько существует функций F из m-элементного множества в n-элементное, удовлетворяющих заданным ограничениям?
- Сколько существует различных перестановок из 52 игральных карт? Ответ: 52! (52 факториал), то есть, 80658175170943878571660636856403766975289505440883277824000000000000 или примерно 8,0658 × 1067.
- При игре в кости бросаются две кости, и выпавшие очки складываются; сколько существует комбинаций, в которых сумма очков на верхних гранях равна двенадцати?
Решение: Каждый возможный исход соответствует функции (аргумент функции — это номер кости, значение — очки на верхней грани). Очевидно, что лишь 6+6 даёт нам нужный результат 12. Таким образом, существует лишь одна функция, ставящая в соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего одна комбинация, при которой сумма очков на верхних гранях равна двенадцати.
Разделы комбинаторики: Перечислительная комбинаторика, Структурная комбинаторика, Экстремальная комбинаторика, Теория Рамсея, Вероятностная комбинаторика, Топологическая комбинаторика, Инфинитарная комбинаторика.