3.4. Сочетания, структура соединений

Вернемся к задаче о размещениях, как к построению всех функций на декартовом произведении r‑S и n‑X мно­жеств.

Из изложенного в 3.3 следует, что множество всех та­ких функций можно представить в виде двух непе­ре­се­ка­ющихся множеств: функций c повторениями значений и инъек­тивных функций.

Покажем, что инъективные функции можно разбить на классы эквивалентности.

Ясно, что если r > n, то множество инъективных функ­ций пусто. Это непосредственно вытекает из формулы (3.7). Поэтому будем считать, что r  n.

Скажем, что элементы y = x₁, x₂, … x_r и y' = x'₁, x'₂, … x'_r эквивалентны, если найдется такая подстановка f, что f(y) = y'.

Покажем, что это отношение рефлексивно, сим­мет­рично и транзитивно и, следовательно, разбивает все мно­жество инъективных функций y на классы.

Действительно, рефлексивность следует из суще­ствования единичной подстановки е(y) = y, симметричность вытекает из существования обратной подстановки: если f(y) = y', то f^-1(y') = y, транзитивность определяется правилом произведения подстановок: если f₁(y) = y', а f₂(y') = y'', то f₂f₁(y) = y''.

Рассмотрим теперь вопросы о построении и числе классов эквивалентности.

Для построения любого класса эквивалентности выбе­рем произвольную инъективную функцию y = x₁, x₂, … x_r  и построим все перестановки ее значений. Таких пере­становок будет r! Множество всех этих перестановок образует класс функций, замкнутый относительно все­воз­мо­жных подстановок на множестве {x₁, x₂, … x_r}. В качестве представителя класса можно выбрать любую из этих функций. Мы выберем такую, для которой x₁ < x₂ < …< x_r.

Если r = n, то этими подстановками исчерпывается все множество инъективных функций, поскольку r! = A_r^r, в противном случае найдется функция со значениями x'₁, x'₂, …, x'_r, из которых хотя бы одно отлично от любых других из всех предыдущих перестановок. Но тогда вместе с ней имеем еще r! перестановок, соответствующих новому классу инъективных функций. Представитель полученного класса снова выберем так, чтобы было выполнено x'₁< x'₂ < …< x'_r.

Поступая аналогично, построим все классы эквивалентности.

Обозначим число всех классов эквивалентности — m.

Поскольку каждый класс эквивалентности содержит r! инъективных функций, определенных на {x₁, x₂, …, x_r} и при этом имеем все классы, то m∙r! = A_n^r. Следовательно,

m = A_n^r / r!. (3.12)

Отношение A_n^r / r! имеет специальные обозначения:

n

r либо C_n^r.

(Первое читается: n над r, второе — С из n по r.)

Число C_n^r определяет количество классов перестановок в разбиении множества инъективных функций на классы. Каждый такой класс полностью определяется своим представителем, для которого выполнено: x₁< x₂ < …< x_r. Поэтому можно считать, что C_n^r определяет мощность множества всех упорядоченных r‑ок, со значениями в n‑X. Это множество имеет специальное наименование: сочетания. Имеется и другое название: r‑подмножества n‑X множества.

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

Теорема 3.4 Сочетания из n различных эле­мен­тов по r (n ≥ r) эквивалентны множеству классов упо­рядоченных размещений, инвариантных относи­тельно всех перестановок входящих в них элементов. Число этих классов равно

C_n^r = A_n^r / r! = n! / (r!(n - r)!).

Пример структуры соединений представлен на рисунке 3.4

Числа C_n^r исторически известны, как биномиальные коэффициенты. Они обладают рядом интересных свойств, которые будут рассмотрены в следующем разделе.