5.4. Разбиения

Разбиение множества X из n элементов на k блоков – это формирование множества Q = {B1, …, Bk}, в котором B1 B2 ...

Bk = X , Bi ∩ Bj = , Bi ≠ для 1 ≤ i < j ≤ k. Обозначим множе-

ство всех разбиений множества X на k блоков через Πk(X), а через Π(X) – множество все разбиений.

Существует алгоритм построения разбиений, описанный в рекуррентной форме.

Можно показать, что разбиение Q множества {1, …, n} однозначно определяет разбиение Qn−1 множества {1, …, n−1}, которое получается из Q после удаления элемента n (или пустого блока) из соответствующего блока. Также если имеется разбиение W={B1, …, Bk} множества {1, …, n−1}, то можно отыскать все разбиения Q множества {1, …, n}, для которых Qn−1 = W, т.е. такие разбиения:

B1 {n},..., Bk ,

…

B1 ,..., Bk {n},

B1 ,..., Bk ,{n}.

Обозначим такую последовательность через E. Тогда алгоритм разбиений выглядит следующим образом: если у нас есть список