- •Оглавление
- •Предисловие
- •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.2. Размещения без повторений
Введем ограничения на постановку задачи о размещениях. Пусть на декартовом произведении n‑Х и r‑S множеств построены все функции F: r‑S→ n‑X. Сколько из них инъективных? В качестве примера рассмотрим случай, когда r = n = 3.
Все функции, соответствующие этому случаю, представлены на рисунке 3.3:
1, 1, 1 1, 1, 2 1, 1 , 3
1, 2, 1 1, 2, 2 1, 2, 3
1, 3, 1 1, 3, 2 1, 3, 3
2, 1, 1 2, 1, 2 2, 1, 3
2, 2, 1 2, 2, 2 2, 2, 3
2, 3, 1 2, 3, 2 2, 3, 3
3, 1, 1 3, 1, 2 3, 1, 3
3, 2, 1 3, 2, 2 3, 2, 3
3, 3, 1 3, 3, 2 3, 3, 3
Рисунок 3.3
В данном примере из всех полученных функций имеем 6 инъективных . Все они на рисунке 3.3 выделены.
Размещения, соответствующие инъективным функциям называются размещениями без повторений либо инъективными размещениями.
Ясно, что инъективные функции составляют всего лишь подмножество всех функций F : r‑S → n‑X. Поэтому для их получения достаточно наложить ограничения на алгоритмы (3.5) или (3.6). Рассмотрим этот вопрос на примере решения задачи выбора без повторений r объектов на множестве n‑X.
Данная задача имеет следующую интерпретацию.
В урне имеется n пронумерованных шаров. Последовательно один за другим извлекаются r шаров и их номера фиксируются. Сколько и каких различных r‑ок шаров может быть выбрано?
Проведем соответствующие комбинаторные рассуждения.
Выбор значения первого элемента у1 можно осуществить n способами. Выбор второго элемента у2 можно осуществить только n–1 способами с каждым из первых, запретив применять уже выбранное значение. Индуктивно предполагая, что таким образом выбраны уже r – 1 элемент, получим, что r‑тый элемент можно выбрать n(n -1…(n - (r -1)) способами с каждым из предыдущих, поскольку для него запрещен выбор любого из уже выбранных предыдущих значений. Поэтому всего будет получено n(n-1…(n-(r-1)) различных элементов комбинаторной конфигурации.
Для определения числа инъективных размещений приняты обозначения: Anr или [n]r.
В соответствии с проведенными выше рассуждениями имеем
Anr = n(n - 1)… (n - (r - 1)). (3.7)
Выражение (3.7) представляет полином по переменнойn степени r.
Коэффициенты s(r, k) этого полинома известны в комбинаторике как числа Стирлинга первого рода. Они вычисляются следующим образом. Представив (3.7) в виде полинома в развернутой записи, видим, что s(r, 0) = 1, а s(r, r-1) = = r-1! для любого r n. Остальные числа s(r, k) подчиняются рекурсии:
s(r +1, k) = s(r, k) - r s(r, k - 1).
Последняя формула легко выводится из (3.7) по индукции.
Алгоритм инъективных размещений получим, если введем рассмотренные выше ограничения в алгоритме (3.6). С учетом ранее введенных обозначений, будем иметь:
Рассмотренная нами задача именуется: выбор без возвращений.
Соответствующая задача расположения имеет следующую формулировку.
Требуется расположить r пронумерованных шаров по n пронумерованным урнам так, чтобы ни в какую урну не попадало два шара одновременно. Сколько и каких расположений возможно?
Ясно, что эта задача также решается применением алгоритма (3.8), соответственно в обозначениях, принятых для алгоритма (3.5).
На основании изложенного выше, имеем доказательство следующей теоремы.
Теорема 3.2 Размещения r различных объектов n различными способами без повторений эквивалентны всем инъективным функциям, определенным на множестве r‑S со значениями в множестве n‑X, число которых равно
Anr = n(n - 1)… (n - (r - 1)).