Теория конфигураций и теория перечисления

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

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

Правило суммы

Если элемент A можно выбрать m способами, а элемент B можно выбрать k способами, то выбор элемента A или B можно осуществить m + k способами.

Правило суммы можно перефразировать на теоретико-множественном языке. Обозначим через | A | число элементов множества A, через A B - объединение множеств A и B, через AxB - декартово произведение множеств A и B. Тогда для непересекающихся множеств A и B выполняется равенство:

| A B | = | A | + | B |.

Обобщением правила суммы является правило произведения.

Правило произведения

Если элемент A можно выбрать m способами, а после каждого выбора элемента A элемент B можно выбрать k способами, тогда, упорядоченную пару элементов (A, B) можно выбрать m*k способами.

Правило произведения можно распространить на выбор последовательности (x₁, x₂, …, x_n) произвольной конечной длины n.

На теоретико-множественном языке правило произведения формулируется так:

| Aх B | = | A | | B |.