AOP_Tom3 (1021738), страница 29
Текст из файла (страница 29)
В общем случае ответ довольно сложен (см. упр. 12), хотя мы уже видели, как решать задачу в частном случае, когда все карты различны по старпзинству. Мы удовлетворимся здесь выводом формулы для среднего числа стопок в этом пасьянсе. Пусть имеется т различных тнпон карт и каждая встречается ровно р раз. Например, в обычной колоде для бриджа пг = 13, а р = 4, если пренебрегать различием масти. Замечательную симметрию обнаружил в атом случае П.
Л. МакМагон (см. Согггб!насосу Апа)увез 1 (СашЬг!г)ке, 1913., 212-213)): число перестановок с 1+1 сериями равно числу перестановок с тр — р — 1+ 1 сериями. Это гоотношение легко проверить прп р = 1 (формула (7)), однако при р > 1 оно кажется довольно неожиданным. Можно доказать свойство симметрии, установив взаимно однозначное соответствие между перестановками. такое, что каждой перестановке с А. + 1 сериями соответствует перестановка с тр — р — Й+ 1 сериями. Мы настойчиво рекомендуем читателю постараться самостоятельно найти такое соответствие, прежде чем двигаться дальше.
Какое-нибудь очень простое соответствие на ум не приходит; доказательство Мак-Магона основано на производящих функциях, а не на комбинаториом построении. Однако установленное Фоатой соответствие (теорема 5.1.2В) позволяет упростить задачу, так как в нем утверждается существование взаимно однозначного соответствия между перестановками с 1+ 1 сериями и перестановками, в двухстрочном представлении которых содержится ровно к столбцов ,", таких, что х < у. Пусть дано мультимножество (р 1, р.
2,, р. т), Рассмотрим перестановку в двухстрочном прсдстаплении с 1 ... 1 2 ... 2 ... т ... т хг~ ... хгр хгг ... хгр ... хрн ... х,„р ) (32) Сопоставим с ней другую перестановку того же мультимножества; с 1 ... 1 2 ... 2 ... т .. т ) Ф 1 х1! ... хг .'г г ... уыр ''' хгг ... хгр / (33) где х' = п1 + 1 — х. Если перестановка (32) содержит й столбцов вида ,", таких, что х < у, то (33) содержит (т — 1)р — й таких столбцов. потому что необходимо рассмотреть лишь случай у > 1, а неравенство х < у зквивалентно х' > т+ 2 — у. Поскольку (32) соответствует перестановке с )г+ 1 сериями, а (33) ." перестановке с тпр — р — й + 1 сериями и преобразование, переводящее (32) в (33), обратимо (оно же переводит (33) в (32)), то тем самым доказано условие симметрии Мак-Магона.
Пример зтого построения содержится в упр. 14. В силу свойства симметрии среднее число серий в случайной перестановке должно равняться —.', ((1+1)+(пгр — р —.1+1)) = 1+ -'р(га — 1). Например, для стандартной колоды среднее число стопок в пасьянсе Ньюкомба равно 25 (так что раскладывание зтого пасьянса вряд ли покажется столь уж увлекательным занятием). На самом деле после нег южных рассуждений можно определить среднее чигло серий в общем случае для любого данного мультимножегтва (п1 хы пг хг; пы ' хр,), где все хь различны. Пусть и = п1 + пг + .
+ и и все перестановки а~ аг... а„этого мультимножества выписаны в явном виде. Посмотрим, как часто а, оказывается болыпе ары при каждом фиксированном значении г, 1 < г < гь Число случаев, когда а, > о; ы, равно в точности половине числа случаев, когда а, Ф а,рм и нетрудно видеть, что а, = а;+г = х. ровно в Хп (и — 1)/п(п — 1) случаях, где Ю вЂ” общее число перестановок. Следовательно, а, = аьы ровно в ?У г г (пг(пг 1) + ' ' '+ п~л(пат 1)) = (п~ + ' ' '+ пм и) п(п — 1) п(п — 1) случаях, а а, > а,+г в у (пг — (пг~ + + пг )) случаях.
Суммируя по г'и прибавляя Ю, потому что в каждой перестановке одна серия заканчивается элементом ав, получим обнгее число серий во всех Л перестановках: Ю(- — — (и +" +и )+1). ,уп 1 12 2п (34) Выполнив деление на Т, получим искомое среднее чигшо серий. Поскольку серии играют весьма важную роль в изучении "порядковых статиг.- тик", имеется весьма обширный список работ, посвященных этой томе, включая некоторые пшы серий, не рассмотренные здесь. Дополнительнувх информацию можно найти в книге Г.
Х ВатЫ, П. В, Вагсоп, Сошб)пасопа1 СЬапсе (1.опбоп; Сп())п 1962, гл. 10) и в обзорной статье С. 1.. Ма11ожз, Аппа)з оу Ма?)г. 91абзг)сз 36 (1965), 236-260. УПРАЖНЕНИЯ 1. (М26) Выведите Формулу Эйлера (13). 2. (М22] (а) Попытайтесь развить идею, использованную в тексте при доказательстве тождества (8). Рассмотрите последовательности а1аз... а, содержащие ровно 4 различных элементов, и докажите, чта (Ь) Используя эта тождество, докажите, чта ( )( ) =( )(и — гп)! прин>га. 3.
(НМ23) Вычислите сумму 2 („")( — 1)" 4. (М21) Чему равна сумма 2" ( — 1) ("„) М (",~)? 5. (М20) Найдите значение ("„') 1падр, егти р — простое чишю. 8. (М21) Мистер Палл заметил, чта из формул (4) и (13) можно получить 7. (НМ40) Является ли распределение вероятностей для серий, задаваемое формулой (14), асимптатичгски нормальным? (Ср. с упр.
1.2.10 — 13.) 8. [М24) (П. А. 13ак-Магон.) Покажите, чта вероятность тата, чта длина первой серии достаточно длинной перестановки есть ?ы длина второй есть ?г,..., а длина?г-й серии > 1в равна Он обнаружил, чта ~ьэа(-1)е '(",~') = О при всех у > О, выполнив суммирование сначала па й, а затем па у > О; отсюда и! = 0 при любом и > О. Не допустил ли ан какой-нибудь ошибки? Ц1П 1/(1ю + Ь)! 1/(Н + Н +1з)! ... Ц(11 -~-(э + 1э ~-. +(ь)! 1/(1э+(э).... 1/(Н+Н+ +1). 8,1 О 1 1/)з' .. 1/(1з + + Эь)' 1/(ь! О О 9.
]МЯ0] Пусть йь(з) = 3 рь я, где рь — вероятность того, что общая длина первых 5 серий случайной последовательности (бесконечной) равна гп. Найдите "простые" выРажениЯ длв 61(э), Аэ(х) и длв пРоизводащей фУнкции Ь(л,х) = 2„ьЭЫ(Я)х двУх переменных. 10. (НМЗО] Определите асимптотическое поведение математического ожидания и дисперсии распределения Аь(е) из предыдущего упражнения при болыпих 1ь 11.
(М40] Пусть Нь(э) = 2" Рэ з, где Рь,„— вероятность того, что длина й-й серии в случайной (бесконечной) последовательности равна пь Выразите Н1(з), Нэ(з) и производящую функцию Н(цх) = 2 ь Нь(л)х" от двух переменных через известные функции. 12. (МЭЮ] (П А. Мак-Магон.) Обобщите формулу (13) на случай перестановок мульти- множества, доказав, что число перестановок мультимножества (пз К пэ .
2,..., пп . пг), имеющих ровно я серий, равно +1) (, — 1+Эг — /) ( — 1+5 — «) ~п — 1+5 — /) э=о где и и! +пэ г +и 13. [05] Каким будет среднее число стопок в пасьянсе Ньюкомба, если пользоваться обычной колодой для бриджа (из 52 карт), игнорируя старшинство карт, но считая, что трефы < бубны < черви < пики'! 14. (М10! Перестановка 3111231423342244 содержит 5 серий; найдите соответствующую перестановку с 9-ю сериями с помощью построения для условия симметрии МакМагона, приведенного в тексте раздела ь 15.
]М81] (Неремеэюающиесл серии.) В классической литературе 19 в. по комбинаторпому анализу рассматриваемый нами вопрос о сериях в перестановках не изучался, но некоторые авторы изучали попеременно восходящие и нисходящие серии. Так, считалось, что перестановка 53247618 содержит 4 серии: 532, 247, 7б1 и 18. (Первая серия будет восходящей илн нисходящей в зависимости от того, а1 < лэ или а1 > ам таким образом, перестановки а|аэ...а„, а ...аэа1 и (и+ 1 — а~)(п + 1 — аг) .. (и+ 1 — и ) содержат одинаковое число перемежающихся серий.) Максималыюе число серий этого типа в перестановке и элементов равна и — 1.
Найдите среднее число перемежающихся серий в случайной перестановке множества (1, 2,..., и). ]Указание. Разберите вывод формулы (34).] 16. (МУ0] Продолжим предыдущее упражнение. Пусть ],"] — число перестановок множества (1, 2,..., и), которые имеют ровно Эс перемежающихся серий Найдите рекуррентное соотношение, с помощью которого можно вычислить таблицу значений ]„"]; найдите также соответствующее рекуррентное соотношение,тля производящей функции С (е) = ~ь] ~ ]еь/и!, ИспользУЯ это послеДнее соотношение, найДите пРостУю фоРмУлУ Длл диспе1ь спп числа перемежающихся серий в глучайной перестановке множества (1, 2,..., и). 17. ]М05] Существует всего 2" погледовательностей а~ аэ...
а . где каждый элемент аэ— либо О, либо 1. Сколько среди них последовательностей, содержащих ровно /с серий (т. е. содержащих ровна Эс — 1 элементов а,, таких, что а„> агы)? 18. (М88) Существует всего и! последовательностей Ь| Ьг.
Ь», в которых каждый элемент Ьэ — целое число, лежащее в диапазоне 0 < Ьз < и — 1. Сколько среди них последовательностей, содержащих (а) ровно й нисходящих серий (т. е. содержаших ровно й соотношений элементов, таких, что Ь» Ьг ш) и (Ъ) ровно Ь отличающихся элементов? Рис. 4. Неатакующие ладьи на шахматной доске при заданном числе?г = 3 падей ниже главной диагонали. ь 19. (Мйб) (Дж. Риордан (3. Вюгйап).) (а) Сколькими способами можно расположить н неатакующих падей (т. е, никакие две ладьи не должны находиться иа одной вертикали или горизонтали) на шахматной доске размером п х и так, чтобы ровно?г из них находились на заданной стороне от главной диагонали? (Ъ) Сколькими способами можно расположить й неатакующих падей иа заданной стороне от главной диагонали шахматной доски размером п х и? Например, на рис.
4 показан один из 1о 619 способов расположения восьми неатакующих падей на обычной шахматной доске с тремя ладьями на незаштрихованном участке ниже главной диагонали, а также один из 1 050 способов расположения трех неатакующих ледей на треугольной доске. » 20. (М81] Говорят, что перестановка требует /с чтений, если ее нужно просмотреть й рвз слева направо, чтобы прочитать все элементы в порядке неубывания. Например, перестановка 491825367 требует четырех чтений: при первом чтении получаем 1, 2, 3, при втором — 4, 5, 6, 7; затем — 8 и 9. Найдите связь между сериями и чтениями.
21. [М22) Если перестановка а~ аэ... а множества (1, 2,..., и) содержит /с серий и требует 1 чтений е соответствии с упр. 20, то что можно сказать о перес гановке а„... аэ а~? 22. (М86) (Л. Карлиц, Д. П. Розель и Р. А. Скоувилл.) Покажите, что не существует перестшювки множества (1, 2,..., и) с и+ 1 — г сериями, требующей в чтений, если гв < и; однако такая перестановка существует, если и ) и+ 1 — г ) з ) 1, «в ) и 23. (1тМ48) (Вальтер Вейссблюм (1Ча!Сег ЖейэЫпш).) "Удлиненные серии" перестановки а~ аэ... а» получаются, если вставлять вертикальные черточки в тех местах, где нарушается установившаяся монотанностгб удлиненные серии бывают как возрастающими, так и убывающими в зависимости от того, в каком порядке расположены первые два элемента, так что длина каждой удлиненной серии (кроме, возможно, последней) ) 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
