Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 12
Текст из файла (страница 12)
12. (М16] Покажите, что (29) есть следствие, вытекающее из предположения (28). 13. (МН] Докажите, что число перестановок мультимножества (А а, В Ь, С с. В г), Е . е, Е 1), не содержащих пар гтоящих рядом букв са и 6Ь, равно В ) (4+В+8+Г~ (И+В+С+В+à — 1~ (С+и+В+Г~ с 14.
)Муд] Один из способов определить перестановку х, обратную перестановке л, который подсказан нам в других определениях этого раздела, — поменять местами строки двухстрочного представления л и так выполнить устойчявую сортировку столбцов, чтобь| элементы верхней строки расположились в порядке неубывания. Например, если а < Ь < с < й,то из этого определения следует, что обратной перестановкой к г и Ь 6 г)о Ь 6 о Ы будет асг)аиаЬЬои'. Исследуйте свойства этой операции обращения; имеется ли, например, какая-нибудь п1юстая связь между данной операцией и соединительным произведением? Мсокио ли подсчитать число перестановок, таких, что к = я"? и 1б. ]М26] Докажите, что перестановка а~... а„мультимножества (гц ' х1. г12 ' хм, пт х где х~ < хэ < < х, и п~ + пэ + .
+ и = гп, является циклом тогда и только тогда, когда ориентированный граф с вегнпинами (хмхе,,х,) и дугами нз х, в аь,+-.~-ь, содержит ровно один ориентированный цикл, В таком случае число способов представления перестановки в виде цикла равно длине этого ориентированного цикла. Например, ориентированным графом, соответствующим перестановке а два способа представления перестановки в виде цикла имеют вид (Ь а 6 6 с а с а Ь с) и (саоосасбаЬ), В этой формуле для С будем рассматривать ъг как произведение переменных х, На пример, при пъ = 2 имеем С =1+хъ к(хъ)+ хеихт)+хъхь в(хъхъ)+къ хек(хъхт)+хтхък(хтхъ)+хтхтк(хтхт)+". т т т т = 1+хъап+хтатд+х,а„+хъхгаматт+хъхъатъаы+хтатт+... Таким образом, коэффициент при хъ'...
х" в С равен сумме 2 гг(я) по веем перестановкам ъг мультимножества (пъ . хъ,...,п х ). Нетрудно видеть, что этот коэффипиеит равен также коэффициенту при х",'... х" в вырвлгевии (аъъхь +."+аъп»х»)тч(атъхъ + . +аз,ъх,)"т... (а»пхъ + +а»,„х, )" Цель данного упражнения — доказать формулу 1 — апхь -аюхь С = 1/В, где В = ъ)ег -амъхь аъ х» -ат,„хт» -а зхт ... 1 — а,.т, аътхт 1 — атехт которую П, А. Мак-Магон (Р. А.
МасМаЬоп) в своей книге Соъпбшагогу Апв(увы 1 (1915), равд. 3, назвал "основной теоремой". Например, если а; = 1 при всех ъ и /, то эта формула дэхт С=1/(1 — (хъ +хе+ "+х )) [Р( тъ э»ъ-эъ ъъ -д )[ ъР( тъ т»ъ-тъ» -т )[ [Р,(О- 1тч ...~.-)[ с) Пусть юъ, ..., ю~, хъ,, х~ — комплексные числа иа единичной окрухгиости. Определите вес ю(я) перестановки;г Е Р(1"' ...тп» ) как произведение весов ее столбцов в дэухстрочпом представлении, где вес столбца ъь равен ти,/юю если 1 и ъг и коэффициент при х",'... х,"„оказывается равным (и,+ . +и, )ъ/пъ!... и, Ь как и должно быть.
Для доказательства основной теоремы Мак-Магона покажите, что а) ъФг т р) = гт(тг) ъъ(р); Ь) в обозначениях из уцр, 19 П = 2 лр(т)ьг(я), где сумма берется по всем перестановкам ъг из множества (хъ,...,х с) из (а) и (Ь) следует .0 С = 1. 21. [МЭ1[ Пусть заданы пъ,..., и и ъъ > О. Сколько перестановок аъ ат... а, мультимиожестза(пъ 1,...,и, тп) удовлетворякътусловиюат+ъ > ат-ъ(при 1 < 1 < и = иъ+...+и 7 22. [ЛбУО) Пусть Р(х",' ...
х» ) означает мъюжество всех возможных перестановок мультимиожества (пъ хъ,..., пм.хм) и пусть Рд(х"„'х",' ... х" ) — подмножество Р(хд'х",' ... х" ), в котором первые пд элементов ие равны хо. а) задав число й 1 < г < тп, найдите одвозиачиое соответствие между Р(1"'... т» ) и множеством всех упорядочеииых пар перестановок, которые соответственно принадлежат Рд(Оэ1"ъ... 1™) и Рд(0~(1+ 1)"'+'... тп" ), для некоторого х > О. [Указание. Для каждого ъг = аъ...а» 6 Р(1тч ...пъ" ) положите, что 1(т) — перестановка, полученная путем замены 1+ 1, ..., тп значением 0 и удаления всех 0 иа последних пъ+ъ+ +и позициях; аналогично положите, что г(я) — перестановка, полученная путем замены 1,..., г значением О и удаления всех 0 ва первых пъ+ +пъ позициях.) Ь) Докажите, что число перестановок Рд(0»д1»ч ...
пъ" ), имеющих в двухстрочиом представлении рз столбцов д и йт столбцов ~д, равно оба < с или оба > с, в противном случае вес ранен «1/«л. Докажите, что сумма ш(я) по всем гг 6 Р(1"г...ял" ) равна гдепбг озиачветпг+. +пг, гг>г означает пгвг+ -.+п ивиутреииеесуммироваиие выполняется по всем (рг,...,р ), таким, что рбг — — ры = lс.
23. (МЗЗ] Цепочку ДНК можно рассматривать как гдово четырехбуквенного алфавита. Предположим, мы скопировали цепочку ДНК и полностью разложили ее иа однобуквенные составляющие, а затем случайным образом их вновь объединили. Докажите, что, если поместить полученную таким образом цепочку вслед за исходной, число позиций, в которых эти две цепочки будут отличаться, с большей вероятностью будет четным, чем нечетным.
(Указание. Примените к этому случаю результат предыдущего упражнения.) 24. («7) Рассмотрим некоторое отиоигение В, которое может существовать между двумя иеупорядочеииылпг парами букв; если (ю,х)В(у,«), мы говорим, что (ш,х) сохр«илсщ (у, «), в противном случае (ш, х) перемещает (у, «). Операция «прая«позиции "„' ",' применительно к В меняет "„*, „',' или ", "„' в зависимости от того, сохраняет или перемещает пара (г«, х) пару (у, «), полагая, что иг ~ х и у эл «; если иг = х или у = «, то траиспозиция всегда формирует *, „. Операция сортировки двухстрочного массива (*„,' "' *„" ) применительно к В находит наибольшее х„такое, что х, > х,тг, и траиспоиирует (взаимно переставляет) столбцы г' и 1+1 до тех пор, пока ве установится хг « х .
(Мы ие ставим условия, чтобы уг... ул представляло собой пересгагговку хг... х„,) в) Для данного (;,( '" „„") докажите, что для каждого х 6 (хг,..., х„) существует единственное у 6 (уг,...,у,), такое, что во«с(.',,( '") = вис(„„,' ' „,") для некоторых Х«, ум, ., ~Хи,ул Ь) Обозначим через ( '„",' " "," ) Оя ( л( ' *„' ) результат сортировки ('„",' " "„'„';,' " ",( ) применительно к В. Например, если В всегда истинно, Ов является просто сопоставлением, если В всегда ложно, Оя представляет собой включающее произведение г.
Обобщите теорему А — докажите, что любая перестановка гг мультимиожества М имеет единственное представление вцда гг = (х г г... хг ю уг ) ® ((хм ° . х«лл ул) Я ° ° (л) (хп ., . хии уг)), удовлетворяющее (16). если переопределить цикл таким образом: в (П) вместо (хг х« ... х„) подставить (х« ...
х„хг), Например, пусть (ш, х)В(у, «) означает, что ш, х, у и «различиы. Из этого, в свою очередь, следует, что ублажение вырэлгеиия (12) по аналогии с яыражеиием (17) есть (г1абса) Оя ((сЬЬа) Ся) ((с46) Оя ((г16) Оя(г1)))) . (Операция Оя отнюдь ие всегда следует закону ассоциативности; скобки в обобщенном разложении следует раскрывать справа налево.) в5.1.3. Серии В главе 3 была проанализирована длина неубывающих серий в перестановке и показано, что этот параметр позволяет проверить случайность последовательности. Если поместить вертикальные черточки до и погле перестановки аг аз... а„, а также между а и а.лг, когда а > аутг, то серг«гамп будут называться серии, ограниченные парами черточек. Например, в перестановке )3 5 7)1 6 8 9~4(2( имеется четыре серии. В разделе 3.3.2О были найдены среднее число серий длины к в случайной перестановке множества (1,2,..., а) и ковариацня числ~а серий длины у и длины 1т Серии важны при изучении алгоритмов сортировки, так как они представляют упорядоченные серии данных.
Поэтому-то мы теперь вновь вернемгя к вопросу о сериях. Обозначим через (2) где целое и > 0 и й также целое. Условимся, что ( )=ага (3) т. е. будем считать, что в нуль-перестановке (пустой перестановке) не содержатся нисходящие серии. Читатель, возможно, найдет небезынтересным сравнение (2) с рекуррентным соотношением для чисел Стирлннга (формулы 1.2.6-(46)). В табл. 1 приведены числа Эйлера для малых и. В табл. 1 можно заметить некоторые закономерности. По определению имеем ( )+( )+ ° .+( )=и!; (") =' (4) число перестановок множества (1,2,,п), имеющих 1ювно й нисходящкх серий а! > а!+1 и й + 1 восходящих серий.
Такие числа (",) возникают н в других контекстах; их обычно называют числами Эйлера, потому что Эйлер проанализировал их в своей знаменитой книге 1пзбгш!опез Са!сий ВНегелгюа!!з (БС Ре1ехвЬцгй: 1755, 485-487) после того, как впервые использонал несколькими годами ранее (Сотшепг. Асад. Яп1 Ьпр. Реггор, 8 (1736), 147-158, 313); их следует отличать от чисел Эйлера Е„, о которьпс идет речь в упр.
5.1.4-23. Угловые скобки в (ь) напоминают символ '>', который присутствует в определении убывания. Конечно, ('„') также равно числу перестановок, в которых имеется Й возрастаний а. < а еы Из любой данной перестановки множества (1,., н — Ц можно образовать и новых перестановок, вставляя элемент н во все возможные места. Если в исходной перестановке содержалось Й нисходящих серий, то ровно !г + 1 новых перестановок бучут иметь (г нисходящих серий; в остальных и — 1 — й перестановках будет по к+ 1 серий, поскольку всякий раз, когда и вставляется не в конец суцгествующей серии, число нисходящих серий увеличиваегся на единицу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
