Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 13
Текст из файла (страница 13)
Например, нз перестановки 31245 можно получить шесть перестановок 631245, 361245, 316245, 312645, 312465, 312456. Все эти перестановки, кроме второй и последней, содержат по две нисходящие серии вместо одной исходной. Отсюда имеем рекуррентное соотношение Таблица 1 ЧИСЛА ЭЙЛЕРА 8 1 247 4293 9 1 502 14608 ( )=1. ( ) =О, гдеи>1. Соотношение (6) следует из (5) вследствие свойства симметрии ( )=( ), гдеи>1, (7) которое вытекает из того факта, что каждая непустая перестановка аг ат ... а„, содержащая !г нисходящих серий, имеет н и — 1 — 8 восходящих серий. Другое важное свойство чисел Эйлера выражается формулой которая была впервые выведена китайским математиком Ли Шан-Ланом и опубликована в 1867 году.
[См. З.-С. Матса!о((, А Н!аготу ог" СЬ!пезе Майегпаг!са (Вег!!и: Ярг1пбег, 1997, 346-348); особый случай, если и < 5, был независимо рассмотрен японским математиком Йошнсуке бг!ацунага (б!асвппаба Уо)г!вп!ге), который умер в 1744 году.) Тождество Ли Шан-Лана следует из свойств операции сортировки. Рассмотрим гп" последовательностей аг ат...
а„, где 1 < а; < пг. Любую такую последовательность можно устойчиво рассортировать в порядке неубывания и получить: а;, <а;,«.. а;„, где !г гз... 1„— однозначно определенная перестановка множества (1, 2,..., и), такая, что гу < !уе,, если аа = а;„,; другими словами, нз гу > (у~г следует аа < аа, Покажем, что если в перестановке гЧ !з...(„ содержится (г серий, то число соответствующих ей последовательностей аг ат...
аи равно ('х+~ ); тем с»- мым будет доказана формула (6), если залгенить й значением и- !г и воспользоваться (7), поскольку (") перестановок имеют т~ — 5 серий. Пусть, например, и = 9, г1 1з, .. г„= 3 5 7 1 66 94 2 н требуется подсчитать число последовательностей аг ат... а„, таких, что 1 < аз < аз < ат < аг < ае < аа < ав < а4 < ат < ги. о о о а о 1 4 1 1 11 П 1 26 66 1 57 302 1 120 1191 о о о о о о о о о 26 1 302 57 г416 и 91 15619 15619 88234 156190 а о о о о о о а о о о о 1 а 120 4293 247 88234 14608 о а о о о о о о о а о о о о о о о 5аг Средняя длина первой серии равна„таким образом, Р! + 2рз+ + прп = (!Х! — И) + 2(йз — Дз) + ' '+ (и — 1)йи-! — Чн)+ гйз 1 1 1 = Ч! + Ф + + !1„= — + — + ° ° + — .
ы 1! 2! (22) Предел при и -+ оо равен е — 1 = 1.71826..., а для конечных и это значение равно е — 1 — Б„, где 4, довольно мало (для бозьших и. — Прим. ред,): 1 ( 1 1 е — 1 б„= 1+ + + ~< (и+1)! ~ и+2 (и+2)(в+3) Х (и+1)'. Поэтому лля практических печей удобно рассмотреть серии случайной бесконечной последовательности различных чисел и!, пз, аз ~ ° ° ° ! под "случайностью"' последовательности здесь подразумевается то, что все и! возможных взаимных расположений первых и элементов последовательности равновероятны (при любом и. — Прим.
ред.). Так что средняя длина первой серии случайной бесконечной последовательности в точности равна е — 1. Носко!!ько усовершенствовав этот метод, можно установить средшою длину к-й серии случайной последовательности. Пусть !1з — вероятность того, что общая длина первых й серий > ш: тогда !1з равно величине 1/т!., умноженной на число перестановок множества (1, 2,..., т), которые содержат не более й серий: (23) Вероятность того, что общая длина первых й серий равна т. есть ез„, — ймз,ец. Следовательно, обоз!, !чин через Хз среднюю длину А-й серии, находим, что Х ! + - + Х ь = средняя общая длина первых й серий = (!1з! — дзз) + 2(!1ш — 2зз) + 3(!Хзз — ~!зз) + " = !Хз! + !1зз + Фз + " ..
Вычитая Х ! + "° + Х з ! и используя значения !1ьм, из (23) поаучаем нужную нам формулу: 1( 1 ) 1( 2 ) 1( 3 ) ~~- ( т ) 1 тй! Доскольку (з~!) = О, кроме случая й = 1, значение Х з оказывается равным коэффициегггу при зз ' в производящей функции д(з,1) — 1 (см. (19)); таким образом, имеем Х(з) = ~~! Хаз „вЂ” 3. з з(1 — з) (25) з>е Таблица 2 СРЕДНЯЯ ДЛИНА й-И СЕРИИ Ь» полагая е = л + еу. На рис, 3, на котором нанесены оба графика этих уравнений, ВВДнО, что они пересеиаютси В точках е = ео, г1, 2м ет,32,..., ГДВ ер = 11 ат = (3.03364 30156 13044-) + (7.46143 92856 54255-) е, (23) и при больших (с мнимая часть О(еа„.~) равна приблизительно 3( а) + 2и.
е*"' е1ву=а е' 'соелюж --"--- Рис, 3. Корни уравнении е' ' = е. 1.71828 18284 59045+ 1,95249 24420 12560- 1.99579 13690 84285- 2.0аааз 885О4 76806- 2.00005 75785 89710+ 2.00000 50727 55710- 1.99999 96401 44022+ 1. 99999 98889 04744+ 1,99999 99948 43434- 1О 11 12 13 11 15 16 17 18 2.00000 00012 05997+ 2.00000 аооа1 93672+ 1.99999 99999 99909+ 1,99999 99999 97022- 1.99999 99999 99719+ 2.00000 ООООО ооаро+ 2.ааааа ааааа аоооа+ 2.00000 00000 00000+ 2.ааааа ааааа оаоао- 1 — э 1пп (, ~(х — х») = -1 при я > 0 и этот предел равен -2 при х = О, функция В(х)=7.(х)+ + + + + + + "+ — г — г~ г — х» х еэ х йэ хиба х йт не имеет особых точек па комплексной плоскости при ф < ~х +~(. Значит, 71 (г) можно разложить в степенной ряд 2» р»х, который сходится абсолютно при ф < ~х +»~; отсюда следует, что р»М» -» О при й -» оо, где М = )э~э~~ — е.
Коэффициентами для 7,(х) служат коэффициенты разложения функции 2 1 1 1 1 + + + + + +11 (х), 1 — х 1 — 3/х~ 1 — х/х~ 1 — з/х 1 — х/х,„ а именно Е„ж 2 + 2г, "соэ пй~ + 2гэ " гоэ пдэ + ° + 2г " соэ пд,ч + 0(г ~~»), (29) если положить х» = г»е ". Иь (30) Отсюда можно проследить асимптотическое поведение Е„. Имеем д~ = 1.17830 39784 74668+; йэ = 1.31268 53883 87636+; йэ = 1.37427 90757 91688-' 9» = 1.41049 72786 51865-; г» = 8.07556 64528 89526-, гэ — — 14.35456 68997 62106-, гэ = 20 62073 15381 80628- г» = 26.88795 29424 54546-, (31) таким образом, главный вклад в 7„— 2 дают г~ и дм а ряд (29) сходится очень быстро. Дальнейший анализ [Ж.
%. Ноокег, САСМ 12 (1969), 411-413] показывает, что В„,(х) -Ф -х пРи гп -» оо; следовательно, Рвд 22„»>э г» сов яд» действительно сходншсл к Ь„при и > 1. Можно провести более тщательный анализ и полностью определить распределение вероятностей для длины Й-й серии и для общей длины первых Й серий (см.
упр. 9-11). Сказывается, сумма Ео + . + Е» асимптотически приближается к 25 - 1+ О(8-»). В заключение этого раздела рассмотрим свойства серий в случае, когда в перестановке допускаются одинаковые элементы. Бесчисленные пасьянсы, которым посвящал свой досуг знаменитый американский астроном 19 в. Саймон Ньюкомб (Вппоп ХенсошЬ), имеют непосредственное отношение к интересующему нас вопросу. Он брал колоду карт н складывал их в одну стопку до тех пор, пока они шли в порядке неубывания по старшинству; как только следующая карта оказывалась младше предыдущей, он начинал новую стопку.
Он хотел найти такую вероятность, при которой вся колода окажется разложенной на заданное количество стопок. Задача Саймона Ньюкомба состоит, следовательно, в нахождении распределения вероятностей для серий случайной перестановки мультимножества. В общем случае ответ довольно сложен (см. упр. 12), хотя мы уже видели, как решать задачу в частном случае, когда все карты различны по старшинству, Мы удовлетворимся здесь выводом формулы для среднего числа стопок в этом пасьянсе. Пусть имеется т различных типов карт и каждая встречается ровно р раз. Например, в обычной колсще для бриджа т = 13, а р = 4, если пренебрегать различием масти.
Замечательную симметрию обнаружил в этом случае П. А. МакМагон [см, Сош!лпагогу Апа!уз!я 1 (СашЬг!с1яе, 1915, 212-213)): число перестаиовок с Й+ 1 сериями равно чвслу перестановок с гпр - р - /с+ 1 сериями. Это соотношение легко проверить при р = 1 (формула (7)), однако при р > 1 оио кажется довольно неожиданным. Можно доказать свойство симметрии, устаиовив взаимно однозначное соответствие между перестановками, такое, что каждой перестановке с й + 1 сериями соответствует перестановка с тр — р — й + 1 сериями. Мы настойчиво рекомендуем читателю постараться самостоятельно найти такое ссютветсхвие, прежде чем двигаться далыпе. Какое-нибудь очеиь простое соответствие иа ум ие приходит; доказательство Мак-Магона основано иа производящих функциях„а не иа комбииаторном построении, Однако установленное Фоатой соответствие (теорема 5.1.2В) позволяет упростить задачу, так как в нем утверждается существование взаимно однозначного соответствия между перестановками с 1+1 сериями и перестановками, в двухстрочном представлении которых содержится ровно й столбцов "„таких, что х < р.
Пусть дано мультимножество (р. 1, р 2,..., р. т). Рассмотрим перестановку в двухстрочном представлении 1 ... 1 2 ... 2 ... ш ... т лы ... х~р жш .. хгг .. х ь~ .. х г / (32) Сопоставим с ней другую перестаиовку того же мультимиожества: где х' = т + 1 — х. Если перестановка (32) содержит й столбцов вида "„таких, что х < д, то (33) содержит (гл — 1)р — й таких столбцов, потому что необходимо рассмотреть лишь случай й > 1, а неравенство х < у эквивалеитио х' > т + 2 — у.
Поскольку (32) соответствует перестановке с й+ 1 сериями, а (33) — перестановке с тр — р — й + 1 сериями и преобразование, переводящее (32) в (33), обратимо (оно же переводит (33) и (32)), то тем самым доказано условие симметрии Мак-Магона. Пример этого построения содержится в упр. 14. В силу свойства симметрии среднее число серий в случайной перестановке должно равняться .-', ((к+1)+(тр-р-.5+1)) = 1+1р(т — 1). Например, дня стандартной колоды среднее число стопок в пасьянсе Ньюкомба равно 25 (так что раскладывание этого пасьянса вряд ли покажется столь уж увлекательным занятием). На самом деле после несложных рассуждений можно определить среднее число серий в общем случае для любого данного мультимножества (п~ -хы пт хт,..., пья .
х„,), где все хь различны. Пусть и = п~ + пт + ° + и и все перестановки а~ аз... а„этого мультимиожества выписаны в явном виде. Посмотрим, как часто а; оказывается больше аьы при каждом фиксироваииом значении 1, 1 < 1 < и. Число ыучаев, когда а, > а,ч.ы равно в точности половине числа случаев, когда а; ф а,ч.м и нетрудно видеть, что а; =- аьы — — х ровно в Хц (и — 1)/ц(п — 1) случаях, где Х вЂ” общее число перестановок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
