Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 68
Текст из файла (страница 68)
Взбгпег, М. Ь. %ас)ш, Х Согп1ипасопа) Тйеогу А32 (1989), 1бб — 187.) 21. (айС1адайМаСЬ.Х 1(1962),81-88.) ПУСтЬд(йс,...,й ) = (йс+ . +й )'. 13(йс,...,Л )/ йс!...й,„',сс(йс,...,й ), где а(хс,...,х ) =П1«2< (х;+х1). Для тсао чтобы доказать, что д(111,..., й ) равно числу способов заполнения сдвинутой диаграммы, нужно сначала доказать, что д(пс,..., й ) = д(й1 — 1,..., и ) + ° + д(й„..., и -1). Тождество, соответ- СтВУЮЩЕЕ УПР. 17, ИМЕЕТ ВИД Х1Л(Х1+ д,...,Хп)/а(Х1+ д,..., Хп) + .
+ Х«1а(Х1,...,Хп + д)/а (Хс,..., Х„+ У) = (Хс+ . + Хп)22(Х1,..., Х )/а(Х1,..., Х„). ОНО НЕ ЗаВИСИт От д; ЕСЛИ вычислить производную, как в упр. 17, можно обнаружить, что 2х,х1/(х~1-х~)+2х2х /(х~- х2) =О, 22. Будем считать, что йс = АС, добавив к исходной форме нули, если в атом возникнет йеобходимостгб если гй > Ас и и, > О, число способов, очевидно, равно О.
При гй = Ас ответ таков: (й1+т-1) (йз+т — 2) ( й, ) бес (й1 + сй 1) (й2+ сй 2) (йп1) Дакааайсельсйсеа. Можно считать, что йп« = О, так что, если й > О, пеРвые й, столбцов массива должны быть заполнены числами 1 в строке 1, и тогда можно рассмотреть оставшуюся форму (йс-й,...,й -й ). Применив индукцию по т, получим число способов (йс+ — 2) (32+ -3) (й беС «252 <щ (31+си-2) (йз+ гй-3) ()сп, 1) где й1 — 1с представляет число элементов щ в строке 2. Суммирование по кэзкдому индексу Й1 можно выйолнить независимо; в итоге получим (и1+ш-1) (й2+1й-2) (й2+ш-2) (йа+ш-3) (й«п 1+1) ( йм ) бес (йс+щ-1) (йт+ш-2) (йзтш-2) (йэ+т-3) (йс«1+1) (й ) Это и есть искомый отве~, поскольку и = О, Полученный результат можно привести к определителю Вайдермонда при помощи операции нвд строками: 23(йс+Щ-1, йг+гй-2, ..., и )/(йс-1)! (йс-2)!...
ОЬ (Ответ к этому упражнению, полученный при решении аналогичной задачи из теории групп, приводится в работе О. Е, (асс)евоос) Тйеогу оК Сгоир С)сага<сага (Ох(огд, 1940), 189.] 23. (Хоагва( сге Масй (3) 7 (1881), 187-184) (Это частный случай упр. «.1.3-8, когда все серии имеют длину 2, кроме, вероятно, последней, которая может иметь длину 1.) Если и > 2, элемент и должен оказаться иа одной из крайних справа позиций в какой- либо строке. Если поместить его в крайнюю справа клетку стоки 7с„можно получить ("„'!)Ать !А„ы способов заполнения остальных клеток.
Пусть Ь(х) = ~ Аз„-!з~" ~/(2п — Ц! ы 1(д(з) — д(-х)); !? ! тогда и! и ! = Е ! " ~ж,!. „„."!, . (Е !.„,?,.) - =, ! ! ~2Ь вЂ” 1 г ьл? ! !!й ! В выражении для Ь(з)у(э) заменим э на -э, сложим исходное и преобразованное выражения — и получятся Ь(х)э = Л'(з) — 1; следовательно, Ь(з) = Сапе. Полагая Ь(з) ж д(к)— Ь(з), имеем Ь(г) Ь(з) = Ь'(э); значит, Ь(е) = вес з и д(х) = эес э+сап э = сап( ! з+-'к). Коэффициенты Аэ„таким образом, — это числа Эйлера ]Ее„], а коэффициенты Аз ! — это числа тангенса Гз~ ! = ( — 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 О 1 2 2 5 5 4 2 О О 5 10 14 16 16 61 61 56 46 32 16 0 в котором частичные суммы попеременно формируются слева направо и справа налево [А. Л. Кещрпег, ТоЬойц Маей. Х 87 (1933), 348-349].
25. В общем случае, если и„! — число перестановок мнозкества (1, 2,..., и), не содержащих шзклов, длина которых больше Ь„то ~ , 'н,ьэь/п! = ехр(з+ зэ/2+ + э~/Ь); это можно доказать, перемнсвкив ехр(з) х . х ехр(э /Ь), в результате чего получится !!!'!Р Г'Ь~,.) !! ь!!+еж+ +Ш! ь (см. также упр. 1.3.3-21). Аналогично ехр(2, з э'/е) — соответствующая производящая функция для перестановок, длины шюклов которых принадлежат данному множеству Я.
26. Интеграл от 0 до оо равен пр+'!!~Г((с + 1)/2)/2!'+~!!~, потому что его можно свести к гамма-функции (в упр. 1.2.5-20 С = 2яэ/!/й). Таким образом, интегрируя в пределах от -оо до со, получим О, если 1 нечетное, в противном случае — н!'+м! ~ !/к В!/2!з!+'!! (1/2).'. 27. (а) Если г! < г,+! и с; < с!+!, то неравенства ! < Я,„.!+! < ! + 1 несправедливы. Если г! > г,+! н с, > с!е!, мы, определенно, не получим !'+ 1 < б)...,.+! < Ь (Ь) Докажите по индукции по числу строк в диаграмме для а!...
аь что из неравенства а! < а,е! следует с; < с!+!, а из а! > а,е! следует с, > с,+!. (Рассмотрите строку 1 и последовательность "вытесненных" элементов.) (с) Это следует из теоремы П, (с). 28. Данный резульщт получен А. М. Вершиком н С. В. Керовом (Докл, АН СССР 233 (1977), 1024-1028); см. также В. Г. Ьойап, Ь, А. 8ЬеРР, АсЬвосез !и МаСЬ. 26 (1977), 206-222. ]Дж. Байк (Л. Вай), П, Дейфт (Р. 1)е!Й) и К. Йохансон (К. Лойапвеоп) показали в 1998 году, что среднеквадратичное отклонение равно В(п!~е); более того, вероятность того, что длина меньше 2!/й+ Сп'!~, стремится к ехр(- /! (х — 1) н (я) ю(х), где пв(х) = 2из(х) + хи(х) и и(х) — асимптоты функций Айри А1(я) вэ х -? оо.] 29. Среднее число возрастающих подпоследовательностей длиной 1 равно (,)/Л.
(Как следует из упр. 8 и 29, вероятность того, что самая длинная возрастающая последовательность имеет длину > еь/й или < ~/й/е, равна О(1/ь/й). (Л. О. 111хоп, Ебясгесе МаСЬ. 12 (1975), 139-142.] 30. ]Ебзсге1е МасЬ. 2 (1972), 73-94; упрощенное доказательство принадлежит Марку ваи 41ыовену (см. Матс яап Ьеепъеп, Е1есзгоп/с Х СошЬ1паголсз 3, 2 (1996), рарег ФВ15).] 31. х„= о1«7з1, где ао = 1, а~ = 2, а„= 2а«-~ + (2п — 2)а«-з; 4 а«з /и! = екр(2з+ зз) ж (2 1«з /и ) ° х«екр(7п1пп 7н+ ~lй — т — з )п2) при четном и, (Сьь Е. Впсаз, ТЬеойе г(ез 7«огпбгеэ (189Ц, 217-223.) 32. Пусть т« = / 1«е и 0 ~з41/~/йяя. Тогда гяо = гл~ = 1 н ш «~ — т = пщ м если интегрировать по частям. Хаким образом, т„= 1«вследствие (40).
33. Верно: это равно бес';", ( ",). (Митчелл (МйсЬеН) в Ашег. э. МасЬ. 4 (1881), 341-344, показал, что это —. число членов разложения симметричной функции, которая теперь наэьпается функцией Шура. Конечно, еглн 0 < а~ < < а, это будет число членов в Я „„„„(хпхз,, ..,х„,), где п~ = а,„— ш, пз = а г — (ш — Ц, ..., н„, = а~ — 1. Данная функция Шура представляет собой сумму по всем обобщенным диаграммам формы (пп..., и ) с элементами в (1,..., т) произведений х для всех у в диаграмме. Здесь обобщенная диаграмма — это то же самое, что обычная диаграмма, но в строке допустимо присутствие равнык элементов.
В рассматриваемом определении мы допускаем, что параметр пь равен нулю. Например, Яиэ(хм ха,хз) = я~хе+я~ха+х~хз+х~хзхз+х~хзхз+х,хз+ 3 2 2 2 хе~ха+хзхз~ для обобщенной диаграммы ", ", ]з, з~з, 'з, 'з, зз, зз. Количество такихдиаграмм равно Ь(1, 3, 5)/Ь(1, 2, 3) = 8. Распространяя алгоритмы 1 н В на обобщенные диаграммы (Рас16с з. МагЬ. 34 (1970), 709-727], можно получить комбинаторное доказательство весьма примечательнмх тождеств: « Ял(хн ° °,х «)Ял(У» ° °,9«) = П П Л 1 хауз «« ) Ял(хм...,хю)Яьг(рм ° ° 9«) = Пп(1+хоуз) Здесь суммирование выполняется по ж:ем возможным формам А, а Ат обозначает транспонированную форму. Впервые эти тождества были найдены в работе )2.
Е. ЕВ41еиооб, Ргоа Ьопг)оп МагЬ. Яос. (2) 40 (1936), 40-70, ТЬеогепз Ъ'. Замечание. Отсюда, в частности, следует, что любое произведение последовательных биномиальнык коэффициентов (') ( +')... ('+') можно разделить на (~) ( +')... (~+'), поскольку это отношение есть 3(а+1,...,а+ 1,а,й — 1,...,1,0)/Ь(1,...,1,0). Значение Ь(1,...,1, 0) = (1 — Ц!... 1! О! иногда называют суперфакториалом. 34. Длина уголка есть такэке длина любого зигзагообразного пути от левой нижней ячейки уголка (х,у) до его правой верхней ячейки (х',у'). Докажем более сильный результат. Если существует уголок длиной а + Ь, то существует либо уголок длиной а, либо уголок длиной Ь. Рассмотрим ячейки (х,у) = (хну~), (хз,уз), ..., (х,+му,+ь) = (х',у'), которые обрамляют нижнюю часть формы диаграммы.
Если х,+~ = х,, то ячейка (х„у~) имеет у~элок ллнной а; и противном случае (х„«п 9 +ь) имеет угокок длиной Ь. [Слс Уарапезе Х МаСЬ. 17 (1940), 165-184, 411-423. Накаяма первым рассмотрел уголки в процессе анализа групп перестановок и подошел очень близко к открытию теоремы Н.] 36. В результате выполнения шагов СЗ.С5 на 1 уменьшается точно Ьч элементов массива р, если 941 возросло, поскольку алгоритм отслеживает зигзагообразный путь от р„к 1ь«, В следующий раз выполнение этих же шагов начнется с большего значения 7 или будет проходить выше либо па уровне того же зигзага, что и в предылущий раз, Таким образом, массив 9 заполняется слева направо и сиизу вверх; для того чтобы заставить процесс идти в обратном направлении, мы должны организовать движение слева направо и сверху вниз.
Н1. [Инициализация.] Присвоить рзз о О, 1 < / < и, и 1 < з < и'„Затем присвоизь з +- 1 н У о- и,. Н2. [Поиск ненулевой ячейки.] Есая до > О, перейти к шагу НЗ. В противиом случае, если з < и';, увеличить з на 1 и повторить этот шаг. В противном случае, егзи / > 1, уменьшить з' ца 1, присвоить з +- 1 и повторить этот шаг, В противиом случае остаиовить процесс (массив з! теперь обиулеи). НЗ. [Уменыпеиие 4, подготовка к движению по зигзагу,] Уменьшить 4„.
па 1 и присвоить ! +- з, й о- пь Н4. [Переход вниз или влево.! Если ! < пь и рм > рьзтпь, увеличить ! иа 1 и вернуться к шагу Н4. В противном случае, если !з > /Ь уменьшить й на 1 и вернуться к шагу Н4. В противном случае вернуться к шагу Н2. 5 Первый зигзаг для данного столбца 3 заканчивается приращением р ., поскольку рз < . < р„влечет за собой р„> О. Кюкдый последующий путь для столбца / проходит "зз ниже или па том же уровне, что и предыдущий, так что он также закончится на ро., 5 Неравенства, которые используются в этом способе, свидетельствуют о том, что построеииый алгоритм является обратным по отношенизо к описанному при постановке задачи.
[Х Сотй!па!от!а! Тйеогу АЗ1 (1976), 216-221.] 36. (а) Коэффициент пРи ам есть число Решений т = ) й69зз, так что можно РаспРостранить иа данный случай результат предылущего упражнения. (Ь) Если аз, ..., аь— любые положительные целые числа, можно доказать, испатьзуя индукции по й, что [ "]1/(! — е)(1 — ")" (1 — ") = ! 1/о ".аз+О(пз' ').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
