- •Оглавление
- •Предисловие
- •1. Теоретико‑множественные основания дисциплины
- •1.1. Понятия и аксиомы теории множеств
- •1.2. Декартовы произведения, отношения и отношение эквивалентности
- •1.3. Понятия образа, прообраза, функции и отображения на конечном множестве. Аксиома выделения.
- •1.4. Аксиомы степени и бесконечности. Мощности и кардинальные числа множеств
- •1.5. Счетные и континуальные множества
- •1.6. Ординалы и трансфиниты. Аксиома выбора и континуум‑гипотеза
- •2. Основы математической логики
- •2.1. Высказывания и функции на высказываниях
- •2.2. Операции математической логики
- •2.3. Понятие формулы и свойства операций
- •2.4. Разложения булевых функций. Принцип двойственности. Совершенные нормальные формы.
- •2.5. Понятие полноты системы булевых функций
- •2.5. Исчисление предикатов
- •2.6. Введение в методы теории доказательств
- •1 Если X a,
- •0 Если X a.
- •1 Если X a,
- •0 Если X a.
- •3. Комбинаторика
- •3.1. Размещения
- •3.2. Размещения без повторений
- •3.3. Перестановки, подстановки и их свойства
- •3.4. Сочетания, структура соединений
- •3.5. Свойства биномиальных коэффициентов
- •Структура соединений
- •3.6. Понятие производящей функции
- •3.7. Соединения с повторениями
- •3.8. Разбиения множеств
- •3.9. Разбиения чисел
- •3.10. Композиции чисел
- •4. Основы теории графов
- •4.1. Основные понятия и определения
- •4.2. Графы и бинарные отношения
- •4.3. Понятие изоморфизма и изоморфизм плоских графов
- •4.4. Степени вершин графа
- •4.5. Представление графов матрицами
- •4.6. Представление графов списками инцидентности. Оценка пространственной сложности алгоритмов.
- •4.7. Маршруты, цепи, циклы и связность
- •4.7. Эйлеровы циклы и цепи
- •4.9. Гамильтоновы циклы. Оценка временной сложности алгоритмов
- •4.10. Деревья
- •4.11. Раскраска вершин и теорема Шеннона об информационной емкости графа
- •4.12. Раскраска ребер графа и теоремы о хроматическом классе
- •Ответы и решения
- •Список литературы
3.7. Соединения с повторениями
Задача построения всех размещений из n элементов по r рассмотрена в 3.1 — 3.3. Показано, что число всех размещений равно nr, а среди них имеем Anr инъективных. Остальные nr-Anr размещений определим как размещения с повторениями. Отметим, что в случае, когда r > n, в силу (3.6) Anr = 0 и можно считать, что все nr размещений являются размещениями с повторениями.
Рассмотрим, что подразумевают под перестановками и сочетаниями с повторениями.
Задача построения перестановок с повторениями состоит в следующем.
Пусть множество n‑X состоит из элементов различных видов и при этом имеем ki неразличимых элементов i‑того вида (i = 1,q), таких, что k1 + k2 +…+ kq = n.
Например, 6‑X множество может иметь следующую структуру:
X = {1, 1, 1, 2, 2, 3}.
Тогда k1 = 3, k2 = 2, k3 = 1.
Построим на n‑X все перестановки и определим мощность этого множества.
Теорема 3.5 Если множество n‑X состоит из элементов различных видов и при этом имеем ki неразличимых элементов i‑того вида (i = 1, q), таких, что k1 + k2 +…+ kq = n, то число всех перестановок с повторениями равно
n! / (k1! k2! …kn!). (3.28)
Доказательство. Преобразуем n‑X в индексированное множество n‑X, присвоив каждому элементу n‑X индекс, равный его порядковому номеру. Например, для n‑X из приведенного выше примера будем иметь
n‑X = {11, 12, 13, 24, 25, 36}.
Далее будем считать, что элементы n‑X, имеющие разные индексы также различны. В таком случае мощность множества всех перестановок n‑X равна n!.
Заметим, что каждый элемент полученного множества перестановок включает в себя все отмеченные элементы k1‑подмножества X. Учитывая это, аннулируем индексацию на элементах k1‑подмножества. В результате имеем разбиение всего множества n! перестановок на классы эквивалентных (в данном случае попарно совпадающих) элементов. Поскольку элементы k1‑подмножества можно переставлять k1! различными способами, то столько же элементов будет содержать каждый из классов. Следовательно, всего таких классов будет n!/ k1!. Составим из представителей данного класса множество мощности n!/ k1!, а затем последовательно применим к нему процесс аннуляции индексов, описанный выше для k2, …, kq‑подмножеств. В результате имеем множество перестановок с повторениями мощности n!/(k1! k2! …kn!), что и требовалось.
Рассмотрим пример.
Пусть 4‑X = {2, 2, 3, 3}. Проиндексируем все элементы этого множества: {21, 22, 33, 34} и построим все перестановки его, рассматривая его элементы как попарно различные. В таком случае имеем 4! = 24 элемента всех перестановок:
21223334 21223433 2133223421343322 21342233 21332234
22213334 33222134 34223321 22213433 34222133 33223421
33212234 22332134 34332221 34213322 33342122 22343321
34212233 22342133 33342221 33212234 22332134 34332221.
Аннулировав индексацию, получим
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, yY эквивалентны, если найдется такая подстановка f, что y = f(y). Также, как и в 3.4 доказывается, что это отношение рефлексивно, симметрично и транзитивно, а, следовательно, разбивает все множество размещений на классы эквивалентных элементов.
Обозначим число этих классов Ĉnr.
Рассмотрим пример. Пусть 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!/(k1!k2!) = 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 = y1, y2 ,…, yr) любого класса так, чтобы было выполнено у1 ≤ y2 ≤…yr. Далее, следуя Эйлеру, поставим в биективное соответствие сочетаниям с повторениями сочетания без повторений по правилу:
y1, y2, …, yr y1, y2 + 1, …yr + (r ‑ 1) (3.29)
В нашем примере соответствующая биекция представлена левой и правой частями рисунка 3.5.
Число всех сочетаний без повторений в условиях (3.29) определится, как Cnr+r-1. Следовательно, столько же имеем сочетаний с повторениями.
На основании проведенных рассуждений имеем теорему.
Теорема 3.6 Сочетания с повторениями из n элементов по r эквивалентны множеству всех классов размещений, инвариантных относительно всех перестановок входящих в них элементов. Число этих классов равно
Ĉnr = Cnr+r-1 = (n + r - 1)! / (r!(n - 1)!). (3.30)
Из (3.30), в частности, следует, что Cnr+r -1 = Cnn -1+r - 1.