9. Основные понятия комбинаторики

Основная задача комбинаторики, как раздела дискретной математики, – пересчет и перечисление элементов в конечных множествах [24].

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

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

При этом под решением задачи оптимизации «в сильном смысле» понимается нахождение всех элементов минимизирующих (максимизирующих) целевую функцию, а под решением задачи оптимизации «в слабом смысле» – нахождение единственного произвольного элемента [24].

Рассмотрим основополагающие правила комбинаторики – правила суммы и произведения.

Пусть Х – конечное множество, состоящее из n элементов х. Тогда говорят, что элемент х из Х может быть выбран n способами и пишут |Х|=n. Эта запись совпадает с записью мощности множества Х.

Пусть Х₁,...,Х_k – попарно непересекающиеся множества, т.е. Х_iХ_j=, ij.

Очевидно, что в этом случае

.

Таково комбинаторное правило суммы. Для k=2 оно формулируется следующим образом. Если объект х может быть выбран n способами из множества Х, а объект y из непересекающегося с ним множества Y, – другими m способами, то выбор «х или y» может быть осуществлен n+m способами.

Правило произведения для k=2 формулируется следующим образом. Если объект х может быть выбран n способами и после каждого из таких выборов объект y в свою очередь может быть выбран m способами, то выбор упорядоченной пары – вектора (х,y) может быть осуществлен nm способами.

Например, Х:{x₁,x₂}, Y:{y₁,y₂}.

Тогда упорядоченные пары (x,y) описываются декартовым произведением

XY={(x₁,y₁),(x₁,y₂),(x₂,y₁),(x₂,y₂)}.

Выбор упорядоченной последовательности из k объектов вектора (х₁,х₂,...,х_k) может быть осуществлен n₁·n₂·...·n_k способами, где n_i – число способов выбора i-го объекта х_i, i меняется от 1 до k (записывается: ).

В частности, если все n_i равны, что может быть, например, в случае, когда элементы принадлежат одному и тому же множеству, т.е. рассматривается декартово произведение Х^k, то число способов равно n^k.

Набор элементов х_i1,...,x_ik из множества Х={x₁,...,x_n} (вектор) называется выборкой (комбинацией) объема k из n элементов или, иначе, (n,k) выборкой.

Выборка называется упорядоченной, если порядок следования элементов в ней задан. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными.

Если порядок следования элементов не является существенным, то такая выборка называется неупорядоченной.

В выборках могут допускаться и не допускаться повторения элементов, т.е. имеются выборки с повторением и выборки без повторений.