AOP_Tom3 (1021738), страница 24
Текст из файла (страница 24)
[Указание. Покажите, что, если взять любую перестановку а)... а„ множества (1,, п — 1) и поместить число п на все возможные места, обобщенный индекс увеличится на (9, 1,, и — 1) в некотором порядке.) ° 25. [МЯО[ (Фоата и Шуценберже.) Пусть существует перестановка о = а) ... аГц обозначим через шб(о) ее индекс, а через )пг(о) — число ее инверсий. а) Определите взаимно однозначное соотвегствие, которое преобразует перестановку а множества (1,, и) в перестановку 7(а), имеющую такие два свойства. ()) !пс) Що)) = )пч(а); (б),пля 1 < ) < и числа 1 появляется слева от у' + 1 в 7(а) тогда и только тогда, когда оно появляется слева от з + 1 в а.
Какая перестановка при этом соответствует 7(а), если а = 198263745? Для какой перестановки 7(о) = 198 263745? [Указание. Если и ) 1, напишите а = х)о)хзоз, ..хьаза, где х),, хь — все элементы, меньшие, чем а„, если а~ < а„: в противном случае хц, хь — все элементы, болыпие, чем а„; другие элементы появятся а цепочках (возможно, пустых) а),, аю Сравните число инверсий Ь(о) = о)х)азхз...аьхз с шг(а); в этом выражении числа а„отсутствует в 6(а).) Ъ) Обозначьте через 7 другое однозначное соответствие д, которое имеет два следующих свойства: (!) !п))(д(а)) = !п)(о); (б) !пг(д(о)) = )пб(о) [Указание. Примите во внимание обратные перестановки.) 26.
[Мдд[ Чему равен статистический коэффициент корреляции между числом инверсий и индексом случайной перестановки? (См. упр. 3.3.2 — (24).) 27. [М37[ Докажите, что в дополнение к (15) существует простое соотношение между )пг(а~ аз... а ) и п-мерной строкой (д), дз,..., 7„), Используйте это соотношение для получения производной соотношения (17) в общем случае и формирования алгебраического вырахсения в виде производящей функции двух переменных где суммирование выполняется по всем и.' перестановкам а) аз...
а„. ь 28. [95] (Р. В. Флойд (ГГ %. Р!оу)Г), 1983.) Если а~ аз .. а„— перестановка множества (1, 2,..., и), то его суммарное смещение определяется как 2", ) [а) — 1[. Найдите верхнюю и иижнк)ю границы суммарного смещения в терминах количества инверсий. 29. (дд) Если л = а) аз... а„и )г' = а', а';... а'„суть перестановки множества (1,2,...>и), то обозначим их произведение лл' как а'„а'„... а',„. Пусть )пг(л) обозначает количество инверсий, как й в упр. 25 Покажите, что шг(лл') < пш(л) + !пг(л') и что равенство соблюдается тогда и только тогда, когда л.)г' расположено "ниже" л' (как введено в упр.
12). аб.1.2. Перестановки мультимножествв До сих пор мы рассматривали перестановки мназ)сесглаа элементов, но это частный случай перестановок ждльглимнозкестеа, (Мультимножество — это то же самое, что н множество, но в нем могут содержаться одинаковые элементы. Некоторые основные свойства мультимножеств обсуждались в разделе 4.б.3 — 19.) Рассмотрим, например, мультимножество М = (а, а, а, Ь, Ь, с, )Г, г(, )(, )Г), в котором содержится 3 элемента а, 2 элемента 6, 1 элемент с и 4 элемента г(.
Повторения элементов в мультимножестве можно записать и другим способом: (2) М = (3 а, 2 Ь, с, 4 с(). Перестановка мультимножества* М вЂ”. это некоторое расположение его элементов в ряд, например с а !з с! Н а Ь с! а г!. С другой стороны, такую последовательность можно назвать буквенной строкой, содержащей 3 буквы а, 2 буквы Ь, 1 букву с и 4 буквы с1.
Сколько существует перестановок мультимножества М7 Если бы мы рассматривали все элементы М как различные, обозначив их как аы аз, аз, Ьы Ьз, сг, 4, Ыз, г!з, г!4, то получили бы 10! = 3,628,800 перестановок, но после отбрасывания индексов многие из них оказались бы одинаковыми. Фактически каждая перестановка М встретилась бы ровно 3! 2! 1! 4! = 288 раз, поскольку в лн>бой из них индексы при буквах аь можно расставить 3! способами, при Ьл (независимо) -. 2! способами, прн сь — одним способом, при — 4! способами соответственно. Поэтому число перестановок М равно 10! , = 12,600. В применении к общему слу чаю те же рассуждения показывают, что число переста- новок любого мультнмножестна равно полиномиальному коэффициенту (, „)=,, п ') и! ггыпг,...l п1!пзЕ.. (3) где п| — число элементов первого типа, пз — число элементов второго типа и т.
д., а и = гц + пз + — общее число элементов. Количество перестановок множества было известно еще н древние времена. В древнееврейской Книге Творения (ок. 100 г. н. э.), наиболее раннем литературном произведении иудейского философского мистицизма, даны верные значения первых семи факториэлов, после чего говорится: "Продолжай, и получишь чигла, которые уста не могут произнести, а ухо не может воспринять". [Сефер Этзирах, конец части 4. См. Бо!опюп СапЖ, асио!!ез !и ~ебген' Аз!гопозпу апс! Млййетабсв (Хеи' Уог!с; Кгае, 1970), 494 — 496„АгуеЬ Кар!ап, Берег Уегьйгай (Уогй ВеасЬ., Маше: Бапшс! %е!зег, 1993).) Это первый известный в истории подсчет числа перестановок. Второй встречается в индийском классическом произведении Ануйогадварл-сучрл (ок.
500 г. н. э.), правило 97, в котором приводится формула числа перестановок шести элементов. которые не расположены ни в порядке возрастания, нн в порядке убывания: бх5х4х3х2х1 — 2, [См. С, СЬайгаъагг!, Вп!!. Са!спыа Ма1Ь. Яос. 24 (1932), 79-88. лАнуйогадварасутра" одна нз книг канонов джайнизма, религиозной секты, распространенной в Индии.) Соответствующее правило для мультимножеств впервые, по-видимому, встречается в книге лЛилаватп", написанной Бхаскарой Ахарьей (ок.
1150 г.) (равд. 270 †2). У Бхаскары это правило сформулировано весьма сжато и проиллюстрировано лишь двумя простыми прнлгерами: (2, 2, 1, Ц и (4,8,5, 5, 5). В результате н английском переводе это правило не сформулировано корректно, впрочем, имеются некоторые сомнения относительно того, понимал ли сам Бхаскара, о чем говорил. * В англоязычной литературе текле нерестаноекн иногда называют "репнкгосюо" е отличие от 'репннгас1он". Вслед за этим правилол» Бхаскара приводит интересную ч>ормулу (4+ 8+ 5+ 5 -»- 5) х 120 х 11111 с па а 6 Ь сдддд! саЬдс!аЬдад) (4) Здесь верхняя строка содержит элементы М в поря,<ке неубывания и нижняя это сама перестановка. Соедини»пельиое произведение <зтд двух перестановок мультимножеств о н !3 — это перестанонка, которая получается, если (а) взять двух- строчные обозначения для о и <3, (Ь) записать соответствующие строки в одну и (с) рассортировать столбцы так, чтобы элементы верхней строки расположились в порядке неубывания.
Сортировка должна быть устойчивой в том смыл че. что взаимное расположение элементов нижней строки сохраняется, если соответствующие элементы верхней строки равны, Например, с а с! а Ь т Ь д д а д = со 6 д д а Ь с! а д, так как а а Ь с д а Ь д д д а а а Ь Ь с д с! д с! Нетрудно видеть. что операция саед»лнительного произведения ассоциативна, т. е. (отд) т т = <зт(дт т) для суммы 20 чисел 48555 ч- 45855+ .. Верное правило для нахождения числа перестановок в случае, когда только один элемент может повторяться, найдено независимо немецким ученым иезуитом Лтанасиусом Кирхером (Л<Ьапазшэ К<гсЬег) в его миоготол<нол» труде о музыке (Мизигй!а Етпл егэа!!э 2 (Ноше: 1650), 5 — 7]. Кирхера интересовал вопрос о количестве мелодий, которые можно создать из данного набора нот; для этого он придумал то, что называл "музарифметикой'. На стр. 18 — 21 сво<шо труда он дает верное зна <ение числа перестановок мультимножестна (сп С, и.
1>) при нескольких значениях та и и, хотя описал он свой метод вычислений лишь для случая и = 1. Общее правило (3) появилось позже н книге Жана Престэ (Л. Ргезсес) В!етепэ де Масбешас!9иез (Раг!»и 1675. 351- 352), в которой с<держится одно из первых изложений комбииаторной математики, написанных в Западной Европе. Престз верно сформулировал правило для произвольного мультимножества, но проиллюстрировал его лишь простым примером (а, а, 6, Ь, с, с). Он особо отметил, что деление на сумму факторналон, которое он считал естественным обобщением правила Кирхера, было бы ошибкой.
Несколько лет спустя Джон Валлис (3ойп Ъа111з) в своей книге В<ьсоигэе оу Соп>Ь>паНопэ (Ох!огс1: 1685, СЬарсег 2), опубликованной вместе с <шо же Тгеа<!зе оЕ А!8ебга, рассмотрел зто правило более подробно. В 1965 году Доминик Фиата (!Зош1п19ие Ровса) ввел одно интересное понятие, так называемое "соединительное произведение' (!псе»се!аВоп р»одпсс), которое поэзо>шло распространить многие известные результаты, касающиеся обычных перестановок, ца обп,ий случай персстанопок мульшышо кества. [Сз».
Рибб !пэс, Я<а<<э< !9ие, 1!шч. Раг<э, 14 (1965), 81-241: а также .Гессиге <»осев ш Мас!>. 85 (Ярг!»>8ег, 1969).) Предполагая, что элементы мультимпожества каким-то способом линейно упорядочены, можш> рассмотреть доихстрочную но>нации>, например и что она подчиняется законам сокращения влечет за собой влечет эа собой кто=кто от т = Фттг Существует "единичный элемент" (7) (8) ггте=ето=о, где е — нуль-перестановка, 'расположение в ряд" элементов пустого множества. Закон коммутативности, вообще говоря, не выполняется (см.
упр, 2), тем не менее о т гт = Д т о, если о и р не содержат общих букв. (9) Аналогичным способом понятие цикла можно распространить на случай, когда элементы могут повторяться. Будем записывать в виде (хг хв ... хк) (10) перестановку, двухстрочное представление которой получается путем устойчивой сортировки столбцов ~хг хэ ... х„) по верхним элементам. Например, 1' г1 Ь д д а с а а 6 гг''1 )'а а а 6 6 с г( г( гг' гг''1 'т 6 г1 г1 а с а а 6 гг гг/ (, с а Ь г1 гг а 6 д а гт ) г а а гг 6 Ь 6 Ь гг с с гг' г1 д г) г1') гг' Ь с Ь с а с гг' а г1 г1 Ь Ь 6 г1) ' (12) Если можно записать я в виде о т Д, где о содержит, по крайней мере, одну букву а, то крайнее слева а в верхней строке двухстрочного представления о должно так что перестановка (4) фактически является циклом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
