Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1), страница 8

[Указание. Вспомните методы работы со связями в памяти.[ 5. [35[ Для выполнения алгоритма из упр. 4 на типичном компьютере потребуется время, првблнзите тано пропорциональное и+6| + . +Ь„, а зто в среднем равно 9(п ). Можно лн создать алгоритм, порядок времени выполнения которо~о был бы существенно меныпе, чем п~? ° б. [85[ Придумайте алгоритм вычисления таблицы инверсий 6~ Ьз...6„, соответствующей данной перестановке а, аэ...а множества (1,2,...,п), время работы которого на типичном компьютере было бы порядка и!об и. 7.

[80[ Помимо таблицы 6| Ьз... 6, определенной в этом упражнении, можно определить некоторые типы таблиц инверсий, соответствующих данной перестановке а~ оз... а„мно. жества (1., 2,..., и). В этом упражнении мы рассмотрим три других типа таблиц инверсий, которые возникают в приложениях. Пусть с; — число инверсий, перепл компонента которых равна у, т. е. число элементов, меньших у и расположенных правее у. [Перестановке (1) соответствует таблица 000142157:, ясно, что 0 < с, < т?[ Пусть В, =б„г и Сг = с„. Покюките, что при 1 < у < и справедливы неравенства 0 < Ву < у и О < Ст < и — у; покажите также, что перестановку а~ аз... а„можно однозначно определить, если задана таблица с~ сз.

с„или В~ Вз... В, или С~ Сз С . 8. [ЛЩ) Сохраним обозначения, принятые в упр. 7. Пусть а[ аз... а'„— перестановка, обратная к аь аз... а, и пусть соответствующие ей таблицы инверсий — Ь', Ьз...Ь'„, с', сз... с'„, В[ Вз... В„и С[ Сз... С„. Найдите как можно больше интересных соотношений 9. [М21[ Докажите, что в обозначениях, принятых в упр, 7, перестановка ег ат...а„ представляет собой инволюцню (т. е. обратна самой себе) тогда и только тогда, когда Ьу = С, при1 <? <и. 10. [ИХЯО] Рассмотрите представленный иа рис.

1 октаэдр как многогранник в трехмерном пространстве. Чему равен диаметр усеченного октаэдра (расстояние между вершннамн 1234 и 4321), если все ребра имеют еданичную длину? 11. [М35[ Если л = а~ аз...а представляет собой перестановку множества (1,2,...,п), то обозначим как В(я) ж ((о„а.) [ 1 < у, а, > оу) множество ее инверсий, а как Е(тт) = ((аи ат) ( т > у, ат > аз ) ° ° т ° ° т ° ° ° ° ° ° ° т ° ° т ° ° ° 1 т т ° ° ° ° ° * ° ° т ° ° Рис.

2. Соответствие Франклина между разбиениями на различные части, Замечание. Как следствие получаем формулу Эйлера: (1 — з)(1 — з )(1 — х )... = 1 — з — х + х + з — з — з + з з з т ы ы Ртз+тчуз лтножество ее '"неинэерснй". а) Докажите, что Е(л) н Е(т) транзитивны. (Множество Я упорядоченных пар называется птранлитливним, если для любых (а,6) и (Ь,с), принадлежащих Я, пара (а,с) также принадлежит Я.) )т) Обратно, пусть Š— любое транзитивное подмножество множества Т ы ((х, р) ! 1 < р < х < п), дополнение которого Е = Т» Е также транзитивно.

Докажите, *по существует перестановка я, такая, что Е(л) = Е. 12. [М28) Используя обозначения, принятые в предыдущем упражнении, докажите, что если кт н кз — перестановки, а Š— минимальное транзитнвное множество, содержащее Е(ттт ) 0 Е(ттз), то Е -- также транзитивное множество. (Следовательно, если мы говорим, что ттт находятся "над" яз, ко~да Е(лт) С Е(ттз), то определена решептка перестановок; существует единственная самая низкая" перестановка, находящаяся»нади двумя данными перестановками. Диаграмма решетки при и = 4 представлена иа рис.

1.) 13. (мйу) известно, что в разложении определителя половина членов выписывается со знаком "+", а половшю — со знаком "— ". Другими словамн, при и > 2 перестановок с чстлним числом инверсий ровно столько же, сколько с нсчстлним. Покажите, что вообще. при и > гл количество перестановок с числом инверсий, конгруэнтным З по модулю пз, равно и!~тп, независимо от того, каково целое число З. 14.

(Мй() (Ф. Франклин (Р. Ргап)тйп).) Разбиение числа и на й различных частей — это представление пв видесуммы п=рт+рз+ +ры где рт >рз » . р» > О, Например, разбиения числа 7 на различные части таковы: 7, б+ 1, Ь+ 2, 4+ 3, 4+ 2+ 1. Пусть ,7»(п) — число разбиений л на )з различных частей. Докажите, что 2»(-1)~7»(п) = О, если только и не представляется в виде (31'з к У)7'2 при некотором неотрицательном целом у, в этом случае сумма равна ( — 1)т. Например, для и = 7 сумма равна — 1+ 3 — 1 = 1, потому что 7 = (3. 2 + 2)72.

(Указание. Представьте разбиения в виде массива точек, в з-й строке которого имеется рт точек, 1 < з < й. Найдите наименьшее т', такое, что р,ет < р — 1, н обведите крайние справа точки первых у строк. Если у < р», то этну точек можно, как правило, изъять из массива, повернуть на 4Ь' и поместить в новую, (1+1)-ю, строку. С другой стороны, если 1 > р», то обычно можно изъять пз массива й-ю строку точек, повернуть ее на 4Ь' н поместить справа от обведенных точек (рис. 2). В результате в больитннстве случаев разбиения с четным числом строк и разбиения с нечетным числом строк группируются в пары; таким образом, в сумме следует учитывать только непарные разбиенив.) Поскольку производящая функция для обычных разбиений (не обязательно на различные части) равна 2,'Р(п) " = 1/(1 — г)(1 — гг)(1 — гг)..., получаем неочевидное рекуррентцое соотношение для числа разбиений: Р(п) = Р(н — 1) + Р(п — 2) — Р(п — 5) — Р(п — 7) + Р(л — 12) + Р(п — 15) — -.

15. [М93) Докажите, что соотношение (16) — это производящая функция для чишга разбиений не более чем на и частей, т. е, докажите. что коэффициент при гы в 1/(1— г)(1 — г )... (1 — з") равен числу способов представления т в виде суммы гл = Рг + Рг + + Р, где Рг > Рг » Р > О. [Указание. Нарисуйте точки, как в упр.

14, и покажите. что существует нзаимно однозначное соответствие между и-мерными строками чисел (Рырм,р ). такими, что Рг > Рг » - . Р > О, и последовательностями (Ры Рг, Рг, ), такнмн. что и > Рг > Рг > Рг » О, обладающее тем свойством, что Р + Рг + + Р„= Р~ + Рг + Рг + .. Иными словами, покажите. что разбиениям не более чем на н частей соответствуют разбиения на части, не превосходящие и.) 16. [М95[ (Ч. Эйлер.) Докажите следующие тождества, интерпретируя обе части соотношений в терминах разбиений: 1 1 11 (1-еь ) (1- )(1-4 )(1-4гх)". 1-4 (1-4)(1-4') „,„ / „„.<„ П (1 + 4ь ) = (1 + И + )(1 + 9' ) " г>о (1, И1, г) 17. [90) Каковы 24 тетрады (йы дг, дг, ег), для которых в соответствии Мак-Магона, определенном в конце этого раздела. (Рырг,рг-рг) = (0,0,0,0)1 16.

[М30) (Т. Н1оЬагб, САСЛ1 6 (1963), 210.) Пусть и > 0 и последовательность 2" и-разрядных целых чисел Ло,, Хг -г получена случайным образом, причем каждый разряд каждого числа независилю от других разрядов принимает значение 1 с вероятностью Р, Рассмотрим последовательность Ха й О, Х~ г9 1, ..., Хг г 19 (2" — 1), где ег — операция 'исключающее или" над двоичными представлениями.

Так, если Р = О, то последовательность будет такой: О, 1,..., 2" — 1; если Р = 1, то она будет такой: 2" — 1,..., 1, О; если же р = -', .то каждый элемент последовательг: ности — случайное число между 0 и 2" — 1. Вообще же, цри разных Р это хороший способ получении последовательности случайных целых чисел со смещенным числом инверсий, в то время как распределение элементов последовательности, рассматриваемой как единое целое, равномерно (еш(огпг) в том смысле, что все и-разрядные целые двоичные числа будут иметь одинаковые распределения, Определите среднее число инверсий в такой последовательности как функцию от вероятности Р. 19.

[МйЦ (К. Мейер (С. Меуег).) Если пг и и — взаимно прсктые числа. то известно, что последовательность (т шог) п)(2гп шог) и)... ((и — 1)гп спой и) представляет собой перестановку множества (1, 2,..., и — 1). Покажите, что число инверсий этой перестановки может быть выражено в терминах сумм Дедекинда (см. п. 3.3,3). 20. [М38) Следующее знаменитое тождество, принадлежащее Якоби [Еплс(шпепга гтоса Т)гептил Ропсбопшп Е111рг!сагпш (1829), 164[, лежит в основе многих заыечательных соотношений, содержащих эллиптические функции: П( — " " 'и —.' "')( — "") = (1 — кК1 — е)(1 — ие)(1 — и е)(1 — ие )(1 — и е ),. =1 — (и+е)+(ее+ее') — (и и +и е )+ — ( 1) и(Ие("'), Если, например, положить и = э, и = л, то получится форлгула Эйлера из упр.

14. Есле 2 положить э =,/й?е, о ж егйе, то получим Ц(1 — 1"-'л)(1- ры ' ')(1-4'") = ~. (-1)" "6" —:а< <с~~ Существует ли комбииаториое доказательство тождества Якоби, аналогичное доказательству Франклина для частного случая из упр.