AOP_Tom3 (1021738), страница 23
Текст из файла (страница 23)
[Мйу] Докажите, что в обозначениях, принятых в упр. 7, перестановка а| аэ...а„ представляет собой инволюцию (т. е. обратна самой себе) тогда и только тогда, когда 6; = Сл при 1 < 1 < и. 10. [НМ20] Рассмотрите представленный на рис. 1 октаэдр как многогранник в трехмерном пространстве. Чему равен диаметр усеченного октаздра (расстояние между вершинами 1234 и 4321), если все ребра имеют единичнук| длину? 11. [М85] Если к = а| ал .. а„представляет собой перестановку множества (1,2,,п), то обозначим как Е(я) = ((а„а ) [ л < 1, о, > а,) множество ее инверсий, а как Е(гг) = ((ац ау) ! г > /, аг > аз) множество ее "неинверсийб а) Докажите, что Е(гг) и Е(л) транзнтивны. (2Множество Я упорядоченных пар называется транзитиенмм, если для любых (а,б) и (6, с), принадлежащих 5, пара (а,с) также принадлежит Е ) Ь) Обратно, пусть Š— любое транзитнвиое подмножества множества Т = ((з, у) ~ 1 < у < х < гг), дополнение которого Е = Т г Е также транзитивио.
Докажите, чта существует перестановка л, такая, что Е(л) = Е. 12. (М28) Используя обозначения, принятые в предыдущем упражнении, докажите, что если ггг и лз - - перестановки, а Š— минимальное транзнтивное множество, содержащее Е(ггг ) 0 Е(ггз), то Š— также транзнтивное множество. (Следовательгго, если мы говорим, что ггг находится "над" лз, когда Е(ггг) С Е(ггз), то определена решегака перестановок; существует единственная "самая низкая" перестановка, находящаяся "над" двумя данными перестановками. Диаграмма решетки прн и = 4 представлена на рис.
1.] 13. (МЯУ) Известно, что в разложении определителя половина членов выписывается са знакозг "+", а половина — - со знаком "— ". Другими словами, при а > 2 перестановок с чеглнмм числом инверсий ровна столько же, сколько с нечетным. Покажите, что вообще. при и > гл количество перестановок с числом инверсий, конгрузнтным 1 по модулю т, равна и!/т, независимо от того, каково целое число б 14.
[МЯ4) (Ф. Франклин (Г. ггапЫги).) Разбиение числа п на )г различных частей — это представление и ввиде суммы п = рг+рз+ +рь, где рг > рз » рь > О. Например, разбиения числа 7 иа различные части таковы: 7, б + 1, 5 + 2, 4 + 3, 4 + 2 + 1. Пусть /ь(л) — число разбиений и на 1 различных частей. Докажите, что 2.„(-1)~/ь(а) = О, если только и не представляется в виде (3/з х /)/2 при некотором неотрицательном целом 1; в этом случае сумма равна ( — 1)'. Например, для и = 7 сумма равна — 1 ш 3 — 1 = 1, потому что 7 = (3 2 + 2)/2.
(Указание. Представьте разбиения в виде массива точек, в г-й строке которого имеется р, точек, 1 < г < 1. Найдите наименьшее /, такое, что р,чг < р — 1, и обведите крайние справа точки первых / строк. Если г < ры то зти г точек можно, как правило, изъять из массива, повернуть на 45' и поместить в новую, (1+1)-ю, строку. С другой стороны, если у > рь, то обычно можно изъять из массива 1-ю строку тачек, повернуть ее на 45' и поместить справа ат обведенных точек (рис. 2) В результате в большинстве случаев разбиения с четным числом строк и разбиения с нечетным числом строк группируются в пары; таким образом, в сумме следует учитывать толька непарные разбиения.) Рис. 2.
Соответствие Франклина между разбиениями на различные части. Замечание. Как следствие получаем формулу Эйлера: (1 — з)(1 — з )(1 — з )... = 1 — з — з + з + з — з — з + з з з г ы гз ), 1ззз.ггуз Поскольку. производящая функция для обычных разбиений (не обязательно на различные чагти) равна 2,'р(п)а" = 1/(1 — з)(1 — хэ)(1 — х~)..., получаем неочевидное рекуррентиое соотношение для числа разбиений: р(п) = р(п — 1) -Ь р(п — 2) — р(п — 5) — р(п — 7) -Ь р(н — 12) + р(п — 15)— 15. (М85) Докажите, что соотношение (1б) — это производящая функция для числа разбиений ие более чем на и частей. т, е.
докажите, что коэффициент при з в 1/(1— х)(1 — х )... (1 — з") равен числу способов представления пл в виде суммы т = рл + рз + э -.. +р, где рл > рэ » .. р > О. (Указание. Нарисуйте точки, как в упр. 14, и покажите, что существует взаимно однозначное соответствие между и-мерными строками чисел (рл,рп р„), такими. что рл > рл » р„> О, и последовательностями (РмРл,Рз, .), такими, что и > Рл > Рэ > Рз » . О, обладающее тем свойством, что рл +р +. + р = Р1 + Рл+ Рз + . Иными словами, покажите, что разбиениям не более чем на и частей соответствуют разбиения на части, не превосходящие и.) 16.
(М25] (Д. Эйлер ) Докажите следующие тождества. интерпретируя обе части соотношений в терминах разбиений: 1 1 4 4 (1 — йл ) (1 — хИ1 — йз)(1 — 9' ) — = Е '/П л-~> (1 , )(1 , г) чйе 1<э<» П( + ' ) =( + И1+ "И + ') л.>е 2 >о 1«л<, 17. (90) Каковы 24 тетрады (йц дэ, 9>, 94), для которых в соответствии МаклМагона, опрш деленном в конце этого раздела. (р„рэ,рз, р<) = (0,0, О, 0)? 18. (М30) (Т Н!ЬЬагс1, САС51 6 (1963), 210.) Пусть и > () и последовательность 2" и-разрядных целых чисел Ла;, Хэ -л цолучена случайным образом, причем каждый разряд каждого чиг ~а независимо от других разрядов принимает значение 1 с вероятностью р Рассмотрилл последовательность Ле Ол О, Х.
л9 1, ..., Хт -л Э (2" — 1), где 01 — - операция "исключающее или" над двоичнымн представлениями. Так, если р = О, то последовательность будет такой О, 1,..., 2" — 1; если р = 1, то она будет такой: 2" — 1,..., 1, О, если же р = — ', то каждый элемент последовательности — случайное число между 0 и 2" — 1. Вообще же, при разных р это хороший способ получения последовательности случайных целых чисел со смещенным числом инверсий, в то время как распределение элементов последовательности, рассматриваемой как единое целое, равномерно (опйопп) в том смысле, что все и-разрвдиьсе целые двоичные числа будут цметь одинаковые распределения.
Определите среднее число инверсий в такой последовательностя как функцию от вероятности р. 19. [Мха) (К. Мейер (С. Меуег) ) Егли ш и и -- взаимно простые числа, то известно, что последовательность (т гллоб п)(2ш шоб и) .. ((и — 1)гп лпоб и) представляет собой перестановку множества (1, 2,, и — 1) Покахсите, что число инверсий этой перестановки может быть выражено в терминах сумм Дедекинда (см. и. З.З 3) 20. (М45) Следующее знаменитое тождество, принадлежащее Якоби (эллис(ашевга Хата Тйеоба Рилс11огцип Е/(лрс1сагнт (1829), 554), лежит в огнове многих замечательных соотиошеллий, содержащих эллиптические функции П(1 -и" ' 'И1- " '''П1 — ''') ь>1 2 з 2 2 = (1 — и)(1 — в)(1 — ив)(1 — и в)(1 — ив )(1 — в в ) . =1 — (в+в)«-(и в+ив') — (и в +и в )+ (-Ц~и(()в( г ).
— в <Э<в« Если, например, положить и = з, в = х~, то получится формула Эйлера пз упр. 14, Ести положить г = в/в7вз в = в/вю, то получим вв« Существует лн комбинаторное доказательство тождества Якоби, аналогичное доказательству Франклина для частного случая из упр. 14? (Таким образом, нужно рассмотреть 'комплексные разбиения" гл + и/ = (р> т Ф /) + (рз + дэ/) -~- ' ' -~- (рв + с/ю) где р +в„/ — — различные ненулевые комплексные числа; рм ол, — неотрицательные целые числа, причем ~р, — в,( < 1. Согласно тождеству Якоби число таких представлений с четными /г равно числу представяепий с нечетными к, если только гл и и не являются соседними треугольными числак1и!) Какими еще замечательными свойствами обладают комплексные разбиении? ° 21.
(М25) (Г. Д. Кногт (С. П. Кпосв).) Покажите. чзо перестановку а1.. а„можно получить с помощью стека (см, упр. 2.2 1 — 5 или 2.3 1-6) тогда и только тогда, когда С, < С, 1+ 1 при 1 < / < п (см. обозначения в упр. 7). 22. (Мйб; Задана перестановка а; аз .. а множества (1, 2,..., и).
Пусть /б — число индексов 4 < /, таких, что а, 6 (а,+1, а, +2,..., агю). (Если а,в1 < а,. с<темснты этого множества "оборачиваются" от п к 1. Когда / = и, используется множество (а„+1, о„+2, и).) Например, перестановка 591826473 приводит к /и ...
6э = 001214246. а) Докажите что а1 аз... а„можно восстановить по числам /и йз .. л„ Ь) Докажите, что /м + йэ + . т Ь, — суть индексы а1 аэ... а,. ь 23. (М27) (Русскал рулетка.) Группа из и человек, приговоренных к смерти, которые отдаюг предпочтение теории вероятности перед теорией чисел, могла бы, рассевшись по кругу и несколько модифицирован метод Иосифа (упр. 2), попробовать такой способ самоубийства. Первый приговоренный нажимает спусковой крючок револьвера, направив его себе в висок; с вероятностью р произойдет роковой выстрел, и он покинет круг. Затем револьвер ш реходит ко второму приговоренному и он делает то же самое.
Далее сюжет повторяется по кругу с постоянной вероятностью р > 0 до тех пор, пока будет кому его продолжать. Пусть а, = /с, если /с-к~у приговоренному выпал /-й роковой выстрел. Докажите, что порядок "выбывания" а1аз .. а„появится с вероятностью, которая является функцией только и, р и индекса дуальной перестановки (и+ 1 — а„)... (и+ 1 — аз) (и+ 1 — а1).
Какой порядок ввыбывання" наименее вероятен? 24. (Мйб) Для заданного множество целых чисел Г(1) /(2)... Г(п), где Г(/) > 3, вбобщеннъ~б индекс перестановки а1аз .. а„равен сумме всех нижних индексов /', таких, что а~ > Г(л, 1), плюс общее число инвеРсий, таких, что ю' < / и Г(а,) > а, > ал Значит, если 1(/) = / для всех /, обобщенный индекс совпадает с обычным индексом, но при Г(/) > и для всех /' это будет зисло инверсий. Докажите, что число инверсий, для которых обобщенный индекс равен /с, — то же самое, что и число перестановок, которые имеют й инверсий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
