3.7. Соединения с повторениями

Задача построения всех размещений из n элементов по r рассмотрена в 3.1 — 3.3. Показано, что число всех разме­щений равно n^r, а среди них имеем A_n^r инъективных. Ос­тальные n^r-A_n^r размещений определим как размещения с повторениями. Отметим, что в случае, когда r > n, в силу (3.6) A_n^r = 0 и можно считать, что все n^r размещений являются размещениями с повторениями.

Рассмотрим, что подразумевают под перестановками и сочетаниями с повторениями.

Задача построения перестановок с повторениями сос­тоит в следующем.

Пусть множество n‑X состоит из элементов различных видов и при этом имеем k_i неразличимых элементов i‑того вида (i = 1,q), таких, что k₁ + k₂ +…+ k_q = n.

Например, 6‑X множество может иметь следующую структуру:

X = {1, 1, 1, 2, 2, 3}.

Тогда k₁ = 3, k₂ = 2, k₃ = 1.

Построим на n‑X все перестановки и определим мощность этого множества.

Теорема 3.5 Если множество n‑X состоит из эле­ментов различных видов и при этом имеем k_i нера­зличимых элементов i‑того вида (i = 1, q), таких, что k₁ + k₂ +…+ k_q = n, то число всех перестановок с повторениями равно

n! / (k₁! k₂! …k_n!). (3.28)

Доказательство. Преобразуем n‑X в индексированное множество n‑X^, присвоив каждому элементу n‑X^ индекс, равный его порядковому номеру. Например, для n‑X из приведенного выше примера будем иметь

n‑X^ = {1¹, 1², 1³, 2⁴, 2⁵, 3⁶}.

Далее будем считать, что элементы n‑X^, имеющие разные индексы также различны. В таком случае мощность множества всех перестановок n‑X ^ равна n!.

Заметим, что каждый элемент полученного множества перестановок включает в себя все отмеченные элементы k₁‑подмножества X. Учитывая это, аннулируем индексацию на элементах k₁‑подмножества. В результате имеем раз­биение всего множества n! перестановок на классы эк­ви­валентных (в данном случае попарно совпадающих) эле­ментов. Поскольку элементы k₁‑подмножества можно пе­ре­ставлять k₁! различными способами, то столько же эле­мен­тов будет содержать каждый из классов. Следовательно, всего таких классов будет n!/ k₁!. Составим из представителей данного класса множество мощности n!/ k₁!, а затем последовательно применим к нему процесс аннуляции индексов, описанный выше для k₂, …, k_q‑подмножеств. В ре­зуль­тате имеем множество перестановок с повторениями мощ­ности n!/(k₁! k₂! …k_n!), что и требовалось.

Рассмотрим пример.

Пусть 4‑X = {2, 2, 3, 3}. Проиндексируем все элементы этого множества: {2¹, 2², 3³, 3⁴} и построим все пере­становки его, рассматривая его элементы как попарно раз­личные. В таком случае имеем 4! = 24 элемента всех пере­становок:

2¹2²3³3⁴ 2¹2²3⁴3³ 2¹3³2²3⁴2¹3⁴3³2² 2¹3⁴2²3³ 2¹3³2²3⁴

2²2¹3³3⁴ 3³2²2¹3⁴ 3⁴2²3³2¹ 2²2¹3⁴3³ 3⁴2²2¹3³ 3³2²3⁴2¹

3³2¹2²3⁴ 2²3³2¹3⁴ 3⁴3³2²2¹ 3⁴2¹3³2² 3³3⁴2¹2² 2²3⁴3³2¹

3⁴2¹2²3³ 2²3⁴2¹3³ 3³3⁴2²2¹ 3³2¹2²3⁴ 2²3³2¹3⁴ 3⁴3³2²2¹.

Аннулировав индексацию, получим

2233 2233  2323 2332 2323 2323

2233 3223 3232 2233 3223 3232

3223 2323 3322 3232 3322 2332

3223 2323 3322 3223 2323 3322.

Выделив представителей классов эквивалентностей, получим все перестановки с повторениями:

2233 2323 2332  3223 3232 3322.

Всего перестановок в рассмотренном примере имеем

4! / (2!2!) = 6.

Рассмотрим задачу построения сочетаний с повторени­я­ми.

Пусть имеем отображение F:r‑X  n‑Y. В нем соот­ношения между r и n могут быть выбраны произвольно: r < n, r = n или r > n. Скажем, что элементы y, yY эк­ви­ва­лентны, если найдется такая подстановка f, что y = f(y). Так­же, как и в 3.4 доказывается, что это отношение рефлек­сив­но, симметрично и транзитивно, а, следовательно, разби­вает все множество размещений на классы эквивалентных элементов.

Обозначим число этих классов Ĉ_n^r.

Рассмотрим пример. Пусть n = r = 3. Построив все размещения, получим

111 112 113 121 122 123 131 132 133

211 212 213 221  222 223 231 232 233

311 312 313 321 322 323 331 332 333.

Разбивая это множество элементов на классы, заметим, что число элементов в каждом классе будет, вообще говоря, различным. Это следует из различной повторяемости ком­по­нент, составляющих каждую перестановку. Например, класс, определяемый элементом 111 будет представлен в един­ственном числе, поскольку любая перестановка переводит этот элемент в себя. Класс, определяемый представителем 122, в силу (3.28) состоит из трех элементов, поскольку n!/(k₁!k₂!) = 3!/(2!1!) = 3 и т.д.

В рассматриваемом нами примере разбиение на классы можно выполнить так, как показано в левой части рисунка 3.5. На этом рисунке все сочетания с повторениями выделены курсивом.

111 123

112 121 211 124

113 131 311 125

122 212 221 134

123 132  213  231 312 321 135

133 313 331 145

222 234

223 232 322 235

233 323 332 245

333 345

Рисунок 3.5

В общем случае выберем представитель y = y_1, y_{2 ,…,} y_r) любого класса так, чтобы было выполнено у₁ ≤ y₂ ≤…y_r. Далее, следуя Эйлеру, поставим в биективное соответствие сочетаниям с повторениями сочетания без повторений по правилу:

y_1, y_{2, …,} y_r  y_1, y₂ + 1_{, …}y_r + (r ‑ 1)  (3.29)

В нашем примере соответствующая биекция пред­став­лена левой и правой частями рисунка 3.5.

Число всех сочетаний без повторений в условиях (3.29) определится, как C_n^r_+r-1. Следовательно, столько же имеем соче­таний с повторениями.

На основании проведенных рассуждений имеем теорему.

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

Ĉ_n^r = C_n^r_+r-1 = (n + r - 1)! / (r!(n - 1)!). (3.30)

Из (3.30), в частности, следует, что C_n^r_{+r -1} = C_n^{n -1}_{+r - 1}.