Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 9
Текст из файла (страница 9)
14? (Таким образом, нужно рассмотреть "комплексные разбиения" ьэ+ гб = (р~ +Ф1) +(рэ+еэ1) + +(рэ+ оэ1) где р + оэ1 — различные ненулевые комплексные числа; р» р и — неотрицательные целые числа, причем )р? — 4 ) < 1. Согласно тождеству Якоби число таких представлений с четными й равно числу представлений с нечетными /г, если только щ и и не являются соседними треугольнымн числами!) Какими еще замечательными свойствами обладают комплексные разбиения? ь 21. (М85) (Г.
Д, Кнотт (С. В. Клоы).) Покажите, что перестановку аы..о„люжпо получить с помощью стека (см. упр, 2.2.1-3 нли 2.3.1-6) тогда я только тогда, когда С, < С?+1 + 1 при 1 < у < и (см. обозначения в упр. 7). 22. (М26) Задана перестановка а1 аэ ., а„множества (1, 2,..., и). Пусть Ь, — чясло индексов 1 < 7', таких, что о, б (а,+1, а, +2,..., оэ ю ). (Если аэ ы < а,, элементы этого множества "оборачиваются" от и к 1, Когда 1 = п, используется множество (а„+1, а„+2,..., и).) Нш|рньгер, перестановка 59182б473 приводит к )м ..'лэ = 001214240.
а) Докажите. что а~ еэ .. а„можно воссэщювить но числам б, лэ... л„. Ь) Докажите,что?м+йэ+ +܄— сутьиндексыа1аэ...а„. ь 23. (М87) (Ррсскал рулсшка.) Грушэа из и человек, приговоренных к смерти, которые отдают предпочтение теории вероятности перед теорией чисел, могла бы. рассевшись по кругу и несколько модифицировав метод Иосифа (упр. 2), попробовать такой способ самоубийства. Первый приговоренный нажимает спусковой крючок револьвера, направив «го себе в висок; с вероятностью р произойдет роковой выстрел, и он покинет круг. Затем револьвер переходит ко второму приговоренному и он делает то же самое, Далее сюжет повторяется по кругу с постоянной верояэностью р > 0 до тех пор, пока будет кому его продолжать. Пусть а. = к, если ?г-му приговоренному выпал у-й роковой выстрел.
Докажите, что порядок "выбывания' а~ оэ...ак появится с вероятностью, которая является функцией только и, р в индекса дуаэьной перестановки (и+1 — о )... (и+1 — аэ) (и+1 — а~). Какой порядок "выбывания" наименее вероятен? 24. (М86) Для заданного множество целых чисел Г(1) 1(2)...1(и), где Г(7) > 1, обобщениии индекс перестановки а~ аэ... а равен сул~ме всех нижних индексов,1, таких, что а; > 1(а э~), плюс общее число инверсий, таких„что 1 < у и 1(а„) > а, > а . Значит, если 1(~) = 7 для всех у, обобщенный индекс совпадает с обычным индексом, но при 1(7) > п для всех у это будет число инверсий. Докажите, что число инверсий, для которых обобщенный индекс равен?г, — то же самое, что и число перестановок, которые имеют А инверсий.
[Указаиие. Покажите, что, если взять любукг перестановку аг... а мвожества (1,..., и — Ц и поместить число и иа гке возможиые месгв, обобщенный индекс увеличится на (О, 1,..., и — 1) в иекотором порядке.) ° 25. [МЯО) (Фоата и Шуцепберже.) Пусть существует перестановка а = аг...
а„; обозначим через )пг((о) ее индекс, а через пш(а) — число ее инверсий. а) Определите взаимпо одяозначпое соответствие, которое преобразует перестановку и множества (1,..., и) в перестшювку /(о), имеющую такие два свойства: (г) 1па(у(о)) = гпч(а); (й) для 1 < у < и число у гюявляется слева от у + 1 в у(а) тогда и только тогда, когда оно появляется слева от У+ 1 в о. Какая перестановка при этом сооь ветствует У(о), если а = 1982637457 Для какой перестаповки 7(о) = 1982637457 [Указание. Если и > 1, напишите и = хгогхмтз ..хьи»а, где хг, ..., хь — все элементы, меньшие, чем а„, если аг < а„„.в противном случае хг, ..., х» — все элементы, больгпие, чем а; другие злемепты появятся в цепочках (возможно, пустых) аы ..., оы Сравните число инверсий 5(о) = огхгагхз...оьхь с 1ич(а); в этом выражении число а„отсутствует в 5(п).) Ь) Обозначьте через 7' другое однозначное соответствие 9, которое имеет два следующих свойства: (г) 1пг)(9(о)) = )пч(а); (й) )п~ (д(а)) = 1пг)(о).
[Указаиие. Примите во виимание обратные перестановки.) 26. [МЙ5) Челгу равен статистический коэффициент корреляцгги между числом инверсий и индексом случайной перествновки7 (См. упр. 3.3.2-(24).) 27. [МУ7) Докажите, что в дополнение к (15) существует простое соотношение между гпч(аг аз...а„) и и-мерной строкой (дг,еи,е»). Используйте это соотношение для получения производной соотношения (17) в общем случае и формирования алгебраического выражения в виде производящей фупкции двух переменных гг г, г '~ ы г»г»»...а Г»гд»г»ь..» Г где суммироваиие выполняется по всем и! перестановкам аг аз...
а„. ° 28. [85) (Р. В, Флойд (11. %. Р1оуг(), 1983.) Если аг аг... а — перестановка множества (1, 2,..., и), то его суммарное смеглеиие определяется квк 2„,"»г [а; -У[. Найдите верхнюю и нижнюю границы суммарного смещения в терминах количества инверсий. 29. [88) Если п = аг аг... а и гг' = а', аг... а'„суть перестановки множества (1, 2,..., и), то обозиачим их произведение кк' как а'„а'„... а,',„.
Пусть иш(гг) обозначает количество инверсий, как й в упр. 25. Полюките, что 1пч(яя') < ьчч(я) + 1пч(гг') и что равенство соблюдается тогда и только тогда, когда гггг' расположено "ниже" гг' (как введено в упр. 12). «5.1.2. Перестановки мупьтммножества До сих пор мы рассматривали перестановки м~ожесглва элементов, но это частный случай перестановок мрльшпмнозгсесгива. (Мультимножество — это то же самое, что н множество, но в нем могут содержаться одинаковые элементы.
Некоторые основные свойства мультимножеств обсуждались в разделе 4.6.3-19.) Рассмотрим, например, мультимиожество М = (а, а, а, 5, 5, с, с(, г(, г(, г(), в котором содержится 3 элемента а, 2 элемента 5, 1 злемепт с и 4 элемента г(. Повторения злемеитов в мультимножестве можио записать и другим способом: (2) М = (3 а, 2 Ь, с 4 г() Вслед за этим правилом Бхаскара приводит интересную формулу (4 + 8 + 5 + 5 + 5) х 120 х 11111 для суммы 20 чисел 48о55 + 45855 + . . Верное правило для нахождения числа перестановок в случае, когда только один элемент может повторяться, найдено независимо немецким ученым иезуитом Лтанасиусом Кирхером (ЛгЬапае!иэ К!гсЬег) в его многотомном труде о музыке !5!пзигй!а Гп!гегза)(э 2 (Воще: 1650), 5-7).
Кирхера интересовал вопрос о количестве мелодий, которые можно создать из данного набора нот; для этого ои придумал то, что называл "музарифметикой". На стр. 18-21 своего труда он дает верное значение числа перестановок мультимиожества (гп С, и !1) при нескольких значениях гп и п, хотя описал он свой метод вычислений лишь для случая и = 1. Общее правило (3) появилось позже в книге Жана Престэ (д. Ргевгег) Е)егпепз Не Ма!Ьстат!диез (Раг!э: 1675, 351-352), в которой содержится одно из первых изложений комбинаторной математики, написанных в Западной Европе.
Престэ верно сформулировал правило для произвольного мультимиожества, но проиллюстрировал его лишь простым примером (а, а, 6. 6, с, с). Он особо отметил, что деление на сумму факториалов„которое ои считал естественным обобщением правила Кирхера, было бы ошибкой. Несколько лет спустя Джон Валлис (3о!ш %Ы!!е) в своей книге ПВсоигзе ог СоюлбгиаВопэ (ОхГоЫ: 1685, С!гаргег 2), опубликованной вместе с его же Ггеаг!ее ог А78ебга, рассмотрел это правило ботев подробно.
В 1965 году Доминик Фонта (1гопнп!цие Розга) ввел одно интересное понятие, так называемое "соединительное произведенная (!пгегса!,гг!оп ргойнч). которое позволило распространить многие известные результаты, касающиегя обычных перестановок. на общий случай перестановок мульгпмножества. [См.
Ри!з!. !ггег. Я!аг!ьт!цие. (!и!ч. РаПк 14 (1965), 81 — 241; а также Еесгпге Уогех !ц 5!аВь 85 (Ярйпйег, 1969).) Предполагая, что элементы мультимножества каким-то способом линейно упорядочены, можно рассмотреть деухстаречиую нотацию, например < а и а Ь 6 с И Н г! И) саЬИИаЬИае!' Здесь верхняя строка содержит элементы .Н в порядке неубывання и нижняя-- это сама перестановка.
Соединипгельиое произведение а г,9 двух перестановок мультимножеств о и,9 — — зто перестановка, которая получается, если (а) взять двух- строчные обозначения для о и !!, (Ь) записать соответствующие строки в одну и (с) рассортировать столбцы так. чтобы элементы верхней строки распщюжилнсь в порядке пеубывания. Сортировка должна быть устойчивой в том смысле, что взаимное расположение элементов нижней строки сохраняется, если соответствующие элементы верхней строки равны.
Например, с а На 6 г 6 г(На ~1= со 6 4г! а 6 Над, так как Нетрудно видеть, что операция соединительного произведения ассоциативна, т. е. (6) (о тЯтз = ат(Рг-д и что она подчиняется законам сокращения хта = хтФ влечет за собой а =ф, атя = Дтх влечет за собой а = Д. Существует "единичный элемент" атес ето=а где с — нуль-перестановка, "расположение в ряд'" элементов пустого множества, Закон коммутативности, вообще говоря, не выполняется (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
