AOP_Tom3 (1021738), страница 165
Текст из файла (страница 165)
12. (С. Т. Сш!Ьаиг), Р. Нояепвзсесг!, МаСЬ. еС Ясгепсея Нигпвзпев 4 (1963), 9-33.) Предположим, что (а,Ь) б Е, (Ь,с) б Е, (а,с) К Е. Тогда при некотором Ь > 1 имеем а = хе > хз » хз = с, где (х„х,~г) б е(яг) с! е(кз) при 0 < з < сг. Рассмотрим следующий контрпример при минимальном Ь. Поскольку (а,Ь) ф Е(лг) и (Ь,с) ф Е(ггг), то (а,с) гх Е(згг); аналогично (а,с) ф Е(ггз), следовательно, Ь > 1. Но если хг > Ь, то (хг, Ь) 6 Е противоречило бы минимальности сг, а из тога, что (хг, Ь) б Е, следовало бы (а 6) б Е. Аналогично, если хг < Ь, получится, что и (Ь хг) б Е, и (Ь хг) б Е невозможны. 18. Для любого фиксированного выбора Ьг,...,Ь г г,Ьмег,...,б„в таблице инверсий в сумме 2 Ь, предполагается, что каждый остаток по модулю т встречается точно один рэз по мере того, как Ь пробегает все возможные значения О, 1, ..., т — 1.
14. Конструкция, предложенная в указании, переводит пары разбиений на различные части одна в другое во всех случаях, кроме двух: ! = Ь = рз и! = Ь = рз — 1. В этих особых случаях п равно соответственно (2/ — 1)+ +! = (3! — !)/2 и (21)+ +(!+1) = (3! +!)/2 и существует единственное непарное разбиение на у частей. (Первоначальное доказательство Эйлера в Агог! Сошпгеле. Асад. Ясг. Рез. б (1754), 75-83, также очень интересно. С помощью простых преобразований он показал, что бесконечное произведение равно зг, если мы определим з в виде степенного ряда 1 — зз" ' — зз" 'я„зг для п > 1.
Конечная версия бесконечной эйлеровой суммы рассмотрена Кнутом и Патерсоном (Расегяоп) в Ргбоаасс! С3ивгзег!у 16 (1978), 198-212.) 15. Транспонируйте точечную диаграмму с тем, чтобы перейти от р к Р. Производящая функция для Р получается довольно легко, так как сначала можно выбрать любое число единиц (производящая функция 1/(1 — з)), затем независимо выбрать любое число двоек (производящая функция 1/(1 — зз)), ... и, наконец, любое количество чисел и.
16. Коэффициент при з" 4~ в первом тождестве равен количеству разбиений числа гп на не более чем п частей. Во втором тождестве он равен количеству разбиений числа т на и различных неотрицательных частей, т. е. представляет собой сумму т = рз+ рз+ + р, где рг > рз » . р„> О. Это то же самое, что и разбиения т — (") = Ог +Оз + + д„, где г7г > Оз » 9„> О, так как можно установить взаимно однозначное соответствие д, = р, — и+ з.
(Сошшепзагб Асагсепг!тв Бсгеайагиш Рессора!гсапш 13 (1741), 64 — 93.) Замечание. Второе тождество получаем предельным переходом п -г оо вследствие д-ггомиальиой теоремы (см. упр. 1.2.6-58). Аналогично и первое тождество получаем предельным переходом г -з оо в дуальной форме этой теоремы. доказанной в ответе к тому же упражнению. ПУсть псз = Пз з(1+ 9+ + Ц ') и ехРг(з) = 4 „аз"/и!д. Из пеРвого тождества следует что ехр„(з) равно 1/П~~ (1-4~з(1-9)) при )9~ < 1; из второго следует что этаже выражение равно Д~ (1+ 9 йе(1 — д ')) при )ф > 1.
Полученное в результате тождество ехРр(2) ехРр 1(-2) = 1 эквивалентно фоРмУле ( 1)й й(й 1)72 которая является следствием из 9-номиальной теоремы при х = -1. 18. Пусть д = 1 — р. Сумму 2 Рг(а) по всем щ)учаям и инверсий можно вычислить суммированием по Ь, где О < )р < и — точное число крайних битовых позиций, в которых соблюдается равенство между ! и у и между Х, и Х! в инверсии, Х, 6) 1 > Х, 6) / при 1 С /. Таким образом будет получена формула 2,2<2<„2~(р + 9 ) (р 2" '2" + 2р92" (2" — 1)). После суммирования и упрощения она преобразуется в 2" '(р(2— р)(2 (рз + 2) )/(2 2 2) + ( 2 + „2)2 1) 19. Число инверсий равно ((рп//и) — (пп/и) — (тп(у — 2)/и) ) = ~ (ту' юо)1 п < пп и!о!1 и] = ес <!'< Ос!<!<й (п)г/п)(г — (и — г) — (и — г — 1)), 0< < что можно привести к виду -'(и — 1)(п — 2) — ! по(тп, и, 0).
[См. Стейе, 198 (1957), 162 — 166.) 20. См. Е. М. 'ррт!8Ы, 2. Воо!1ов Ма)Ь. 5ос. 40 (1965), 55 — 57; н 3. 2о!новв1!у, Пйсгесе Ма!Л. 9 (1974), 293-298. Тождество Якоби можно быстро доказать следующим образом. Так как П(1 — и"с' ') =(-П"и( ° )с(2) П(1,! '„' ") й=! й=1 вследствие 9-номи4льной теоремы, рассмотренной в унр. 1.2.6-58, при 9 = ие имеем П( — ." "-')( — .' '.') = й=! Для фиксированных 7' после умножения обеих частей на П„",(1 — и ей) = Пй,(1 — 9 ) получим („2 ) П„,(1 — дй) = 1+ 0(9 т) !)). При и -й оо отсюда следует тождество Якоби.
21. Интерпретируйте С; как число элементов в стеке после /-го вывода. (Характеристики Ьй, и Вй таблиц перестановок в стоке рассмотрены в упр. 2.3.3-19,) 17. 0000 1101 1010 1011 1001 2012 0100 1201 0110 0111 0101 0212 0010 1021 0120 0121 0011 0122 0001 1012 0102 0112 0012 0123 (-). (").(') П ( —.'-' й) й= †2 ( — 1) и( 2 )с(2) ~ ( 1 (пе)(2)( и е ) / (,) ( — 1)!п(2)е( 2 ). ! 22. (а) Расставьте числа [1,2,...,н) по кругу, как на циферблате часов, и установите указатель на 1.
Затем для ! = и, и — 1, ..., 1 (именно в этом порядке) передвигайте указатель против часовой стрелки Ь; + 1 шагов, удаляя из круга те числа, на которые он указывает, и назовите их а~.. (Ь) Каждое ! подсчитывается так часто, как "замыкается" последовательность а; а;~.ы .. а„; это и будет число случаев, когда аз > агы прн Х > !. Таким образом, каждое Х при а, > азт~ соответствует подсчитанным однократно индексам 1, ..., 1. [Сно-Н!и Нап, Адгалсеэ !в МаНс 105 (1994), 28-29; тот же результат получен и Роулингсом (В.ан!!пбв) в контексте следующего упражнения.[ 23. Предположим, например, что и = 5 и а» а»аз аг໠— — 31425.
Тогда число холостых выстрелов перед каждым смертельным должно быть 2+ 5Лц 2 + 4Ьм 1+ 3Лэ, 1+ 2Лэ, Лв, где Л вЂ” некоторое неотрицательное целое. Обратите внимание, что дуальной перестановке 14253 соответствует Ь-таблица 01122 в обозначениях предыдущего упражнения. В общем случае вероятность серии а~ аэ... о будет равна )( ь„,+! -Иь» ) ( ь,аь„ ы,...,ь„йа — Ч~ Чэ 9» где р = 1 — д, — вероятность фаталыюго исхода после предыдущих 1 — 1 роковых выстрелов и Ь» Ьэ... Л» соответствует двойственной последовательности а~ ею .. а„. В частности. при р~ = = р„ = р = 1 — д получим вероятность д"' "т "/С»(д).
Таким образолц будет порядок п ... 21. [Х. Тгеабиау, П. Ва»»йпкэ, МаГЛ. ЛХаб. 67 (1994), 345-354,' Роулингс обобщил этот результат для перестановок мультимножеств в Хлк Х ЬХагЛ. Хг ЛХаНс бс!. 15 (1992), 291 — 312.] 24. ПУсть ае = О. БУдем говоРить, что обобщенный спрск возникает пРи 7 ( и, если а~ > !(аз ы). После вставки н между аз ~ и а! появляется новый обобщенный спуск тогда и только тогда, когда а, ~ < Х(аз) ( п. Предположим, что это произонгло, когда Х имело значение ХЛ > Хэ » ..
Хь > О; пусть другое значение Х будет Х» > Х„~ > > Хьаь Тогда Х„= и и можно показать, что обобщенный индекс увеличивается на и — Л, когда и вставлено именно перед а,». [Особый случай, при котором Х(Х) = Х+Х для некоторых д > О, рассмотрен Д. Роулингсом, Х. СогпЬХлагогХа! ТЛеогу А31 (1981), 175 — 183; он обобщил его па перестановку мультимножеств в рабате йтеаг апИ Ми!В!шеаг А!8ебга 10 (1981), 253-260. В этом упражнении определено и! различных статистик перестановок, каждая из которых имеет производящую функцию С (з), выведенную в (7) и (8).
Можно определить и значительно больше таких статистик, обобщив формулировку задачи о русской рулетке следующим образом: после Х вЂ” 1 рокового выстрела новый круг начинается с участника Д,(ац .,аз ~), где Хх — произвольная функция, принимающая значения на (1,...,п) ! (ац...,аз ~). [См. Спо-Н!и Нал, Са!сн! Селегйеп (ТЬеэ!е, 1лпю 8!гавЬопгб, 1992), Раг! 1.3, 57.[ 25. (а) Если а» < а„, то Ь(а) имеет ровно столько же инверсий, сколько а, так как элементы в а! теперь инвертировали хг вместо а„. Но, ерш а» > а„, Л(а) имеет на и — 1 инверсий меньше, поскольку х! теряет свою инверсию а„и инверсию каждого эвемента в о .
Таким образом, если положить к = а и рекурсивно переобозначить х~ .. а» Х(Л(а)), то перестановка Х(а) = х~ ..к будет обладать желаемыми свойствами. Получится Х(198263745) = 912638745 и Х! '!(198263745) = 192687345. (Ь) Здесь ключевыми являются соотношении !пг(о) = !пг(о ) и !пб(а ) = !пб(~(а) ), еслиа естьинверсияа. Такимобразом, еслиа, =а, аз = /(а,),аз — — оэ, а» = Х '(аз) — Ц и ໠— — а»,получим )пе(аз) = ше(а4) — шй(аз) — шй(<22 ) = 1пй(а, ) = 1пй(а); 1пй(аз) = шй(а4 ) = )пй(аз ) = шй(аз) = шт(ал) = )пе(а). (Магйь Насйг)ОЫеп 83 (1978), 143-159.[ 26.
(Решение предложено Дороном Зильбергером (Погон Еез!Ьегйег).) Среднее от лпт(а) шй(а) равно 1 — [ал ) ал[ 1 [а) ) а)»1), 1<2<2<» 1<1<« что представляет собой полинам от п степени, меньшей или равной 4. Вычисление этой суммы для 1 < и < 5 дает соответственно значения О, -', з, '2', з', таким образом, .полинам ил)ест вид )и(и — 1) + —,' из(и — 1)2. После вычитания шеап(д )2 и деления на оаг(дп) получим ответ: 9/(2и+ 5) для и > 2, если исходить из (12) и (13).
27. Рассматривая 9»... 92 91 как перестановку мультимножества, получим 1пе(а1 аз .. а„) = 1пт(дп...9241) (см. раздел 5.1.2). Отсюда, используя обозначения из ответа к упр. 16 и результаты упр. 5.1.2-16, получим Е1," ',, =Е' Е. Нп(ш,з) 'л 1 1 1.. „) ыд(»1 .. ) 2 22 1- "+и (1 — )„.(1- .) ~- „, И "Ози)зиеззт -+2 21,42,...,4 йс ( и ) з,+ы,+" 12 1 З) 112 1 — ''= = 21)п [и"[ ~~| П 719— ( н)' ЗО,З1,22, 1=0 = И). [Нп[ П Екр.(".) 2=О ОО ОО 1 = 21)ч [и"[ л л л л 1 — 21шзи(1 — ш) ,=аз=о В результате имеем элегантное тождество 1 Н.()п П 1 1шлзлн ~ П зе)(1 „,2) (1 ш )(1 — 2)(1 — 22) (1 — 2»)' из которого и появляется требуемая производящая функция Н„(ш, 2) = 2 '„ш'" оп Щп ) пд)п) (последняя получена Д. П.
Равелем (П. Р. Вове!1е) в Ргос. Ашег. Масй. 5ос. 45 (1974), 144-150). В упр. 25 показано, что та же функция двух переменных подсчитывает индексы и инверсии. Приведенное здесь доказательство принадлежит Гарсиа (Саго)а) и Гесселю (Свозе!) (слз. Айлапсеэ )п Масй. 31 (1979), 288-305], которые стремились получить существенно более общий результат Если в упр.
4.7 — 27 положить га = оо, то придем к рекуррентному соотношению 2-1 Н.(ш,.) =Е(„") . — (П(1-.-- ))Н.,(-,.) 2=1 1=1 28. Взаимная замена двух соответствующих элементов изменяет значение суммарного смещения на величину 0 илн ш2; следовательно, суммарное смещение зй(аз аз... а ) < 2 1пе(аз аз...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
