AOP_Tom3 (1021738), страница 22
Текст из файла (страница 22)
14) показывают, что на самом деле справедливы формулы Е„(2)=( ) — 1, = Г ) - (:) е-()=Г 2) — Г 1) ") =Г~')-Г~')" п>2; п>3; п>4; п > 5. Общая формула для Е„(/с) содержит около 1.6ъ'к слагаемых: сс+й-2 п+Ес-3 и+1с-6 п+й-8 и+1с — и — 1 п+/с — и, — с — 1 где и„= (31~ — Е)/2 — так называемое "пентагональное число'! Разделив С„(х) на и1, получим производящую функцию д„(э) распределения вероятностей числа инверсий в случайной перестановке п элементов. Она равна произведению Дп(э) = пс(с)ссэ(э) ...сси(э)~ где!О.(а) = (1+ г + + а ' ')/Й вЂ” производюцая функция равномерного распределения случайной величины, принимавшей целые неотрицательные значения, меныцие й. Отсюда* шеап(д„) = пгеап(йг) + шеап(пп) + .
+ 1 О г — + .+ 2 тат(д„) = тат(51) + тат(Аз) + + шеап(а„) и — 1 п(п — 1) 2 4 наг(йн) пз — 1 п(2п+ 5)(п — 1) (12) 1 О + — + + 4 (13) 12 Таким образом, среднее число инверсий довольно велико — около -'пз; стандартное отклонение также весьма велико -- около -'пзбг. В качестве интересного завершения данной темы рассмотрим одно замечательное открытие. принадлежащее П. А. Мак-Мвгону (Р. А. МасМа)юп) [Агпег. Х Мабг. 35 (1913), 281 — 322).
Определим индекс перестановки п1 пе... оп как сумму всех ~. таких, что ау ) пзьм 1 < З < и. Например, индекс перестановки 59182 64 73 равен 2+4+6+8 = 20. Индекс случайно совпал с числом инверсий. Если составить список всех приведенных ниже 24 перестановок множества (1,'2,3,4), то получится, что число перестановок, пмеющп»данный пндекс lс, равно шглу перестановок, ггггеющпх Й инверсий. Количестно Перестановка Индекс инверсий Количество Перестановка Индекс инверсий 2 3 3 4 О 3 2 3 2 5 О 1 1 2 2 3 4 3 4 2 5 3 4 4 5 6 1 4 2 3 2 5 1 4 3 3 6 Нн первый взгляд, гтот факт может показаться почти очевидным, однало после некоторых размышлений он начинает квзатьгя чуть ли не мистическим, и не видно никакого простого прямого его доказательства, Мак-Магон нашел следующее остроумное косвенное доказательство.
Пусть )пс)(ог пг...и„) —. индекс перестановки а1 от... п„и соответствугощая произнодящая функция есть Н (а) г~, Ыща1 аг, а, ) (14) Здесь и дачее шеап(й) означает среднее значение случайной величины д, а гас(й) — диспеРсию вен~чины а - Пщг.». нерее. 1234 124)3 1 3)2 4 1 3 4(2 1 4(2 3 1 4(3~2 2(1 3 4 2)1 4(3 2 3~1 4 2 3 4)1 2 4)1 3 2 4)3~1 3)1 2 4 3)1 4)2 3)2)1 4 3)2 4)1 3 4)1 2 3 4~2~1 4)1 2 3 4~1 3!2 4)2)1 3 4(2 3~1 4)3~1 2 4~3)2)1 где сулсма в (14) берется по всем перестановкам множества (1, 2,..., и). Требуется доказать, что Н„(г) = 0„(г). Для этого определим взаимно однозначное соответствие межДУ и-меРными стРоками (Ф,йг,...,Он) неотРицательных целых чисел, с одной стороны, и упорядоченными парами и-мерных строк ((а,, аг,..., а„), (ры рг,..., р„)), с другой стороны, где ас ат ., а„— суть перестановка множестна индексов (1, 2, и) н р, > р » . рн > О.
Это соответствие будет удовлетворять условию с?с +с?т+ '''+ Фс =!Исс(асад...ан) + (рл +рт+ '+р ). (15) Производящая функция 2 гд' дд+' +д", где сумма берется по всем и-мерным строкам неотрицательных целых чисел (Ом с?т,..., д„), равна б)„(г) = 1/(1 — г)"; а производящая функция 2 гд'+"'~ +"", где сумма берется по всем и-мерным строкам целых чисел (рм рт,, .., р„), таких, что рс > рт » . р„> О, раина (16) как показано в упр. 15.
Существование взаимно однозначного соответствия, которое удовлетворяет условию (15) н которое мьс собираемся установить, доказывает равенство 12„(г) = Нн(г)Р„( ), т. е. (17) Но с7„(г)/Р„(г) и есть С„(г), как следует из (8). Требуемое соответствие определяется с помощью простой процедуры сортировки. Любая и-мерная строка (Омдг,,, ..Оа) может быть устойчиво реорганизована в иоРЯдке невозРастаннЯ Д„, > йм» 4,„, гДе ас од...а„- — пеРестановка, такаЯ, что 4, = 4„,~, и поДРазУмевает а. < а,.
Установим (РмРг,...,Р„) (с?„,,4„,,...,с?,,) н затем для ! < с < и вычтем 1 из каждого р,, ..., р для таких 2, котоРые соответствУют а. > а ем По-пРежнемУ Рс > Р » Рсп поскольку р. обязательно превышает р д.м если только а > а дс. Полученная в результате пара ((ас, аю..., а„), (р„рт,...,рд)) удовлетворяет условию (15), поскольку суммарное улсеньшенпе элементов р равно плп(ал аг... а„). Например, если и = 9 н (4с,..., с?д) = (3,1,4. 1,5,9,2,6,5), то полтчилс ас...
ад = 685931724 и (рс ., рд) = (5, 2, '2, 2, 2, 2, 1, 1, 1). Несложно вернуться к (Ом42,...,4н), когда заданы а, а ., „и (, ) (см. упр. 17). Итак, желаемое соответствие установлено, теорема Мак-Магона об индексах доказана. Д. Фоата (12. Гаага) и М. П. Шуцснберже (М. Р. БсЬйггепЬегбег) отыскалн неожиданное расширение теоремы Мак-Магона через 65 лет после его первой публикации. Чисто ссерсстаповок и элементов, которые имеют Й ипверссис п индекс:1, равно чиглу перестановок, которые илсеют 1 инверсий и индекс й. Фактически Фоата и Шуценбсрже нашли простое однозначное соответствие между псрестановками первого н второго типов (см.
упр. 25). У П РА Ж Н Е Н И Я 1. (1О) Какова таблица инверсий лля перестановки 271845936? Какой перестановке соответ ствует таблица инверсий 5 О 1 2 1 2 О О? 2. [МЯ0] Классическая задача Иосифа формулируется следующим образом (см. также упр. 1.3.2-22): и рабов вначале стоят по кругу; после того как и|-го раба казнят, круг смыкается, затем опять казнят ш-го раба и так до тех пор, пока всех рабов не постигнет эта печальная участь Таким образом, порядок,в котором рабы подвергаютск наказанию, представляет собой перестановку множества (1, 2,...,п).
Например, если и = 8 и га = 4, порядок будет иметь вид 54б13872 (первым казнили 5-го раба и т. д.); таблица инверсий для этой перестановки имеет вид 3531 0010. Найдите простое рекуррентное соотношение для элементов 6| Ьл... Ь таблицы инверсий в общей задаче Иосифа для и рабов, если каждого пл-го раба казнят 3. [10] Пусть перестановке а| ол... а„соответствует таблица инверсий 6| Ьл... 6 . Какой перестановке о| ол...
а„соответствует таблица инверсий (и — 1 — Ьл)(п — 2 — Ьл) (О Ь„) т 4. [80] Придумайте пригодный для компьютерной реалнзацни алгоритм, который по данной таблице инверсий 6| Ьл... Ь, удовлетворяющей условиям (3), строил бы соответствующую перестановку а| ол... а„. [Указание. Всцомните методы работы со связями в памяти.] б. [05] Для выполнения алгоритма из упр.
4 на типичном компьютере потребуется время, приблизительно пропорциональное и+Ь|+ +Ь„, а это в среднем равно 6(п~). Можно ли создать алгоритм, порядок времени выполнения которого был бы существенно меньше, чем и'? О. [20] Придумайте алгоритм вычисления таблицы инверсий Ьлбл 6, соответствующей данной перестановке а| аз... а„ множества (1, 2,...,о), время работы которого на типичном компьютере было бы порядка и 1ой и 7.
[80] Помимо таблицы Ьл Ьл .. Ь, определенной в этом упражнении, можно определить некоторые типы таблиц инверсий. соответствующих данной перестановке а| аэ .,. а„множества (1, 2,..., п). В этом упражнении мы рассмотрим трн других типа таблиц инверсий, которые возникают в приложениях. Пусть с„ — число инверсий, переел компонента которых равна 1, т. е. число элементов, меныпих 1 и расположенных правее 11 [Перестановке (1) соответствует таблица 000142157; Ясно, что 0 < с| < 71] ПУ'сть Ву = Ьл ° и Сл с Покажите, что при 1 < 0 < и справедливы неравенства 0 < В, < у и 0 < Сл < и — 1; покажите также, что перестановку а| оз...
а„можно однозначно определить, если задана таблица с| сл .. с„или В| Вэ... В, илн С| Сэ... Суо 8. [ЛЩ] Сохраним обозначения, принятые в упр. 7. Пусть о| а', а'„— перестановка, обратная к а| а|... а, и пусть соответствующие ей таблицы инверсий — Ь', Ьз... Ь'„, с| сл...с'„, В[ В~э .. В„' и С[ С~... С„'. Найдите как можно больше интересных соотношений 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
