серий тогда и только тогда, когда [Ui + + Un\ = к. Отсюда получается ответ {1)/п[; это свойство впервые обнаружил С. Тэнни (S. Таппу) [см. Duke Ma.th. J. 40 (1973), 717-722].

26. Например, вЦ! - z) = (z + 26z + 66г + 26г + г)/(1 - zf.

27. Следующее правило дает взаимно однозначное соответствие между перестановкой ai 02 .. - an, имеющей к нисходящих серий, и п-узловым разрастающимся лесом, имеющим А; + 1 лист. Первый корень - ai, а его потомки - лес, соответствующий аа .. .а, где к - наименьшее число, удовлетворяющее ak+i < ai, или к = п. [R. Р. Stanley, Enumerative Combinatorics 1 (Wadsworth, 1986), Proposition 1.3.16.]

РАЗДЕЛ 5.1.4 1.

А 345789\ V5 9 2 4 8 1 7У

2. Пусть Pj - элемент столбца t - 1, если р, вставляется в столбец t. Тогда {qj,Pj) принадлежит классу t-1, qj < qi, Pj < Pi\ таким образом, по инодкции приходим к заключению, что существуют индексы ii,..., it, обладающие нужным свойством. Обратно, если qj < gi, Pj < Pi и {qj,pj) принадлежит классу t - 1, то, когда вставляется pi, столбец t-1 содержит элемент < pi. Таким образом, {qi,pi) принадлежит классу > t.

3. Здесь столбцы представляют собой последовательные "вытеснения" в смысле (9), которые образуются при вставке pi. Строки 1 и 2 отражают операции над строкой 1 (ср. с (14)). Если убрать столбцы, во второй строке которых стоит элемент оо, то строки О и 2 образуют "вытесненный" массив, как в (15). Сформулированный метод перехода от строки к к строке к + 1 - это не что иное, как описанный в данном разделе алгоритм определения классов.

4. (а) Проанализируйте разные случаи. Рассмотрите сначала воздействие на строку 1 и воздействие на последовательность элементов, вытесненных из строки 1, а затем распространите анализ по индукции на диаграмму заданного размера. (Ь) При помощи допустимых обменов можно смоделировать операции алгоритма I, представив диаграмму до и после выполнения процедуры в виде канонической перестановки. Напри.мер, рядом допустимых обменов можно трансформировать

17 11 4 13 14 2 6 10 15 1 3 5 9 12 16 8

17 И 13 4 10 14 2 6 9 15 1 3 5 8 12 16

(см. (4) и (5)).

5. Допустимые обмены симметричны в направлении слева направо, а каноническая перестановка для Р очевидным образом переходит в Р, если вставлять элементы в обратном порядке.

6. Будем считать, что существует всего t классов; из них точно к имеют нечетное число элементов, поскольку элементы класса имеют вид

(см. (18) и (22)). Вытесненный двухстрочный массив имеет ровно t - к фиксированных точек, что следует из способа его формирования. Следовательно, по индукции диаграмма без ее первой строки имеет t - к столбцов нечетной длины. Таким образом, t элементов в первой строке приводят к появлению к столбцов нечетной длины по всем диаграммам.

7. Число столбцов, а именно - длина строки 1, равно числу классов (упр. 2). Число строк равно числу столбцов в . Далее, применив результаты упр. 5 (или теоремы D), завершаем доказательство.

8. Диаграмма Р, в которой содержится более v? элементов, должна иметь либо более п строк, либо более п столбцов. Однако суш;ествует и диаграмма размером пхп. [Этот результат впервые был доказан в Compositio Math. 2 (1935), 463-470.]

9. Подобные перестановки обладают взаимно однозначным соответствием с парами диаграмм вида (п, п,..., п); таким образом, с учетом (34) ответ таков:

/т1!Д(271-1,271-2,...,71)У / п! Y

V (2n-l)!(2n-2)!...n! ) ~ V(2n - l)(2n - 2)2 ... n"(n - l)"-... 1V

Воистину удивительно, что решением этой задачи является такая простая формула. Теперь можно подсчитать число перестановок {1,2,..., тп}, в которых отсутствуют возрастающие последовательности длиннее т и убывающие последовательности длиннее п.

10. Доказываем по индукции, что на шаге S3 оба массива - и P(r-i)s, и Pr(s-i) - меньше, чем Р(г+1)з и Pr(s+i)-

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

12. 1 2 } \ 2 ) -----2 } ~ \ 3 / - путь, пройденный в общей

сложности. Минимальное значение равно сумме первых п членов последовательности 1,2,2,3, 3,3,4, 4,4,4... в упр. 1.2.4-41; эта сумма равна приблизительно л/8/9п. (Почти для всех диаграмм из п элементов оценка значения минимума подходит очень близко к этой границе, как следует из упр. 29. Поэтому среднее число применений щага S3 равно в(п/).)

13. Пусть в перестановке участвуют элементы множества {1, 2,..., п}, так что а, = 1, и предположим, что qj = 2. Случай 1, j < i. Тогда 1 вытесняет 2, а значит, строка 1 диаграммы, соответствующей перестановке ai... Oi-i Oj+i... Оп, есть строка 1 в Р; вытесненная перестановка - та же, что и прежняя вытесненная перестановка, но ее наименьший элемент теперь равен 2; результат по индукции можно расширить и на п. Случай 2, j > i. Применим результат случая 1 к Р, приняв во внимание результат упр. 5 и тот факт, что {Pf = (Р).

15. Как и в (37), приведенная в качестве примера перестановка соответствует диаграмме

следовательно, искомое число равно f(l,т,п) = {I + т + пу. {I - т+1)(1 - п + 2)(т - п + 1)/ {I + 2)! (т + 1)! (п)! при условии, разумеется, что I > т > п.

16. Как следует из теоремы Н, 80 080 способами.

17. Поскольку полином д антисимметричен по х, он обращается в О при Xi = xj; следовательно, он делится на х, - xj при всех г < j. Таким образом, g{xi,... ,Хп;у) = h{xi,... ,Xn;y)A(xi,... ,Хп). Здесь функция h должна быть однородным полиномом первой степени xi,... ,Хп,у, симметричным относительно xi,... ,х„, так что h{xi,. ..,Хп;у) = a{xi + + Хп) + by для некоторых а и 6, зависящих только от п. Можно вычислить а.

положив у = 0; можно вычислить 6, взяв частную производную по у и затем положив у = 0. Получим

- Д(а;1,... ,Xi + y,... ,а;п)у=о = -к- xi,. ..,Хп) = Д(ж1,... ,а;„) -.

оу axi - Xj

Окончательный результат таков:

J2 Zii/iXi-Xj)) = е Z{x/{x,-Xj)+Xj/{Xj-Xi)) = ().

18. Она должна равняться Д(a; 1,... jin) • (Ьо+ -----1-bmу""), где все 6*, - однородные

симметричные полиномы степени m - А; от переменных х. Имеем

А{Х1,.. .,Xi+y,.. .,Хп)\у=о = А{хи... ,а;„) e(i/ ULiii - J,)),

где сумма берется по всем ("Г) способам выбора различных индексов jijfc # г. Теперь в выражении bk = х/ Y[i~iix{ - Xj,) можно скомбинировать группы из А; + 1 членов, имеющих данный набор индексов ,jk], например, при к = 2 сгруппируем наборы

из трех членов вида а"/(а - 6)(а - с) + 6""/(6 - а)(6 - с) + с"*/(с - а)(с - 6). Сумма членов каждой группы вычисляется, как в упр. 1.2.3-33: [г"~*] 1/(1 - Xiz){l - Xj г)... (1 - Xjz). Таким образом, находим, что

= е(л;-,)2:(р......

где s(pi,...,pj) - симметричная функция, содержащая всевозможные различные одночлены вида ifj ... х, с различными индексами ii,... ,ij G {1,..., n}, a внутренняя сумма берется по всем разбиениям т - к точно на j частей, таких, что pi > •• > Pj > 1, Pi + • + Pj = m - к. (Этот результат получен совместно с Э. А. Бендером в 1969 году.)

При m = 2 ответ равен (s(2) + {п - \)s{\)y -Ь (з)г/) Д(а;1,... ,а;п); при m = 3 получаем (s(3) + ((п - l)s(2) + s(l, l))y + (";Xl)y + Оу) Hxx, ... ,x„) и т. д.

В другом выражении 6 представляет собой коэффициент при г"* в выражении

где а/ = !d<ii<. .<i,<n Xii - элементарная симметричная функция. Умножение на у* и суммирование по А; дает ответ в виде коэффициента при г" в выражении

L /(1 + г(у-х1))...(1 + г(у-Хп)) \ yz \ (1-гх1)...(1-.х„) v

19. Пусть транспонированная диаграмма имеет форму (nl, Пг,..., пг)\ ответ будет таким:

где п = ]n, = XHj. (Эту же формулу можно выразить в менее симметричной форме, воспользовавшись соотношением = \(n + nf).)

Замечание. В работе W. Feit, Ргос. Amer. Math. Soc. 4 (1953), 740-744, показано, что число способов размещения целых чисел {1,2, ...,п} в массиве, который является "разностью" двух форм диаграмм {щ,..., nm)\(i, •.., Im), где О < lj < и п = (hj-lj), равно п\ det(l/((nj - j) - {h -i))0-