Разбиение перестановки на циклы по k элементов.
Перестановка p m-множества M называется циклом, если p(x1)=x2, p(x2)=x3, …, p(xm-1)=xm, p(xm)=x1, где x1, x2, x3, …, xm-1, xm – все, различные, элементы множества M. Этот цикл обозначается через (x1x2x3…xm-1xm). Каждая перестановка состоит из конечного числа циклов, и эту перестановку можно записать в виде произведения циклов.
Пример. Перечислим все перестановки множества {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 циклов.
Приведем рекуррентные формулы для числа Стирлинга первого рода
;
, где n>0;
, где n>0, 1£k£n.
k n | ||||||||
Ясно, что .