Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 63
Текст из файла (страница 63)
и, наконец, любое количество чисел и. 18. Коэфф»щиент при х"д ' в первом тождестве равен количеству разбиений числа ш на ие более чем и частей. Во втором тождестве он равен количеству разбиений числа т на гг различных неотрицательных частей, т. е. представляет собой сумму гп = рг + рэ + .. + р„, где рг > рэ » . р„> О. Это то же самое, что и разбиения гп — (") = 9»+9»+. +9, где 9» > 9» » .
9„> О, так как можно установить взаимно однозначное соответствие ф = р; — и + г. [Сотшепгагй Асадет!та Бс!епдагпт РеггороЬЗапш 13 (1741), 64-93.) Замечание, Второе тождество получаем предельным переходом и -г оо вследствие 9-номиальиой теоремы (см. Упр. 1.2.6-58). Аниюгично и первое тождество получаем предельным переходом г -+ оо в дуальной форме этой теоремы, доказанной в ответе к тому же упражнению. Пусть и!р = П» г(1+ 9+ . +Ч" ') и ехрр(э) = ~ „э» /и!р. Из первого тождества следУет, что ехур(х) Равно 1/П» о(1-д х(1 9)) пРи !9! < 1: из втоРого слеДУет, что это же выражение равно П» „(1+9 ~э(1 — д ')) при (9) > 1. Полученное в результате тождество ехрт(э) ехр„, (-э) = 1 эквивалентно формуле ( 1)э МЭ-Мгэ ~ (1-) (-1' -) (-"-' которая является следствием из 7-номнэльной теоремы при х = -1.
17. оооо 01оо оо1о ооа1 1101 1201 1021 !012 1о1о о11о 012о а1а2 1О11 0111 О121 О112 1оо1 01о1 аа11 оо12 2012 0212 0122 0123 18. Пусть 9 = 1 — р. Сумму 2 Рг(»») по всем случаям и инверсий можно вычислить суммированием по й, где О < к < и — точное число крайних битовых позиций, в которых соблюдается равенство между» н,у и между Х, и Хз в инверсии, Х; 6»» > Хз 6» у при » < /.
Таким обРазом 6Удет полУчена фоРмУла 2,е<ь<„2~(Р~ + 9~)~(Р 2" " '2" ""' + 2рд2 " '(2" " ' — 1)). Послесуммированияиупрощенияонапреобразуетсяв2" '(р(2- р)(2" — (р' + ат)")/(2 — рэ — 9») + (р' + дэ)" — 1). 19. Число инверсий равно ((п»у/и) — (т»/и) — (гп(у — »)/и)) ж ~ (п»7 що») в < и»» щобп) = е<»<1« е« '1« (п»г/и) (г — (и — г) — (и — г — 1)), 0«<ь что можно привести к виду 1(и — 1)(п — 2) — „1па(гп, н, О).
(См. Сгеае, 198 (1957), 162-166,) 20. См, Е. М. Жпба», Х Хватов Ма»5. Яос. 40 (1965), 55-57; и Л. Хо1понз)»у, Воз<ге»е Ма»5, 9 (1974), 293-296. Тождество Якоби можно быстро доказать следующим образом. Так как П(1 и е ) ( 1) к( 2 )э(э) П(1 — к с ) вследствие 9-номнбльной теоремы, рассмотренной в упр. 1.2.6-58, прн 9 = иэ имеем п П(1 — к~с" »)(1 — и~ 'с~) = ь=» Для фиксированных у после умножения обеих частей на Цэ„»(1 — кьэ ) = Цэ-»(1 — Ф ) получим (э,у) П,",,(1 — дэ) = 1+ О(9"+' 0~).
При и -э со отсюда следует тох<дество Якоби. 21. ИнтерпретируйтеС1 как чнсчоэлементОвв Стеке пОСЛеУ-го вьпюда. (Характеристики Ь» н Вь таблиц перестановок в стеке рассмотрены в упр. 2,3,3-19.) 22. (а) Расставьте числа (1,2,...,и) по кругу, как на цнферблате часов, и установите указатель на 1. Затем для у = и, и — 1, ..., 1 (именно в этом норядке) передвигайте указатель против часовой стрелки Ь, + 1 шагов, удаляя из круга те числа, на которые он указывает, и назовите нх а . (Ь) Каждое 1 подсчитывается так часто, как "замыкается" последовательность а, ашы .. а„; это и будет число случаев, когда а, > аьы прн у > 4.
Таким образом, каждое у при а > а,э~ соответствует подсчитанным однократно индексам 1, ..., у. [лэпо-Нш Нап, Аг(тавсеэ ш МагЬ, 105 (1994), 28-29; тот же результат получен и Роулингсом (Вапйвбэ) в контексте следующего упражнения.) 23. Предположим, например, что и = 5 и а1 оэ аз алоэ = 314 25. Тогда число холостых выстрелов перед каждым смертельным должно быть 2+ 5Ьм 2+ 4Ьэ, 1+ ЗЬэ, 1+ 2Ьэ, Ьэ, где Ь вЂ” некоторое неотрицательное целое. Обратите внимание, что дуальной перестановке 14 253 соответствует Ь-таблица 01 12 2 в обозначениях предыдущего упражнения. В общем случае вероятность серии аэ аэ...
а будет равна л,,....л„йо 1 — ф 1 — йэ 1 — 9» л„л„ где р = 1 — 4 — вероятность фатального исхода после предыдущих у — 1 роковых выстрелов н Ь1 Ьэ... Ьь соответствует двойственной последовательности о1 аэ, а . В частности, при р1 ж = р = р = 1 — 4 получим вероятность Ол'~""'"л"/С„(4). Таким образом, будет порядок и ... 21.
[Л. Тгеабтгау, О. Вам)1пбэ, Маей. Маб. 67 (1994), 345-354; Роулингс обобщил этот результат для перестановок мульти множеств в 1п К Х Ыаэ5. 4э ЫагЬ. Яс1 16 (1992), 291-312.] 24. Пусть ао = О. Будем говорить, что обобщенный спуск возникает при У < и, если о, > 1(азэ1). После вставки и между а~ 1 и а; появляется новый обобщенный спуск тогда и только тогда, когда а„~ < г(аз) < и. предположим, что это произошло, когда у' имело значение 11 > уэ » . 1» > О; пусть другое значение у будет йь > уь 1 » улэь Тогда 1' = и и можно показать, что обобщенный индекс увеличнвается на и — Ь, когда и вставлено именно перед алс [Особый случай, при котором Щ) ж у+И для некоторых И > О, рассмотрен Д.
Роулннгсом, Х СошМвагопа( ТЬешу А31 (1981), 175-183; он обобщил его на перестановку мультимножеств в работе Ипеаг апд Мий!йпеаг А)беЬга 10 (1981), 253-260. В этом упражнении определено и! различных статистик перестановок, какгдая иэ которых имеет производящую функцию Сл(х), выведенную в (7) и (8). Можно определить и значительно больше таких статистик, обобщив формулировку задачи о русской рулетке следующим образом: после,у — 1 рокового выстрела новый круг начинается с участника у,(ам...,о.
1), гле ~; — произвольная функция, принимающая значения на (1,...,п) '1 (ап...,а. ~). [См. Спо-Ьйп Нап, Са1сп! )эепегэ1еп (ТЬеэ)э, Упт. БэгаэЬопгб, 1992), Рагг 1,3, 37.[ 25. (а) Если а1 < а, то Ь(о) имеет ровно столько же инверсий, сколько и, твк как элементы в оз теперь инвертировали х, вместо а . Но, если а~ > а„, Ь(а) имеет на и — 1 инверсий меньше, поскольку х теряет свою инверсию о и инверсию каждого элемента в а .
Таким образом, «сли положить х„= а и рекурсивно переобозначить хэ... х„э = у(Ь(о)), то перестановка у(о) = х1... х„будет обладать желаемыми свойствами. Получится у(198263745) = 912638745 и 1~ 0(198263745) = 192687345. (Ь) Здесь ключевыми являются соотношения Ьш(а) = шт(о ) и 1пб(а ) = 1вб(~(а) ), если о есть инверсия о. Таким образом, если п1 —— а, аэ = У(о,), аэ = пэ, пл = У (пэ) -0 и пэ = ал, получим !пт(аэ) = !пт(а<) = !пг((аз) = !пг!(аг ) =!ас)(а, ) = !пг!(а); шг!(аэ) = гпг!(а4 ) = 1пб(аз ) = гпг!(аг) = гпт(аг) = гпт(а).
(Магб. 74асЪг!<Ъгеп 83 (1978), 143-159.) 28. (Решение предложено Дороном Зильбергером (Потоп Ее!!Ьегбег).) Среднее от !пт(а) йм!(а) равно — ) (о >оь) ! [о!>а~+г), 1 ь 1<1<ей~ ~<г«» что представляет собой полинам от и степени, меньшей или равной 4. Вычисление этой суммы лля 1 < и < 5 дает соответственно значения О, -, -„—, —; таким образом, полинам имеет вид ~1п(п — 1) +,~„пг(п — 1)г. После вычитания шеап(р„)т и деления на так(9~) получкм ответ: 9/(2п+ 5) для и > 2, если исходить из (12) н (13).
27. Рассматриваяд ...!П9г какперестановкумультимножества, получим!пт(агою ..и„) = !пг(ор ° йт 9г) (см раздел 5 1.2), Отсюда, использтя обозначения из ответа к упр. 16 и результаты упр. 5.1.2 — 16, получим 1 — з 1 — з" Нп (ю з) 'с, 1п~чю ...а ! шемь..а ) ~~ рг+" +р (1 — з)...(1 — з") а рюю!зю+юэ" чч ю,м,...,р йе ( и ) ь+гь+- Ъо, Ъ»Ъ где (и ) ~ ПГ!р —, ьюьььр,-- ь и!и (и") П ехр„,(луи) ;=о ОО ОЭ 1 и! (и") ПП 1 — аз~"и(1 — ~) В результате имеем элегантное тождество 1 Н (гл,з)й П Г вЂ” ' Е( — И1 — ')...(1- "И1 — )(1 — ') .
(! — "Г из которого и появляетск требуемая производящая функция Н„(ш, л) = ~ ю'" з'" ' (последнкя получена Д. П. Розелем (О. Р. оспе!!е) в Рпю. Ашег. Маей. Яос. 45 (1974), 144-150). В упр. 25 показано, что та же функпня двух переменных подсчитывает индексы н инверсии. Приведенное здесь доказательство нринвдлежит Гарсиа (Саш!а) п Гесселю (Сеше!) (см, Аг(ъапсез ш Маей, 81 (1979), 288-505), которые стремились получить существенно более общий результат. Если в упр.
4.7-27 положить т = оо, то придем к рекуррептному аютпошению 28. Взаимная замена двух соответствующих элементов изменяет значение суммарного смещения на величину 0 или ~2; следовательно, суммарное смещение гб(аг ог .. о„) < 2!пт(п~ аг... а ). Можно также доказать, что Я(аг аэ... а ) > 1пч(аг аэ... а„).
Предположим, что 7'— наименыпий элемент, который находится не на своем месте, и аь = 77 Пусть 1 будет макснмальным, причем 1 < Ь и аг > Ь. Взаимный обмен аг и аь уменьшает количество инверсий на 2(1с — 1) — 1, а суммарное смещение — на 2(Ь вЂ” 1). Таким образом, если для сортировки данной перестановки аг аэ, а„требуетси пг поиторений этого алгоритма, получим Ы(агат...
а„) = иш(агат... а„)+гп. Замечание. Среднее суммарное смещение случайной перестановки равно (пэ — 1)/3 (см. упр, 5.2.1-7). Производящая функция для среднего суммарного смещения не имеет простой формы. 29. Можно похучить гг как произведение гпч(л) операций транспонирования т, где операция т, меняет местами 7' и у + 1. Например, путь 1234 -ь 1324 -г 1342 -+ 3142 на рис. 1 соответствует тп затем — тэ, затем — тг; следовательно, 3142 ггтэтх Таким образом, можно получить лгг' из л', выполнив 1пч(л) операций транспонирования, каясдая из которых изменит количество инверсий на х1, Отсюда следует, что шч(ля') < шч(л) + !пч(л').
Если имеется равенство, кикдое транспонироваиие добавляет одну инверсию, т. е. Е(лл') Э Е(л'). Значит, если Е(гггг') Э Е(гг'), нам нужно показать„что негготорая последовательность из (Е(лл') ( — (Е(л')( = шч(лл') — гпч(л') операций транспонирования преобразует гг' в лл'. Данные операции транспонярования определяют л. Этим доказывается справедливость соотношения гяч(л) < (пч(лл') — гпч(гг'); следовательно, должно соблюдаться равенство. Предположим. что л' = 314592637 и Е(лл') З Е(л').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
