Это свойство канонической формы позволяет получить замечательное однозначное соответствие междумножеством всех перестановок, представленных в циклическом виде, и множеством всех перестановок, представленных в линейной форме. Например, канонической формой для перестановки 6 2 1 5 4 3 является (4 5) (2) (1 6 3); удалив скобки, получим перестановку 4 5 2 1 6 3, циклической формой которой является (2 5 6 3) (1 4); удалив скобки, получим 2 5 6 3 1 4, циклической формой которой является (3 6 4) (1 2 5) и т. д.

Это соответствие имеет многочисленные применения в изучении перестановок различных типов. Например, зададимся вопросом: "Сколько циклов имеет перестановка из п элементов в среднем?". Чтобы ответить на него, рассмотрим множество всех п! перестановок, представленных в канонической форме, и уберем скобки. Останется множество всех п! перестановок, расположенных в некотором порядке. Поэтому первоначальный вопрос будет эквивалентен следующему: "Сколько в среднем минимумов слева направо имеет перестановка из п элементов?". На последний вопрос мы уже ответили в разделе 1.2.10; это была величина {А + 1) из анализа алгоритма 1.2.ЮМ, для которой найдены статистические характеристики

min 1, ave Я„, max n, dev уяй-Я. (21)

(На самом деле мы искали среднее число максимумов справа налево, но очевидно, что это то же самое, что число минимумов слева направо.) Более того, мы, в сущности, доказали, что перестановка из п объектов имеет к минимумов слева направо с вероятностью /п!; следовательно, перестановка пз п объектов имеет к циклов с вероятностью []/п\.

Можно также задать вопрос о среднем расстоянии между минимумами слева направо, которое эквивалентно средней длине цикла. Согласно (21) общее число циклов во всех п! перестановках равно п! Я„, так как это nl, умноженное на среднее число циклов. Если выбрать один из этих циклов наугад, то чему будет равна его средняя длина?

Представьте себе все п! перестановок {1,2,...,п}, записанных в циклической форме. Сколько среди них будет трехэлементных циклов? Чтобы ответить на этот вопрос, выясним, сколько раз появляется конкретный трехэлементный цикл {xyz). Очевидно, что он появляется ровно в (п - 3)! перестановках, так как это число способов, которыми можно переставить оставшиеся п - 3 элемента. Количество различных возможных трехэлементных циклов {xyz) равно п{п - 1){п - 2)/3, поскольку X можно выбрать п способами, у - (п - 1) способами, а z - (п - 2) способами, и среди этих п{п - 1){п - 2) вариантов каждый отличный от других трехэлементный цикл появляется в трех формах: {xyz), {yzx), {zxy). Поэтому общее число трехэлементных циклов среди всех п\ перестановок равно п{п - 1)х (п-2)/3, умноженному на (п-3)!, т. е. п!/3. Аналогично общее число т-элементных циклов равно п\/т, где 1 < m < п. (Это дает еще одно простое доказательство того факта, что общее число циклов равно п\ Н„. Следовательно, как мы уже знаем, среднее число циклов в случайной перестановке равно Я„.) В упр. 17 показано, что средняя длина случайно выбранного цикла равна п/Я„, если считать, что все п! Я„ циклов являются равновероятными. Но если элемент в случайной перестановке выбран случайно, то средняя длина содержащего его цикла будет несколько больше, чем п/Нп-

Чтобы закончить анализ алгоритмов АиВ, следует узнать среднее число единичных циклов в случайной перестановке. Это очень интересный вопрос. Предположим, мы записали п\ перестановок, перечислив сначала те, в которых нет единичных циклов, затем те, в которых есть только один единичный цикл и т. д. Например, для п = 4 это будет выглядеть так.

Нет фиксированных

элементов: 2143 2341 2413 3142 3412 3421 4123 4312 4321

Один фиксированный

элемент: 1342 1423 3241 4213 2431 4132 23li 3124

Два фиксированных

элемента: ШЗ 1432 1324 4231 3214 2134

Три фиксированных элемента:

Четыре фиксированных

элемента: 1234

(В этом списке отмечены единичные циклы, т. е. элементы, которые в результате перестановки остаются на месте (фиксированные элементы).) Перестановки, не имеющие фиксированных элементов, называются беспорядочными; число таких перестановок- это количество способов так разложить п писем по п конвертам, чтобы ни одно из них не попало в свой конверт.

Пусть Рпк -число перестановок из п объектов, имеющих ровно к фиксированных элементов. Тогда, например,

Pio = 9, F41 = 8, F42 = 6, F43 = О, Р44 = 1.

При изучении приведенного выше списка обнаруживаются главные соотношения, связывающие эти числа. Можно получить все перестановки с к фиксированными элементами, сначала выбирая те к элементов, которые нужно зафиксировать (это можно сделать (J?) способами), а затем переставляя оставшиеся п - к элементов всеми Р{п-к)о способами, которые больше не оставляют фиксированных элементов. Отсюда

Рпк [I) Pin-k)o- (22)

Существует также правило, которое говорит о том, что "целое - это сумма составляющих его частей":

п\ - Рпп

-Ь Рп(п-1) + Рп(п-2) + Рп{п-3) + • • • (23)

Подставив (22) в (23) и выполнив простые преобразования, получаем

Эта формула должна быть справедлива для всех целых положительных п. Она уже встречалась ранее, в разделе 1.2.5 (в связи с попытками Стирлинга обобщить факториальную функцию), а простой вывод ее коэффициентов был приведен в разделе 1.2.6 (пример 5). Мы приходим к выводу, что

= 1-1 + 1-... + (-1)«-1. (25)

ml 1! 2! ml

Теперь пусть Рпк - вероятность того, что перестановка из п объектов имеет ровно к единичных циклов. Так как Рпк - Pnk/nl, из (22) и (25) получаем

Рпк = + + ЫГ-т-] (26)

jfc! V 1! 2! (

Следовательно, производящую функцию G„{z) = р„о + Pniz + p„2Z + • можно представить в виде

;„() = 1 + (г-1) + --- + (г-1)"= т-У- (27)

о<<«--

Из этой формулы следует, что Giz) = G„ i(2). Воспользовавшись методами, которые применялись в разделе 1.2.10, получим следующие статистические характеристики для числа единичных циклов:

(min О, ave 1, max n, dev 1), если n > 2, (28)

Несколько более прямой способ подсчета числа перестановок, не имеющих единичных циклов, следует из принципа включения и исключения, который имеет большое значение для многих задач перечисления. Общий принцип включения и исключения можно сформулировать следующим образом. Дано N элементов и М подмножеств этих элементов Si,S2, ,3м- Необходимо подсчитать, сколько элементов не попало ни в одно из этих подмножеств. Пусть 5-число элементов множества 5. Тогда искомое число объектов, не принадлежащих ни одному из множеств Sj, равно

1<]<М 1<]<к<М l<t<j<k<M

+ (-1)51П---п5м. (29)

(Таким образом, сначала из общего числа N вычитается количество элементов множеств Si,...,Sm; но это меньше искомой величины, так как мы вычли больше, чем нужно. Поэтому снова добавляем число элементов, которые являются общими для пар множеств, Sj П 5а., для каждой пары Sj и 5*.; но это уже больше искомой величины. Поэтому вычитаем элементы, общие для каждой тройки множеств, и т. д.) Существует несколько способов доказательства этой формулы, и читателю предлагается найти один из них самостоятельно (см. упр. 25).

Чтобы подсчитать число перестановок из п элементов, не имеющих единичных циклов, рассмотрим N = п\ перестановок и обозначим через Sj множество перестановок, в которых элемент j образует единичный цикл. Если 1 < ji < J2 < " • • < jk < п, то количество элементов в Sj, П Sj Г\ П Sj -это число перестановок, в которых Ji,.. ,]к образуют единичные циклы. Очевидно, что оно равно (п - к)\. Таким образом, формула (29) принимает вид

ЧТО согласуется с (25).

Принцип включения и исключения был предложен А. де Муавром (А. de Moivre) [см. его работу Doctrine of Chances (London, 1718), 61-63; 3rd ed. (1756, переиздано