Таблица 1

числа эйлера

Соотношение (6) следует из (5) вследствие свойства симметрии

где п > 1,

п-1-к

которое вытекает из того факта, что каждая непустая перестановка 0102 • . а„, содержащая к нисходящих серий, имеет и п - 1 - А; восходящих серий. Другое важное свойство чисел Эйлера выражается формулой

п > О,

которая была впервые выведена китайским мате.матиком Ли Шан-Ланом и опубликована в 1867 году. [См. J.-C. Martzloff, А History of Chinese Mathematics (Berlin: Springer, 1997, 346-348); особый случай, если n < 5, был независимо рассмотрен японским математиком Йошисуке Мацунага (Matsunaga Yohisuke), который умер в 1744 году.] Тождество Ли Шан-Лана следует из свойств операции сортировки. Рассмотрим т" последовательностей oi 02 ... а„, где 1 < щ < т. Любую такую последовательность можно устойчиво рассортировать в порядке неубывания и получить:

Oil < < • • < ai„ , (9)

где ii 12 in - однозначно определенная перестановка множества {1,2,..., п}, такая, что ij < ij+i, если ai- = Oi.; другими слова.ми, из ij > ij+i следует Ojj < Oj.i. Покажем, что если в перестановке iii2---in содержится к серий, то число соответствующих ей последовательностей oi ог.. .а„ равно С""," j; тем самым будет доказана формула (8), если заменить к значением п - А; и воспользоваться (7), поскольку () перестановок имеют п - к серий.

Пусть, например, n = 9,iii2---Jn=357168942H требуется подсчитать число последовательностей oi ог ... а„, таких, что

1 < аз < 05 < От < Oi < Об < Og < Од < 04 < 02 <

< т.

(10)

Оно равно числу последовательностей b1b2--.bg, таких, что

\ <bi <Ь2 <Ьз <Ь4 <Ьъ <bQ <Ьт <Ьъ <Ьд <т + Ъ,

поскольку можно положить 61 = аз, 62 = 05 + 1, 63 = ат + 2, 64 == oi + 2, 65 = Об + 3 и т. д. Число способов, которыми можно выбрать элементы Ь, равно просто-напросто числу способов выбора 9 предметов из т-\-Ъ, т. е. ("); аналогичное доказательство годится для произвольных тг и /с и любой перестановки iii2 - in с к сериями.

Так как в обеих частях равенства (8) стоят полиномы от т, вместо т можно подставить любое действительное число, получив интересное выражение степеней через последовательные биномиальные коэффициенты:

---{:){:)<)г:)--а:-г)г:-) <">

Например,

-{1)-<г)-{г)-

в основном благодаря именно этому свойству числа Эйлера весьма широко применяются в дискретной математике. Положив в (11) z = 1, докажем еще раз, что („"i) = 1. поскольку биномиальные коэффициенты обращаются в О во всех слагаемых, кроме последнего. Положив х = 2, получим

Подставив X = 3, 4, ..., убедимся, что все числа () полностью определяются соотношением (11), и придем к формуле, впервые найденной Эйлером:

) = (, + 1)"-,"("1)+(, 1Г(";1)-... + (-1)Ч"(")

= E(-i)f")( + i-ir. п>о,к>о. (13)

Рассмотрим теперь производящую функцию для серий. Если положить

»"И=1:(,!,)й- (">

то коэффициент при г* будет равен вероятности того, что случайная перестановка множества {1,2,..., тг} содержит ровно к серий. Поскольку к серий в перестановке столь же вероятны, как ип + 1 - к, среднее число серий должно равняться (n -Ь 1) и, следовательно, gni) = (гг + 1). В упр. 2, (Ь) показано, что имеет место простая формула для всех производных функции gn{z) в точке z - 1:

Так, в частности, дисперсия 5(1) + 5п(1) ~ sni) равна (п + 1)/12 при п > 2, что указывает на довольно устойчивое распределение около среднего значения. (Эта же величина была найдена в упр. 3.3.2-(18); в нем она называлась covar(iii, Д).)

функция з„(г) - полином, поэтому с помощью формулы (15) и формулы Тейлора ее можно представить в виде

Второе равенство следует из первого, поскольку вследствие условия симметрии (7)

gn{z) = г»+1з„(1/г), тг > 1. (17)

Из рекуррентного соотношения для чисел Стирлинга

с:}=<-){ллч:}

при тг > 1 получаются два более простых представления:

,.w = i ±ф -1)--/=! = 1 ра - .)"-<=! {;}. (18)

Производящая функция от двух переменных*

п>0 к,п>0

равна,следовательно,

{{z-\)xY п\к\ e(-i) -ly (1-г)

z-l ) ~ е(-1)-,

(20)

Это еще одно соотношение, проанализированное Эйлером.

Другие свойства чисел Эйлера можно найти в обзорной статье L. Carlitz, Math. Magazine 33 (1959), 247-260. (См. также работы J. Riordan, Introduction to Combinatorial Analysis (New York: Wiley, 1958, 38-39), 214-219, 234-237**; D. Foata, M. P. Schiitzenberger, Lecture Notes in Math. 138 (Berlin: Springer, 1970).)

Рассмотрим теперь длину серий; какова в среднем длина серии? В разделе 3.3.2 уже было проанализировано математическое ожидание числа серий данной длины; средняя длина серии равна примерно 2. Это согласуется с тем фактом, что в случайной перестановке длины п содержится около (n + 1) серий. Применительно к алгоритмам сортировки полезна несколько отличная точка зрения; рассмотрим длину к-й слева серии перестановки при к = I, 2, ....

Какова, например, длина первой (крайней слева) серии случайной перестановки oi 02 ... о„? Ее длина всегда > 1; она > 2 ровно в половине случаев (а именно, если oi < 02). Ее длина > 3 ровно для 1/6 случаев (если oi < 02 < 03). Вообще, ее длина > т с вероятностью qm = 1/m! для 1 < т < п. Следовательно, вероятность того, что длина этой серии равна в точности т, есть

Рт qm- qm+1 = 1/т\ - l/(m + 1)!, где 1 < m < п;

Рп = 1/п\. (21)

* в оригинале - "super generating function". - Прим. перев.

** Имеется русский перевод: Риордан Дж. Введение в комбинаторный анализ. - М.: Изд-во иностр. лит., 1963. - Прим. перев.