logo
флеров

Число разбиений

Определение.

Разбиение конечного множества X, X = n , есть неупорядоченный набор  = {B1 , B2 , ... , Bk } подмножеств множества X таких, что

  1. Bi   для всех i от 1 до k;

  2. Bi  Bj =  , если i  j

  3. B1  B2  ... Bk = X.

Мы называем Bi классом (блоком) разбиения  и говорим, что  имеет k классов. Пусть S(n, k) - число разбиений n - множества на k классов.

S(n, k) называется также числом Стирлинга второго рода.

Разбиения соответствуют размещениям n различных объектов по k одинаковым ящикам при условии, что каждый ящик не пуст.

Пример.

S (4, 2) =7. Действительно, четыре объекта {1, 2, 3, 4} можно следующим образом разбить на два класса:

{1}{2, 3, 4}; {3}{1, 2, 4}; {1, 2}{3, 4};

{2}{1, 3, 4}; {4}{1, 2, 3} {1, 3}{2, 4};

{1, 4}{2, 3}.

Условимся полагать, что S(0,0) = 1.

Читатель должен убедиться, что для n  1 имеют место соотношения:

S(0, k) = 0 при k>0,

S(n, k) = 0 при k > n,

S(n, 0) = 0,

S(n, 1) = 1,

S(n,2) = 2n-1  1,

S(n, n) =1,

S(n, n  1) = .

Утверждение 1.11. Числа Cтирлинга второго рода удовлетворяют следующему основному рекуррентному соотношению:

S(n+1, k) = S(n, k  1) + kS(n, k). (1.12)

Доказательство.

Рассмотрим таблицу разбиений n+1 объекта на k классов.

1) Для некоторых разбиений (n+1)-ый объект есть единственный элемент в классе. Число таких разбиений есть S(n, k  1).

2) Для других разбиений (n+1)-ый объект не является единственным элементом класса ни для какого класса. Следовательно, существует kS(n, k) таких разбиений, так как каждому разбиению множества {1, ... , n} на k классов соответствует в точности k разбиений, образованных добавлением элемента n+1 поочередно к каждому классу.

Таким образом, мы представили все разбиения n+1 элемента на k классов в виде объединения непересекающихся подмножеств разбиений двух перечисленных типов. Поэтому

S(n+1, k) = S(n, k  1) + kS(n, k).

Утверждение 1.12. Число сюръективных отображений множества X, |X| = n, на множество Y (|Y| = m) равно m!S(n, m).

Доказательство.

Каждое сюръективное отображение X = {1,2,...,n} на Y = {y1,y2,...,ym} индуцирует разбиение X на m различных классов 1,2,..., m (в класс i попадают все такие x, что f(x) = yi); наоборот, каждому разбиению X на m классов соответствует m! сюръективных отображений X на Y. Действительно, выражение m!S(n, m) дает число способов разбить X на m классов, а затем линейно упорядочить классы, скажем, (B1 , B2 , ... , Bm ). Свяжем последовательность (B1 , B2 , ... , Bm ) с сюръективной функцией f, определенной формулой f(i) = yj , если iBj . Это устанавливает требуемое соответствие между количеством сюръективных отображений и числом разбиений.

Ниже приводится список некоторых основных формул для количества разбиений множества из n элементов на k классов - S(n,k).