3.8. Разбиения множеств

Под разбиением множества n‑X на k блоков понимают любое семейство непустых множеств {X₁,X₂,…X_k}, таких, что X₁  X₂ … X_k = n‑X и X_i  X_j = Ø для любых 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:

X_n = Σ_kⁿ _{= 0} S(n, k) (3.34)

Первые восемь чисел Белла представлены в таблице 3.2

При подсчете числа разбиений необходимо иметь в виду, что числа Белла растут очень быстро. Так, например, уже при n = 20 B_n = 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 блоков. Для этого объединим в один блок X_i  n‑X, (i = 1, k) те значения из n‑X, которые функцией F отображаются на одно и то же значение из k‑Y. По нашему построению ни один из k полученных блоков не пуст, пере­сечение всех этих k блоков пусто, а их объединение сос­тав­ляет n‑X. Следовательно, множество блоков {X₁, X₂, …, X_k}, определенное поставленным соответствием, представляет разбиение n‑X.

Определим на множестве {X₁, X₂, …, X_k} функцию F*, которая отображает любой блок X_i на свой собственный номер i. Ясно, что F* биективна на всяком фиксированном множестве блоков {X₁, X₂, …, X_k}. С другой стороны, любая из F* однозначно связана с F: она может быть получена из F путем объединения в один блок X_i  n‑X, (i = 1, k) тех значений из n‑X, которые функцией F отображаются на одно и то же значение из k‑Y.

Проведенные выше рассуждения показывают, что алгоритм построения всех разбиений множества n‑X может состоять в следующем.

1. Построить на множестве всех сюръективных функций F:n‑X  k‑Y все классы эквивалентности, инвариантные всевозможным перестановкам элементов k‑Y на значениях этих функций и выбрать по представителю каждого из этих классов;

2. Каждому представителю класса F поставить в соответствие, биективную функцию F* с областью определения, получаемой путем объединения в один блок X_i  n‑X, (i = 1, k) тех значений из n‑X, которые функцией F отображаются на одно и то же значение из k‑Y и областью значений k‑Y. То есть для каждой функции F построить такую функцию F* , что F*:{X₁, X₂, …., X_k} → k‑Y.

3. Для каждой из F* построить искомые блоки, на основании биекции F*:

{X₁, X₂, …., X_k} = F* ^-1(k‑Y),

где для каждого 1 i  k имеем X_i = {j  n–X: F^*(X_i) =i}

Из рассмотренного выше следует, что имеет место за­висимость между числами S(n, k) и множеством всех сюръективных функций F из n‑X на k‑Y: каждому разбиению со­ответствует свой класс эквивалентности, определяемый все­возможными перестановками блоков разбиения. Поэтому, обозначив символами «s_{n, k}» множество всех функций F, получим, что

S(n, k) = s_{n, 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) = {X₁, X₂, …., X_k.