Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 65
Текст из файла (страница 65)
также исчерпывающее исследование В1сЬагс) Р. 8»ап!еу, Мевпонз Ашег, Ма»Ь. 8ос. 119 (1972)» 19. (а) Пусть 8 = (а ( а — простая перестановка, а — левый множитель в разложении х). Если 8 состоит из /с элементов, то левые множители Л в разложении перестановки вг такие, что»в(Л) ~ О есть не что иное, как ровно 2» соединительных произведений подмножеств множества 8 (см, доказательство теоремы С); следовательно, ~„р(Л) = Д ез(1+Зв(а)) = О, следовательно, р(а) = -1 н 8 непусто. (Ь) Ясно, что с(в»... в ] = р(я) = О, если вг = вв прн некотором 7' ~ Ь.
В противном случае в(вв... в„) = (-1)", где вв... в„имеет г инверсий; это ровно (-1)', где з — число четных циклов перестановки вв... в, что, в свою очередь, равно (-1)" в', где в — число циклов перестаиовни вв... в„. 20. (а) Соотношение, очевидно, следует из определения соединительного произведения. (Ь) По определению с1ев(Ь,») = ~ с(в»...в )Ь»;, ..,Ь» »8»в,...,» свв Полагая ЬО = Ьвв — агвх; и применяя результат упр.
19, (Ъ), получим Е хн,х,„д(хч ...хс„)и(х;, ...х»„), в>О»«в,,.э й*в поскольку р(вг), как правило, равно нулю. (с) Используйте результат упр. 19, (а) и покажите, что 17 г С = 1, если рассматривать произведения всевозможных элементов х как перестаноюси некоммутативных переменных, учитывая естественное алгебраическое соглашение (а + в3) г х = а 7 вг+»в г вг. Сжатое толкование этого комбинаторного доказательства и похожие доказательства других важных теорем даны Д.
Зильбергером (1). Ее»ОЬегбег, )У»затесе Ма»Ь, 56 (1985), б1-72». 21. П», ("в~"„'~"в-"), если положить пз = 0 при й < О, поскольку существует (" +"„''~'" ") способов вставить элементы пв в такую перестановку мультимножества (и» 1,..., а (пв — 1Ц. 22. (а) Перестановка слева направо 1(вг) существует в Ро(0" 1"' ...
в"') для некоторого Ус; но вместо перестановки((х) рассмотрим ее двухстрочное представление, в котором 0 размещен последним, а не первым в верхней ст1юке. Число Ь элементов О в 1(вг) и г(вг) равно ЧИСЛУ Стапбцаа Вв В ДВУХСт)ЮЧНОМ ПРЕДСтаВЛЕННИ ВГ„ДЛЯ КОТОРЫХ 7 < В < Й; Зта таКХСЕ и число столбцов, для которых 1г < 2 < я. Можно легко воспроизвести !г из двухстрочиых представлений 1(я) и ! (!г), поскольку каждый столбец '„с у, Ь < Ф вкл!очек в 1(х), каждый столбец с 1 < 1, Ь включен в г(я), а оставшиеся столбцы получеиы путем слияния !О илк 3 из((я) с 33 или О из г(!г) слева направо. (Ь) Пусть 3 — начальная форма перестановки и пусть а — любая перестановка из РО(0""1"'...ш" ). Сформируйте Л следующим образом: уделите первые по элементов из о; затем замените 0 элементами х, имеющими подстрочиые индексы из первых по элементов !г; замените другие элементы элементами у, имеющими подстрочные индексы из осяпппихся ненулевых элементов из !г.
Сформируйте также р следующим образом: удалите элементы 0 из !г и замените и, появлений у на хз или у, соответственно тому, имеют ли столбцы ! из 3 Ь = 0 или Ь 23 О, в порядке слева направо, Например, если я = ОООООО111!1222233333 ОООООО11111222233333 2мюзэзиеииезкпе а о = 32мюэц332313ООю1 то пслУчим = ззузузвзУ1У!Я!Угузвзв1узвзу! И Р = УОУОУОВ1ХОХОУ1угузузугязвзз1, И обратно, можно воссоздать !г и о из Л и р. (с) В выражении из п. (а) этой задачи имеем ю(!г) = 23(!(я)) 23(г(к)), поскольку столбец 1 из !г либо стаиовится 1 веса ш;/юэ в !(!г) или г(я), либо разлагается иа столбцы ! и „", имеющие веса 3;/33 и 33/33.
Если !(1г) имеет р столбцов О и 93 столбцов 5, его р еи П,' ,(," ,"' "/зр " ) = П,'=,( !/ !)"' '. Теперь П,' ( М ! Г" комплексное сопряжение по отношению к П' 1(гг /3!)Ог; таким образом, сумма весов по всем элементам из РО(О" 1"' ...1"') упрощается: """! ~ (") ГИ-"Г С-)ж )21+- +Ю=О Аиэлогичиые соображения применимы и к г(гг). Полученная сумма положительна, поскольку член для Ь = 0 ненулевой.
28. Можно считать, что исходная цепочка была рассортирована. Пусть 2 = 2, гл = 4, !31 = 233 = 2! = 32 = +1, ю! = в!3 = 33 = 33 = -1 в соотношениях п. (с) из предыдущего упражнения. Тогда ю(!г) = ( — 1)~, где И вЂ” число столбцов 1, для которых у ~ /с. (Сл!. С!!Бз, 23!!Ьегбег, Епгорезл Х СошЬ. 4 (1983), 221-223. Впервые этот результат был получен совершенно другим способом: см. Азйлу, 1зп!а!1, Коогпзчпг!Ог, Х СогпЬ. ТЬеогу А26 (1978), 277-287.
Авторы последней работы отыскали интересные связи между пе. рестановками мультимножеств и интегралами произведений полииомов Лагерра 7,„(в) = 2„„" О ("„+3)(-в)"/Ь!.] Аналогичное сооткошеиие для пятибуквеииого алфавита несправедливо. поскольку 5! перестановок множества (1, 2, 3,4, 5) включает 1+ 10 + 45 с четным числом отличий и О+ 20+ 44 с нечетным числом.
24. (а) Двойное траиспоиироваяие „„" восстанавливает „'.. В данном эогг(*,' "*„") = (*,', " *,", ) порядок сортировки будет нарушен, если найти крайний слева элемент х в верхней строке и транспонировать его влево. В результате будет получег соответствующий у. (зиачеиие эогг( ', "'," ) также определяется единственным образом.) (Ь) Двухстрочиое представление !г имеет вид У! ...Х11 У2 ...Зз,, У1.
Вг,) и = эогг — ( У! вг! У2 .. ви У! а результат п. (а) дает нам тот инструмент, который необходим в данком случае. (Если Й сохраняет определенные статистики в двухстрочном представлении, то получеииэл конструкция может быть использована для доказательства средствами комбинаторики иекоторых интересных теорем. См. Спо-Х!и Нап, А!!гавсез гп ЛХагЬ. 105 (1994), 26-41.) РАЗДЕЛ 5.1.3 1. Достаточно показать, что, подставив зто значение в (11), получим, что равенство выпоиняется при к.
= Й, если Й > 1. Используя (7), получим формулу При «< Ь суммирование по у можно распространить на диапазон 0 < у < и + 1, а зта сумма будет равна О (зто (п + 1)-я разность полинома н-й степени от У), 2. (а) Число последовательностей о«от... а„, которые содержат каждый из элементов (1, 2,... 4) по крайней мере по одному разу, равно ф 41, как показано в упр. 1 2 6-64; числа таких последовательностей, удовлетворя1ощих условиям, аналогичным (10), при и« = 4 равно ("„' «), поскольку нужно выбрать и — д нз возможных знаков "'=". (Ь) Сложите результаты (а) при и« = и — 4 н» вЂ” 4 — 1.
3. Из (20) получаем (-4я) (-2*) т е «' — 1 с « — 1 Следовательно. результат равен (-1)"+'В +«2"+'(2"+«-1)Д»+1). Другой вариант таков: тождество 2/(е т«+ 1) = 1+ «ап)«х позволяет выразить ответ в форме (-1) Ы пг«Т„, если и нечетное, где через Т обозначены коэффициенты в разложении твнгенса по формуче «а» з Т«г + Т«зз/3! + Т«з'~5! + ° . Если н > 0 четное, то в соответствии со свойством симметрии (7) сумма обращается в О. Обратите внимание, что нз (18) теперь следует любопытное тождество для чисеа Стирлинга; ~ п ) Ь) 2В«+«(1 — 2"+') +1 4. (-1)"4 (").
(Рассмотрите коэффициент при я е' в (18).) б («) = (Ь+ 1) — йт ьз (Ь+ 1) — Ь гя 1 тоФйор при О < Ь < р. Результат следует из формулы (13), упр. 1.2.6-10 н теоремы 1.2.4Р. 6. Нельзя сначала суммировать по Ь, поскольку слагаемые отличны от О прн сколь угодно больших у и й, а сумма абсолютных величик бесконечна. Вот более простой пример, демонстрирующий суть ошибки. Пусть а«« = (Ь вЂ” у) 1()в Й) = 1), Тогда ~ ) а «~ ы ~ ~'(5,») =+1, в то время как ~~~ ) а«« = ~ (-5«о) = -1. 1>о ~ «>е / 1>е «>е « уйе / «>о 7.
Да. (Р. Х. Ра»Ы„П, Е. Ваг«оп, СоглЬ«васопе1 СЬапсе (1962), 150 — 154; см. также ответ к упр. 25.) 8. [СошЫпагогу Ала)укм 1 (1915), 190.] Ответ получается методом включения и исключения. Например, 1/((ь + 1з)ь(з'((з + 4+ 1е)! есть вероятность того, что хь « хь +ь, хььзьз ь.ь « ° хьь+ьз+ьз и хььь.ьз+ьз+ь « " хььтьз+ьзь-ьь+ьз+ьз.
Простой О(пз)-алгоритм для подсчета числа перестановок множества (1,..., и), которые имеют соответственно длины серий (1ь.....1ь), был предложен Н. Г. де Брейиом (Н. О. ь)е Вгп1)п) в Ньеив Агсбьеь" зпог )ИзЬопь(е (3) 18 (1970), 61-65. 9. рз,„= йз,„— дм тц в (23). Поскольку ~„з йь„,х хь = —," 9(х,х) и р(х,0) = 1, получим Ь(, )=~'Ьь()* = — 19(, )(1- )+ —, =, П„+ —, х, (1 — х ')х з 'х Таким образом, Ьз(з) = е' — (е' — 1)/з: Ьз(з) = (е ' — зе') + с* — (е * — 1)/з. 10. Пусть М = Хь + .
+ Ьи — средяее значение; тогда 2„ьИих" = Ь'(1,х), где производная берется по х и равна х/(е"-' — т) — х/(1 — х) = М(х). По теореме о вычетах -и — и —, й М( )з " 'ь(~ = М„-2(п+ -') +1+ — '+ — '— —, 2ьгз у з если интеграл берется по окружности радиуса г, где )хь) < г < (хз) (Обратите внимание па полюс второго порядка в точке з = 1.) Более того, абсолютное значение етого интеграла меньше, чем у|М(х)~ г и ' ь(з = 0(г "), Интегрируя по окружностям все большего и большего радиуса, получим сходящийся ряд М» = 2п — з + Еь>ь 231(1/хь" (1 — хз)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
