1) Перестановки 2) Разрывающее множество вершин и рёбер
7

1 Комбинаторика. Общие понятия.

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

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

Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.

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

       Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества;

       Перестановкой из n элементов (например чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n;

       Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений;

       Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел;

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

К разделам комбинаторики относят:

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

            Структурная комбинаторика;

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

            Теория Рамсея;

            Вероятностная комбинаторика;

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

            Инфинитарная комбинаторика.