Средняя длина первой серии равна, таким образом,

Pi+2p2 + --- + np„ = {qi - 92) + 2(92 - дз) + • • + (и - l)(gn-i - qn) + Щп

= + + + +

Предел при п оо равен е - 1 = 1.71828..., а для конечных п это значение равно е - 1 - S„, где 6„ довольно мало (для больших п. - Прим. ред.):

11 1 е - 1

<5п = 7-ТТТ 1 + - + 7-- + • • • <

п + 1)! V п + 2 {п + 2){п + 3) J - (п + 1)\

Поэтому для практических целей удобно рассмотреть серии случайной бесконечной поспедовательности различных чисел

а1,а2,аз,

под "случайностью" последовательности здесь подразумевается то, что все п\ возможных взаимных расположений первых п эле.ментов последовательности равновероятны (при любом п. - Прим. ред.). Так что средняя длина первой серии случайной бесконечной последовательности в точности равна е - 1.

Несколько усовершенствовав этот метод, можно установить среднюю длину к-й серии атучайной последовательности. Пусть qm - вероятность того, что общая длина первых к серий > т: тогда qkm равно величине 1/т\, умноженной на число перестановок множества {1,2,..., т}, которые содержат не более к серий:

/ /тп\ / т \\

+ +

qkm =

,(o/---\yfc-i

те!. (23)

Вероятность того, что общая длина первых к серий равна те, есть qm - qk(m+\)-Следовательно, обг;31хачив через Lk среднюю длину k-\i серии, находим, что

Li + + Lk = средняя общая длина первых к серий

= {qk\ - qko) + 2{qk2 - qks) + 3(to - qki) + • •

= qki +qk2 +qk3 -\- •

Вычитая Li + + Lk-i и используя значения qkm, из (23) получаем нужную нам формулу:

т>1

Поскольку = О, кроме случая к = 1, значение Lk оказывается равным коэф-

фициенту при z*" в производящей функции д{г,1) - 1 (см. (19)); таким образом, имеем

..к . (1-)

liz) = lkz = -z. (25)

к>0

Из формулы Эйлера (13) получим представление в виде полинома от е: к

.=ЕЕм)-(г;)£

т>0 j=0

=d-)-t:(.!,)S-i:(-4-e(. 7-i)£

j=0 m>0 "" j=0 m>0

± {-\f-ij-i j" Л (-l)-ij-i-i (A;-i)! n! (yfc-i-l)! n\

j=0 • n>0 у=й > n>0

(26)

Эту формулу для Lk впервые получила Б. Дж. Гэсснер (В. J. Gassner) [см. СкСШ 10 (1967), 89-93]. Имеем, в частности,

Li = е - 1 7=i 1.71828... ;

La = е2-2е 1.95249... ;

= еЗ -Зе-ь е к. 1.99579... .

Итак, следует ожидать, что вторая серия будет длиннее первой, а третья серия будет в среднем еще длиннее! На первый взгляд, это может показаться странным, но после минутного размышления становится ясно, что, поскольку первый элемент второй серии будет, скорее всего, малым числом (именно это служит причиной окончания первой серии), у второй серии больше шансов оказаться длиннее, чем у первой. Тенденция такова, что первый элемент третьей серии будет даже меньше, чем первый элемент второй серии. Числа Lk важны в теории сортировки посредством выбора с замещением (раздел 5.4.1), поэтому интересно подробно проанализировать их значения. В табл. 2 приведены первые 18 значений L с точностью до 15 десятичных знаков. Рассуждения, приведенные в предыдущем абзаце, могут поначалу вызвать подозрение, что L+i > Lfc, на самом же деле значения колеблются, то возрастая, то убывая. Заметим, что Lk быстро приближаются к предельному значению 2. Весьма примечательно то, что эти нормированные полиномы от трансцендентного числа е так быстро сходятся к рациональному числу 2! Полиномы (26) представляют некоторый интерес и с точки зрения численного анализа, поскольку являются прекрасным примером потери значащих цифр при вычитании почти равных чисел; используя арифметику с плавающей точкой и представление с точностью до 19 значащих разрядов, Гэсснер пришла к неверному заключению о том, что L\2 > 2, а Джон У. Ренч (мл.) (John W. Wrench, Jr.) отметил, что выполнение арифметических операций с точностью до 42 значащих разрядов дает значения L28 с точностью только до 29 значащих цифр.

Асимптотическое поведение Lk можно определить, исходя из простых положений теории функций комплексного переменного. Знаменатель в (25) обращается в нуль лишь при е*~ = z, т. е. когда

е~ cosy = а; и е~ siny = у, (27)

Таблица 2

средняя длина к-Й серии

полагая г = х + гу. На рис. 3, на котором нанесены оба графика этих уравнений, видно, что они пересекаются в точках z = zq, zi,zi,Z2,Z2,. ., где zq = 1,

21 = (3.08884 30156 13044-) + (7.46148 92856 54255-) г, (28)

и при больших к мнимая часть 3(zft+i) равна приблизительно Q{zk) + 27г.

-5 •

-10 •

е-"- smy = y х-1,

Рис. 3. Корни уравнения е

Z-1