и число столбцов, для которых к < t < j. Можно легко воспроизвести тг из двухстрочных представлений /(тг) и г(7г), поскольку каждый столбец I с j,k < t включен в /(тг), каждый столбец с t < j,k включен в г(7г), а оставшиеся столбцы получены путем слияния I или ° из /(тг) с ° или из г{п) слева направо.

(b) Пусть 7Г - начальная форма перестановки и пусть ст - любая перестановка из Ро(0"°1" ...т""*). Сформируйте А следующим образом: удалите первые тю элементов из ст; затем замените О элементами х, имеющими подстрочные индексы из первых по элементов тг; замените другие элементы элементами у, имеющими подстрочные индексы из оставшихся ненулевых элементов из тт. Сформируйте также р следующим образом: удалите элементы О из ст и замените Uj появлений j на Xj или t/j соответственно тому, имеют ли столбцы I из тг fc = О или к ф О, в порядке слева направо. Например, если тг =

2313?302310?о1озЕо!о, » а = Swlosiofloolo?, то получим А = Х2У2УЗХЗУ1У1Х1У2УЗХЗХ1У2ХЗУ1

я р = УЗУ2У3Х1Х3Х2У1У1У3У2У1Х3Х2Х1. и обратно, можно воссоздать тг и ст из А и р.

(c) в выражении из п. (а) этой задачи и.меем w{tt) = w{l(n)) w{r{n)), поскольку столбец 1 изп либо становится { веса Wj/wk в 1(тт) или г{тт), либо разлагается на столбцы I и к, имеющие веса Zj/zo и Zo/zk- Если 1{тт) имеет pj столбцов ° и qj столбцов , его вес равен n.irV?"") = Теперь n.LiKAi)- есть комплексное сопряжение по отношению к Ylj-iiuJj/zj); таким образом, сумма весов по всем элементам из РоСО*!" ...<") упрощается:

fc! (т11 + • • + nt- fc)!

pi+--+pt

Аналогичные соображения применимы и к г(п). Полученная сумма положительна, поскольку член для fc = О ненулевой.

23. Можно считать, что исходная цепочка была рассортирована. Пусть t = 2, m = 4, wi = W3 - Zl = Z2 = -1-1, W2 = = Z3 = Z4 - -1 В соотношениях п. (с) из предыдущего упражнения. Тогда «(тг) = (-1), где d - число столбцов {, для которых j ф к. [См. Gillis, Zeilberger, European J. Comb. 4 (1983), 221-223. Впервые этот результат был получен совершенно другим способом; см. Askey, Ismail, Koornwinder, J. Comb. Theory A25 (1978), 277-287. Авторы последней работы отыскали интересные связи между перестановками мультимножеств и интегралами произведений полиномов Лагерра (х) = ELo (n-?)(-)Vfc!-] Аналогичное соотношение для пятибуквенного алфавита несправедливо, поскольку 5! перестановок множества {1,2,3,4,5} включает 1 + 10 -f 45 с четным числом отличий и О -f 20 -I- 44 с нечетным числом.

24. (а) Двойное транспонирование восстанавливает В данном sort(yJ У..у) = (;• ) порядок сортировки будет нарушен, если найти крайний слева элемент х в верхней строке и транспонировать его влево. В результате будет получен соответствующий у. (Значение sort(? ;" ) также определяется единственным образом.)

(Ъ) Двухстрочное представление тг имеет вид

\xil... yi X21... У2 ... Xtl... yt j

a результат п. (a) дает нам тот инструмент, который необходим в данном случае. [Если R сохраняет определенные статистики в двухстрочном представлении, то полученная конструкция может быть использована для доказательства средствами комбинаторики некоторых интересных теорем. См. Guo-Niu Han, Advances in Math. 105 (1994), 26-41.]

РАЗДЕЛ 5.1.3

1. Достаточно показать, что, подставив это значение в (И), получим, что равенство выполняется при х = к, если fc > 1. Используя (7), получим формулу

г=0 0<j<r<k

к к-з

При S < к суммирование по j можно распространить на диапазон 0<j<Ti--l,a эта Сумма будет равна О (это (п + 1)-я разность полинома п-й степени от j).

2. (а) Число последовательностей aiai-.-a, которые содержат каждый из элементов (1,2,... ,д) по крайней мере по одному разу, равно {}д!, как показано в упр. 1.2.6-64; число таких последовательностей, удовлетворяющих условиям, аналогичным (10), при т - q равно ("!*), поскольку нужно выбрать п - q кз возможных знаков "=" (Ь) Сложите результаты (а) при m = n- qvLn-q~\.

3. Из (20) получаем

V -= 2 = i /JzM- (-2) п\\кГ е-2 + 1 х1е--1 е-2-1

п к

= Е~?-((-4Г-(-2Г)-

11>0

Следовательно, результат равен (-l)"""5„+i2"""(2"""-1)/(п + 1). Другой вариант таков; тождество 2/(е~ + 1) = 1 ftanhx позволяет выразить ответ в форме (-1)*"~Т„, если п нечетное, где через Т„ обозначены коэффициенты в разложении тангенса по формуле

tan г = Tl г + ГзгЗ! + Тъг/Ъ\ + • • •.

Если п > О четное, то в соответствии со свойством симметрии (7) сумма обращается в 0.

Обратите внимание, что из (18) теперь следует любопытное тождество для чисел Стирлинга:

Г п-1 fc! 2B„+i(l -2"+) 4"lfcJ(-2)* n + 1

4. (-1)"+"(,!). (Рассмотрите коэффициент при г"+в (18).)

5. () = (fc + 1)Р - fcP = (fc + 1) - fc = 1 modulop при О < fc < p. Результат следует из формулы (13), упр. 1.2.6-10 и теоремы 1.2.4F.

6. Нельзя сначала суммировать по fc, поскольку слагаемые отличны от О при сколь угодно больших j и fc, а сумма абсолютных величин бесконечна.

Вот более простой пример, демонстрирующий суть ошибки. Пусть Ujk = (fc - j) [\j - fc = 1]. Тогда

rOj/b = ((5jo) =+1, в TO время как ЕГЕ"-* = У~)(-<?fco) = -1-

j>oVfc>0 / j>0 fc>oVj>0 / *;>0

7. Да. [F. N. David, D. E. Barton, Combinatorial Chance (1962), 150-154; см. также ответ к упр. 25.]

8. [Combinatory Analysis 1 (1915), 190.] Ответ получается методом включения и исключения. Например, l/{li + Ь)!/з! (4 + h + 1бУ- есть вероятность того, что xi < < xi+i,

Простой 0(т1)-алгоритм для подсчета числа перестановок множества {1,..., п}, которые имеют соответственно длины серий {li,...,lk), был предложен Н. Г. де Брейном (N. О. de Bruijn) в Meuw Archief voor Wiskunde (3) 18 (1970), 61-65.

9. Ркт = qkm - 9fc(m+i) В (23). Поскольку k.mlkmzx = g{x,z) И g{x,0) = 1, получим

hM = j:hkiz)x> = -gix,z)il-z ) + W

Таким образом, hi (г) = - (e - l)/z; h2{z) = (e - ге==) -f- - (e - 1)/г.

10. Пусть Mn = Li H-----t- in - среднее значение; тогда Л/„х" = h{l,x), где производная берется по г и равна x/(e"-i ~ 2;) - а;/(1 - х) - М{х). По теореме о вычетах

/М(.).-d. = Mn-2(n-.) + l + + Jl!,

если интеграл берется по окруж1Юсти радиуса г, где < г < 2 (Обратите внимание на полюс второго порядка в точке 2 = 1.) Более того, абсолютное значение этого интеграла меньше, чем /M(z) г"""dz = 0(г""). Интегрируя по окружностям все большего и большего радиуса, получим сходящийся ряд М„ = 2п - -f Х](.>1 23?(l/zjJ(l - Zk)).

Для определения дисперсии воспользуемся соотношением /г"(1, х) = -2/г(1, х) - 2х{х - 1)е""/(е" - х). Рассуждая, как при определении среднего значения, но на сей раз по отношению к полюсу третьего порядка, приходим к выводу, что коэффициенты при h"(l,x) асимптотически стремятся к 4п -I- ti - 2Л/„ плюс слагаемый большего порядка малости; отсюда получается асимптотическая формула для дисперсии n-t-1 (п.71юс экспоненциально уменьшающиеся слагаемые).

11. Ркп = Ylti>i.....tt>iDiti,- ,tk-i,n,l), где D{li,l2, - Jk) - определитель Мак-Магона из упр. 8. Разлагая этот определитель по элементам первой строки, получим Ркп = соР(*;-1)п +ciP(fc 2)n Н-----hCfc 2Pin - Ек{п), где Cj и Ек определяются следующим образом:

.-..еГЛС-Г)-..!-...!):

Elin) = 1/(п + 1)! - 1/п!; Е2(п) = 1/(п + 1)!;

(-.)*е(,:з)57т.

Пусть Роп = О, C{z) = Y:c = - 1)/(1 - г) и пусть

г., v-r, , Z (е--1)х2 х2(е--еП е-1 - z

Eiz,x) = j:Ek,iin)zx = l-eJ+ (1 - x) (1-х)Ц - x - z) +

Tl, fc

Полученное рекуррентное соотношение эквивалентно формуле C{x)H{z,x) = H{z,x)/x + E{z,x); отсюда H{z,x) = E{z,x)x{l - x)/(xe~ - 1). Разлагая в степенной ряд правую часть, придем к соотношению Hi{z) = hi{z) (см. упр. 9); H2{z) = ehi(2) + 1 - е\