AOP_Tom1 (1021736), страница 49
Текст из файла (страница 49)
Необходимо вставить левую скобку непосредственно перед каждым минимумом слева направо (т, е. перед тем элементом, перед которым нет меньшего элемента). 09 10 11 13 19 Ц Х[Ц Х[2] Х [3] Х [4] Х[5] Х [6] т 4 Л5 ЛЗ Л5 -б -б †— 2 -2 — 2 б б б 5 5 5 — 5 — 5 4 -1 — 1 — 1 4 4 3 -4 -5 — 5 5 5 5 ЛЗ Л5 ЛЗ вЂ” 6 3 3 — 2 — 2 — 2 6 б 6 5 5 5 4 4 4 — 1 †-б 3 2 2 — 1 — 1 -2 6 б 2 35 ЛЗ Л5 3 3 3 2 2 2 6 6 6 5 5 5 4 4 4 — б -б 1 1 1 Π— 2 -б †2 б б Это свойство канонической формы позволяет получить замечательное однозначное соответствие между множеством всех перестановок, представленных в циклическом виде, и множеством всех перестановок, представленных в линейной форме.
Например, канонической формой для перестановки 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,10М, для которой нацдены статистические характеристики ппп 1, ате Х„, шах и, бег Մ— Н (21) (На самом деле мы искали среднее число максимумов справа налево, но очевидно, что зто то же самое, что число минимумов слева направо.) Более того, мы, в сущности, доказали, что перестановка из п объектов имеет !с минимумов слева направо с вероятностью ["„]/и!; следовательно, перестановка пз и объектов имеет к циклов с вероятностью [„Д /и!.
Можно также задать вопрос о среднем расстоянии мелсду минимумами слева направо, которое эквивалентно средней длине цикла. Согласно (21) общее число циклов во всех и! перестановках равно и! Хьч так как это и!, умноженное на среднее число циклов. Если выбрать один из этих циклов наугад, то чему будет равна его средняя длина? Представьте себе все и! перестановок (1,2,...,п), записанных в циклической форме. Сколько среди них будет трехзлементных циклов? Чтобы ответить на этот вопрос, выясним, сколько раз появляется конкретный трехэлементный цикл (худ).
Очевидно, что он появляется ровно в (и — 3)! перестановках, так как это число способов, которыми можно переставить оставшиеся и — 3 элемента. Количество различных возможных трехэлементиых циклов (хй г) равно п(п — 1)(п — 2)/3, поскольку х можно выбрать и способами, у — (и — 1) способами, а г — (и — 2) способами, и среди этих п(п — 1)(п — 2) вариантов каждый отличный от других трехэлементный цикл появляется в трех формах: (худ), (угх), (гху). Поэтому общее число трехзлементных циклов среди всех и! перестановок равно и(п — 1) х (и — 2)/3, умноженному на (и — 3) !, т. е.
и!/3. Аналогично общее число т-элементных циклов равно и)/т, где 1 < т < и. (Это дает еще одно простое доказательство того факта, что общее число циклов равно и! Н„. Следовательно, как мы уже знаем, среднее число циклов в случайной перестановке равно Х„.) В упр. 17 показано, что средняя длина случайно выбранного цикла равна и/Хн, если считать, что все и! Х„ циклов являются равиовероятными.
Но если элемента в случайной перестановке выбран случайно, то средняя длина содержащего его цикла будет несколько больше., чем и/Х„. Чтобы закончить анализ алгоритмов А и В, следует узнать среднее число единичных циклов в случайной перестановке, Это очень интересный вопрос. Предположим,. мы записали и! перестановок, перечислив сначала те, в которых нет единичных циклов, затем те, в которых есть только один единичный цикл и т. д.
Например, для и = 4 зто будет выглядеть так. Нет фиксированных элементов: 2143 2341 2413 3142 3412 3421 4123 4312 4321 Один фиксированный элемент: 1342 1423 3241 4213 2431 4132 2314 3124 Два фиксированных элемента: 1243 1432 1324 4231 3214 2134 Три фиксированных элемента: Четыре фиксированных элемента: ~234 (В этом списке отмечены единичные циклы, т. е. элементы, которые в результате перестановки остаются иа месте (фиксированные элементы).) Перестановки, пе имеющие фиксированных элементов, называются беспорядочимми; число таких перестановок — это количество способов так разложить и писем по и конвертам, чтобы ни одно из них не попало в свой конверт.
Пусть Р„ь — число перестановок из и объектов, имеющих ровно 1 фиксированных элементов. Тогда, например, Рзо = 9, Рм = 8„ Р4з = 6, Роз = О, Ры —— 1. При изучении приведенного выше списка обнаруживаются главные соотношения, связывающие эти числа. Можно получить все перестановки с Й фиксированными элементами, сначала выбирая те 2о элементов, которые нужно зафиксировать (это можно сделать (") способами), а затем переставляя оставшиеся и — )о элементов всеми Р~„цо способами, которые больше не оставляют фиксированных элементов. Отсюда 2п~ Р»ь ~„/Р~ (22) Существует также правило, которое говорит о том, что "целое — это сумма соста- вляющих его частей": (23) и! = Р»» + Р~~» О + Рш~ з) + Р~(~ з) + Подставив (22) в (23) и выполнив простые преобразования, получаем Роо Р1о Рэо Рзо п1 = — + п — + п(п — 1) — + п(п — 1) (и — 2) — + О! 1! 2! 3! (24) Эта формула должна быть справедлива для всех целых положительных и.
Она уже встречалась ранее, в разделе 1.2.5 (в связи с попытками Стирлинга обобщить факториальную функцию), а простой вывод ее коэффициентов был привгдеи в разделе 1.2.6 (пример 5). Мы приходим к выводу, что 1 то 1 1 щ — =1 — — + — — ..+( — 1) (25) гп! 11 21 пз! Теперь пусть рьь — вероятность того, что перестановка из и объектов имеет ровно 1» единичных циклов. Так как р„» = Р„»(и.', из (22) и (25) получаем ы' ,, = -' ~У1- -+ - — + ( )-- 1с! ~, 1! 2! (и — (г)!/ (26) Следовательно, производящую функцию С„(г) = р„а + р„»г + р„ггг + можно представить в виде 1 1 „1 С„(г) = 1+ —, (г — 1) + .. + —, (г — 1)" = ~ —, (г — 1)'. 1! 0<г<п (27) Из этой формулы следует, что С'„(г) = С„»(г). Воспользовавшись методами, которые применялись в разделе 1.2.10, получим следующие статистические характеристики для числа единичных циклов: (ппп О, ате 1, »пах и, меч 1), если и > 2.
(28) Несколько более прямой способ подсчета числа перестановок, не имеющих единичных циклов, следует из принципа включения и исключения, который имеет большое значение для многих задач перечисления. Общий принцип включения и исключения можно сформулировать следующим образом. Дано Х элементов и М подмножеств этих элементов 5», 5г,,.., 5м. Необходимо подсчитать, сколько элементов не попало ни в одно из этих подмножеств. Пусть ~5~ †чис элементов множества 5. Тогда искомое число объектов, не принадлежащих ни одному из множеств 5, равно А' — ') ~5,~+ ~ !5, с15„! — ~' Д с15, л 5,~+ ". »<г<м г<г<»<гг »й~<г«»<М + ( — 1) ~5» Л. О5гг( (29) и) — ~1) ( — ц! + (") (и — 2).
— (8) ( — 5)! + ". + (-ц" (") 0., что согласуется с (25). Принцип включения и исключения был предложен А. де Муавром (А. 6е ЪЛо»тге) [см. его работу Нос»юле оГ СЬапсез (Ьопбоп, 1718), 61-63; Згб еб. (1756, переиздано (Таким образом, сначала из общего числа А» вычитается количество элементов множеств 5»,...,5м; но это меньше искомой величины, так квк мы вычли больше, чем нужно.
Поэтому снова добавляем число элементов, которые являются общими для пар множеств, 5 Г1 5», для каждой пары 5 и 5»; но это уже больше искомой величины. Поэтому вычитаем элементы, обп»ие для каждой тройки множеств, и т. д.) Существует несколько способов доказательства этой формулы, и читателю предлагается найти один из них самостоятельно (см. упр. 25).
Чтобы подсчитать число перестановок нз и элементов, не имеющих единичных циклов, рассмотрим А» = пй перестановок и обозначим через 5, множество перестановок, в которых элемент 7' образует единичный цикл. Если 1 < 7» < уг « .. 7» < и, то количество элементов в 5, О 5, О. О 5 „— это число перестановок, в которых 7»,...,7» образуют единичные циклы. Очевидно, что оно равно (и — 1с)!. Таким образом, формула (29) принимает вид СЬе)эеа, 1957), 110 — 112].
Но значение этого принципа не было по достоинству оценено до тех пор, пока В. А. Витворт (Чг. А. %ЬНшоггЬ) не популяризировал и не развил его в своей знамени7юй книге СЛо1се апс? СЬапсс (СашЬги)бе, 18б7). В разделе 5.1 будет продолжено изучение комбинаторных свойств перестановок. УПРАЖНЕНИЯ 1. [02] Рассмотрите преобразование множества (О, 1, 2,3,4,5, б), которое меняет х на 2х шос(7. Покажите, что это преобразование является перестановкой, и представьте ее в циклической форме. 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
