[Замечание. Производящие функции для первых трех серий выведены Кнутом в САСМ 6 (1963), 685-688. В работе Barton, Mallows, Ann. Math. Statistics 36 (1965), 249, выведена формула 1 - Hn+i{z) = (l - H„(z))/(1 - z) - L„hi{z) для n > 1, a также формула (25). Другой подход к решению этой задачи продемонстрирован в упр. 23. Поскольку соседние серии не являются независимыми, не существует простой связи между решенной здесь задачей и более простым результатом упр. 9 (последний, вероятно, и более полезен).]

12. [Combinatory Analysis 1 (1915), 209-211.] Число способов, которыми можно разместить элементы мультимножества в t различных ячейках, равно

Nt= + - 1 t + ni-l" t + nrn-l-

поскольку имеется (""j") способов разместить единицы и т. д. Если потребовать, чтобы ни одна ячейка не пустовала, то, пользуясь методом включения и исключения, найдем, что число способов равно

Пусть Рк - число перестановок, содержащих к серий; если поместить А; - 1 вертикальных черточек между сериями и t - А; дополнительных вертикальных черточек в любые из оставшихся п - А; позиций, получим один из Mt способов разделить мультимножество на t непустых различаемых частей. Следовательно,

Приравнивая эти два значения Mt можно выразить Pi, Р2, ... последовательно в терминах Ni, n2,----(Желательно отыскать более прямое доказательство.)

13. 1 -Ь il3 X 3 = 20.5.

14. Как следует из найденного Фоатой соотношения, данная перестановка соответствует

/1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4\ (31)т(1)т---т(4)= (3 1 1 2 3 4 3 2 1 1 3 4 2 2 4 4j

но согласно (33) она соответствует

/1 11122223333444 4\ \,2 443331144212123У

которая, в свою очередь, соответствует 2342341421432131. Последняя же имеет 9 серий.

15. Число перемежающихся серий равно увеличенному на единицу числу индексов j, таких, что 1 < j < п и либо Oj-i < Oj > Oj+i, либо Oj i > Oj < aj+i. При фиксированном j вероятность равна ; следовательно, среднее значение при п > 2 равно 1-1- (п - 2).

16. Каждая перестановка множества {1, 2,..., п-1}, которая имеет А; перемежающихся серий, при вставке нового элемента п во все возможные позиции порождает А; перестановок с А; такими сериями, 2 перестановки с А;--1 сериями и п -А; - 2 перестановки с А;-1-2 сериями. Следовательно,

= А;

п-1 А;

п-1 к-1

+ {п-к)

п-1 к-2

Удобно положить I ь I = 5ко, Gi{z) = 1. Тогда

Gn{z) = -((1 - г)С„ 1(г) + (2 + (п - 2)z)Gn-i{z)).

Хп = ((п - 2)хп-1 + 2п - 2).

Его решение при п > 2 имеет вид Хп - п - \. Еще одно дифференцирование приведет к рекуррентному соотношению для t/„ = Gn{l):

Уп = i((n - 4)уп-1 + 1 - f п + 6).

Положим Уп = ап + /Зп + у и, решая уравнения относительно а, jS, 7, получим t/„ = - Цп + 55 при п > 4. Следовательно, vax{gn) = (16п - 29), п > 4. Эти формулы для математического ожидания и дисперсии получены Ж. Бьенэйме (J. Bienayme) и приведены без доказательства [Bull. Soc. Math, de France 2 (1874), 153-154; Comptes Rendus Acad. Sci. Paris 81 (18,75), 417-423, см. также замечание Бертрана (Bertrand) на с. 458]. Рекуррентное соотношение для Щ}} полученр Д. Андрэ (D. Andre) [Comptes Rendus Acad. Sci. Paris 97 (1883), 1356-1358; Annales Scientiuques de IEcole Nor-maie Superieure (3) 1 (Paris, 1884), 121-134]. Андрэ обратил внимание на то, что дп{-1) = О при п > 4. Таким образом, число перестановок с четным числом перемежаюш;ихся серий равно п./2. Он также доказал формулу для математического ожидания и определил количество перестановок, которые имеют максимальное число перемежающихся серий (см. упр. 5.1.4-23). Можно также показать, что

..„=(i±£)"-,.,„r.,(l),

где дп{г) - производящая функция (18) для восходящих серий. [См. F. N. David, D. Е. Barton, Combinatorial Chance (London: Griffin, 1962), 157-162.)

(2*-) (г-г) последовательностей, заканчивающихся элементом О, а {j) последовательностей, заканчивающихся элементом 1.

18. (а) Пусть данная последовательность - таблица инверсий, которая была рассмотрена в разделе 5.1.1. Если в этой последовательности имеется к нисходящих серий, инверсия соответствующей перестановки имеет к нисходящих серий (см. ответ к упр. 5.1.1-8(е)); следовательно, ответ для данной задачи - (). (Ь) Это число удовлетворяет равенству f{n,k) = kf{n-l,k) + {п-к + l)f{n-l,k-l), значит, оно должно быть равно [См. D. Dumont, DuJce JVfath. J. 41 (1974), 313-315.)

19. (a) () в соответствии с теоремой 5.1.2В. (b) Существует (п - /г)! способов расположения п - к последующих неатакующих ладей на всей доске; следовательно, ответ - 1/(п - ку. раз Yj>oanj{i), где Onj = (") - решения для случая (а). Это приводит к {",}, принимая во внимание результат упр. 2. [В гл. 5 книги Риордана Introduction to Combinatorial Analysis (Wiley, 1958) анализируется общий случай размещения ладей.]

В прямом доказательстве этого результата, авторство которого принадлежит Э. А. Бен-деру (Е. А. Bender), каждое разбиение множества {1, 2,..., п} на А; непустых непересекающихся подмножеств соответствует некоторому расположению п - к ладей. Пусть разбиение таково:

{1,2,... ,n} = {au,ai2,... ,aini} U • • U {a/ti,... ,afc„},

где Qij < ai(j+i) при 1 < j < П{, 1 < г < A;. Ему соответствует следующее расположение ладей: ладьи помещаются в aij-й столбец a,(j i)-h строки, где I < j < Щ, 1 < i < к. Например, позиция, приведенная на рис. 4, соответствует разбиению {1, 3, 8}U {2}U{4, 6}U {5} и {7}.

20. Число чтений равно числу серий в обратной перестановке. Первая серия соответствует первому чтению и т. д.

21. Перестановка имеет п + 1 - к серий и требует п + 1 - j чтений.

22. [J. Combinatorial Theory 1 (1966), 350-374.] Если rs < п, то при некотором чтении выбирается t > г элементов, = j + 1, ..., Oi, = j + t, где n < < it. Нельзя получить am > am+i для всех m в диапазоне ik < m < ik+i- Таким образом, перестановка содержит, по меньшей мере, t - 1 таких мест, где а < am+i\ отсюда следует, что в перестановке не более п - t + 1 серий.

С другой стороны, рассмотрим перестановку «г -.. «2 Qi, в которой блок aj содержит числа = j (по модулю г) в порядке убывания; например, когда п = 9 и г = 4, эта перестановка имеет вид 847362951. Если п > 2г - 1, эта перестановка имеет г - 1 возрастаний. Значит, в ней имеется п+1 -г серий. Более того, если г > 1, она требует точно п + 1-fn/r] чтений. Можно по-другому расставить элементы в {А;г--1,..., кг+г}, не меняя числа серий; таким способом можно уменьшить число чтений до любой желаемой величины > fn/r].

Теперь предположим, что rs>n, г + з<п + 1кг,з>1. Как показано в упр. 20 и 21, молено считать, что г < s, поскольку отражение инверсии с п -I-1 - г сериями и я чтениями имеет п + 1 - S серий и г чтений. После этого рассуждения предыдущего абзаца можно применить ко всем случаям, кроме тех, где s > п + 1 - [п/г] и г > 2. Чтобы завершить доказательство, можно воспользоваться перестановкой в форме

2fc--l 2fc-l ... 1 n-l-2-r n-l-l-r ... 2fc--2 2fc ... 2 n--3-r ... n-1 n,

которая имеет n-l-l-r серий ип-l-l-r-A; чтений, О < < {п - г).

23. [SIAM Review 3 (1967), 121-122.] Допустим, что бесконечная перестановка состоит из независимых частей, подчиненных равномерному закону распределения. Пусть fk{x)dx - вероятность того, что fc-я удлиненная серия начинается с х, и пусть g{u,x)dx - вероятность того, что удлиненная серия начинается с х, при условии, что предыдущая удлиненная серия начинается с и. Тогда fi{x) = 1, fk+i{x) = fk{u)g(u,x)du. Здесь g{u,x) = Em>iffm(«,a;), где

gm{u,x) = Pr(u < Xi < • • • < A,„ > X или и > Xi > > Хт < x)

= Pt(u <Xl<---<X,n)+ phu >Xl>--->Xm)

- Pi{u < Xi < < Xm < x) - Pv(u > Xl > > Xm > x) = {4" + {1-иГ + \u-x\)/m\.

Следовательно, g{u,x) = e" + e~" - 1 - e""" и получим /2(х) = 2e - 1 - - e". Можно показать, что Д(х) стремится к предельному значению (2cos(x - 5) - sinj - cos5)/(3sin5 - cosi). Средняя длина серии, начинающейся с х, равна -I- е" - 1; таким образом, длина fc-ой удаленной серии Ck равна fk(x)(e + е" - l)dx; Ci = 2е - 3 и 2.43656; Ci = Зе - 8е -- 2 « 2.42091. Аналогичные результаты имеются в разделе 5.4.1.

24. Рассуждая, как и раньше, получим в результате

1+ е 2*(/-fgV(/ + 2pg(2-*--l-bg((2pg)-*--l)/(2pg-l))).

0<*<п

После суммирования и упрощения получим искомую функцию

2" (р + чПр(р - q)/(p + - pg) - i) + (2pg) W/(p + q)ip + q- pq)

+ + <?) +2-

25. Пусть Vj = {Ui-\-----hf/j) mod 1; тогда Vi,...,Vn - независимые равномерно распределенные числа в интервале [О .. 1), образующие перестановку, которая имеет к нисходящих