Лекция: Разбиения

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

Пусть есть разбиение множества Х из 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 представлен в таблице.Числа Стирлинга второго рода

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

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

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