AOP_Tom3 (1021738), страница 167
Текст из файла (страница 167)
Если 1(л) имеет р, столбцов " и 91 стачбцов 10, ега вес равен П,,(з,гш,' 1/3,'иг,' 1) = П 1(шг/31)УУ У'. Теперь П,,(шг/21) 41 есть комплексное сопряжение по отношению к П',(игг/2,)4', таким образом, сумма весов по ВСЕМ ЭЛЕМЕНтаМ ИЗ Ро(0 1га ... Ра) уПращаЕтСя Уй (П! + . + Н! — К)! ~ ~(Пг) (Пг) (Ш! )ГЛ (Шг )Уг Ю4-" тш=ь Аналогичные соображения применимы и к г(л).
Полученная сумма положительна, поскольку член для Ь = О ненулевой. 23. Можно считать, что исходная цепочка была рассортирована. Пусть 2 = 2, гп = 4, шг = шз — — 21 = 22 = +1, шз = ш4 = 3 = 24 = — 1 в соотношениях п. (с) из предыдущего упражнения.
Тогда !0(гг) = (-1)~, где 41 — число столбцов '„, для которых 1 ф Ь. (См. С!В!в, 2ег)Ьегбег, Еигареаи Х СашЬ, 4 (1983), 221 — 223. Виервые этот реэульлнт был получен совершенно другим способом; см. Авйеу, 1вша!1, Коогигуш41ег, Х Сал!Ь. ТЬеогу А25 (1978), 277-287. Авторы последней работы отыскали интересные связи между перестановками мультимножеств и интегрю!ами произведений полнномов Лагерра Е„(х) = ~,", о („"+!) ( — г) ~/ЬЬ) Аналогичное соотношение для пятибуквенного алфавита несправедливо, поскольку 51 перестановок множества (1,2,3,4, 5) включает 1 + 10 + 45 с четным числом отличий и 0 + 20 + 44 с нечетным числом.
24. (а) Двойное транспонирование "„',* восстанавливает "„,*. В данном загс(„*,' " '„" ) = (*~, - ",", ) порядок сортировки будет нарушен, если найти крайний слева элемент х в верх- 27 -. У" ней строке н транспонировать ега влево. В результате будет получен соответствующий у.
(Значение вот!(*,'," ) также определяется единственным образом.) 21 У' (Ь) Двухстрочное представление л имеет вид У1 ...г! 1 У2 ...х2 2 ... Уг ...Хгог) гг = ьаг! ( х!! ... У! хз! ... УЗ ... х!1 . Уг а результат п. (а) дает нам тот инструмент, который необходим в данном случае.
[Если Н сохраняет определенные статистики в двухстрочном представлении, то полученная конструкция может быть ислольэована для доказательства средствами комбинаторики некоторых интересных теорем. См. Сио-Х!и Нап, Аг)галеев!и Магй. 105 (1994), 25 — 4Ц 8. [Сошбзпаоогу Ала1ущэ 1 (1915), 190.) Ответ получается методом включения и исключения. Например, 1/(!з + Н)'1з'(14 + 14 + 1в)! есть вероятность того, что хз « .. хззтз„ хзз ззз у з « ' ' ' хззз ззыз и хззщзщзэз « ' ' ' хзз ззззззыззззмз.
Простой 0(пз)-алгоритм для подсчета числа перестановок множества (1,..., и), которые имеют соответственно длины серий ((з,,1з), был предложен Н. П де Брейном (ЬЬ С. з1е Вгиззв) в Нзеозг АгсбзеГ тоог Рззэйипз1е (3) 18 (1970), 61-65. 9. рзм = дзм — дщ +з1 в (23). Поскольку ~ з дзтх хз = — *д(х,х) и д(х,О) = 1, получим 1з(з,х) = ) Ьз(х)х = — д(х,з)(1 — х ) + — з = +— х х з (1 — хз)х х зх 1 — х 1 — х еы П' — х 1 — х' Таким образом, Ьз(х) = е' — (е' — 1)/-, Из(х) = (ез' — хе*) + е — (ез* — 1)/х.
10. ПУсть ЛХз зз Хз + + Մ— сРеднее значение; тогда Л„Мзх" = Ь'(1,х), где пРоизводная берется по х и равна х/(е* ' — х) — х/(1 — х) = М(х). По теореме о вычетах — ф М(х)х " з(з = М„ — 2(п + -') + 1 + ' + 27гз Х хз — 1 йз — 1 ' если интеграл берется по окружности радиуса г, где )хз) < г < ~хз) (Обратите внимание ца полюс второго порядка в точке х = 1.) Более того, абсолютное значение этого интеграла меньше, чем ~~ИХ(з)~г " 'з(з = 0(г "). Интегрируя по окружностям все большего и большего радиуса, получим сходящийся ряд ЛХ„= 2п — з + ) з>з 2Я(1/х~",(1 — хз)).
Для определения дисперсии воспшзьзуемся соотнозпением Ио(1, х) = — 2Ь'(1, х) — 2х(х— 1)е '/(е» ' — х) . Рассуждая, как при определении среднего значения, но на сей раз по отношению к полюсу третьего порядка, приходим к выводу, что коэффициенты при И" (1, х) асимптотически стремятся к 4п + — н — 2ЛХ„плюс слагаемый большего порядка малости, з отсюда получается асимптотическая формула для дисперсии - н+ о (плюс экспоненциально з з уменьшающиеся слагаемые) 11 Рз = Х„'зз>з,,з„>зР(сз,,1з з, и, 1), где Р((з,1з,,1з) — определитель Мак<Магона из упр.
8. Разлазая этот определитель цо элементам первой строки. получим Рз„ж союз зж+сзР~з зж+ .+со зрзз — Ез(п), где с, и Ез определяются следующим образом: (1 +" +1з )! ( х- ~у / (пзч-1).' зз,,ззз.зйз >о =( — 1)' ~~ (, ) ( ), = — 1+с( —,— —,+ .+( — 1)'Ч; ~>о Ез(п) = 1/(и+ 1)! — 1/и!; Ез(п) = 1/(и + 1)!; Ез(п)=( — 1) ~( ™ ) Р И>3. .>а Пусть Ро„= О, С(х) = 2" сзх = (е' ' — 1)/(1 — х) и пУсть (е з — 1)х хз(е з — е') е* — 1 — х Е(юх) = ~ Езтз(п)з" х = 1 — ез + ' + Полученное рекуррентное соотношение эквивалентно формуле С(х)Н(з, х) = Н(з, х)/х + Е(х,х), отсюда Н(з,х) = Е(з,х)х(1 — х)/(хе' ' — 1). Разлагая в степенной ряд правую часть, придем к соотношению Нз (х) = Ьз(х) (см.
Упр. 9); Нз(х) = еЬз(х) + 1 — е . (Замечание. Производящие функции для первых трех серий выведены Кнутом в САСМ 6 (1963), 635-688. В работе Ваггоп, Ма!)онз, Апл. МаГЪ. Я!а!!зг!гз 36 (19б5), 249, выведена формула 1 — Н л.1(л) = (1 — Н (л))/(1 — х) — Ь„51(з) для и > 1, а также формула (25). Другой подход к решению этой задачи продемонстрирован в упр. 23. Поскольку соседние серии не являются независимыми, не существует простой связи межпу решенной здесь задачей и более простым результатом упр. 9 (последний, вероятно, и более полезен).) 12. [Сошб!пасогу Апа!уэ!з 1 (1915), 209 — 211.] Число способов, которыми можно разместить элементы мультимножества в ! различных ячейках, равно м — ('+"' ')( "' ) ( +" ) поскольку имеется ('т"' ') способов разместить единицы и т.
д. Если потребовать, чтобы л1 ни одна ячейка не пустовала, то, пользуясь методом включения и исключения, найдем, что число способов равно Пусть Р» — число перестановок, содержащих !г серий; если поместить к — 1 вертикальных черточек между сериями и ! — !г дополнительных вертикальных черточек в любые из оставшихся и — к позипий, получим один из М~ способов разделить мультимножество на ! нгпустых различаемых частей. Следовательно, М~=Р~+( )Р, 1+( )Р~ г+ Приравнивая эти два значения М~ можно выразить Рн Рю ... последовательно в терминах !гн Хю .... (Желательно отыскать более прямое доказательство.) 13. 1 + з 13 х 3 = 20.5. 14. Как следует из найденного Фоатой соотношения, данная перестановка соответствует ! 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 1 )3 112343211342244у' но согласно (33) она соответствует 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 41 ( 2 4 4 3 3 3 1 1 4 4 2 1 2 1 2 3/' которая, в свою очередь, соответствует 2342341421432131.
Последняя же имеет 9 серий. 15. Число перемежающихся серий равно увеличенному на единицу числу индексов у, тэ ких, что 1 < 2 < и и либо а~-1 < а > озэц либо а~-1 > а < а эь При фиксированном !' вероятность равна 2; следовательно, среднее значение при и > 2 равно 1 + 1(п — 2) 16. Каждая перестановка множестиа (1,2,..., и — 1), которая имеет !г перемежающихся серий, при вставке нового элемента л. во все возможные позиции порождает й перестановок с й такими сериями, 2 перестановки с !г+ 1 сериями и и — й — 2 перестановки с й+ 2 сериями. Следовательно, ) )=Й) )+2! ))+(и — 1)) Удобно положить ),') = Юле, С1(х) = 1.
Тогда С (з) = †((1 — л ) С' ,(з) + (2 + (и — 2)л)С„ (х)). Дифференцирование приводит нас к рекуррентному соотношению для х„= С'„(1): 1 х„= — ((п — 2)х„г + 2л — 2). и Его решение при и > 2 имеет вид х = тп — —.. Еще одно дифференцирование приведет к г рекуррентному соотношению для у = С'„'(1); у„= — ((и — 4)у„г +;п — — п+ 6). а г ге п г Положим у„= оп~ + /1и + у и, решая уравнения относительно а, б, 7, получим у„= -„'пг — Цп+ эог при и > 4. Следовательно, тат(де) = — 'о(16п — 29), п > 4.
Эти формулы для математического ожидания и дисперсии получены Ж. Бьенэйме (3. Вгепаупге) и приведены без доказательства (Во!1. Яос. Маг!ь г1е Ргалсе 2 (1874), 153- 154; Сотргеэ Кепс!из Асаф Бс!. Рапэ 81 (1875), 417 — 423, см, также замечание Бертрана (Вегсгапб) на с. 458] Рекуррентное соотношение для ((")) полученр Д. Андрэ (П Аписе) (Сопгрсеэ Нелбиэ Асад. 8с1. Рапэ 97 (1883), 1356-1358, 'Алла!еэ бс!епг!бг!иеэ де ГЕсо!е Хогша!е Яарег!еаге (3) 1 (Рапэ, 1884), 121 — 134)ч Андрэ обратил внимание на то, что д„( — 1) = О при п > 4 Таким образом, число перестановок с четным числом перемежающихся серий равно гг!/2.
Он также доказал формулу для математического ожидания и определил количество перестановок, которые имеют максимальное число перемежающихся серий (см. упр. 5.1.4 — 23). Можно также показать, что С (г)=( — ) (1+ш)"+д( ), ш=)/ — ', п>2, где 9,(г) — произнодящая функция (18) для восходящих серий. (См. Р. Х. Рат!б, П. Е. Ваггоп, СоглЫпасопа1 Сбапсе (Ьопбоп: Сг!!Оп, 1962), 157 — 162.) 17.
(,","',); (, " г) последовательностей, заканчивающихся элементом О, а (. „",) последовательностей. заканчивающихся элементом 1. 18. (а) Пусть данная последовательность — — таблица инверсий, которая была рассмотрена в разделе 5.1.1.
Если в этой последовательности имеется !г нисходящих серий, инверсия соответстнуюшей перестановки имеет й нисходящих серий (см ответ к упр. 5.1.1-8(е))., сггедовательно, ответ для данной задачи — ("„), (Ь) Это число удовлетворяет равенству /(и, 1г) = !г/(гг — 1, /г) + (и — й+ 1)/(п — 1, !с — 1), значит, оно должно бьггь равно (, ",). [См. П. Пншопс, Риус Маг!ь Х 41 (1974), 313-315.) 19. (а) („") в соответствии с теоремой 5.1.2В. (Ь) Существует (и — й)! способов расположения п — /г последующих неатакуюших падей на всей доске; следовательно, ответ -— 1/(и — й)! раз ~ г>оа„г(„'), где а„г = (,") .-- решения для случая (а). Это приводит к („" ), принимал во внимание результат упр. 2. (В гл. 5 книги Риордана 1пггог!асс!ол Го СопгЫласог!а! Апа1уэ!э (Чгг!еу, 1958) анализируется общий случай размещения падей.) В прямом доказательстве этого результата, авторство которого принадлежит Э.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
