i переходит в j в результате перестановки тг*"*", где к - наименьшее неотрицательное целое, такое, что тг* переводит г в число, которое < т.

14. Запишем обратную пере4;таповку к заданной в канонической циклической форме и уберем скобки. Величина A - N - это сумма последовательных элементов, которые больше заданного и находятся непосредственно справа от него Например, если исходной является перестановка (1 6 5)(3 7 8 4), то канонической формой обратной перестановки будет (3 4 8 7) (2) (1 5 6). Введем массив

Величина А - это количество "точек", т. е. она равна 16. Число точек под к-м элементом - это количество минимумов справа налево среди первых к элементов (в приведенном выше примере под элементом 7 находятся 3 точки, так как в последовательности 3 487 всего 3 минимума справа налево). Значит, среднее равно Hi + Н2 + + Нп - {п + 1)Нп - н.

15. Если первым символом линейного представления является 1, то последним символом канонического представления является 1. Если первым символом линейного представления является некоторое m > 1, то в каноническом представлении появляется "... Im...". Поэтому единственным решением является перестановка одного объекта. (Можно считать, что существует также перестановка из пустого множества объектов.

16. 1324,4231, 3214,4213, 2143, 3412, 2413,1243, 3421,1324,....

17. (а) Вероятность того, что этим циклом является т-цикл, равна п\/тп, деленному на nlHn, т. е. рш = 1/(тЯп). Средняя длина цикла равна pi + 2р2 + Зрз + = X i(m/mHn) = п/Нп (Ь) Поскольку общее число т-циклов равно п\/т, общее число появлений элементов в т-циклах равно тг!. Согласно свойству симметрии каждый элемент появляется так же часто, как и любой другой, поэтому к появляется в т-циклах п!/п раз. Следовательно, в этом случае рт = 1/п для всех кит; среднее равно Ylmi пп/п = (п+1)/2.

18. См. упр. 22, (е).

19. \Рпо - п!/е = l/(n -Ь 1)! - 1/(71 -Ь 2)! -Ь • • •, т. е. сумме знакопеременного ряда, члены которого убывают по модулю. Эта сумма меньше, чем l/(7i -Ь 1)! < \.

20. Существует всего а\ -Ь q2 -Ь • циклов, которые можно переставлять между собой, причем каждый отдельный т-цикл можно независимо от других записать m способами. Поэтому ответом будет

(«1 + а2+-)1"2"3".. .

21. l/(a;i! 1" «2! 2" ...), если тг = qi 4- 2а2 -I----; в противном случае вероятность равна 0.

Доказательство. Выпишите в ряд qi циклов длины 1, q2 циклов длины 2 и т. д., вместо элементов вставив пробелы. Например, если Qi = 1, 0:2 = 2, аз = 0:4 = =0, то получим "(-) (-) (-)". Заполните пустые позиции всеми тг! возможными способами. Тогда каждая перестановка нужного вида появится ровно Qi! 1"q2! 2" ... раз.

22. (а) Если ki + 2к2 + - тг, то вероятность в п. (ii) равна YIj>q fiJjз) ™ п° предположению равно (1 - w)w/ki! 1*/гг!2* .... Отсюда

f ,„ т h [[fi,3,kj}) [[f{w,J,kj+Sjm)=,, .у

f(w,m,k„) J -К т{кт + 1)

Тогда по индукции получим

1 /шЧ* f{w,m,k) = -[j /Кт.О).

Теперь из условия (i) следует, что

Л»,™,.,4(!)*е-.

[Другими словами, am выбирается из распределения Пуассона; см. упр. 1.2.10-15.]

Е (П/(«-)) Е Р{п;кик2,...)

кхМ,->.< ki,k2,->0

= (l-tu)w".

Следовательно, вероятность того, что ai + 2а2 Ч----< п, равна (1 - + w Н-----1- w") =

(c) Среднее равно

Е( Е (fcl,fc2,...)Pr(Ql=fcl,Q2 = fc2,...))

п>0 V*;i+2*;2+-=n /

= (1-«;)Е«"( Е (fcbfc2,...)/fci!l*fc2!2*=...).

п>0 *;i+2*;2+-=n

(d) Пусть (ai, аг,...) = аг + Q4 + «6 Н----• Среднее значение линейной комбинации ф

равно сумме средних значений аг, «4, «6,----Среднее значение am равно

/./кто,.) = Е(Ггт)тЫе

Следовательно, среднее значение ф равно

2 4 о 2

Искомым ответом будет Hn/2j

(e) Положим (ai, аг,...) = г""" и заметим, что среднее значение ф равно

= а-.,Е»"( Е КУ)

п>0 0<]<п/т- J

п>0

Отсюда

= (l-w)E«"G„m(2).

GnmW- E Tii-j P"*--:;;iiifc! E -71-

Статистическими характеристиками будут (min О, ave l/m, max [n/mj, dev y/l/m), где n > 2m.

23. Постоянная Л равна exp{-t - Ei(t)) dt, где Ei{x) = edt/t. [См. Trans. Amer. Math. 5oc. 121 (1966), 340-357, гДе доказывается множество других фактов, в частности, что средняя длина самого короткого цикла приближенно равна е~ 1п п.] Следующие члены асимптотического представления In были найдены Ксавье Гордоном (Xavier Gourdon). Первые члены ряда выглядят так:

Л„ + 1Л - ±е-п- + {±е - i(-l)")n- + (Цде + (-1)" + + и;"-)п-

где ш = е". Вильям Ч. Митчелл (William С Mitchell) с высокой точностью вычислил значение Л = .62432 99885 43550 87099 29363 83100 83724 41796-1- [Afath. Сотр. 22 (1968), 411-415]. Пока неизвестны какие-либо соотношения, связывающие Л с классическими математическими константами. Тем не менее эта же константа была вычислена в другом контексте Карлом Дикманом (Karl Dickman) в работе Arkiv for Mat., Astron. och Fys. 22A, 10 (1930), 1-14. Ho совпадение заметили только спустя много лет [Theor Сотр. Sci. 3 (1976), 373].

24. См. D Е Knщh, Proc. IFIP Congress (1971), 1, 19-27.

25. Одно доказательство (индукцией по ЛО основано на том, что когда Л-й элемент является членом S множеств, он добавляет к сумме в точности следующую величину:

(o)-(i) + (2)--- = (l-ir = 5o.

Другое доказательство (индукцией по АГ) основано на том, что число элементов, принадлежащих Sm, но не принадлежащих 5i U • • U Sm-i, равно

IMJ- Е \Sjr)SM\+ J2 \ЗзПЗкПЗм\----.

l<j<M 1<}<к<М

26. Пусть No = N и

1<Л< <Jk<m

Тогда искомой формулой будет

»,-(-)»,.,.(•+>„-...

Это можно вывести из самого принципа включения и исключения либо воспользоваться формулой

(П(;)-гг)с:,)-=(:)(*г)-(:)("то---.

как в упр. 25.

27. Пусть Sj -это числа из заданного интервала, кратные т, и пусть = ami ...mt. Тогда \Sj n 5fc = N/mmk и т. д. Поэтому ответом будет

N-nY У -----

it<t" 1<*<*""* V rnj V rnj

Это также будет решением упр. 1.2.4-30, если принять, что mi,...,mt - простые числа, являющиеся делителями N.

29. Пропуская человека, присвойте ему новый номер (начиная с п -I-1). Тогда к-м казненным будет номер 2А:, а человек с номером j для j > п прежде имел номер (2j) mod {2п -Ь 1).

31. См. CMath, раздел 3.3.