logo
флеров

Циклическая структура перестановок

Перестановки множеств и мультимножеств - один из самых богатых объектов перечислительной комбинаторики. Основная причина этого - большое разнообразие способов комбинаторного представления перестановки. Перестановку можно представлять как слово или как функцию. В частности, функция : [n]  [n], задаваемая равенством (i) = a i , соответствует слову a1a2 ... an.

Если рассматривать перестановку  конечного множества S как взаимно однозначное отображение : S  S, то естественно для каждого xS рассмотреть последовательность x, (x), 2(x), ... . В конце концов (так как  - взаимно однозначное соответствие, и множество S предполагается конечным) мы вновь получим x. Таким образом, для некоторого единственного наименьшего k  1 имеем, что k(x) = x и элементы x, (x), ... ,  k-1(x) все различны. Назовем последовательность (x, (x), ... ,  k-1(x)) циклом перестановкидлины k. Циклы (x, (x), ... ,  k-1(x)) и ( i(x),  i+1(x), ... ,  k-1(x), x, ... ,  i-1(x)) считаются эквивалентными. Каждый элемент S встречается тогда в единственном цикле перестановки , и мы можем рассматривать  как объединение непересекающихся циклов или, по-другому, как произведение различных циклов C1, ... , Cn. Например, если перестановка : [7]  [7] определена как , то есть (1) = 4, (2) = 2, (3) = 7, (4) = 1, (5) = 3, (6) = 6, (7) = 5, то  = (14)(2)(375)(6). Конечно, возможны различные обозначения такого представления перестановки; например, имеем:  = (753) (14) (6) (2). Можно определить стандартное представление:

Пусть c(n, k) - число таких перестановок множества из n элементов, которые имеют k циклов. Будем обозначать множество всех перестановок n - элементного множества символом n .

Утверждение 1.4. Числа c(n,k) удовлетворяют следующему рекуррентному сотношению:

c(n, k) = (n - 1) c(n-1, k) + c(n-1, k-1) , n, k 1,

с начальными условиями c(n, k) = 0 при n  0 или k  0, за исключением c(0, 0) = 1.

Докажем сфомулированное утверждение.

Возьмем перестановку   n-1 с k циклами. Мы можем вставить символ n после любого из символов 1, 2, ... , n-1 в разложении перестановки  на непересекающиеся циклы n-1 способом, получив таким образом разложение на непересекающиеся циклы перестановки n с k циклами, где n встречается в цикле длины, не меньшей 2. Следовательно, существует (n-1)c(n-1,k) перестановок n c k циклами, для которых (n)n.

С другой стороны, если выбрана перестановка n-1 с k-1 циклом, ее можно достроить до перестановки n с k циклами, удовлетворяющей условию (n) = n. Положим

Следовательно, имеется c(n - 1, k - 1) перестановок n с k циклами, для которых (n) = n, и доказательство закончено.

Числа c(n,k) = ( - 1)n-ks(n,k) известны под названием чисел Стирлинга первого рода без знака.

Укажем на еще одну важную роль чисел c(n, k).

Пусть x - переменная. Фиксируем n  0. Тогда имеет место

Утверждение 1.5.

Доказательство. Положим

Отсюда следует, что

b(n, k) = (n  1)b(n  1, k) + b(n  1, k  1).

Поэтому b(n, k) удовлетворяют тем же рекуррентным соотношениям и начальным условиям, что и c(n, k), а значит, они совпадают.