Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 11
Текст из файла (страница 11)
В случае, если перестановка является таким циклам, наше рассуждение доказывает, что не существует левых множителей, кроме с и самого цикла. Если же перестановка содержит повторяющийся элемент у, то всегда можно выделить нетривиальный цикл в качестве левого сомножителя, в котором элемент у встречается всего лишь однажды. Если перестановка непростая, то ее можно раз.тагать на все меньшие и меньшие части, пока не будет получено произведение простых перестановок.
Можно даже показать, что такое разложение является единственным с точностью до порядка записи коммутирующих сомножителей. Теорема С. Каждую перестановку мультттмножесгва можно записать е виде произведения пт т пз т ' ' т о~ т > () (2т) где и — циклы, не содержаптне повторяюитттхття элементов. Это прсдглаеленпе единственное в том смысле, что лва любых таких представления одной и той же перестановка можно преобразовать очно в пру~ос, последовательно меняя местамн соседттпе непересекающиеся циклы.
Термин "непересекающиеся циклы" относится к циклам, не имеющим общих элементов. В качестве примера можно проверить, что перестановка ааЬЬсса разлагается на лшожители ровно пятью способами: (а Ь) т (а) т (с И) т (Ь с) = (а Ь) т (с И) т (а) т (Ь с) -- (а Ь) т (с А) т (Ь с) т (а) = (с д) т (а Ь) т (Ь с) т (а) = (с т() т (а Ь) т (а) т (Ь с). Дакааательстпео. Нужно установить, что выполняется сформулированное в теореме свойство единственности. Применим индукцию по длине перестановки; тогда достаточно доказать, что если р и а -- два различных цикла, не содержащих повторяющихся элементов, и рта = птд,, то р и а —. непересекающиеся циклы и о = отй где д -- некоторая перестановка. Пусть у — произвольный элемент цикла р, тогда у любого левого сомножителя в разложении и т д, содержащего этот элемент р, будет левый сомножитель р. Значит, если р и а имеют общий элемент, цикл а должен быть кратен Ьц тогда и = р (так как они простые), что противоречит нашему предположению.
Следовательно, цикл, содержащий р и не имеющий общих элементов с и, должен быть левым сомножителем в разложении ф. Применив законы сокращения (7), завершим доказательство. В качестве иллюстрации теоремы С рассмотрим перестановки мультимножества М = ( 4. а, В Ь, С . с), состоящего из .4 элементов а, В элементов Ь н С элементов с.
Пусть тт'(А, В, С, пт) — число перестановок мультимножества ЛХ, двухстрочпое представление которых не седермсиш столбцов вида „", ьь, , 'и содержит ровно т столбцов вида ь. Отсюда следует, что имеется ровно А — ш столбцов вида '„.,  — т столбцов вида ь, С вЂ” В+та столбцов вида,',, С вЂ” А+т столбцов вида," и.4+В-С-т столбцов вида,; следовательно, ь,, (23) Теорема С предлагает другой способ подсчета этих перестановок: коль скоро столбцы '„ь,,' исключены, в разложении перестановки единственно возможны такие простые множители: (аЬ), (ос), (Ьс), (або), (асЬ). (24) Каждая пара этих циклов имеет хотя бы одну общую букву, значит, разложение единственно, Еглн цикл (а 6 с) встречается в разложении Й раз, то из нашего предыдущего предположения следует. что (а ь) встречается пь - 6 раз, (ь с) встречается С вЂ .4+ пь — 6 раз, (а с) встречается С вЂ” В+ пь — 6 раз и (а с Ь) встречается А+ В— С -2пь+ /с раз.
Следовательно, Х(А, В, С, пь) равно числу перестановок этих циклов (полнномнальному коэффициенту), просуммнрованному по всем значениям Ьл Ж(А, В, С, ти) (С+ пь — Ь)! ~~Ь-" (пт-Ь))(С вЂ” А+пь — Ь))(С вЂ” В+пь-6)! 6)(А+ — С вЂ” 2пь+Ь)! (25) Сравннвая (23) с (23), обнаруживаем, что должно выполняться тождество Оказывается, с этим тождеством мы встречались в упр. 1.2.6-31: ~-(М вЂ” В+Я) (Я+В-Я) ( В+у ) (В) (Я) (27) где М = А +  — С вЂ” пь, Ас = С вЂ” В + пь, В = В. Я = С, а у = С вЂ” В + пь — Ь. Аналогично можно подсчитать число перестановок мультимножества (А.а, В Ь, С с, П - о1, если количества столбцов разлпчных типов в ннх задано следующим образом. Тнп с с столбца: Частота: г А — г Ь Ь с И И а с ь с с с (23) д  — л В-А+г П-г А-л  — А+л (Здесь А + С = В+ В.) Возможнымн циклами в разложении такой перестановки на простые множители будут 11вкл: (а Ь) (Ь с) (с И) (ь! а) (а Ь с с() (с! с Ь а) (22) Частота: А — г-э  — д-э П-г — л А-д-э э д — А+г+ь при некотором э (см.
упр. 12). В этом случае циклы (а 6) и (с с() заменяют друг друга так же, как циклы (Ь с) н (о а), поэтому необходимо подсчитать число различных разложеннй на простые множители. Оказывается (см. упр. 10), всегда существует единственное разложение, такое, что цикл (а Ь) никогда не следует непосредственно за (с Ы), а (Ь с) не встречается сразу после (а а). Отсюда, используя резудьтат упр. 13, получаем тождество (В) ( А — а-е ) (В+ — т — е — 1) ° н Вб х (В-т — я)! (А — а — е)) е! (о — А+т+л)! =(',)(",')(',) (:,) Вынося из обеих частей множитель (я т) и несколько упрощая Факторналы, приходим к сложному на вяд пятипараметрнческому тождеству бнномиальных козффнциентов: (В)(А-э — 1)(В+ — т-а — 1)(В-А+о) ( А-а ) =(',)(",')(',) " Используя тождество (27), можно выполнить суммирование по е, а затем легко вычислить получившуюся сумму по б Таким образом, выполнив всю работу, мы не смогли обнаружить какое-либо тождество, которое мы бы еще не умели выводить.
Но мы, по крайней мере, научились подсчитывать число перестановок определенного вида двумя различнымн способамн, а зги методы подсчета — хорошая подготовка к решению задач, которые еще ждут нас впереди. УПРАЖНЕНИЯ 1. »М05» Да али нею г Пусть М~ и Мг — мультнмножества, Если а — перестановка Мп а 0 — перестановка Мм то а г  — перестановка М~ С Мь 2. »10» Соединительное произведение перестановок с а Ы а 6 и Ь Н 0 а 0 представлено в (о); найдите соединительное произведение Ь 0 0 а 0 г с а 4 а Ь, которое получается, если сомножителя поменять местами. 3.
»М13» Верно лн утверждение, обратное (9)? Иначе говоря, если перестановки а н 3 коммутатнвны относительно операции соединительного произведения, то следует ли нз зтото. что они не содержат общих букв'? 4. »М11» Каноническое разложение перестановки (12) в соответствии с теоремой Л при а с 6 < с с 0 задается формулой (1?). найдите каноническое разложение в случае, когда 0<с<6<а. б. »М23] В условии (Ь) теоремы В требуется, чтобы х было меньше р. Что будет, если ослабить это требование, заменив его требованием х С 0? б.
»М15» Сколько существует цепочек, состоящих ровно нз т букв а и п букв Ь, таких, что ровно Ь буке Ь стоят непосредственно перед буквами а н нет никаких других букв, кроме а и Ь? ?. »МИ» Сколько строк из букв а, Ь, с, удовлетворякнцих условиям (18), начинаются с буквы а, с буквы Ь, с буквы с? 8. [20] Найдите все разложения перестановки (12) на два множителя а г 0.
9. (УУ] Напишите программы, которые формировали бы разложения зманной перестановки мультимножества, описаннью в теоремах Л и С. ь 10. (М80) Да или неги е Согласно теореме С разложение на простые множители не вполне однозначно, тем не менее можно следующим образом обеспечить единственность. "Существует линейное упорядочение < на множестве простых перестановок, такое, что каждая перестановка мультнмиожества имеет единственное разложение и~ гиг т .
Ти„иа простые множители, удовлетворяющее условию и, -с аг ьм если и, коммутирует с из+1 при 1 < ~ < и? в 11. (М26] Пусть и,, ам..., и~ — циклы без повторяющихся элементов. Определим частичное упорядочение м на множестве 8 элементов (хм..., х, ), полагая х, -г х„если 1 < 2 и сп имеет. по крайней эгера, одну обвгую букву с а .. Докажите гледующую связь между теоремой С и понятием "топологическая сортировка" (раздел 2.2.3): число различных разложений перестюговьзг о1 тиег то, на простые множители раено количесгвущгособов топологической сортировки данного частичного упорядочения. (Например, в соответствии с (22) существует пять спооэбов топологической сортировки упорядочения х1 м хы хэ < хм х1 .< хо) Обратно, если на множестве из 1 элементов задано какое-либо частичное упорядочение, то существует множество циклов (ание,...,о~), которое определяет это частичное упорядочение указанным способом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
