Разбиения

Разбиения не были рассмотрены среди типовых комбинаторных конфигураций, потому что получить для них явную формулу не так просто, как для остальных.

Пусть есть разбиение множества Х из m элементов на n подмножеств:

,,, при

Подмножества называются блоками разбиения.

Между разбиениями и отношениями эквивалентности существует взаимнооднозначное отношение. Если и - два разбиения Х, то говорят, что разбиение есть измельчение разбиения, если каждый блок есть объединение блоков.

Если k =2, упорядоченное разбиение множества М на два подмножества, имеющие соответственно и элементов, определяется сочетанием (без повторений) из n элементов по или из n элементов по (). Следовательно, число разбиений R (,) равно биноминальному коэффициенту. Таким образом,

В общем случае число упорядоченных разбиений (), для которых, равно, а число R(n, k) упорядоченных разбиений на k подмножеств вычисляется по формуле

Числа называются полиномиальными коэффициентами, поскольку для всех справедливо соотношение

Пример. В студенческой группе, состоящей из 25 человек, при выборе старосты за выдвинутую кандидатуру проголосовали 12 человек, против – 10, воздержались – 3. Сколькими способами могло быть проведено такое голосование?

Пусть М – множество студентов в группе, - множество студентов, проголосовавших за выдвинутую кандидатуру, - множество студентов, проголосовавших против, - множество студентов, воздержавшихся от голосования. Тогда - упорядоченное разбиение множества M. Искомое число R (12, 10, 3) равно.

Число разбиений исходного множества M на k подмножеств,, неупорядоченных между собой, вычисляется по формуле

,

а число всех возможных разбиений множества M на k подмножеств, неупорядоченных между собой, равно

Пример. Сколькими способами из группы в 25 человек можно сформировать 5 коалиций по 5 человек?

Пусть X – множество людей в группе, - число коалиций по i человек, где i =1,…25. Тогда по условиям задачи, и, следовательно, искомое число будет равно

Теорема. Пусть S(n, k) – число разбиений множества n-X на k блоков. Тогда вычисление S(n, k) может быть выполнено рекурсивно на основе тождеств:если, если n =0,, если n >0.

Доказательство. Для доказательства рассмотрим множество всех разбиений n-X на k подмножеств.

Это множество можно представить двумя пересекающимися классами: тех разбиений, которые содержат одноэлементный блок { n }, и тех, которые его не содержат. В этом случае n содержится по крайней мере в двухэлементном блоке. Мощность первого класса равна, т. е. такова, каково число разбиений множества {1, 2, …, n -1} на k -1 блоков. Мощность второго класса равна, поскольку каждому разбиению множества {1, 2, …, n -1} на k -1 блоков соответствует в этом классе ровно k разбиений, образованных добавлением элемента n поочередно к каждому блоку. Доказательство окончено.

Числа S(n, k) называются числами Стирлинга второго рода. Рассчитанные по формулам (3.31)-(3.33), они могут быть представлены в виде треугольной таблицы – треугольника Стирлинга. Треугольник Стирлинга для значений n от 0 до 7 представлен в таблице. Числа Стирлинга второго рода

n	k

Числа Белла определяются как сумма всех разбиений от 0 до n блоков множества n-X. (3.34)

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

При посчете числа разбиений необходимо иметь в виду, что числа Белла растут очень быстро. Так, например, уже при n = 20 B_n = 51 724 158 235 372. Числа Белла