AOP_Tom3 (1021738), страница 169
Текст из файла (страница 169)
р > 1, р» + + р, = гп — Ь. (Этот результат получен совместно с Э. А. Бендером в 1969 году.) При гл = 2 ответ равен (э(2) + (и — 1) э(1)р + (")у )»3(хм..., х„); при т = 3 получаем (э(3) + ((и — 1)э(2) + э(1, 1))у + (" ') э(1)у' + (»)у') /1(яп, х ) и т, д. В другом выражении Ь» представляет собой коэффициент при ям в выражении где а~ = ~,<и «, <„хч, .. хч — элементарная симметричная функция. Умножение на р" и суммирование по й дает ответ в виде коэффищ»ента при зм в выражении 19. Пусть транспонированная диаграмма имеет форму (и',, г»м..., и',); ответ будет таким: /(г: пэ — г.
"и,") — /(пмпм...,пм) ~ ' +1), 2 ' ' ' ~ п(п — 1) где и = г и» = ~„п',. (Эту же формулу можно выразить в менее симметричной форме, воспользовавшись соотношением г,'»и, = -'(и+ г и, ).) Замечание. В работе Ж. ге!1, Ргос. Атег. Ма»Ь.
Яос. 4 (1953), 740 — 744, показано, что число способов размещения целых чисел (1,2,..., и) в массиве, который является "разностью" двух форм диаграмм (и»,..., и„,) 1(!м...,1м), где 0 < 11 < и, и и = 2 (л» вЂ” 1 ), равно и! бес(1/((и, — 1) — (П вЂ” »))!). 20.
Аргулзент, который был отвергнут при обсуждении теоремы Н, в данном случае справедлив - — соответствующие события действительно независимы. Замечание. Если рассмотреть все и! способов маркировки узлов, то рассмотренные здесь маркировки представляют собой маркировки, не имеющие "инверсий". Инверсии в перестановках — это то же самое, что инверсии маркировок дерена в особых случаях, когда дерево является просто путем. [См. А. В!огпег, М. 1,. %а<Ьэ, Х Сотудпагопа1 Т!зевсу А52 (1989), 165-187.] 21.
[3Г1<Ь!8ап Магб. Х 1 (1952), 81 — 88[ ПУстьд(иц...,и ) = (из-Г . +п )'. <1(иц,и. )/ из! ..и,! о(иц..., и ), где а(хц...,х ) = П з«о<1<,„(х;+ хд) Для того чтобы доказать, что д(ли..., и ) равно числу способов заполнения сдвинутой диаграммы, нужно сначала доказать, что д(иц..., и ) = д(из-1,, и ) + + д(ии ..,, л, — 1). Тождество, соответствующее упр. 17, имеет вид хз,Ь(хз + у,..., х„)/а(хз + у,...,х ) + .. -+ х„<з(хц..., х„+ у)/о'(хп,х + у) = (хг+ . + х )г5(хи..., х„)/о(хц...,х„). Оно не зависит от у; если вычислить производную, как в упр.
17, можно обнаружить, что 2х,х,/(х, — х, )+ 2х,х;/(х,— ,') = О. 22. Будем считать, что т = !г', добавив к исходной форме нули, если в этом возникнет необходимость; если зи > А! и и > О, число способов, очевидно, равно О. При т = )г' ответ таков: (и, +из — 1) (из+т — 2) ( и ) без (из+ т — 1) (из+ т — 2) (ии) Доказательсизео. Можно считать, что и = О, так что, если и > О, первые и~ столбцов массива должны быть заполнены телами з в строке з', и тогда можно рассмотреть оставшуюся форму (из — и,, ии — ии). Применив индукцию по ги, получим число способов (Йз+т — 2) (!гз+т — 3) ()г — з) без "з<зз<т (!гз+ти 2) (йз -1-ги — 3) (!зп з) где и, — )г! представляет число элементов т в строке 1'.
Суммирование по каждому изщексу Йз можно выполнить независимо; в итоге получим (из+т — 1) (из+т-2) (газ+и-2) (из+за-3) (и,к-з+1) ( ии ) без (из-гт — 1) (из+т-2) (из+из — 2) (из+т-3) (и з+1) (и ) Это н есть искомый ответ, поскольку и = О. Полученный результат можно привести к определителю Вандермонца при помощи операции над строками: Ь(из+т — 1,из+гл — 2, , и )/(т — 1)! (гп — 2)!... О!. [Ответ к этому упражнению, полученный при решении аналогичной задачи из теории групп, приводится в работе О.
Е. Е!зз!еиоод Тйеогу оГ Сгоар С)загассегэ (Ок(огд, 1940), 189.[ 23. [доипза! де Ма!5. (3) 7 (1881), 167-184.[ (Это частный случай упр. 5.1.3-8, когда все серии имеют длину 2, кроме, вероятно, последней, которая может иметь длину 1.) Если и > 2, элемент и должен оказаться на одной из крайних справа позиций в какой- либо строке.
Если поместить его в крайнюю справа клетку стоки 15 можно получить ("„'!)Аы-!А„щ способов заполнении остальных клеток. Пусть 1«(х) = ~ ~А! -!хы '/(2п — 1)! = -'(д(х) — д( — х)); »й! тогда «! ! ! )= «! " !»*-«.— ° "«ьб»(«»«ь *«)-!=.'! )-! ~2/с — 1/ ц»й! й! В выражении для Ь(г)у(з) заменим е на — е, сложим исходное и преобразованное выражения .— и получится 1!(х) = Ь (х) — 1; следовательно, Ь(х) = !ш! ю Полагая Й(з) = д(з)— Ь(е), имеем Ь(г) Ь(х) = Ь (г); значит Ь(е) = вес з и д(э) = эес я+ сап з = сап( э я+ 4 х).
Коэффициенты Ае, таким образом, — это числа Эйлера )Еа»), а коэффициенты А! ! — это числа тангенса Тг -! = ( — 1)" '4" (4" — 1)Ве»/(2п) (см. упр, 5.1.3 — 3), Таблицы этих чисел имеются в Магб. Согпр. 21 (1967), 663-688! начало погледовательнодти (Ао, А!, Ам... ) = (1, 1, 1, 2, 5, 16,61, 272, 1385, 7936,...). Самый простой способ вычисления числа тангенса и чисел Эйлера — это, возможно, построение треугольного массива 1 0 1 1 1 0 0 1 2 2 5 5 4 2 0 0 5 10 14 16 16 61 61 56 46 32 16 0 в котором частичные суммы попеременно формируются слева направо и справа налево (А.
Л. Кешрпег, Тббо)ги Маей. Х 37 (1933), 348 — 349), 25. В общем случае, если и ь — число перестановок множества (1, 2,..., и), не содержащих циклов, длина которых больше Ь, то ~ ц„ья /и! = ехр(с+ я~/2+ +я~/Ь); зто можно доказать, перемножив ехр(х) х х ехр(я /Ь), в результате чего получится ч«э! !!''(«. ) » «!«+М«+- +ьо,= (см. также упр. ).3.3 — 2Ц. Аначогично ехр(~, з я'/з) — соответствующая производящая функция для перестановок, длины циклов которых прина,ллежат данному множеству з. 26.
Интеграл от О до оо равен и!'"'ц"! ((1+ 1)/2)/2!'+~!«~, потому что его можно свести к гамма-функции (в упр. 1.2,5-20 ! = 2хэ/!/и). Таким образом, интегрируя в пределах от -оо до оо, получим О, если 1 нечетное, в противном случае — пцэ 07~!/к В!/2!э«+'!«э(С/2)!. 27. (а) Если г, < г,+! и с; < с«!!, то неравенства ! < Ц,!«,»! < «+ 1 несправедливы, Если г, > г«+! и с, > с,.!!, мы, определенно, не получим «+ 1 < Яч««! < !. (Ь) Докажите по индукции по числу строк в диаграмме для а!... а„что из неравенства а; < а«+! следует с; < с!.!!, а нз а, > а,.г! следует с, > с,+!, (Рассмотрите строку 1 и последовательность »вытесненных" элементов.) (с) Это следует из теоремы П, (с).
28. Дшгный результат получен А. М. Вершиком и С. В. Керовом (Докл. АН СССР 233 (1977), 1024 — 1028); см. также В. Г. Ьобап, Ь. А. БЬерр, А!2галсеэ !и МвсЛ. 26 (1977), 206-222. [Дж. Байк (Л. Вш)«), П. Дейфт (Р. Пе!Т!) и К. Йохансон (К. Лойапяеоп) показали в 1998 году, что среднеквадратичное отклонение равно 0(п ~ ); более того, вероятность того, что длина !7е, меньше 2!/и Ч-1пце, стремится к ехр( — /, (х — 1)и~(х)!4х), где ц»(х) = 2и (х) + хи(х) и ц(я] — асимптоты функций Айри А!(х) ез х -+ оо.) 29. Среднее число возрастающих подпоследоиательностей длиной ! равно (",) /О (Как следует из упр.
8 и 29, вероятность того, что саная длшшая возрастающая последовательность имеет длину > ел/и или < л/и/е, равна 0(1/чьй). [Х Р. Р!хоп, Р!ясгеье Мас!ь. 12 (1975), 139-142.[ 30. [Ргзстеье Маг!ь. 2 (1972), ?3-94; упрощенное доказательство принадлежит Марку ван Льювену (см. Магг чап 1.ееилчев, Е!ее!гоп!с Х СотЬьпасоПся 3, 2 (1996), рарег 4/315).[ 31. х = а(„?ьр где аь = 1, аь — — 2, а„= 2а„ь + (2и — 2)а„ь, 2 а„з"/и! = ехр(2ь+ хя) = (Х.'1„х /ьь!); х, ехР(-'п (ил — -'и+ чьй — -' — -.' !в 2) пРи четном и.
[См, Е. 1 исаЯ, ТЬдог!е дея л?ошЬгея (1891), 217-223.] 32. Пустын = 1 !"е О 0 ььь!!/ч/йкк. Тогда гпэ = ть = 1 и гп яь — т„= иьп„н если интегрировать по частям Таким образом, т„= ь„вследствие (40) 33. Верна, это равно ь)ес,"', ь (."',). [Митчелл (М!ссйе!!) в Ашег. Х Ма»6. 4 (1881), 341-344, показал, что это — число членов разложения симметричной функции, которая теперь называется функцией Шура. Конечно, если 0 < аь « а, это будет число членов в Зт, „,(хнхь,...,хьь), где иь = аш — т, пз = а„, ь — (т — 1), ..., и = аь — 1.
Данная функция Шура представляет собой сумму по всем обобщенным диаграммам формы (иь>...,п,„,) с элементами в (1,...,»п) произведений х, для всех 1 в диаграмме. Здесь обобщенная диаграмма — это то же самое, что обычная диаграмма, но в строке допустимо присутствие равных элементов. В рассматриваемом определении мы допускаем, что параметр иь равен нулю Например, Яыэ(хь, хя, хэ) = х, хь+хьхз+х,хе Ьхьхзхз+хьхяхз+хьхз+ ь ь я я хьяхз+хяхяя для обобщенной диаграммы ", ", 'ь, ььь, 'ь, 'ь, зя, ья Количество таких диаграмм равно Ь(1, 3, 5)/ь6(1, 2, 3) = 8. Распространяя алгоритмы 1 н Р на обобщенные диаграммы [Рэсьбс Х Ма»Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
