Тема: разбиения на блоки и циклы
Основные вопросы, рассматриваемые на лекции:
1. Разбиения множества на m блоков.
2. Число Стирлинга второго рода.
3. Разбиения перестановки на m циклов.
4. Число Стирлинга первого рода.
5. Факториальные многочлены.
Краткое содержание лекционного материала
1. Разбиения множества на m блоков. Говорят, что семейство множеств { M 1,…, Mk } является разбиением множества M на k блоков M 1,…, Mk, если M 1,…, Mk – непустые, попарно не пересекающиеся, подмножества множества M и объединение множеств M 1,…, Mk есть множества M. Число (или S (n, k)) всех разбиений n -множества M на k блоков называется числом Стирлинга второго рода.
Пример 1. Перечислим все разбиения множества {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}}
Мы видим, что .
Примечание. Пусть | 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. Число Стирлинга второго рода. Приведем рекуррентные формулы для числа Стирлинга второго рода:
;
, где n >0;
, где n >0, 1£ k £ n.
Непосредственно число Стирлинга второго рода вычисляется по следующей формуле: .
k n | ||||||||
Число всех разбиений n -множества M называется числом Белла Bn.
Ясно, что .
3. Разбиения перестановки на m циклов. Перестановка p m -множества M называется циклом, если p(x 1)= x 2, p(x 2)= x 3, …, p(xm -1)= xm, p(xm)= x 1, где x 1, x 2, x 3, …, xm -1, xm – все, различные, элементы множества M. Этот цикл обозначается через (x 1 x 2 x 3… xm -1 xm). Каждая перестановка состоит из конечного числа циклов, и эту перестановку можно записать в виде произведения циклов.
Пример 2. Перечислим все перестановки множества {1,2,3,4}, разбиваемые на 2 цикла:
(1)(234); (1)(243);
(2)(134); (2)(143);
(3)(124); (3)(142);
(4)(123); (4)(132);
(12)(34); (13)(24); (14)(23).
Числом Стирлинга первого рода (без знака) (или s (n, k)) называется число разбиений n -множества B на k циклов.
4.Число Стирлинга первого рода. Приведем рекуррентные формулы для числа Стирлинга первого рода
;
, где n >0;
, где n >0, 1£ k £ n.
k n | ||||||||
Ясно, что .
5. Факториальные многочлены. Любой многочлен от одной переменной можно представить как линейную сумму степеней переменной (базисных многочленов): , , , …
Определим многочлены , , которые также являются базисными: .
Связь между двумя базисными многочленами устанавливается при помощи чисел Стерлинга первого и второго родов:
, .
Вместо «убывающих степеней» можно рассматривать «возрастающие степени»: .
, .