AOP_Tom3 (1021738), страница 27
Текст из файла (страница 27)
х"„, оказывается равным (нт+ . +и )!/пт!... нет!, как и должно быть. Для доказательства основной теоремы Мак-Магона покажите, что а) и(тгтр) = и(тг)и(р); Ь) в обозначениях из упр. 19 В = ~ лр(л) и(л), где сумма берется по всем перестановкам тг из множества (хт,..., хп ); с) из (а) и (Ь) следует Р. С = 1. (М91) Пусть заданы и, ..., и и Ы ) О. Сколько перестановок ат ат... а„мультигтно.
жества (пт 1,..., и„, пг) удовлетворяют условию а? т. т ) а — И при 1 < / < и = пт + . + пи? 22. (М30) Пусть Р(х",'... х" ) означает множество всех возможных перестановок мультимножества (пт хт,..., и х ) и пусть Ре(хелтхтт ... х,"„) — подмножество Р(х"'х",'...
л" ), в котороът первые не элементов не равны хе. а) Задав число г, 1 < с < ти, найдите однозначное соответствие между Р(1"'... т"'") и множеством всех упорядоченных пар перестановок, которые соответственно принадлежа~ Ре(0~11т... Сл') и Ре(Оь(г+ 1)гч ' ... нт" ), для некоторого Ь > О. (Указание.
Для каждого тг = ат...а„Е Р(1гч .. от" ) положите, что 1(тг) — перестановка, полученная путем замены С+ 1, ., т значением 0 и удаления всех 0 на последних птет+ .-Ьн позициях; аналогично положите, что т-(тг) — перестановка, полученная путем замены 1,... 1 значением 0 н удаления всех 0 на первых от+ +пт позицивх.) Ь) Докажите, что чигло перестановок Ре(0"'1л' ... ит" ), имеющих в двухстрочном представлении р, столбцов е и дт. столбцов те, равно оба < Ф или оба > й в противном случае вес равен хс/хл. Докажите, что сумма ю(л) по всем сс б 2>(1"с ...пс™ ) равна где п<с означает пс+ +п„п>с означает псэс+ +лж и внутреннее суммирование выполняется по всем (рс,,р ), таким, что р<с = р>с = Ь. 23. [МхЗ) Цепочку ДНК можно рассл<атривать как слава четырехбуквенного алфавита.
Предположим, л<ы скопировали цепочку ДНК и полностью разложили ее на однобуквенные составляющие, а затем случайным абра<ам их вновь объединили Докажите, чта, если поместить сюлученную таким образам цепочку вслед эа исходной, число позиций, в которых эти две цепочки будут отличаться, с большей вероятностью будет четныл<, чем нечетным. [Указан<се. Примените к этому случаю результат предыдуи<его упражнения.] 24. [27) Рассмотрим некоторое отношение 11., которое может существовать между двумя неупорядоченными парами букв; евши (ю, х)сс(у, х), мы говорим, что (ю, х) свхроняеш (у, х), в противном случае (ю, х) пеусемеиЭвет (у, х). Операция шуюнспоэвцпп „" ,применительно к й меняет <, „', или,' "„' в зависнлюсти от того, сохраняет или перемещает пара (ю, х) пару [у, х), полагая, что ю ~ х и у Эс в; если св = х нли у = х, то транспозиция всегда формирует,* „.
Операция свршпровки двухстрочнога массива ('„'[ ' *„") применительно к 27 находит наибольшее х,, такое, что х, > х,,с, и транспонирует (взаилщо переставляет) сталбць< у и у'+ 1 до тех пар, пока ие установится хс « . х . (Мы ие ставим условия, чтобы ус... У„представляла собой перестановку хс... х .) а) Для данного ('„,' ' *„" ) докажите, что для каждого х б (хс,..., х„) существует единственное У б (У<,...,У,), такое, что загс(сс „*") = загс(„с, „,") длЯ некотоРых хе, ус,, х„, у„.
Ь) Обозначим через ("„,' .. „„")(э) (*„' *.,') результат сортировки („,' ' „,',*,';,') применительно к й. Например, если й всегда истинно, Оэ является просто сопоставлением, если Л всегда ложно, Ов представляет собой включающее произведение г. Обобщите теорему Л докажите, чта любая перестановка х мультилсиожества М имеет единственное представление вида <с = (хсс . хс с Ус) ® ((хсс ° . хз л Ус) Оэ ''' ® (хсс хс с Ус)) удовлетворяющее (16), если переопределить цикл таким образом: в (11) вместо (хс хс ...
х„) подставить (хс ... х„хс), Например, пусть (ю, х)Л(у, х) означает, что ю, х, у и э разлячны. Из этого, в свою очередь, гтедует, что раэложение выражения (12) по аналогии с выражением (17) есть (ссс<Ьсв) Оэ ((сЬЬо) ® ((сс<Ь) ® ((с<Ь) ® (л)))) . (Операция ® отнюдь «е всегда следует закону ассоциативности; скобки в обобщенном разложении следует раскрывать справа налево.) в5.1.3. Серии В главе 3 была проанализирована длина неубывающих серий и перестановке и показано, что этот параметр позволяет проверить случайность последовательности.
Если поместить вертикальные черточки до н после перестановки а, пг... по, а также между и. и и <.с, когда и > а еэ, то сериями будут называться серии, ограниченные нарами черточек. Например, в перестановке Таблица 1 ЧИС7!А ЭсслнгА ( )=1, ( )=О, гдеп>1. (6) Соотношение (6) следует из (5) вследствие свойства симметрии ( )=( ), гдеп>1, (7) которое вытекает из того факта, что каждая непустая перестановка а!аз ... а„, содержащая Й нисходящих серий, имеет и и — 1 — !с восходяпшх серий.
Другое важное свойство чисел Эйлера выражается формулой которая была впервые вьсведсна квтайским математиком Ли Шан-Ланом и опубликована в 1867 году. (Сьс, 3.-С. Масси!о1с, А Нмгогу оЕ СЛ1ссезе Ма!!се!па!сев (Вег!1п: Врг1пбсг, 1997, 346-348); особый случай, если и < 5, был независимо рассмотрен японским математиком Йенс!!суке Мацунага (51асвнпаба ТоЬ1ви)се), который умер в 1744 году.) Тождество Ли Шан-Лана следует из свойств операции сортировки. 1зассмотрим сп" последовательностей асах...а„, где 1 < а, < си. Любую такую последовательность можно устойчиво рассортировать в порядке неубывания и получить: (9) ас,<а;,« .а;„, (10) 1 < аз < аь < ас < ас < ав < аз < аз < ас < аз < га.
где сс са... с„— отпозначно определенная перестановка множества (1,2,..., и), такая, что с, < с жс, если аб = аь.,; другими словами, из с > с +с следует аи < ач, Покажем, что если в перестановке сс ст...!в содержится !с серий, то чигло соответствующих ей последовательностей ас аз...ав равно ("+„' ): тем самым будет доказана формула (8), если заменить Л значением п — Л н воспользоваться (7), поскольку ('„') перестановок имеют и — Й серий. Пусть, например, п = 9, сс сз... св = 35 7 16 8 9 4 2 и требуется подсчитать число последовательностей ас а....
ав, таких, что Оно равно числу последовательностей Ьг Ьг... 6э, таких, что 1 < Ьг < Ьг < Ьз < 64 < Ьл < Ьл < 6« < Ьв < Ьэ < т + 5, поскольку можно положить Ь! —— аг, 6г —— аэ + 1, Ьг = а« + 2, 64 = а~ + 2, Ьл — ав + 3 и т. д. Число способов, которыми можно выбрать элементы Ь, равно просто-напросто числу способов выбора 9 предметов из гп+ 5, т. е. ( +л); аналогичное доказательство годится для произвольных и и /с и любой перестановки гг лг...
г„с Ь сериями. Так как в обеих частях равенства (8) стоят полиномы от ги, вместо пг можно подставить любое денствительное число, получив интересное выражение степеней через последовательные бнномиальиые коэффициенты: Например, В основном благодаря именно этому свойству числа Эйлера весьма широко применяются в дискретной математике. Положив в (1» х = 1, докажем еще раз, что („",) = 1. поскольку биномиальные коэффициенты обращаются в 0 во всех слагаемых, кроме последнего.
Положив х = 2, получим ( )=( )=2" — п — 1, п>1. (12) Подставив х = 3, 4, ..., убедимся, что все числа (",) полностью определяются соотношением (1», и придем к формуле, впервые найденной Эйлером: (13) Рассмотрим теперь производящую функцию для серий. Если положить (14) то коэффициент при «л будет равен вероятности того, что случайная перестановка множества (1, 2,..., п) содержит ровно й серий.
Поскольку Й серий в перестановке столь же вероятны, как и п+ 1 — й, среднее число серий должно равняться 5(п + 1) 1 и, следовательно, д„'(» = г (п +». В упр. 2, (Ь) показано, что имеет место простая формула для всех производных функции д„(«) в точке « = 1: д~~~(» = ( )/( ), и ) т. (15) Так, в частности, дисперсия д'„'(» + д„'(» — д„'(»г равна (п +»/12 при п ) 2, что указывает на довольно устойчивое распределение около среднего значения.
(Эта же величина была найдена в упр. 3.3.2 †(18); в нем она называлась сотах(Н'„ 1«').) функция д„сд) — полинам, позтому с помощью формулы 115) и формулы Тейлора ее можно представить в виде и и д„1д) = —, ) (д — 1)" !с~( 1) = —, ~~~ з + 11 — д)" !с!( ). 116) ' а=о ' ь.=о Второе равенство следует из первого, поскольку вследствие условия симметрии 17) дпсд) = дп~ дгг11/я), гг > 1.
117) Из рекуррентного соотношения для чисел Стирлпнга (";,')=""(.;,) (;) при и > 1 получаются два более простых представления: Гг и „!.) = — ~:(. — )н-"! !(") = —, ~ ."! —.)"-"й!("), ! 8) ' а=о ' ь=о Производящая функция от двух переменныхе (,*) = Е "1 )хп = К ("„) — ';" 119) равна, следовательно, / г1сгз — 1)х)н !и) 1д! /ест 0* — 1) 11 — д) а,п>о ' ь>о 120) Это еще одно соотношение, проанализированное Эйлером.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
