Разбиение перестановки на циклы по k элементов

Перестановка p m -множества M называется циклом, если p(x ₁)= x ₂, p(x ₂)= x ₃, …, p(x_{m -1})= x_m, p(x_m)= x ₁, где x ₁, x ₂, x ₃, …, x_{m -1}, x_m – все, различные, элементы множества M. Этот цикл обозначается через (x ₁ x ₂ x ₃… x_{m -1} x_m). Каждая перестановка состоит из конечного числа циклов, и эту перестановку можно записать в виде произведения циклов.

Пример. Перечислим все перестановки множества {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.

Ясно, что .