Chelsea, 1957), 110-112]. Но значение этого принципа не было по достоинству оценено до тех пор, пока В. А. Витворт (W. А. Whitworth) не популяризировал и не развил его в своей знаменитой книге Choice and Chance (Cambridge, 1867). В разделе 5.1 будет продолжено изучение комбинаторных свойств перестановок.

УПРАЖНЕНИЯ

1. [02] Рассмотрите преобразование множества {0,1,2,3,4,5,6}, которое меняет х на 2х mod 7. Покажите, что это преобразование является перестановкой, и представьте ее в циклической форме.

2. [10] В тексте раздела показано, как можно присвоить (а,Ь, с, d, е,/) •<- (с, d,/, Ь, е,а), выполнив ряд операций замены {х <- у) к введя одну вспомогательную переменную t. Покажите, как сделать то же самое с помощью ряда операций взаимного обмена (х О у) и без вспомогательных переменных.

3. [03] Вычислите произведение ( a/{)(cd/be {) и запишите результат в виде двухстрочной записи. (Ср. с соотношением (4).)

4. [10] Выразите (аЬd){e f)(a с f){bd) в виде произведения непересекающихся циклов.

► 5. [МЮ] В (3) приведено несколько эквивалентных способов представления одной и той же перестановки в циклической форме. Сколько существует таких представлений перестановки, в которых вообще нет единичных циклов?

6. [М23] Как изменится время выполнения программы А, если отказаться от предположения. Что все пустые слова появляются у правого края ввода?

7. [10] Если на вход программы А подается произведение перестановок (6), то чему равны величины JV, У, М, N, f/и из (19)? Каким будет время выполнения программы А без учета ввода-вывода?

► 8. [23] Можно ли модифицировать алгоритм В так, чтобы просматривать входные данные слева направо, а не справа налево?

9. [10] Программы АиВ воспринимают одинаковые входные данные и ответ дают, в сущности, в одинаковой форме. Дают ли обе программы в точности один и тот же вывод?

► 10. [М28] Рассмотрите характеристики времени выполнения программы В, а именно - величины А, В, ..., Z, о которых шла речь в тексте раздела. Выразите общее время выполнения через величины X, Y, М, N, U, V, определенные в (19), и через F. Сравните общее время выполнения программ АиВ для ввода (6), проведя вычисления, как в упр. 7.

11. [15] Найдите простое правило, по которому можно записать тг" в Циклической форме, если перестановка тг задана в циклической форме.

12. [М27] {Транспонирование прямоугольной матрицы.) Пусть матрица (а, ,) размера т У. п, т ф п, хранится в памяти, как описано в упр. 1.3.2-10, так что значение а, , находится в ячейке L -f n{i - 1) -f (j - 1), где L - это ячейка, в которой содержится ац. Необходимо найти способ транспонирования этой матрицы, чтобы получить матрицу (Ь, ,) размера п Х т, где Ь, , = аг хранится в ячейке L + m{i - 1) -f (j - 1). Таким образом, наша матрица должна быть транспонирована "на себя". (а) Покажите, что преобразование транспонирования переводит значение из ячейки L + х ъ ячейку L -f {тх mod N) для всех X из промежутка О < х < N = тп - 1. (Ь) Обдумайте методы выполнения такого транспонирования с помощью компьютера.

► 13. [М24] Докажите справедливость алгоритма J.

► 14. [М5.] Найдите среднее значение величины А, которая является одной из составляющих времени выполнения алгоритма J.

15. [Мй] Существует ли перестановка, для которой каноническая циклическая форма без скобок и линейная форма совпадают?

16. [М15] Пусть задана перестановка 1324 в линейной форме. Преобразуйте ее в каноническую циклическую форму, а затем удалите скобки. Повторяйте эту процедуру до тех пор, пока не придете к исходной перестановке. Какие перестановки получатся в ходе выполнения этого процесса?

17. [М24] (а) В Тексте раздела показано, что среди всех перестановок из п элементов существует всего п\ Нп циклов. Если эти циклы (включая единичные) записать по отдельности на п! Нп листочках бумаги, а затем выбрать наугад один из этих листочков, то чему будет равна средняя длина выбранного таким образом цикла? (Ь) Запишем п\ перестановок на п\ Листочках бумаги, наугад выберем число к и таким же случайным образом вытянем один из листочков. Чему равна вероятность того, что цикл, содержащий элемент А;, является т-циклом? Чему равна средняя длина цикла, содержащего элемент к?

> 18. [М27] Чему РЗ,внэ. Рпктпу вероятность того, что перестановка п объектов имеет ровно А: циклов длины т? Какой будет соответствующая производящая функция Gnmiz)! Чему равно среднее число т-циклов и каким будет среднее квадратичное отклонение? (В тексте раздела рассматривается только случай, когда m = 1.)

19. [НМ21] Пользуясь обозначениями из (25), покажите, что число перестановок F„o в точности равно значению п!/е, округленному до ближайшего целого, для всех n > 1.

20. [М20] Пусть все единичные циклы выписаны явно. Сколько существует различных способов представления в виде циклов перестановки, имеющей а\ циклов длины 1, аз циклов длины 2, ... (см. упр. 5)?

21. [М22] Чему равна вероятность P(n; ai, аз,...) того, что перестановка п объектов имеет ровно ai циклов длины 1, аз циклов длины 2 и т. д.?

22. [НМ34] (Следующий подход, предложенный Л. Шеппом (L. Shepp) и С. Ф. Ллойдом (S. Р. Lloyd), дает удобный и мощный метод решения задач, имеющих отношение к циклическим представлениям случайных перестановок. Вместо того чтобы считать число объектов 71 фиксированным, а число перестановок - переменным, будем предполагать, что мы независимо выбираем величины Qi,Q2,a3..., рассмотренные в упр. 20 и 21, в соответствии с некоторым распределением вероятностей. Пусть w - любое действительное число между О и 1.

a) Предположим, что выбраны случайные переменные ai,a2,Q3,... согласно правилу, которое гласит: "Вероятность того, что am = к, равна f{w,Tn, к)", где f{w,m,k) - некоторая функция. Определите функцию f{w, т, к) так, чтобы выполнялись следующие два условия: (i) Х1*>о/("i ) - Д® 0<ш<1ит>1; (ii) вероятность того, что rti -f 2q2 + Заз + ••• = п и что qi = A:i, аз = к2, аз = А:з, равна (1 - w)wР{щ к\, к2, кз,...), где Р{п; к1,к2,кз,...) определяется в упр. 21.

b) Очевидно, что перестановка, циклическая структура которой имеет вид qi , аз, аз, . , переставляет ровно qi -f 2аз + Заз + объектов. Покажите, что если Q,, i > 1, выбираются случайно в соответствии с распределением вероятностей из п. (а), то вероятность того, что ai + 2а2 + Заз + = п, равна (1 - w)w, а вероятность того, что сумма ai + 2аз + Заз + бесконечна, равна нулю.

c) Пусть ф{а1,а2,. .)-произвольная функция от бесконечного числа аргументов ai, Q3,... . Покажите, что если а,, i > 1, выбираются в соответствии с распределением вероятностей из п. (а), то среднее значение ф равно (1 - и) Х1п>оЗдесь фп обозначает среднее значение ф для всех перестановок п объектов, а переменная Oj представляет число j-циклов в перестановке. [Например, если ф{а1,а2, ) = Qi, то Значением фп будет среднее число единичных циклов в случайной перестановке 71 объектов. Из (28) следует, что ф п - 1 ДЛЯ всех 71.1

d) Используйте этот метод для нахождения среднего числа циклов четной длины в случайной перестановке п объектов.

e) Используйте этот метод для решения упр. 18.

23. [НМ42] (Голомб (Golomb), Шепп (Shepp) и Ллойд (Lloyd).) Обозначим через In среднюю длину самого длинного цикла в перестановке п объектов. Покажите, что In ~ Ап-Ь jA, где А к 0.62433 - константа. Докажите, что lim„ »oo(n - An - jA) = 0.

24. [M4I] Найдите дисперсию величины А, которая является одной из характеристик времени выполнения алгоритма J (см. упр. 14).

25. [М22] Докажите соотношение (29).

► 26. [М24] Обобщите принцип включения и исключения, чтобы получить формулу для числа элементов, которые имеются ровно в г из подмножеств Si, S2, , Sm- (В тексте раздела рассматривается только случай г = 0.)

27. [М20] Используйте принцип включения и исключения для подсчета количества таких целых чисел п в интервале О < п < amim2 - Tnt, которые не делятся ни на одно из тп1,тп2,... ,тп1. Здесь mi, тг, nit и о - положительные целые числа, такие, что nij ± mk, если j ф к.

28. [М21] (И. Каплански (I. Kaplansky).) Если "перестановку Иосифа", определенную в упр. 1.3.2-22, выразить в циклической форме, то получим (1 5 3 6 8 2 4)(7), где п = 8 и m = 4. Покажите, что в общем случае эта перестановка представляет собой произведение (пп-1 ... 2 1)"-(nn-l ... 2)"-...(пп-1)"-.

29. [М25] Докажите, что циклическую форму перестановки Иосифа при m = 2 можно получить, сначала выразив "двойную" перестановку {1, 2,..., 2п}, которая переводит j в (2) mod (2п -Ь 1), в циклической форме, а затем рассмотрев циклы в обратном порядке и убрав все числа, которые больше п. Например, при п = 11 двойная перестановка будет иметь вид (1 2 4 8 16 9 18 13 3 6 12)(5 10 20 17 11 22 21 19 15 7 14), а перестановка Иосифа -(7 И 10 5)(6 3 9 8 4 2 1).

30. [М24] Используя упр. 29, покажите, что фиксированными элементами перестановки Иосифа при m = 2 будут в точности числа (2" - 1)(2п -Ь 1)/(2 - 1) для всех таких положительных d, при которых это выражение дает целые числа.

31. [НМЗЗ] Обобщая упр. 29 и 30, докажите, что к-м казненным для произвольных т и п будет тот, кто находится в позиции х, где х можно вычислить следующим образом: положить X <- km, а затем присваивать х [(т(г -п) - l)/(m -1)J до тех пор, пока х < п. В результате среднее число фиксированных элементов для 1 < п < TV и фиксированного m при TV -> оо будет стремиться к J2k>i("~ l)V("i - (m - 1)) . [Так как это значение лежит между (т - 1)/т и 1, перестановка Иосифа имеет немного меньше фиксированных элементов, чем случайные перестановки.]

32. [М25] (а) Докажите, что для любой перестановки тг = 7Г17Г2 ... 7Г2т+1 вида

тг = (2 3)"=(4 5)"" ... (2т 2т-Ы)=" (1 2У (3 4)= ... (2т-1 2m)"="-i, где каждое Ck -либо О, либо 1, имеет место \тгк - к\ <2 для 1 < А; < 2т -I- 1.

(Ь) Для любой заданной перестановки р элементов {1, 2,..., п} постройте перестановку тг указанного вида, такую, чтобы произведение ртг давало единственный цикл. Таким образом, каждая перестановка "близка" к циклу.

33. [МЗЗ] Пусть m = 2, а п = 2+. Покажите, как построить последовательность перестановок (qj 1, Qj2, •. •, ajп; Д1, /9j2, • • •, Ап) для О < < т, имеющих следующее свойство "ортогональности"-

/(12345), ecnuij;

0!ilPjiai2Pj2 СИгпРзп - S ,

10, если I ф].

Каждое aju и fijk должно быть перестановкой чисел {1, 2, 3, 4, 5}.