- •Оглавление
- •Предисловие
- •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.8. Разбиения множеств
Под разбиением множества n‑X на k блоков понимают любое семейство непустых множеств {X1,X2,…Xk}, таких, что X1 X2 … Xk = n‑X и Xi Xj = Ø для любых i, j ≤ k.
Например, множество {1, 2, 3, 4} можно разбить на два блока следующими способами:
{{1, 2, 3}, {4}}, {{1, 2, 4}, {3}}, {{1, 3, 4}}, {2}},
{1, 2}, {3, 4}}, {{1, 3}, {2, 4}}, {{1, 4}, {2, 3}},
{{1}, {2, 3, 4}}.
Теорема 3.7 Пусть S(n,k) число разбиений множества n‑X на k блоков. Тогда вычисление S(n,k) может быть выполнено рекурсивно на основе тождеств:
S(n, k) = S(n - 1, k - 1) + kS(n - 1, k), если 0 < k < n (3.31)
S(n, n) = 1; если n ≥ 0, (3.32)
S(n, 0) = 0, если n > 0. (3.33)
Доказательство. Формулы (3.32) и (3.33) очевидны. Для доказательства (3.31) рассмотрим множество всех разбиений n‑X на k подмножеств.
Это множество можно представить двумя непересекающимися классами. Тех разбиений, которые содержат одноэлементный блок {n} и тех, которые его не содержат. В этом случае n содержится по крайней мере в двухэлементном блоке. Мощность первого класса равна S(n-1, k-1), то есть такова, каково число разбиений множества {1, 2, …, n-1} на k-1 блоков. Мощность второго класса равна kS(n -1, k), поскольку каждому разбиению множества {1, 2,…, n-1} на k блоков соответствует в этом классе ровно k разбиений, образованных добавлением элемента n поочередно к каждому блоку. Доказательство окончено.
Числа S(n, k) именуются числами Стирлинга второго рода. Рассчитанные по формулам (3.31) — (3.33), они могут быть представлены в виде треугольной таблицы, которая именуется треугольник Стирлинга.
Треугольник Стирлинга, для значений n от 0 до 7 представлен в таблице 3.1.
Таблица 3.1 — Числа Стирлинга второго рода
n |
k | |||||||
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 | |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
1 |
3 |
1 |
0 |
0 |
0 |
0 |
4 |
0 |
1 |
7 |
6 |
1 |
0 |
0 |
0 |
5 |
0 |
1 |
15 |
25 |
10 |
1 |
0 |
0 |
6 |
0 |
1 |
31 |
90 |
65 |
15 |
1 |
0 |
7 |
0 |
1 |
63 |
301 |
350 |
140 |
21 |
1 |
Числа Белла определяются, как сумма всех разбиений от нуля до n блоков множества n‑X:
Xn = Σkn = 0 S(n, k) (3.34)
Первые восемь чисел Белла представлены в таблице 3.2
При подсчете числа разбиений необходимо иметь в виду, что числа Белла растут очень быстро. Так, например, уже при n = 20 Bn = 51 724 158 235 372.
Таблица 3.2 — Числа Белла
n |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Bn |
1 |
1 |
2 |
5 |
15 |
52 |
203 |
877 |
Рассмотрим вопрос об построении алгоритма разбиений.
Каждому разбиению множества n‑X на k блоков можно сопоставить функцию F, отображающую множество значений каждого блока разбиений на его номер в множестве k‑Y. В силу нашего построения каждая такая функция сюръективна.
Поскольку любое разбиение инвариантно относительно всех перестановок составляющих его блоков, то каждому разбиению будет соответствовать в точности k! различных сюръективных функций, отвечающих различным перестановкам номеров блоков разбиения множества n‑X. Другими словами, каждому разбиению множества n‑X на k блоков соответствует свой класс эквивалентности, построенный на множестве всех сюръективных функций из n‑X на k‑Y, инвариантный относительно всех перестановок элементов k‑Y на фиксированных блоках n‑X.
Обратно, всякой сюръективной функции F:n‑X k‑Y можно поставить в соответствие некоторое разбиение множества n‑X на k блоков. Для этого объединим в один блок Xi n‑X, (i = 1, k) те значения из n‑X, которые функцией F отображаются на одно и то же значение из k‑Y. По нашему построению ни один из k полученных блоков не пуст, пересечение всех этих k блоков пусто, а их объединение составляет n‑X. Следовательно, множество блоков {X1, X2, …, Xk}, определенное поставленным соответствием, представляет разбиение n‑X.
Определим на множестве {X1, X2, …, Xk} функцию F*, которая отображает любой блок Xi на свой собственный номер i. Ясно, что F* биективна на всяком фиксированном множестве блоков {X1, X2, …, Xk}. С другой стороны, любая из F* однозначно связана с F: она может быть получена из F путем объединения в один блок Xi n‑X, (i = 1, k) тех значений из n‑X, которые функцией F отображаются на одно и то же значение из k‑Y.
Проведенные выше рассуждения показывают, что алгоритм построения всех разбиений множества n‑X может состоять в следующем.
Построить на множестве всех сюръективных функций F:n‑X k‑Y все классы эквивалентности, инвариантные всевозможным перестановкам элементов k‑Y на значениях этих функций и выбрать по представителю каждого из этих классов;
Каждому представителю класса F поставить в соответствие, биективную функцию F* с областью определения, получаемой путем объединения в один блок Xi n‑X, (i = 1, k) тех значений из n‑X, которые функцией F отображаются на одно и то же значение из k‑Y и областью значений k‑Y. То есть для каждой функции F построить такую функцию F* , что F*:{X1, X2, …., Xk} → k‑Y.
Для каждой из F* построить искомые блоки, на основании биекции F*:
{X1, X2, …., Xk} = F* -1(k‑Y),
где для каждого 1 i k имеем Xi = {j n–X: F*(Xi) =i}
Из рассмотренного выше следует, что имеет место зависимость между числами S(n, k) и множеством всех сюръективных функций F из n‑X на k‑Y: каждому разбиению соответствует свой класс эквивалентности, определяемый всевозможными перестановками блоков разбиения. Поэтому, обозначив символами «sn, k» множество всех функций F, получим, что
S(n, k) = sn, k / k! (3.35)
В качестве примера рассмотрим применение рассмотренного выше алгоритма к построению всех разбиений множества n‑X = {1, 2, 3, 4} на два блока.
На рисунке 3.6 представлены значения всех функций, определенных на 4‑X со значениями в 2‑Y. Подмножество сюръективных функций F выделено полужирным шрифтом.
Множество n‑X представлено верхними прямоугольными областями. Представители всех классов эквивалентности даны левой прямоугольной областью. Каждому представителю класса эквивалентности соответствует дополнение класса, обозначенное правой прямоугольной областью.
К нашем примере в каждом классе эквивалентности имеем всего k! = 2! = 2 элемента. Представитель каждого класса и его дополнение представлены в одной строке.
>
На рисунке 3.7 слева изображены представители классов эквивалентности, образованные множеством функций F, а справа — искомые блоки разбиения множества n‑X. Эти блоки получены путем построения всех отображений
F* -1(k-Y) = {X1, X2, …., Xk.