► 5. [М22] Пусть Р - диаграмма, соответствующая перестановке ai аа ... а„. Используя результаты упр. 4, докажите, что диаграмма соответствует перестановке боп ... аг ai.

6. [М26] (М. П. Шуценберже (М. Р. Schiitzenberger).) Пусть тг - инволюция с к неподвижными точками. Покажите, что диаграмма, соответствующая тг в доказательстве следствия из теоремы В, содержит ровно к столбцов нечетной длины.

7. [М20] (К. Шенстед (С. Scliensted).) Пусть Р - диаграмма, соответствующая перестановке 0102... о„. Докажите, что число столбцов в Р равно длине j максимальной возрастающей подпоследовательности < Ojj < • • • < , где ii < гг < • • < ij; число строк в Р равно длине г максимальной убывающей подпоследовательности о > Ojj > • > Ojv, где ji <J2<- - < Jr.

8. [M18] (П. Эрдеш (P. Erdos), Г. Секереш (G. Szelceres).) Докажите, что в любой перестановке, состоящей из более чем элементов, имеется монотонная подпоследовательность длиной более п; однако существуют перестановки элементов, не содержащие монотонных подпоследовательностей длиной более п. [Указание. См. предыдущее упражнение.]

9. [М24] Продолжая упр. 8, найдите "простую" формулу точного числа перестановок множества {1, 2,... ,п}, не содержащих монотонных подпоследовательностей длиной более п.

10. [М20] Докажите, что массив Р остается диаграммой-после окончания выполнения алгоритма S, если он был диаграммой до этого.

11. [20] Можно ли восстановить исходный вид диаграммы Р по окончании выполнения алгоритма S, если известны только значения г и s?

12. [М24] Сколько раз выполняется шаг S3, если алгоритм S многократно применяется для исключения всех элементов из диаграммы Р формы (щ, пг,..., Пт)? Каково минимальное значение этой величины по всем формам, таким, что щ +П2-\------nm = п?

13. [М28] Докажите теорему С.

14. [М43] Найдите более прямое доказательство теоремы D, п. (с).

15. [М20] Сколько перестановок мультимножества {I а, т Ь, п с) обладают следующим свойством: если читать перестановку слева направо, то число прочитанных букв с никогда не превышает числа букв Ь, которое, в свою очередь, не превышает числа букв а? (Например, перестановка ааЬсаЬЬсаса обладает этим свойством.)

16. [М08] Сколькими способами можно топологически рассортировать частичное упорядочение, представляемое графом (39)?

17. [НМ25] Пусть

д{Х1,Х2, ...,Xn\y) = Xi i{Xi+y,X2, ...,Хп)-¥Х2 i{X\,X2+y, ...,Хп)

-I-----\-Xri A{xi,X2,.. .,Хп+у)-

Докажите, что

д{хиХ2,.. .,Xn;y) = {xi+X2-i----+ + (2)!/) А{хиХ2,... ,а;„).

[Указание. Полином д однородный (все слагаемые имеют одинаковую суммарную степень) и антисимметричный по х (знак д изменится, если поменять местами Xi и Xj).]

18. [НМЗО] Обобщая упр. 17, вычислите при m > О сумму

xTMXi+y, Х2,..., Х„) + ХА{хиХ2+У: ...,Хп) + ---+ XA(Xl,X2, . . . , Хп+У)

19. [М40] Найдите формулу для определения числа способов, которыми можно заполнить массив, подобный диаграмме, но без первых двух клеток в первой строке, например массив такой формы:

m-2 клеток П2 клеток пз клеток

(Элементы в строках и столбцах должны располагаться в порядке возрастания, как в обычных диаграммах.)

Иными словами, сколько диаграмм формы (ni, Пг,..., Пт), составленных из элементов {1, 2,..., шН-----\-Пт}, содержат элементы 1 и 2 в первой строке?

► 20. [М24] Докажите, что число способов такой разметки узлов данного бинарного дерева элементами {1,2, ...,п}, чтобы метка каждого узла была меньше метки любого из его потомков, равно частному от деления п! на произведение "длин поддеревьев", т. е. количеств узлов в каждом поддереве (см. теорему Н). Например, число способов разметки узлов дерева

равно 11! /11 • 4 • 1 • 5 • 1 • 2 • 3 • 1 • lotl 1 = 10-9-8-7-6 (ср. с теоремой Н).

21. [НМ31] (Р. М. Тролл (R. М. Thrall).) Пусть числа тц > пг > • • > Пт описывают форму "сдвинутой диаграммы" в которой строка г + 1 начинается на одну позицию правее, чем строка г; например, сдвинутая диаграмма формы (7, 5,4,1) имеет вид

Докажите, что число способов такого заполнения сдвинутой диаграммы формы (ni, Пг,..., Пш) числами 1, 2,..., п = тц+пгН-----Ыш, чтобы числа во всех строках и столбцах располагались в порядке возрастания, равно частному от деления п! на произведение "длин обобщенных уголков"; на рисунке заштрихован обобщенный уголок длиной 11, соответствующий клетке строки 1 и столбца 2. (Уголки в левой части массива, имеющей вид перевернутой лестницы, имеют форму буквы U, повернутой на 90°, а не буквы L.) Итак, существует

17!/12 11-8-7-5-4-1-9-6-5-3-2-5-4-21-1

способов такого заполнения изображенной выше формы, чтобы элементы во всех строках и столбцах располагались в порядке возрастания.

22. [М39] Сколькими способами можно заполнить массив формы (ni,па,...,Пт) элементами множества {1,2,..., N}, если допускаются одинаковые элементы, причем в строках элементы должны располагаться в порядке неубывания, а в столбцах - только в порядке возрастания? Например, простую форму из т строк (1,!,...,!) можно заполнить () способами; форму из одной строки (т) можно заполнить (""j") способами; форму (2,2) можно заполнить j С) () способами.

► 23. [НМЗО] (Д. Андрэ (D. Andre).) Чему равно число способов {А„) такого заполнения числами {1, 2,..., п} массива из п ячеек

чтобы во всех строках и столбцах они располагались в порядке возрастания? Найдите производящую функцию g{z) - YAnz"/n\.

24. [М28] Докажите, что

пт-{п-п)\/ т \ / т \ (т\ 2

0<q\ ,,..,qn<m

[Указания. Докажите, что A.{ki+n - l,...,kn) = Д(т-Лп+п-1,...,m -fci); разложите диаграмму формы п х (т - п + 1) способом, аналогичным (38); преобразуйте сумму, как при выводе тождества (36).]

25. [М20] Почему (42) является производящей функцией для инволюций?

26. [НМ21] Вычислите хexp(-2x7\/i) rfa; при неотрицательном t.

27. [М24] Пусть Q - диаграмма Юнга из элементов {1, 2,..., п} и пусть элемент г находится в строке Ti и столбце а. Мы говорим, что г "выше" j, если п <rj.

a) Докажите, что при 1 < г < п элемент i выше i+1 тогда и только тогда, когда d > Cj+i.

b) Пусть Q такое, что (Р, Q) соответствуют перестановке

(

\ai 02

... anj

Докажите, что г выше г + 1 тогда и только тогда, когда Oj > Oj+i. (Следовательно, можно найти число отрезков перестановки, зная только Q. Этот результат получен Шуценберже.)

с) Докажите, что при 1 < г < п элемент г выше i + 1 в Q тогда и только тогда, когда г + 1 выше г в Q.

28. [М.5] Докажите, что средняя длина самой длинной возрастающей подпоследовательности в случайной перестановке множества {1,2, ...,п} асимптотически приближается к 2у/п? (Это средняя длина первой строки в соответствии из теоремы А.

29. [НМ25] Докажите, что случайная перестановка п элементов имеет возрастающую подпоследовательность длиной > I с вероятностью < (") !. Эта вероятность равна 0{l n), если I = еу/п + 0(1), и 0(ехр(-Су)), если I -- Zs/n, с = 61пЗ - 6.

30. [Mil] (М. П. Шуценберже (М. Р. Schiitzenberger).) Покажите, что операция перехода от Р к Р - частный случай операции, которую можно связать с любим конечным частично упорядоченным множеством, а не только с диаграммой. Пометьте элементы частично упорядоченного множества целыми числами {1,2,..., п) так, чтобы эта система меток была согласована с частичным упорядочением. Найдите двойственную систему меток, аналогичную (26), путем последовательного удаления меток 1, 2, ..., передвигая