1 Комбинаторика. Общие понятия.
Комбинаторика (Комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике).
Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».
Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.
Для формулировки и решения комбинаторных задач используют различные модели комбинаторных конфигураций. Примерами комбинаторных конфигураций являются:
Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества;
Перестановкой из n элементов (например чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n;
Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений;
Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел;
Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.
К разделам комбинаторики относят:
Перечислительная комбинаторика;
Структурная комбинаторика;
Экстремальная комбинаторика;
Теория Рамсея;
Вероятностная комбинаторика;
Топологическая комбинаторика;
Инфинитарная комбинаторика.