AOP_Tom3 (1021738), страница 166
Текст из файла (страница 166)
а»). 8. Полное разложение на простые множители имеет внд (4) т (Ь с 4) т (Ь) т (а 4 Ь с) т (а 6) г (6 с И) т (о); оно единственно, поскольку никакие два соседние сомножители не коммутируют, Таким образом, имеется восемь решений с а = ц (И)„(И) т (6 с 4), .... 10. В общем случае утверждение ложно, но в некоторых интереснык частных случаях— истинно. При любом заданном линейном упорядочении простых перестановок существует, по крайней мере, одно разложение указанного аида, потому что, если условие нарушается, можно сделать взаимную замену, которая сократит число "инверсий" в разложении. Поэтому условие может не выполняться только потому, что некоторые перестановки имеют не одно такое разложение.
Пусть р о означает, что р коммутирует с а. Следующее условие необходимо и достаточно для единственности разложения в указанном смысле: р а т и р<о-ст влечет засобой р г. Доказательсшео. Если бы р а г, р < и -с г и р т' г, то существовало бы два разложении аггтр = ггрто; значит, условие необходимо. Обратно, для того чтобы показать, что оно достаточно для единственности, предположим, что р~ г т р = и~ г т о два различных разложения, удовлетворяющих условию, 64ожно считать, что а~ < р~ и, следовательно, о~ = рь для некоторых Ь > 1; далее, а~ «р, при 1 < У < Ь.
Поскольку рь ~ о~ = рь, то рь ~ .< ац следовательно, 6 > 2. Пусть У таково, что о~ < рз и р, С о~ при У < 1 < Ь, Тогда из р,э~ о~ 62 и р~э~ < п~ -с рз следует, что р~е~ р~: отсюда получается рз .С рз+и а это — противоречие. Таким образом, если на множестве простых перестановок Я задано отношение порядка, удовлетворяющее указанному выше условию, и если известно, что все простые множители перестановки к принадлежат Я, то можно заключить, что л имеет единственное разложение указанного типа.
Такое условие выполняется, например, когда Я представляет собой множество циклов в (29). Но множество всех простых перестановок нельзя упорядочить таким образом. Если, скажем, (а Ь) -С (Ы е), то придется предположить, что (а Ь) м (И е) м (Ь с) -< (е а) м (с 4) м (а 6) ь (4 е), а это — противоречие. (См. также следующее упражнение.) 11. Наша цель — показать, что если р(1)... р(1) есть перестановка множества (1,..., 1), то перестановка хмм... хек~ топологически рассортирована тогда н только тогда, когда пр~м т том > — — о~У . тщ, и что если хщц... хр~ > и хщп,,. хщц — различные топологические сортировки, то ор1 > ~ омю при некотором 1 Первое свойство следует из того, что хы» может быть первым в топологической сортировке тогда и только тогда, когда ижм коммутирует с о„рЗ м,и~ (но отлично от него), а из этого условия следует, что орщ~ т ' ' 'тоэ<ц = пш тор~В ~ гар<Ц~.~У пп и можно использовать индУкцию.
ВтоРое свойство вытекает из того, что если у — наименьший индекс, при котором р(1) 4 Ч(1) (пусть для опРеделенности Р(У) < о(1)), и спРаведливо хрб~ з4 хщю по опРеделению топологической сортировки, то ом,> не имеет общих букв с и ~„г Для того чтобы получить произвольное частичное упорядочение, положим, что цикл ть состоит из всех упорядоченных пар (~', 1'), таких, что х, -< х, и либо 1 = /с, либо з' = 6; эти упорядоченные пары входят в цикл в произвольном порядке в качестве отдельных элементов цикла. Так, для частичного упорядочения х~ .< хм хз ч хю г~ < хэ циклы были бы следующими: о~ = ((1, 2)(1, 4)), аз = ((1, 2)), оз = ((3, 4)), оэ = ((1, 4)(3,4)).
12. Никаких других циклов образовать нельзя хотя бы потому, что исходная перестановка не содержит столбцов,'. Если (а Ь с И) встречается э раз, то цикл (а Ь) должен вгтретиться А — г — э раз, поскольку имеется всего А — т столбцов ь и только два вида циклов вносят вклад в эти столбцы. 13. Используя двухстрочное представление, сначала поместите А — 1 столбцов вида „ д затем .
— оставшиеся 1 букв а во вторую строку и буквы Ь, а также все остальные буквы. 14. Поскольку в двухстрочном представлении перестановки к элементы под любой буквой всегда располагаются в порядке неубывания, то не всегда выполняется равенство (к ) = л, но всегда справедливо ((л ) ) = л . Прилюбыха и 8 имеет местотождество (отб) = ((и тб ) ) (см. упр. 5-2). Для дшгного мультимножества, все различные буквы которого суть х«« .
х можно охарактеризовать все перестановки, обратные самим себе, приняв во внимание, что каждая из них имеет единственное разложение на простые множители вида 8«т. - г 8 где 6 состоит из 0 или более простых множителей (х,) т. г(»г) г(»1»ь,) т т(х,хм), / < /с«« Ь«. Например, (а) г (а Ь) г (а Ь) т (Ь с) г (с) — перестановка, обратная самой себе. Следовательно, число обратных самим себе перестановок мультимножества (т а, л Ь) равно ппп(т, и) + 1, а соответствующее число для (1 а, т Ь, и с) есть число решений системы неравенств х + у < (, х +» < т, у+» < и в неотрицательных целых числах х, у, ».
Число обратных самим себе перестановок мноэ«сесшеа рассматривается в разделе 5.1.4. Количество перестановок мультимножества (п~ км...,п, х„,), имеющих в своем двухстрочном представлении пб вхождений столбца,"., есть ()(, и,!/(), пп!. Столько г 1 же существует перестановок, в двухстрочной нотации которых содержится пб вхождений Следовательно, должен существовать другой, лучший способ определения обратной перестановки мультимножества. Например, если разложение на простые множители мультимножества к есть о«тоэт тш, как в теореме С, можно определить я = и, г то» то,, где (хш., х„) = (х„...
х,). Доминик Фоата (Попппсйпе Роа»а) и Гуо-Ню Хан (Спо-Нш Нап) пришли к выводу, что было бм желательно определить обращение таким образом, чтобы к и к имели равное число обращений, поскольку производящая функция для обращений, дающих числа пео есть 11, об,/»11«, п»8, (см, упр. 16). Однако, как нам кажется, не существует естественного способа определить инволюцию, обладающую таким свойством.
15. См. теорему 2.3.4.2П. После удаления одной дуги ориентированного графа должно оставаться ориентированное дерево. 16. Если х«< х» <, то элементы таблицы инверсий для разных х, должны иметь вид Ь «« Ьз„,, где Ь „, (число инверсий для крайнего справа элемента х,) не больше, чем и,+«+ п,т» + . Таким образам, производящая функция для /-й части таблицы инверсий есть производящая функция для разбиений не более чем на пг частей, причем никакая часть не превосхолит пге«+ пг+» + ..
Производящая функция для разбиений не более чем на гп частей, где никакая часть не превосходит и, равна»-номивльному коэффициенту ( «")„что довольно просто доказывается по индукции; это также можно доказать с помощью одного из остроумных умозаключений, принадлежащих Ф. Франклину (Р. ЕгапЫш) (см. Ашег.,1. Ма»Ь. 5 (1882), 268-269; см. также РоЧуа, А!ехапбегвоп, Е/ешелге 8ег Ма»йетаб1 26 (1971), 102 — 109). Перемножив производящие функции при / = 1, 2, ..., можно получить искомую формулу для обращения перестановок мультимножеств, которую опубликовал Мак-Магон в Ргос. Еолдов Маса.
Яос. (2) 15 (1916), 314-321. 17. Пусть Ь„(») = (и!,)/и!, тогда желаемая вероятностная производящая функция имеет вид 9(») = 5„(»)/Ь и (»)5„,(») . Среднее от 5„(») равно» (") в соответствии с соотношением 5.1.1-(12), отсюда среднее значение для д равно — (( ) — ( ) — ( ) — )= — (и — и,— пг — )= — ~пп ш Аналогично дисперсия равна 22 (п(п — 1)(2п + 5) — пг(пг — 1)(2пг + 5) — ) 33 = — (и — и, — пг — )+ — (и — и, — пг — .
). 1 3 3 3 1 2 2 2 21 18. Да, верно. Построения из упр. 5.1.1-25 очевидньгм образом распространяются и на этот случай. Можно также обобщить доказательство, которое приведено в разделе 5.1.1- (14), построив взаимно однозначное соответствие между совокупностями т элементов (91, -.,д ), где 91 — мультимножество, которое содержит и; неотрицательных целых чисел, с одной стороны, и упорядоченными парами совокупностей и элементов ((аг,..., а ), (рг,..., р„)), где аг...
а — перестановка мультимножества (пг 1,..., и тп) и рг > > р > О, с другой стороны. Это соответствие, квк и прежде, определяется путем назначения всем элементам 91 нижнего индекса 7'; оно удовлетворяет условию Е(91) + + Е(9 ) = !пд(аг... а„) +(рг+ + р ), где Е(91 ) означает сумму элементов мультимножества д . (Дальнейшее обобщение методики, использованной в этом доказательстие и выводе соотношения 5.1.3-(8), приводится в работе Р. Е.
КлпсЬ, МасЛ. Сотр. 24 (1970), 955-961. См. также исчерпывающее исследование В!<Ьвгд Р. 81ап!еу, Метоиэ Атег. 54агЛ. Яос. 119 (1972).] 19. (а) Пусть л = (а ) п — простая перестановка, и — левый множитель в разложении к). Если л состоит из Л элементов, то левые множители Л в разложении перестановки к такие, что р(Л) ~ 0 есть не что иное, как ровно 2" соединительных произведений подмножеств множества Ь' (см. доказательство теоремы С); следовательно, 2 р(Л) = П (1+р(п)) = О, следовательно, р(а) = — 1 и Я непусто.
(Ь) Ясно, что <(11...1 ) = р(к) = О, если 1; = гь при некотором 1 Р л. В противном случае 3(11... 1„) = (-1)", где 11... г„имеет г инверсий; это ровно ( — 1)', где 3 — число четных циклов перестановки 11... г„, что, в свою очередь, равно ( — 1)" +', где 2 — число циклов перестановки 11... г„, 20. (а) Соотношение, очевидно, следует из определения соединительного произведения. (Ь) Па определению 1)ес(51 ) = ~ ~2(11...1 )Ьп, ...Ь 1<1...
< Полагая Ь,г = 5,1 — обх! и применяя результат упр. 19, (Ь), получим хи, .. хг„д(х„... хм ) и(х;1 ... х,„), > а 1 « ,,..., поскольку р(к), как правило, равно нулю . (с) Используйте результат упр. 19, (а) и покажите, что Р 2 С = 1, если рассматривать произведения всевозможных элементов х как перестановки некоммутативных переменных, учитывая естественное алгебраическое соглашение (о+ !3) гк = п1 к+ 27 111, Сжатое толкование этого комбинаторного доказательства и похожие доказательства других важных теорем даны Д.
Зильбергером (Р. 7е11Ьег8ег, Ргэсгесе МагЛ. 56 (1985), 61 — 72). 21. Пь 1 (""т „~""-'), если положить пь = Оприй < О, поскольку существует (" 3";,~" 3) способов вставить элементы т в такую перестановку мультимножества (пг 1,..., и (т — 1)). 22. (а) Перестановка слева направо !(к) существует в Рг(0" 1"'...4т) для некоторого Л; но вместо перестановки !(к) рассмотрим ее двухстрочное представление, в котором 0 размещен последним, а не первым в верхней строке.
Число Л элементов 0 в !(к) и г(к) равно числу столбцов 13 В дВУхстРочном представлении я, для котоРых 2 < ! < Л; это также и числа столбцов, для которых /г < 1 < /р Можно легко воспроизвести л из двухстрочных представлений((гг) и г(гг), поскольку каждый столбец 12 с 1', Ь < 1 включен в!(л), каждый столбец с 1 < /Ь Ь включен в г(л), а оставшиеся столбцы получены путем слияния 10 или УО иэ 1(л) с у оили 0 из г(л) слева направо. (Ь) Пусть л — начальная форма перестановки и пусть а — любая перестановка из Ро(О"01"' ...Уп" ). Сформируйте Л следующим образом: удшгите первые по элементов из гу; затеи замените 0 элементами х, имеющими подстрочные индексы иэ первых по элементов л; замените другие элементы элементами у, имеющими подстрочные индексы из оставшихся ненулевых элементов из л.
Сформируйте также р следующим образом: удшгите элементы 0 иэ а н замените пг появлений 1 на х, или уг соответственно тому, имеют ли столбцы '„иэ л Ь = 0 или й ~ О, в порядке слева направо. Например, если л = 000000111 11222233333 000000111!1222233333 13!э!зоззгого20320!о а а = 322122шгоззогзоозо! то получим Л = хзузузгзу!у!х!узузхзх!Уохзу! и р = узу2узх!хзхЗУ!Угузузу!хзхзх!. И обратно, можно воссоздать л и а из Л и р (с) В выражении из п. (а) этой задачи имеем иг(л) = !0(1(л)) ш(г(л)), поскольку столбец 11 из л либо становится 13 веса ш1/шу в 1(л) или г(л), либо разлагается на столбцы и уо, имеющие веса з /зо и зо/зу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
