20. Аргумент, который был отвергнут при обсуждении теоремы Н, в данном случае справедлив - соответствующие события действительно независимы.

Замечание. Если рассмотреть все п\ способов маркировки узлов, то рассмотренные здесь маркировки представляют собой маркировки, не имеющие "инверсий" Инверсии в перестановках - это то же самое, что инверсии маркировок дерева в особых случаях, когда дерево является просто путем. [См. А. Bjorner, М. L. Wachs, J. Combinatorial Theory Л52 (1989), 165-187.]

21. [Michigan Math. J. 1 (1952), 81-88.] Пусть (т,n) = (m-l--Ч-Пт)! A(ni,... ,Пт)/ ni\... Пт1сг{п1,..., Пт), где a{xi,.. .,Xm) = П i<i<j<m{xi +Xj). Для ТОГО чтобы докэзать, что д(п1,..., Пт) равно числу способов заполнения сдвинутой диаграммы, нужно сначала доказать, что д{пи ... ,Пт) = g{ni-l,.. .,Пгп) + -- + g{ni,.. .,Пт-1). Тождество, соответствующее упр. 17, имеет вид a;iA(a;i + у,... ,x„)/a{xi +у,.. .,Хп) + • -Ь a;nA(a;i,... ,а;„ +

y)/a{xi,... ,Хп +у) = (xi -{------а;п)Д(а;1,... ,Xn)/cr{xi,. ..,Хп). Оно не зависит от у; если

вычислить производную, как в упр. 17, можно обнаружить, что 2xiXj/{xj-Xi)+2xjXi/{x - x])=Q.

22. Будем считать, что т = N, добавив к исходной форме нули, если в этом возникнет необходимость; если т > N и Пт > О, число способов, очевидно, равно 0. При т = N ответ таков:

/ Гщ +т-1\ Гп2+т-2\ Г Пт \\

\ т-1 ) \ т-1 ) " \m-l)

0 / V 0

Доказательство. Можно считать, что Пт = О, так что, если Пт > О, первые Пт столбцов массива должны быть заполнены числами i в строке г, и тогда можно рассмотреть оставшуюся форму {п1 - Пт, . ,Птп-Пт). Применив индукцию ПО ш, получим число способов

П2<к\ <П1

,rki+m-2\ fk2+m-Z\ \ т-2 ) V т-2 )

\m-2j

к2 + т - 3

где П] - kj представляет число элементов т в строке j. Суммирование по каждому индексу kj можно выполнить независимо; в итоге получим

П1+т-1\ /П2+т-2\ /П2+т-2\ /пз+т-3\ (nm-i+l\ f Пт \

\ т-1 ) \ т-1 ) \ т-1 ) \ т-1 ) " V т-1 ) \m-l)

m-1-m-l j n2--m-2 j 2+т-2\ пзЧ-т-З

Это и есть искомый ответ, поскольку Пт = 0. Полученный результат можно привести к определителю Вандермонда при помощи операции над строками: Д(т--т-1, П2-1-т-2, ..., Пт)/(пг-1)! (т-2)!... О!. [Ответ к этому упражнению, полученный при решении аналогичной задачи из теории групп, приводится в работе D. Е. Littlewood Theory of Group Characters (Oxford, 1940), 189.]

23. [Journai de Math. (3) 7 (1881), 167-184.] (Это частный случай упр. 5.1.3-8, когда все серии имеют длину 2, кроме, вероятно, последней, которая может иметь длину 1.) Если п > 2, элемент п должен оказаться на одной из крайних справа позиций в какой-либо строке. Если поместить его в крайнюю справа клетку стоки к, можно получить

{iJj)A2k-iAn-2k способов заполнения остальных клеток. Пусть

hiz) = е lan-i"-V(2n - 1)! = - 9i-z)y,

п>1

тогда

Hz)giz) = Т (- . )A2k-iAn-2k+izyn\ =(j2 An+izyn\) - 1 = giz) - 1.

в выражении для h(z)y(z) заменим г на -г, сложим исходное и преобразованное выражения - и получится h{z) ~ h(z) - 1; следовательно, h{z) = tan г. Полагая k{z) - g{z) - h(z), имеем h(z)k(z) = k{z); значит, k{z) = sec г и g{z) = sec г-1-tan z = ta.n(z+Tr). Коэффициенты A2n, таким образом, - это числа Эйлера \Е2„\, а коэффициенты А2П-1 - это числа тангенса Г2„-1 = (-1)""Ы"(4" - 1)В2п/(2п) (см. упр. 5.1.3-3). Таблицы этих чисел имеются в Math. Сотр. 21 (1967), 663-688; начало последовательности (Л), Ai, Лг, ) = (1,1,1,2,5,16,61, 272,1385, 7936,...). Самый простой способ вычисления числа тангенса и чисел Эйлера - это, возможно, построение треугольного массива

О 1 1 1 О 0 12 2 5 5 4 2 0 О 5 10 14 16 16 61 61 56 46 32 16 О

в котором частичные суммы попеременно формируются слева направо и справа налево [А. J. Kempner, Tohoiu Math. J. 37 (1933), 348-349].

25. В общем случае, если и„к - число перестановок множества {1,2,..., п}, не содержащих циклов, длина которых больше к, то <nkZ/n\ = exp(z--z/2-l- + z/к); это можно доказать, перемножив ехр(г) х • • • х exp(z/k), в результате чего получится

е"( е 1/Ii!2=i2!...

(см. также упр. 1.3.3-21). Аналогично exp(J3ags V®) - соответствующая производящая функция для перестановок, длины циклов которых принадлежат данному множеству S.

26. Интеграл от О до оо равен п-**Г{{1 + 1)/2)/2+, потому что его можно свести к гамма-функции (в упр. 1.2.5-20 t = Ixjsfn). Таким образом, интегрируя в пределах от -00 до 00, получим О, если t нечетное, в противном случае - пу*!/2(*/2)!.

27. (а) Если п < ri+i и а < a+i, то неравенства г < Qnci+i < г+1 несправедливы. Если Vi > n+i и Ci > Ci+i, мы, определенно, не получим г --1 < Qrjcj+i < г. (Ь) Докажите по индукции по числу строк в диаграмме для Oi.. .Oi, что из неравенства а; < ai+i следует с,- < Ci+i, а из Oi > щ+1 следует а > a+i. (Рассмотрите строку 1 и последовательность "вытесненных" элементов.) (с) Это следует из теоремы D, (с).

28. Данный результат получен А. М. Вершиком и С. В. Керовом (Докл. АН СССР 233 (1977), 1024-1028); см. также В. F. Logan, L. А. Shepp, Advances in Math. 26 (1977), 206-222. [Дж. Байк (J. Baik), П. Дейфт (P. Deift) и К. Йохансон (К. Johansson) показали в 1998 году, что среднеквадратичное отклонение равно &{п); более того, вероятность того, что длина меньше 2i/n + tn, стремится к ехр(- J{x - t)u(x)dx), где и"(х) = 2и(х) + хи{х) и и(х) - асимптоты функций Айри Ai(a;) as а; -> оо.]

29. Среднее число возрастающих подпоследовательностей длиной I равно (")(Как следует из упр. 8 и 29, вероятность того, что самая длинная возрастающая последовательность имеет длину > е/п или < -/п/е, равна 0{l/s/n). [J. D. Dixon, Discrete JVfath. 12 (1975), 139-142.]

30. [Discrete Math. 2 (1972), 73-94; упрощенное доказательство принадлежит Марку ван Льювену (см. Маге van Leeuwen, Electronic J. Combinatorics 3,2 (1996), paper #R15).]

31. Xn - aL„/2j, где ao = 1, ai = 2, = 2a„-i -I- (2n - 2)an-2; Ylanz"-/n\ = ехр(2г -I- z) = (E tnz/n!); Xn ~ exp(nlnn- \n+ \/n- - In 2) при четном п. [См. Е. Lucas, Theorie des Nombres (1891), 217-223.]

32. Пусть Шп = <"е~*~"Л/л/2л-. Тогда mo = mi = 1 и mn+i - Шп = nmn-i, если интегрировать по частям. Таким образо.м, гпп = tn вследствие (40).

33. Верно; это равно det (J. [Митчелл (Mitchell) в Amer. J. Math. 4 (1881), 341-344, показал, что это - число членов разложения симметричной функции, которая теперь называется функцией Шура. Конечно, если О < ai < < am, это будет число членов

в 5п1„2...пт (Ж1,Ж2, . . . ,Хт), где ш = am - т, П2 = ат-1 - (т - 1), . . . , Пт = ai - 1.

Данная функция Шура представляет собой сумму по всем обобщенным диаграммам формы (п1,...,Пт) с элементами в {1,...,т} произведений Xj для всех j в диаграмме. Здесь обобщенная диаграмма - это то же самое, что обычная диаграмма, но в строке допустимо присутствие равных элементов. В рассматриваемом определении мы допускаем, что параметр Пк равен нулю. Например, 521о(а;1,а;2,а;з) = x\x2+x\x3+XiX2+XiX2X3+XiX2X3+Xix\ + X2X3+X2XI для обобщенной диаграммы 2, з 2 з; 2. li з- Количество таких диаграмм равно Д(1, 3, 5)/Д(1, 2,3) = 8. Распространяя алгоритмы I и D на обобщенные диаграммы [Pacific J. Math. 34 (1970), 709-727], можно получить комбинаторное доказательство весьма примечательных тождеств:

т п

5A(a;i,...,a;m)5A(t/i,...,t/n) П П \-rv

т п

5л(х1,... ,х„)5лт(у1,... ,Уп) = П + "УУ

.\ i=lj = l

Здесь суммирование выпо.11няется по всем возможным формам Л, а обозначает транспонированную форму. Впервые эти тождества были найдены в работе D. Е. Littlewood, Ргос. Loadon Math. Soc. (2) 40 (1936), 40-70, Theorem V.

Замечание. Отсюда, в частности, следует, что любое произведение последовательных биномиальных коэффициентов ()(°) ... (°) можно разделить на (*) (*)... {к), поскольку это отношение есть Д(а + I,... ,а + 1,а,к - 1,..., 1,0)/А(1, ...,1,0). Значение Д(/,..., 1,0) = (Z - 1)!... 1! О! иногда называют суперфакториалом.

34. Длина уголка есть также длина любого зигзагообразного пути от левой нижней ячейки уголка {х,у) до его правой верхней ячейки (х,у). Докажем более сильный результат. Если существует уголок длиной а + Ь, то существует либо уголок длиной а, либо уголок длиной 6. Рассмотрим ячейки {х,у) = {xi,yi), {х2,У2), (ха+ь,Уа+ь) - {х,у), которые обрамляют нижнюю часть формы диаграммы. Если Xa+i = Ха, то ячейка (xa,yi) имеет уголок длиной а; в противном случае (Жо+i, Уа+ь) имеет уголок длиной 6. [См. Japanese J. Afath. 17 (1940), 165-184, 411-423. Накаяма первым рассмотрел уголки в процессе анализа групп перестановок и подошел очень близко к открытию теоремы Н.]

35. В результате вьшолнения шагов G3-G5 на 1 уменьшается точно hij элементов массива р, если Qij возросло, поскольку алгоритм отслеживает зигзагообразный путь от pj к pi„.. В следующий раз выполнение этих же шагов начнется с большего значения j или будет