- •Оглавление
- •Предисловие
- •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.4. Сочетания, структура соединений
Вернемся к задаче о размещениях, как к построению всех функций на декартовом произведении r‑S и n‑X множеств.
Из изложенного в 3.3 следует, что множество всех таких функций можно представить в виде двух непересекающихся множеств: функций c повторениями значений и инъективных функций.
Покажем, что инъективные функции можно разбить на классы эквивалентности.
Ясно, что если r > n, то множество инъективных функций пусто. Это непосредственно вытекает из формулы (3.7). Поэтому будем считать, что r n.
Скажем, что элементы y = x1, x2, … xr и y' = x'1, x'2, … x'r эквивалентны, если найдется такая подстановка f, что f(y) = y'.
Покажем, что это отношение рефлексивно, симметрично и транзитивно и, следовательно, разбивает все множество инъективных функций y на классы.
Действительно, рефлексивность следует из существования единичной подстановки е(y) = y, симметричность вытекает из существования обратной подстановки: если f(y) = y', то f-1(y') = y, транзитивность определяется правилом произведения подстановок: если f1(y) = y', а f2(y') = y'', то f2f1(y) = y''.
Рассмотрим теперь вопросы о построении и числе классов эквивалентности.
Для построения любого класса эквивалентности выберем произвольную инъективную функцию y = x1, x2, … xr и построим все перестановки ее значений. Таких перестановок будет r! Множество всех этих перестановок образует класс функций, замкнутый относительно всевозможных подстановок на множестве {x1, x2, … xr}. В качестве представителя класса можно выбрать любую из этих функций. Мы выберем такую, для которой x1 < x2 < …< xr.
Если r = n, то этими подстановками исчерпывается все множество инъективных функций, поскольку r! = Arr, в противном случае найдется функция со значениями x'1, x'2, …, x'r, из которых хотя бы одно отлично от любых других из всех предыдущих перестановок. Но тогда вместе с ней имеем еще r! перестановок, соответствующих новому классу инъективных функций. Представитель полученного класса снова выберем так, чтобы было выполнено x'1< x'2 < …< x'r.
Поступая аналогично, построим все классы эквивалентности.
Обозначим число всех классов эквивалентности — m.
Поскольку каждый класс эквивалентности содержит r! инъективных функций, определенных на {x1, x2, …, xr} и при этом имеем все классы, то m∙r! = Anr. Следовательно,
m = Anr / r!. (3.12)
Отношение Anr / r! имеет специальные обозначения:
n
r либо Cnr.
(Первое читается: n над r, второе — С из n по r.)
Число Cnr определяет количество классов перестановок в разбиении множества инъективных функций на классы. Каждый такой класс полностью определяется своим представителем, для которого выполнено: x1< x2 < …< xr. Поэтому можно считать, что Cnr определяет мощность множества всех упорядоченных r‑ок, со значениями в n‑X. Это множество имеет специальное наименование: сочетания. Имеется и другое название: r‑подмножества n‑X множества.
Обобщая полученные результаты, имеем следующую теорему.
Теорема 3.4 Сочетания из n различных элементов по r (n ≥ r) эквивалентны множеству классов упорядоченных размещений, инвариантных относительно всех перестановок входящих в них элементов. Число этих классов равно
Cnr = Anr / r! = n! / (r!(n - r)!).
Пример структуры соединений представлен на рисунке 3.4
Числа Cnr исторически известны, как биномиальные коэффициенты. Они обладают рядом интересных свойств, которые будут рассмотрены в следующем разделе.