Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 66
Текст из файла (страница 66)
Для определения дисперсии воспользуемся соотношением Ь" (1, х) = -2Ь'(1, х) — 2х(х- 1)г* ь/(е' ' — х)з. Рассуждая, как при определении среднего значения, ио иа сей рзз по отиошеиию к полюсу третьего порядка, приходим к выводу, что козффяпиенты при Ьи(1ь х) асимптотически стремятса к 4п + -'и — 2М„плюс слагаемый большего порядка малости; отсюда получается асимптотическая формула для дисперсии з и+ з (плюс экспопенциально уменьшающиеся слагаемые). 11 Рз =2 ь,>ь,,ь,>ьО(сь, .,1ь-ь,п,1),где.О(Ь,(з,...,1з) — определительМак-Магоиа из упр.
8, Разлагая зтот определитель по элементам первой строки. получим Рь соРьь пи+сьРЫ зж+. +сз зРы — Ез(п), где сь и Еь определяются следующим образом: Еь (и) = 1/(и + 1)! — 1/и!,' Ез(и) = 1/(и + 1)!; Е. ( ) = (-1)",". ~,,) ь>0 Пусть Ре = О, С(з) = 2 с зь зи (е' ' — 1)/(1 — з) и пусть (е и — 1)х х (е ' — е') е' — 1 — х Е(х,х) = ~~ь Еь.,(п)зих = 1 — еь + + и,ь Получениое рекурреитное соотношение зквивалентио формуле С(х)Н(х, х) = Н(з, х)/х + Е(з,х); отсюда Н(з,х) = Е(х,х)х(1 — х)/(хе' ' — 1). Разлагая в степеииой ряд правую часть, придем к соотпошепиьо Нь(х) = Ьь(з) (см. упр. 9); Нз(з) = еЛь(з) + 1 — е .
[Замечание, Производящие функции для первых трех серий выведены Кнутом в САСМ 6 (1963), 685-688. В работе Вэхсоп, Ма!!сне, Апп. Масй. 81ас!эсйя ЗВ (1965), 249, выведена формула 1 — Н„+з(х) ы (1 — Н„(х))/(1 — х) — Х.„!»|(х) для и > 1, а также формула (25). Другой повход к решению этой задачи продемонстрирован в упр.
23. Поскольку соседние серии не являются независимыми, не существует простой связи между решенной здесь задачей и более простым результатом упр. 9 (последний, вероятно, и более полезен).) 12. (СошЬ!насосу Апа!уяи 1 (1915), 209-21Ц Число способов, которыми можно разместить элементы мультнмножества в ! различных ячейках, равно (!+и» вЂ” 1) (У+их — 1) (!+и»» — 1) поскольку имеется ('»"„', ') способов разместить единицм и т.
д, Естн потребовать, чтобы ни одна ячейка не пустовала, то, пользуясь методом включения и исключения, найдем, что число способов равно М» = № — ( )Н»-1+ ( )Н»-з — -. Пусть Р» — число перестановок, содержапшх я серий; если поместить к — 1 вертикальных черточек между сериями и ! — к дополнительных вертикальных черточек в любые из оставшихся и — к позиций, получим один из М, способов разделить мульгнмножество на с непустмх различаемых частей. Следовательно, ( 1 ) ( 2 ) Приравнивая зти два значения М~ можно выразить Р», Рэ, ... последовательно в терминах №, №, ....
(Желательно отыскать более прямое доказательство.) 13. 1+ -'13 х 3 = 20.5. 14. Как следует из найденного Фоатой соотношения, данная перестановка соответствует /11112222333344441 (31)т(1)т т(4)»3 ! 1 2 3 4 3 2 ! ! 3 4 2 2 4 4) но согласно (ЗЗ) она соответствует 1111222233334444) ( 2443331144212123/' которая, в свою очередь, соответствует 2342341421432131. Последняя же имеет 9 серий. 15. Число перемежающихся серий равно увеличенному на единипу числу индексов у, таких, что 1 < у < и и либо ау 1 < а > а»»», либо а, > аз < аз»». При фиксированном у вероятность равна 1! следовательно, среднее значение при и > 2 равно 1 + з(и — 2).
18. Каждая перестановка множества (1, 2,..., и-1), которая имеет я перемежающихся серий, прн вставке нового элемента и во все возможные позиции порождает Й перестановок с л такими сериями, 2 перестановки с я+ 1 сериями и и — к-2 перестановки с к+ 2 сериями. Следовательно, Удобно положить ) ' ) = б»о, С»(х) = 1. Тогда С,(х) = -((1 — х )С'„1(х) + (2+ (и — 2)х)С~ 1(х)). Диффереицировапие приводит иас к рессурреитному соотиошению для х„ы С'„(1)! х„= -((и — 2)х„! + 2п — 2).
1 и Его решение при и > 2 имеет вид х, = -и — э. Еще одно дифференцирование приведет к с ! рекуррентному соотношению для р = С'„'(1): 1 а с ы р„= — ((и — 4)рл ! + эп — фп+ 6), и Положим р„= оп + !3п+ 7 и, решая уравиеиия относительно а, !у, 7, получим рл ьп -'пэ — Цц+ ьэб! при и > 4. Следовательно, еаг(рв) = ю (16п — 29), и > 4. Эти формулы лля математического ожидания и дисперсии получены Ж. Бьепэйме (я. В!епауспе) и приведены без доказательства (Ви!1.
яос. МасЛ. де ргапсе 2 (1874), 153- 154; Сошрсеэ Вепдиз Асад. 5Ы. Рэггз 81 (!815), 417-423, см. также замечание Бертраиа (Ветсгэлд) на с. 458». Рекуррептиое соотношение для ((„")) полу ченр Д. Андрэ (В. Апдге) (Сошрсеэ Иепди» Асад. Ясб Раг!э 97 (1883), 1356-1358, Аппа1еэ Бс!епс!бс!ипс де !'Есо!е Хогспа1е Яирдг!еиге (3) 1 (Рапэ, 1884), 121-134». Андрэ обратил внимание иа то, что рл(-1) = О при и > 4.
Таким образом, число перестановок с четным числом перемежающихся серий равно и!12. Ои также доказал формулу для математического ожидания и определил количество перестаиовок, которме имеют максимальное число перемежающихся серий (см. упр. 5.1.4-23), Можно также показать, что Сл(с) = ( — ) (1+и!'))+''9,( — ), ье = )(:, и > 2, где д„(с) — производящая функция (18) для восходящих серий. (См.
Р. !ь, Вае!д, В. Е, Вымыл, Сопьбспасогцд СЛапсе (Ьопдоп! Сг!сйп! 1962), 157- 162.» 17. (",+',); ( „" ) последовательностей, заканчивающихся элемеитом О, а ( „",) последовательностей. закапчиваюьпихся элементом 1. 18. (а) Пусть данная последовательность — таблица инверсий, которая была рассмотреиа в разделе 5,1.1. Если в этой последовательности имеется Л нисходящих серий, инверсия соответствующей перестановки имеет 1с иисходящих серий (см. ответ к упр.
5.1.1-8(е)); следовательно, ответ для данной задачи — ("„). (Ь) Это число удовлетворяет равенству 7(п, 1с) = Лу(п-1, Л) + (и-!с+ 1)1(п-1, Л-1), влачит, оио должно быть равно (,",). »См, В, Випюпс, Вийе МасЛ. Х 41 (1974). 313-315.» 19. (а) (ь) в соответствии с теоремой 5.1.2В. (Ь) Существует (и — Л)! способов расположения и — !с последующих пеатакующих падей на всей доске; следовательно, ответ— 1/(и — Л)! раэ 4'!Лэож( ), где а ! = ( ) — решения Лля случая (а).
Это приводит к („" ), принимая во виимаиие результат упр. 2. (В гл. 5 книги Риордаиа 1псгодиссюп со СошЫиасопа1 Алэ1сх!э (рр!!еу, 1958) анализируется общий случай размещения ладей.» В прямом доказательстве этого результата, авторство которого принадлежит Э. А. Бендеру (Е. А. Вепдег) ! каждое разбиение множества (1, 2...., п) иа Л цепустых непересекающихся подмножеств ссютветствует некоторому расположению и-Л падей. Пусть разбиеиие таково: (1,2,...,п) = (ап,ам,-,агль) ь! 0 (аы,,ааль) где а!.
< а,!1ьь! при 1 < 1 < п„1 < с < Л. Ему соответствует следующее расшиюжеиие падей: ладьи помещаются в ао-й статбец ац еьрй строки, где 1 < у < п„1 < с < 1с. Например, позиция, приведенная ца рис. 4, соответствует разбиению (1, 3, 8) 0 (2) 0 (4, 6) с! (5) 0 (7). 20. Число чтений равно числу серий в обратной перестановке. Первая серия соответствует первому чтению н т. д. 21. Перестановка имеет и+ 1 — к серий и требует и + 1 — у чтений, 22.
(Х СогпЫпасоги1 Тйеогу 1 (1966), 350-374.) Если гз < и, то при некотором чтении выбирается 1 > г элементов, аи — — у+ 1, ..., аи = у'+1, где и « . й. Нельзя получить а > а е~ для всех ш в диапазоне 1е < т < и еь Таким образом, перестановка содержит, по меньшей мере, 1 — 1 таких мест, где а < а +,-, отсюда следует, что в перестановке не более и — 1+ 1 серий. С другой стороны, рассмотрим перестановку а„...
аэ ам в которой блок аэ содержит числа ш у (по модулю г) в порядке убывания; например, когда и = 9 и г = 4, эта пересыновка имеет вид 8 4 7 3 629 5 1. Если п > 2» — 1, эта перестановка имеет г — 1 возрастаний. Значит, в ней имеется и+1-~ серий. Более того, если г > 1, он» требует точно а+1 -(и/г) чтений. Можно подругому расставить элементы в (Ь +1,..., Ь+г), не меняя числа серий; таким способом можно уменьшить число чтений до любой желаемой величины > (и/г). Теперь предположим, что ге > п, с+з < и+1 и г,з > 1. Как показано в упр, 20 н 21, можно считать, что г < з, поскольку отражение инверсии с я+ 1 - г сериями н з чтениями имеет и + 1 — з серий и г чтений.
После этого рассуждения предыдущего абзаца можно применить ко всем случаям, кроме тех, где з > и + 1 — (и/г) н г > 2. Чтобы завершить доказательство, можно воспользоваться перестановкой в форме 2Й+1 2Й-1 ... 1 п+2-г и+1-г ... 23+2 23 ... 2 и+3-г ... и-1 и, которая имеет и+ 1 — г серий и и + 1 — г — я чтений, 0 < й < 1(п — г).
23. (31АМ Яег1еи 3 (1967), 121-122.) Допустим, что бесконечная перестановка состоит из независимых частей, подчиненных равномерному закону распределении. Пусть!е(х) ах— вероятность того, что я-н удлиненная серия начинается с х, и пусть д(и,х)3х — ве. роятность того, что удлиненная серия начинается с х, при условии, что предыдущая удлиненная серия начннаеття с и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
