AOP_Tom3 (1021738), страница 26
Текст из файла (страница 26)
Пусть 1> — произвольный элемент цикла Р, тогда у любого левого сомножителя в разложении и т В, содержащего этот элемент у, будет левый сомножитшгь р. Значит, если р и а имеют общий элемент, цикл и должен быть кратен Р; тогда и = Р (так как они простые), что противоречит нашему предположению. Следовательно, цикл, содержащий у и не имеющий общих элементов с и, дшгжсн быть левым сомножителем в разложении В. Применив законы сокращения (7), завершим доказательство.
$ В качестве иллюстрации теоремы С рассь>отрилэ перестановки мультимножсства ЛХ = (А.а, В Ь, С. с), состоящего >О А элементов а, В элементов Ь и С элементов с. Пусть Х(А, В,С,>п) - — число перестановок мультимножества М, двухстрочное представление которых не содержит столбцов вида „", э~,,' и содержит ровно гп столбцов вида ьэ.
Отсюда следует, что имеется ровно А — т столбцов вида '„ — ш столбцов виде э', С вЂ” В+>и столбцов вида ', С вЂ” А+т столбцов вида гэ и.4+ — С вЂ” ги столбцов вида,; следовательно, ь, (23) за (с а), а (Ь с) не встречается сразу после (!? а), Отсюда, используя результат упр. 13, получаем тождество х (1) — г — э)! (А — !? — э)! э! (д — А+г+э)! Вьшося нз обеих частей множитель (л ) и несколько упрощая факториалы, при- ?Э ходим к сложному на вид пятипараметрическому тождеству биномиальных коэффициентов: Нспазьзуя тождество (27), можно выполнить суммирование по э, а затем легко вычислить получившуюся сумму по б Таким образом, выполнив вск! работу, мы не смогли обнаружить какое-лабо тождество, которое мы бы еще не умели вывалить. Но мы, по крайней мере, научились подсчитывать число перестановок определенного вида двумя различными способами, а эти методы подсчета — хорошая подготовка к решению задач, которые еще ждут нас впереди.
УПРАЖНЕНИЯ 1. ]М05) Да или нею? Пусть М! н Мэ — мультнмножества. Вели а — перестановка Мм а 0 — перестановка ЛБ, то о? 1? — переглановка М! 0 Мь 2. (1О] Соединительное произведение перестановок с а !? а Ь н Ь 4 !1 а 0 представлено в (5); найдите соединительное произведение Ь 4 а а Ы т с а Ы а Ь, которое получается, если сомножители поменять местами. 3. (М10] Верно лн утверждение, обратное (9)? Иначе говоря, если перестановки а и 3 коммутативны относительно операции соединительного произведения, то сэедует ли из этого. что они не содержат общих букв? 4. (М11] Каноническое разложение перестановки (12) в соответствии с теоремой А при а < Ь < с < Ы задается 4юрмулой (17).
Найдите каноническое разложение в случае, когда й<с<Ь<а. б. (М2У] В уюювин (Ь) теоремы В требуется, чтобы х было меньше у. Что будет, если ослабить это требование, заменив его требованием х < 0? 6. [М15] Сколько существует цепочек, состоящих ровно иэ нэ букв а и н букв Ь, таких, что ровно ?г букв Ь стоят непосредственно перед буквами а и нет никаких других букв, кроме а и Ь? 7. ]М81] Сколько строк из букв а, Ь, с, удовлетворяющих условиям (18), начинаются с буквы а, с буквы Ь, с буквы с? ° 8.
(20] Найдите все разложения перестановки (12) на два множителя а т!Э. 9. [ЯЭ[ Напишите программы, которые формировали бы разложения заданной перестановки мультимножества, описанные в теоремах Л и С. ь 10. [М66[ Да илн нега? Согласно теореме С разложение на простые множители не впшше однозначно, гем не менее можно следующим образом обеспечить единственность. "Существует линенное упорядочение М на множестве простых перестановок, такое, что каждая перестановка мультимножесгва имеет единственное разложение ошаз т уо, на простые множители, удовлетворяющее условию о, < оньы если а, коммутирует с огв ~ при 1 < 1 < и? ь 11.
[М36] Пусть аыог, ..о~ — циклы без повторяющихся элементов. Определим частичное упорядочение -С на множестве 1 элементов [хы.... х~), полагая х, < х,, если г < 1 и и; имеет, по крайней мере, одну общую букву с о,. Докажите следующую связь между теоремой С и понятием 'топологическая сортировка" (раздел 2.2.3): число различных разложений перессановкн о~ тот т то~ на прогтые множители равно колнчегтву способов топологической сортировки данного частичного упорядочения. (Например, в соответствии с (22) существует пяту способов топологической сортировки упорядочения х~ -с хю хз ч х4, х~ -С хо) Обратно, если на множестве из 1 элементов задано какое-либо частичное упорядочение, то существует множество циклов [оп ос,, .., о,), которое определяет это частичное упорядочение указанным способом.
12. [М16[ Покажите, что (29) егть следствие, вытекая~шее нз предположения (28). 13. [М21[ Докажите, что число перестановок мультимножества [.4.а,В Ь,С с,Р а,Е е,Г 1"), не содержащих пар стоящих рядом букв са и 4Ь, равно ~( Р ) (А+Вч.Е+Г) (Лч-В+С+Ет Š— С) (С+Р-~-Е+Е) 14. [МЯО[ Один из способов определить перестановку л, обратную перестановке тч который подсказан нам в других определениях этого раздела, -- поменять местами строки двухстрочного представления я и так выполнить устойчивую сортировку столбцов. чтобы элементы верхней строки расположились в порядке неубывш~ия. Например, если а < Ь < с < Ы, то из этого определения следует, что обратной перестановкой к с а Ь г? Ы а Ь с( а а будет асйаг?аЬЬЫа'. Исследуйте свойства этой операции обращения; имеется ли, например, какая-нибудь простая связь между данной операцией и соединительным произведением? Можно ли подсчитать число перестюювок, таких, что я = я ? ° 1б.
[М26[ Докажите, что перестановка а~... а„мультимножества [ *, х,",-*-), где х~ < хэ < < х, и то + пг + + и, = пг, является циклом тогда и только тогда, когда ориентированный граф с вершинами [хытю...,х ) и лугами из х, в а гы.тв, содержит ровно один ориентированный цикл. В таком случае число сгюсобов представления перестапонки в виде цикла равно длине этого ориентированного цикла. Например, ориентированным графом, соответствующим перестановке ( а а а Ь Ь с с с Ы а) ь будет а с Ь а с а а Ь с1 с 4 с а два способа представления перестановки в виде цикла имеют вид (Ь а 6 6 с а с а Ь с) и (саййсасбаЬ). 16. (Мйб) В предыдущем разделе, формула 5.1.1-(8), мы нашли производящую функцию для ннверспа перестановок в частном случае, когда в перестановке участвуют элементы множества.
Покажите, что в общем гтучае перестановок мультплгнохсесшеа производящая функция для инверсий (и! хг,пг . хг,...) равна "х-полиномиальноьгу коэффициенту" ( " )= гг!. '" -'*=П('+я+ + " ') пг,пг,,/ и!. пг. ь=! (Ср. с (3) и с определением г-номиальных коэффициенгов в формуле 1 2 6-(40).) 17. (М24] С помощью производншей функции, найденной в упр. 16, вычислите среднее значение и дисперсию дли числа инверсий в глучайной перестановке мультимножества.
18. (ЛПЗ) (П. А. МакеМагон ) Индекс перестановки а! аг .. а„был определен в предыдущем упражнении; мы доказали, что чисто перестановок этого множества, имеющих данный индекс к, равно числу перестановок. име!ощих )с инверсий. Верно ли вто для перестановок заданного мультимножестваг 19. !(НМЗЗ) Определим функцию Мебиуса д(т) перестановки к: она равна О. если гг содержит повторяющиеся элементы, и (-1) в противном слу гас, если к — произведение )с простых перестановок. (Ср. с определением обычной функции Мебиуса; упр.
4.5.2-16.) а) Докажите, что если к ф с, то ~ д(л) =о, где сумма берется по всем перестановкам Л, являющямся левыми сомножителями в разложении к (т. е по всем Л, таким, что к = Л гр, где р -- некоторая перестановка). Ь) Докажите, что если х! < хг « х и г = х„х„.. х;, где 1 < 1! < гп при 1 < й < и, то д(к) = ( — 1)"с(г! Н ., ! ), где е(г! гг...! ) = э!ба П (гь — г!), !<!<!< ь 20. (НМЗЗ) (Д. гроата.) Пусть (ач) — произвольная матрица действительных чисел. Пользуясь обозначениями нз упр.
19, (Ъ), определим и(к) = апг, а,„,„, где двухстрочное представление перестановки к таково: („,.;:) хп х„... хг„') Эта функция полезна при вычислении производящих функций для перестановок мульти- множества, потому что Л и(к), где сумма берется по всем перестановкам к мультимножества (и! тг,...,п, т )., будет производящей функцией для чигла перестановок, удовлетворяющих некоторым ограннчениЯм. НапРилгеР, если положить ао — — х пРи !' = 1 и ач — — 1 пРи !' ф 1, то 2,'и(к)— производящая функция для числа "ноподвижных точек" (столбцов, в которых верхний и нижний элементы равны). Чтобы можно было исследовать Л и(-г) для всех мультимножеств одновременно, расслютрим функцию гу = ~ ки(г), где су мма берется по всем к из множестна (хг,, х, ) ' всех перестановок мультимножеств, содержащих элементы хг,..., х, и посмотрим на коэффициенты при х",' ...
х,"„'" в С. В этой формуле для С будем рассматривать л как произведение переменных х. Например, при ти = 2 имеем С = 1+лги(хт)+лги(лт)+хтлти(хтлт)+хтхти(хтхт)+хгх,и(хгхт)+лезги(хтхт)+ . г г т т = 1+ятом +лгагг+хта,т+хтхтатгагг+лтхтоттатт+хгагг+' ' ' ° Таким образом, коэффициент при х",'... л" в С равен сумме ~ и(л) по всем перестановкам тг мультнчножества (и, хт,..., и х ). Нетрудно видеть, что этот коэффициент равен также коэффициенту при х',ч .. л'„'„в выражении (амхг + + атмх,„) '(оттхт + .
+ аг хм) "г... (а тлт +... + а,„ык,„)" Цель данного упражнения — доказать формулу 1 — аттхт — омхт где П = т)ес — а тхт -ат, х -от х 1 — а„, л — оттхт 1 — аых, С = 1/гу, — о,тгхт которую П А. Мак-Магон (Р. А. МасМаЬоп) в своей книге СотЬтпасогу Апа1уэтэ 1 (1915), равд. 3, назвал "основной теоремой". Например, если о„. = 1 при всех г и /, то эта формула дает С=1/(1 — (хт+хт+.. +х )) (1г(лР1хертР!рте)((Р(хттхт1тттрт)( (Ре(О"т1 т... пт" )( с) Пусть ют, ..., ятчо т, ..., ты — комплексные числа на единичной окружности. Определите вес ю(л) перестановки л Е Р(1"'... т" ) как произведение весов ее столбпов в двухстрочном представлении, где вес столбца ть равен вт/юг, если / и Ь и коэффициент при х",'...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
