/1/Zi! ll(h+h)\ l/(Zi+b + /3)! ... Il{h+l2+h + --- + lk)\\ 1 1/b! 1/(/2+/з)! ... 1/(/2+/з + --- + /0!

О 1 I/z3! ... 1/(/з + -+

\ О О ... 1 1/Zfc! /

9. [Л/50] Пусть hk{z) - YlPkmz", где pjtm - вероятность того, что общая длина первых к серий случайной последовательности (бесконечной) равна т. Найдите "простые" выражения для hi{z), /12(2) и для производящей функции h{z,x) = Ylkk{z)x° двух переменных.

10. [НМЗО] Определите гьсимптотическое поведение математического ожидания и дисперсии распределения hk{z) из предыдущего упражнения при больших к.

11. [М40] Пусть Hk{z) = YPkmz", где Ркт - вероятность того, что длина к-й серии в случайной (бесконечной) последовательности равна т. Выразите Hi{z), H2(z) и производящую функцию H{z, х) = Xj. Hk{z)x° от двух переменных через известные функции.

12. [Л/55] (П. А. Мак-Магон.) Обобщите формулу (13) на случай перестановок мультимножества, доказав, что число перестановок мультимножества {ni • 1, пг 2,..., Пт т}, имеющих ровно к серий, равно

в-)("Г)Г"»Г"0("-"„Г"0 - r-irO

где П = ni -I- П2 -I-----h Пт-

13. [05] Каким будет среднее число стопок в пасьянсе Ньюкомба, если пользоваться обычной колодой для бриджа (из 52 карт), игнорируя старшинство карт, но считая, что трефы < бубны < черви < пики?

14. [М18] Перестановка 3111231423342244 содержит 5 серий; найдите соответствующую перестановку с 9-ю сериями с помощью построения для условия симметрии Мак-Магона, приведенного в тексте раздела.

► 15. [Af.8i] (Перемежающиеся серии.) В классической литературе 19 в. по комбинаторному анализу рассматриваемый нами вопрос о сериях в перестановках не изучался, но некоторые авторы изучали попеременно восходящие и нисходящие серии. Так, считалось, что перестановка 53247618 содержит 4 серии: 532, 24 7, 761 и 18. (Первая серия будет восходящей или нисходящей в зависимости от того, ai < аг или ai > аг; таким образом, перестановки ai аг ... an, а„ ... аг ai и (п -I- 1 - а\)(п -I- 1 - аг)... (п + 1 - an) содержат одинаковое число перемежающихся серий.) Максимальное число серий Этого типа в перестановке п элементов равно п - 1.

Найдите среднее число перемежающихся серий в случайной перестановке множества {1, 2,..., п}. [Указание. Разберите вывод формулы (34).]

16. [МЗО] Продолжим предыдущее упражнение. Пусть " - число перестановок множества {1, 2,..., п}, которые имеют ровно к перемежающихся серий. Найдите рекуррентное соотношение, с помощью которого можно вычислить таблицу значений ; найдите также соответствующее рекуррентное соотношение для производящей функции Gn(z) = J2k\2 NV"- Используя это последнее соотношение, найдите простую формулу для дисперсии Числа перемежающихся серий в случайной перестановке множества {1,2,..., п}.

17. [MS5] Существует всего 2" последовательностей ai 02 ... о„, где каждый элемент ttj - либо О, либо 1. Сколько среди них последовательностей, содержащих ровно к серий (т. е. содержащих ровно к - 1 элементов aj, таких, что aj > Oj+i)?

18. [М28] Существует всего п\ последовательностей bi 62 ... Ьп, в которых каждый элемент bj - целое число, лежащее в диапазоне О < bj < п - j. Сколько среди них последовательностей, содержащих (а) ровно к нисходящих серий (т. е. содержащих ровно к соотношений элементов, таких, что bj > bj+i) и (b) ровно к отличающихся элементов?

Рис. 4. Неатакующие ладьи на шахматной доске при заданном числе к = 3 ладей ниже главной диагонали.

► 19. [Л/.8б] (Дж. Риордан (J. Riordan).) (а) Сколькими способами можно расположить п неатакующих ладей (т. е. никакие две ладьи не должны находиться на одной вертикали или горизонтали) на шахматной доске размером пхп так, чтобы ровно к из них находились на заданной стороне от главной диагонали? (Ь) Сколькими способами можно расположить к неатакующих ладей на заданной стороне от главной диагонали шахматной доски размером пхп? Например, на рис. 4 показан один из 15 619 способов расположения восьми неатакующих ладей на обычной шахматной доске с тремя ладьями на незаштрихованном участке ниже главной диагонали, а также один из 1 050 способов расположения трех неатакующих ладей на треугольной доске.

► 20. [М21] Говорят, что перестановка требует к чтений, если ее нужно просмотреть к раз слева направо, чтобы прочитать все элементы в порядке неубывания. Например, перестановка 491825367 требует четырех чтений: при первом чтении получаем 1, 2, 3, при втором - 4, 5, 6, 7; затем - 8 и 9. Найдите связь между сериями и чтениями.

21. [М22] Если перестановка ai аг ... а„ множества {1,2,..., п} содержит к серий и требует j чтений в соответствии с упр. 20, то что можно сказать о перестановке . аг ai?

22. [М26] (Л. Карлиц, Д. П. Розель и Р. А. Скоувилл.) Покажите, что не существует перестановки множества {1, 2,..., п} с п+1 - г сериями, требующей s чтений, если rs < п; однако такая перестановка существует, если п>п+1 - r>s>l,rs>n.

23. [НМ42] (Вальтер Вейссблюм (Walter Weissblum).) "Удлиненные серии" перестановки fli Аг ... On получаются, если вставлять вертикальные черточки в тех местах, где нарушается установившаяся монотонность; удлиненные серии бывают как возрастающими, так и убывающими в зависимости от того, в каком порядке ргьсположены первые два элемента, так что длина каждой удлиненной серии (кроме, возможно, последней) > 2. Например, перестановка 756238914 содержит четыре удлиненные серии. Найдите средние длины первых двух удлиненных серий бесконечной перестановки и докажите, что в пределе длина удлиненной серии равна

(1 -I- cot i)/(3 - cot i) и 2.4202.

24. [МЗО] Выразите в виде функции от р среднее число серий в последовательностях, полученных методом, который описан в упр. 5.1.1-18.

25. [М25] Пусть Ui,...,Un - независимые равномерно распределенные числа на интервале [О.. 1). Какова вероятность выполнения равенства [Ui + • + Uni = к?

2в. [М20] Обозначим через операцию Zj, которая умножает на п коэффициент при г" в производящей функции. Покажите, что результат многократного (т раз) применения »9 к 1/(1 - г) может быть представлен в терминах чисел Эйлера.

► 27. [М21] Разрастающийся лес - это лес, в котором узлы пронумерованы {1,2,..., п} таким образом, что родители всегда имеют меньшие номера, чем их потомки. Покажите, что (1) - число п-узловых разрастающихся лесов, в которых имеется fc -I-1 лист.

"5.1.4. Диаграммы и инволюции

В заключение нашего обзора комбинаторных свойств перестановок обсудим некоторые замечательные отношения, связывающие их с массивами целых чисел, называемыми диаграммами. диаграмма юнга формы (rii,пг,..., п), где fii > П2 > • • • >

> О, - это расположение ni -- пг -I-----1- различных целых чисел в массиве

строк, выровненных по левому краю, где в г-й строке содержится щ элементов; при этом в каждой строке элементы возрастают слева направо, а элементы каждого столбца возрастают сверху вниз. Например, диаграмма Юнга формы (6, 4, 4, 1) имеет вид

Диаграммы такой формы ввел Альфред Юнг (Alfred Young) в 1900 году в качестве вспомогательного средства при изучении матричного представления перестановок. [См. Ргос. london math. sac. (2) 28 (1928), 255-292; Bruce E. Sagan, the symmetric group (Pacific Grove, Calif.: Wadsworth к Brooks/Cole, 1991).] Для краткости вместо "диаграмма Юнга" мы будем говорить просто "диаграмма". инволюция - это перестановка, обратная самой себе. Например, существует 10 инволюций множества {1, 2, 3, 4}:

2 3 4\ /1 2 3 4> 4 2 3

/1 2 3 4\ /1 2 3 4\ /1 2 3 4\ /1 2 3 4\ /1 2 3 4\

VI 2 3 4/ V2 13 4J V3 2 14J 1,4 2 3 ij \1 3 2 4/

/1 2 3 4\ /1 2 3 4\ /1 2 3 4\ /1 2 3 4\ Л 2 3 4\

VI 4 3 2/ V1 2 4 3J V2 14 3J V3 4 1 2/ 1,4 3 2 1/

Термин "инволюция" первоначально использовался в классических задачах геометрии; инволюции в общем смысле, рассматриваемые здесь, были впервые изучены X. А. Роте (Н. А. Rothe), когда он ввел понятие обратной перестановки (см. раздел 5.1.1).

Может показаться странным, что мы рассматриваем диаграммы и инволюции вместе, но существует удивительная связь между этими понятиями, не имеющими, казалось бы, друг к другу никакого отношения: число инволюций множества