Разбиение множества на блоки по k элементов.
Говорят, что семейство множеств {M1,…,Mk} является разбиением множества M на k блоков M1,…,Mk, если M1,…,Mk – непустые, попарно не пересекающиеся, подмножества множества M и объединение множеств M1,…,Mk есть множества M. Число (или S(n,k)) всех разбиений n-множества M на k блоков называется числом Стирлинга второго рода.
Пример. Перечислим все разбиения множества {1,2,3,4} на 2 блока:
{{1}, {2, 3,4}},
{{2}, {1, 3,4}},
{{3}, {1, 2,4}},
{{4}, {1, 2,3}},
{{1,2}, {3,4}},
{{1,3}, {2,4}},
{{1,4}, {2,3}}
Мы видим, что .
Приведем рекуррентные формулы для числа Стирлинга второго рода:
;
, где n>0;
, где n>0, 1£k£n.
Непосредственно число Стирлинга второго рода вычисляется по следующей формуле: .
k n | ||||||||
Число всех разбиений n-множества M называется числом Белла Bn.
Ясно, что .
Примечание 1. Пусть |A|=m, |B|=n. Тогда число элементов:
· множества всех отображений множества A в B равно числу всех размещений с повторениями по m из n, то есть |BA|=nm;
· множества всех инъекций множества A в B равно числу всех размещений без повторений по m из n, то есть ;
· множества всех биекций множества A на B равно числу всех размещений без повторений по m из n, то есть n!;
· множества всех сюръекций множества A на B равно произведению числа всех перестановок n-множества B на число всех разбиений n-множества B на m блоков, то есть n!.
Любой многочлен от одной переменной можно представить как линейную сумму степеней переменной (базисных многочленов): , , , …
Примечание 2. Определим многочлены , , которые также являются базисными: .
Связь между двумя базисными многочленами устанавливается при помощи чисел Стерлинга первого и второго родов:
, .
Вместо «убывающих степеней» можно рассматривать «возрастающие степени»: .
, .