AOP_Tom3 (1021738), страница 28
Текст из файла (страница 28)
Другие свойства чисел Эйлера можно найти в обзорной статье Ь. Саг1Их, Масй. Майахте 33 !1959), 247-260. 1См. также работы Л. В1огг1ап, 1псгог!исс!оп со Сог~- Ьгпасопа! Апа!упв!в 1Хеч' Уог1с Чг!!еу, 1958, 38.-39), 214 — 219, 234-237е*; В. Ровса, М. Р. ЯсЬйгхепЬегйег, Ъесгиге Хасен гп Маг!г. 138 1Вег1ш: Врг1пйег, 1970).) Рассмотрим теперь длину серий; какова в среднем длина серии? В разделе 3.3.2 уже было проанализировано математическое ожидание числа серий данной длины; средняя длина серии равна примерно 2. Это согласуется с тем фактом, что в случайной перестановке длины и содержится около -'(и + 1) серий. Применительно к алгоритмам сортировки полезна несколько отличная точка зрения; рассмотрим длину !с-й слева серии перестановки при й = 1, 2, .... Какова, например, длина первой (крайней слева) серии случайной перестановки аг аз... ап? Ее длина всегда > 1; она > 2 ровно в половине случаев (а именно, если аг < аз). Ее длина > 3 ровно для 1/6 щгучаен сесли ас < аз < аз).
Вообще, ее длина > т с вероятностью д„, = 1/т! для 1 < т < п. Следовательно, вероятность того, что длина втой серии равна в точности гп, есть р = д — д +г — — 1/гп! — 1/1т+ 1)!, р„= 1/н! . где 1 < т < и; 121) * В оригинале — "ворег йспегаипй Гопсг!оп". — — Прим. нерее. Яе Имеется русский перевод: Риордан Дж. Введение в комоинаторный анализ. — Мп Изд-во иностр. лиг., 1963. — Прим. нерее.
Средняя задана первой серии равна, таким образом, Рз + 2рз + " "+ пр~ = (Чз — Чг) + 2(Чг — Чз) + + (и — 1)(Чп — з Чв) + пЧв 1 1 1 Ч!+Чз+'''+Чв + +'' + 1! 2! и! (22) Предел при и -э оо равен е — 1 = 1.7182В..., а для конечных и это значение равно е — 1 — бв, где б„довольно мало (для больших и. — — Прим, ред.): 1 ( 1 1 е — 1 + ( (и+ 1)! 1, и+ 2 (и+ 2)(а+3) / (и+ 1)! Поэтому для практических целей удобно рассмотреть серии случайнои бесконечной посзедовательности различных чисел а,,аз,аз под "случайностью" последовательности здесь подразумевается то, что все и! возможных взаимных расположений первых и элементов последовательности равновероятны (при любом и. — При,м ред.).
Так что средняя длина первой серии случайной бесконечной последовательности н точности равна е — 1. Несколько усовершенствовав этот метод, можно установить среднюю длину й-й серии случайной последовательности. Пусть Чь„, -- вероятность того, что общая длина первых Й серий > т; тогда Чь„, равно величине 1/га!, умноженной на число перестановок множества (1, 2,..., т), которые содержат не более й серий: (23) Вероятность того, что общая длина первых 1з серий равна пн есть Чь„, — Чь1„,т1р Следовательно, обз н,ачив через Еь среднюю длину /с-й серии, находим, что Ь| + ..
+ Ьь = средняя общая длина первых /с серий = (Чы — Чьг) + 2(йьг — Чьз) + 3(йаз — Чы) + = Чы + Чьг+ Чьз + Вычитая Ез + + Хь 1 и используя значения Чь„„из (23) получаем нужную нам формулу: !ь= — ( )-: — ( )+ —,( )+ = ~~' ( ™ ) —,. (24) н 31 Поскольку (,) = О, кроме случая 1г = 1, значение Лэ оказывается равным козфо фицненту прн з~ ~ в производящей функции д(з, 1) — 1 (см. (19)); таким образом, имеем 1,(з) = ~~ Ььз~ = (1 — ) (25) ь>а Из формулы Эйлера (13) получим представление Еь в виде полинома от е: ~ Е(- )ь- ('„"") ',™, ь Е(- )ь'Е(„"",)' —,+Е(- )" 'Е 1=-о ~>о ' э=а ~э>а 1)о — э ь-э а " ( 1)ь — э ь-о — г (й-у)). ~~';:, Ь ~'-:, (й-~'-~)! )о Е ( 1)ь-э'.о -1-1 е~.
()г — 1')! у=о >о (26) Эту формулу для Вь впервые получила Б. Дж. Гэсснер (В. Я. Саээпсг) [см. САСМ 10 (1967), 89 — 93). Имеем, в частности, Ь1 = е — 1 1.71828 .. Ег = гг 2е = 1 95249 Еэ = е — Зг ч- зе - 199579 е* 1 сосу = х и е* о)ну=у, (27) Итак, следует ожидать, что вторая серия будет длиннее первой, а третья серия будет в среднем еще длиннее! На первый взоляд, это может показаться странным, но после минутного размышления становится ясно. что, поскольку первый элемент второй серии будет, скорее всего. малым числом (именно зто служит причиной окончания первой серии), у второй серии болыпе шансов оказаться длиннее, чем у первой. Тенденция такова, что первый элемент третьей серии будет даже меньше. чем первый элемент второй серии.
Числа Еь важны в теории сортировки посредством выбора с замещением (раздел 5.4.1), поэтому интересно подробно проанализировать их значения. В табл. 2 приведены первые 18 значений Еь с точностью до 15 десятичных знаков. Рассуждения, приведенные в предыдущем абзаце, могут поначалу вызвать подозрение, что Еьэ.г > Ьгп на самом же деле значения колеблются, то возрастая, то убывая. Заметим, что Хь быстро приближаются к пределыюму значению 2. Весьма примечательно то, что эти нормированные полиномы от трангцендентного числа е так быстро сходятся к рациональному числу 2! 11олиномы (26) представляют некоторый интерес и с точки зрения численного анализа, поскссчьку являются прекрасным примером потери значащих цифр при вычитании почти равных чисел; используя арифметику с плавающей точкой и представление с точностью до 19 значащих разрядов, Гэсснер пришла к неверному заключению о том, что Его > 2, а Джон У.
Ренч (мл.) (Яо1п1 %. %гепсЬ,,1г.) отметил, что выполнение арифметических операций с точностью до 42 значащих разрядов дает значения Еоо с точностью только до 29 значащих цифр. Асимптотическое поведение Ьь можно определить, исходя из простых положений теории функций комплексного переменного. Знаменатель в (25) обращается в нуль лишь при е' ' = о, т. е.
когда Таблица 2 СРЕДНЯЯ ДЛИНЛ Ь-й СИРИИ ть 5 полагая в = х + 49, На рис. 3, на котором нанесены оба графика этих уравнений, видно, что они пересекаются в точках х = хе, х1,21, хт.,ув,..., где хе — — 1, х1 — — 13.08884 30156 13044 — ) + (7.46148 92856 54255 — ) е, (28) и при батьших к мнимая часть ет1хь+1) равна приблизительно й1хь) + 2я. 10 — 10 е* ~ вву=у— ее ~ сов уе я Рис. 3. Корни уравнения е' = к 1.71828 18284 1.95249 24420 1.99579 13690 2.00003 88504 2.00005 75785 2.00000 50727 1.99999 96401 1.99999 98889 1.99999 99948 59045+ 12560- 84285- 76806- 89716-Ь 55710- 44022+ 04744+ 43434— 10 11 12 13 14 15 1б 17 18 2.00000 00012 05997+ 2.00000 00001 93672+ 1.99999 99999 99909+ 1.99999 99999 97022- 1.99999 99999 99719+ 2.00000 00000 00019+ 2.00000 00000 00006+ 2.00000 00000 00000+ 2.00000 00000 00000- Так как ( 1 — г 1пп (, ~1(г — 21) = — 1 при й > 0 и этот предел равен — 2 при й = О, функция Л (г) = Б(2) + + + + + + + + го г 21 г 21 г 22 г 22 гпВ г хи~ не имеет особых точек на комплексной плоскости при ф < (г 4.1).
Значит, В„,(г) можно разложить в степенной ряд 2 ,'ь Ргг", КОтОрЫй Сходится абсолютно при ф < )г,„+1); отсюда следует., что р1Мв -4 0 при й -4 оо, где М = ~г ч1! — г. Коэффициентами для Цг) служат коэффициенты разложения функции 2 1 1 1 1 + + + + + +В (г), 1 — г 1 — г/г, 1 — г/», 1 — г/г 1 — г/» а именно Е„= 2+ 2г "созпВ1 + 2г "созпВ2+ + 2г "созпВ + 0(г ",), (29) если положить гь = гге '. 4В, (30) Отсюда можно проследить асимптотическое поведение 7.„.
Имеем В1 = 1.17830 39784 74668+; Вз = 1.31268 53883 87636+; Вз = 1.37427 90757 91688 —; В4 = 1.41049 72786 5186о-; г1 = 8.07556 64528 89526-, гз = 14.35456 68997 62106 —, гз = 20 62073 15381 80628-, г4 = 26 88795 29424 54546-, (31) таким образом, главный вклад в ń— 2 дают г1 н В1, а ряд (29) сходится очень быстро. Дальнейший анализ [Ч~. '11'. Ноо11ег, СА СМ 12 (1969), 411 — 413) показывает, что В„,(г) — 1 — г при т — у оо; следователю|о, ряд 2 2„1,> г„" сов пВг действительно сходится к 5„при и > 1. Можно провести более тщательный анализ и полностью определить распределение вероятностей для длины Й-й серии и для общей длины первых й серий (см.
упр. 9 — 11). Оказывается, сумма Е1 + + Еь асимптотически приближается к 21 — 1+ 0(8-'). В заключение этого раздела рассмотрим свойства серий в случае, когда в перестановке допускаются одинаковые элементы. Бесчисленные пасьянсы, которым посвящал свой досуг знаменитый американский астроном 19 в. Саймон Ньюкомб (Бппоп 1чезвсошЬ), имеют непосредственное отношение к интересуюшему нас вопросу. Он брал колоду карт и складывал их в одну стопку до тех пор, пока они шли в порядке неубывания по старшинству; как только следующая карта оказывалась младше предыдущей, он начинал новую стопку. Он хотел найти такую вероятность, при которой вся колода окажется разложенной на заданное количество стопок. Задача Саймона Ньюкомба состоит, следовательно, в нахождении распределения вероятностей для серий случайной перестановки мультимножества.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
