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