Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 64
Текст из файла (страница 64)
Если Е(лл') не содержит (4, 1) илн (5,4), или (9,5), илн (6.2), или (8,6), то лл' должно быть равно гг'. В противном сэучае Е(гггг') содерягит одно из них, скажем, (9,5); тогда Е(лл') включает Е(т4л') = Е(3 1 4 9 5 2 68 7). Пгщобным образом по индукции можно доказать справедливость указанного в условиях соотношения для (Е(лл')) — )Е(л')).
РАЗДЕЛ $.1.2 1. Не верно, поскольку оставлен без внимания один вахгный нюанс. Тот, кто ответил "верно', возможно, забыл (или не знает) данное в разделе 4.6.3 определение операции Мг 0 Мг, согласно которому Мг гЗ Мэ является множеством только в том случае, если Мг и Мя также являются множествами. На самом деле о г 6 — перестановка Мг эг Мг. 2. 5 со г(г(а г)а г( Ь. 3. Разумеется, нет, поскольку может быть и а = 8. (Однако теорема о единственности разлоягения показывает, что такие случаи встречаются не часто.) 4 (г()г(Ьсг))г(ЬЬсаг()г(ЬаЬсг()г(г(). 5. Число вхождений пары ... хх...
равно числу столбцов ' либо на единицу меньше, Если х — наименьший элемент, то эти числа равны тогда и только тогда, когда х — не первый элемент перестановки. 6. Несложно подсчитать соответствующее число двъ хстрочиых массивов: (7) (.ь), 7. Используя п. (а) теоремы В, выведем требуемые соотношения аналогично тому, как было выведено соотношение (20): )( )( )( )( ) г) — 1 ) (Е) (С) (В+5 — 1) (С вЂ” Ь) ( А — 1 ) (В) (С) (Е+Ь вЂ” 1) (С вЂ” Ь) 8.
Полное разложение на простые множители имеет вид (гг) т (Ь с и) т (Ь) т (а гг Ь с) т (а Ь) т (Ь с гг) т (гг); оно единственно, поскольку никакие два соседние сомножители не коммутируют. Таким образом, имеется восемь решений «а ж е, (г(), (гг) т (Ь с г4), .... 10. В общем случае утвернгдение ложно, но в некоторых интересных частных глучаях— истинно. При любом заданном линейном упорядочении простых перестановок существует, по крайней мере, одно разлажепие указанного вида, потому что, если условие нарушается, можно сделать взаимную замену, которая сократит число "инверсий" в разложении.
Поэтому условие может не выполняться только потому, что некоторые перестановки имеют не одно такое разложение. Пусть р а означает, что р коммутирует с а. Следующее условие необходимо и достаточно для единственности разложения в указанном смысле: р а г и р < и < г влечет за собой р г.
Дохгыаглвльсщеа. Если бы р а г, р .с а -ч г и р тг г, то существовала бы два разложения атттр = ттрга; значит, условие необходимо. Обратно, для того чтобы показать, что оно достаточно для единственности, предположим, что рг т. т р« = ггг т -. т а два различных разложения, удовлетворяющих условию.
Можно считать, чта ггг -ч рг и, следовательно, ггг = рв для некоторых Ь > 1; далее, аг р при 1 < 2 < Ь. Поскольку рв г аг = рю торэ-г .< аг; следовательно, гг > 2. Пусть у такова, что а'г -г р, и р; ~ аг при у < г < к. Тогда из рг+г аг р и р +г < аг < р. следтет,что р +т р; отсюда получается р; ч р,+г, а эю — противоречие.
'Таким образом, если на множестве простых перестановок Я задано отношение порядка, удовлетворяющее указанному выше условию, я если известно, что все простые множители перестановки гг принадлежат Я, то можно заюпочнть, что гг имеет единственное разложение указанного типа, Такое условие выполняетгя, например, когда Я представляет собой множество циклов в (29). Но множество всех простых перестановок нельзя упорядочить таким образом. Если, скюкем, (а Ь) < (гг е), та придется предположить, что (а 6) < (гг' е) м (Ь с) -с (е а) м (с И) < (а Ь) м (г( е), а это — противоречие.
(См. также следующее упражнение.) 11. Наша цель — показать, что если р(1)... р(1) есть перестановка множества (1,..., 1), то перестановка хрГ П... хый топологически рассортирована тогда и только тогда, когда арГП т тарПГ = агт . таг, н что если хжм,.,хргг1и хвгг1...х гг1 — различные топалагические сортировки, то артгг:р агг г прн некотором у. Первое свойство следует из того, что хвгп может быть первым в топологической сортировке тогда и только тогда, когда ггггп коммутирует с арГП г,...,аг (но отлично ат него), а нз этого условия следует, что а Гг~ т тамг> =агт тавГгг-гтарггг+гт таг иможноиспользоватьиндукцию.
Второесвойство вытекает из того, что если у — наименьший индекс, при котором р(2) те 4(2) (пусть для определенности р(у) < 4(т)), и справедливо хрг 1 г4 хы 1 по определению топологической сортировки, то «грц1 не имеет общих букв с авГг>.
Для того чтобы получить произвольное частичное упорядочение, положим, что цикл ав состоит из всех упорядоченных пар (г, т), таких, что хг ч х, и либо г м гг, либо у = Й; зти упорядоченные пары входят в цикл в произвольном порядке в качестве отдельных элементов цикла. Так, для частичного угюрядочения хг ы хм хв -ч хы хг -с хв циклы были бы следующими: аг = ((1, 2)(1, 4)), аг = ((1, 2)), ав = ((3, 4)), ав = ((1, 4)(3, 4)).
12. Никаких других циклов образовать нельзя хотя бы потому, что исходная перестановка не содержит столбцов '„'. Если (а Ь с И) встречается в раз, то цикл (а Ь) должен встретиться А — г — в раз, поскольку имеется всего А — г столбцов в и талысо два вида циклов вносят вклад в зти столбцы.
13. Используя двухстрочное представление, сначала поместите А — г столбцов вида ~, затем — оставшиеся Г букв а во вторую строку и буквы Ь, а также все остальные буквы. 14. Поскольку в двухстрочном представлении перестановки я элементы под любой буквой всегда располагаются в порядке неубывання, то не всегда выполняется равенство (з ) =я,новсегдасправедливо((я ) ) же . Прилюбыхаидимеетместотождество (ат)1) =((и тд ) ) (см. упр, 5-2), Для данного мультнмножесгва, все различные буквы которого суть х1 « . х можно охарактеризовать все перестановки, обратные самим себе, привяв во внимание, что калсдая из них имеет единственное разложение на простые множители вида бг г ° т 8 где 8, состоит из 0 или более простых множителей (хз) т т(хэ) т(з~хь,) т т(хзвю), 1 < Ь, « .
Рь НапРимеР, (а) т (а Ь) г (а Ь) г (Ь с) т (с) — пеРссгановка, обРатнаЯ самой себе. Следовательно, число обратных самим «ебе перестановок мультимно1кества (гп а, и Ь) равно щш(т,п)+1, а соответствующее число для ((.а, т Ь, и с) есть число решений системы неравенств х+ у < 1, х+ з < ш, у + х < и в неотрицательных целых числах х, у, ю Число обратных самим себе перестановок мнонсесглеа рассматривается в разделе 5.1.4. Количество перестановок мультимножества (п1 хм...,п в,), имеющих в своем двухстрочном представлении пц вхождений столбца ~, есть П, н,!/П,. пп!.
Столько же существует перестановок, в двухстрочной нотации которых содержится пч вхождений Следовательно, должен существовать другой, лучший способ определения обратной перестановки мультимножества. Например, если разложение на простые множители мультимножестеа я есть пгтпгт ° гоп как в теореме С, можно определить я = о, т тпэ го1, где (х1...х ) = (х ...хг). Доминик Фоата (Вопип1цпе Ровса) и Гуо-Ню Хан (Опо-%п Нап) пришли к вьшодуз что было бы желательно определить обращение таким образом, чтобы я и я имели равное число обращений, поскольку производящая функция для обращений, дающих числа ш., есть П, и;),/ П,, и, !„(см, упр.
16). Однако, как нам кажется, не существует естественного способа оцрелелйть инволюцию, обладающую таким свойством, 16. См. теорему 2.3.4.Ю, После удаления одной дуги ориентированного графа должно оставаться ориентированное дерево. 16, Если х| < хт <, то элементы таблицы инверсий для разных х, должны иметь вид ьзг « . ь;,, где ь г (число инверсий для крайнего справа элемента х,) не больше, чем п,ег + и,+з + ... Таким образом, пронзводищая функция для й-й части таблицы инверсий есть производящая функция для разбиениЯ не более чем на пэ частей, причем никакая часть не превосходит из+1+ и~+э + .
Производящая функция для разбиений не более чем на т частей, где пнкакал часть не превосходит и, равна з-номиальному коэффициенту ( '~") „что довольно просто доказывается по индукции; это также можно доказать с помощью одного из остроумных умозаключений, принадлежащих Ф. Франклкну (Г. ГпшЫш) (см. Ашег. Х МаНь 6 (1882), 268-269, см. также Рб!уа, А!ехапг)егзоп, Е)ешелГе г(ег Магйегоагй 26 (1971), 102-109). Перемножив производящие функции прн у = 1, 2, ..., можно получить искомую формулу для обращения перестанспюк мультнмножеств, которую опубликовал Мак-Магон в Ргос.
Ъолдоп МаГЛ. 8ос. (2) 16 (1916), 314-321. 17. Пусть Ь (в) = (и!.)/и!, тогда желаемая вероятностная производящая функция имеет вид у(в) = Ь„(в)/Ь„, (х)Ь,(х) " . Среднее от Ь (з) равно 1 © в соответствии с соотношением 5.1.1-(12), отсюда среднее значение для д равно 2((2) (2) (2) ) 4 2~.~ мц Аналогично дисперсия равна э»в(н(п -1)(2п+ 5) — гвв(п» вЂ” 1)(2п» + 5) †. ) = — ( — — ° — )+ы(' -" -" - ) з з з» в в в 18.
Да, верно. Построения из упр. 5.1.1-25 очевидным образом распространяются и на этот случай. Можно также обобщить доказательство, которое приведено в разделе 5.1.1— (14), построив взаимно однозначное оютветствие между совокупностями пв элементов (»7»,...,9 ), где вув — мУльтимножество, котоРое содеРжнт пв неотРицательпых целых чисел, с одной стороны, и упорядоченными парами совокупностей п элементов ((ав,, ав), (р»,...,р )), гдеа»...ах — перестановкамультнмножества(пв 1,...,п пв» ирв » р > О, с другой стороны.
Это соответствие, как и прежде, определяется путем назначения всем элементам оз нижнего индекса у; оно удовлетворяет условию Е(9»)+.. +Е(9м) =вас((а»...а )+(рв+ +р„), где Б(»1») означает сумму элементов мультимножества вув. »Дальнейшее обобщение методики, использованной в этом доказательстве и выводе соотношения 5.1.3-(8), приводится в работе )Л. Е. КпасЬ, Ма»Ь. Совпр. 24 (1970), 955-961. См.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
