Ьп = a„-e„ i

= а„-а„ 2 = (J)a„-(2)a„ 2,

Cn = b„-d„ i

= 6„-а„ 2-Ь„ 2 = (д)а„-(2)а„ 2 + (4)а„ 4, (4)

dn = c„-e„ i

= с„-а„ 2-Ь„ 2-с„ 2 = (o)a„-(2)a„ 2+(4)a„ 4-(g)a„ 6,

en = d„-b„-i

= d„ -a„ 2-b„ 2-c„ 2-d„ 2 = (o) a„ - (1) a„ 2 + (4) a„ 4 - (5) a„ 6+ (§)дп-8 • Обозначим А{г) = n>onZ", E{z) = J2n>onz" и определим многочлены . . /m\ /т + 1\ 2 , /m + 2\ 4

fc fc=0

Результат (4) кратко можно истолковать так, что В{г) - qi{z)A{z), C{z) - д2(г)А{г), D{z) - дз{г)А{г) и E{z) - 94(2)(2) сводятся к конечным суммам, соответствующим граничным условиям, а именно - значениям a i, а 2, а з,..., которые появляются в (4) (при небольших п), но не в A{z). Чтобы получить подходящие граничные условия, применим рекуррентное соотношение в обратную сторону для отрицательных уровней вплоть до уровня -8.

(Для семи лент таблица была бы аналогичной, однако строки с нечетными п были бы сдвинуты вправо на один столбец.) Тайна последовательности ао,а 2,а 4,... = 1,1,2,5,14,... мгновенно раскрывается специалистом по информатике, так как эта последовательность встречается в связи с очень большим числом рекурсивных алгоритмов (см., например, упр. 2.2.1-4 и формулу 2.3.4.4-(14)). Итак, мы предполагаем, что в случае Т-лент

а 2„ = при О <гг<Т-2;

\п J п + 1

а 2„-1 =0 при О < п < Т - 3.

Чтобы проверить правильность этого предположения, достаточно показать, что (6) и (4) приводят к верным результатам для уровней О и 1. Для уровня 1 это очевидно, а для уровня О необходимо проверить, что

fc>0

для 0<т<Г-2. К счастью, эту сумму можно вычислить стандартными методами (это фактически пример 2 из раздела 1.2.6).

Теперь можно вычислить коэффициенты при B{z) - qi{z)A(z) и т. д. Рассмотрим, например, коэффициент при г"* в D{z) - q3(z)A{z). Он равен

,{ 2т + 2к .

к>0 к>0

V /3 4.m + fcW2fc4(-l)"+*

j (-1) а 2. - 1. I 2m + 2А J U J "ТТТ"

fc>0

=(-""((r-"J-(r*))

как следует из результата примера 3, приведенного в разделе 1.2.6. Таким образом, получены формулы

Л(2) = qoiz)Aiz),

Biz) = qi{z)A{z) - qo{z), С(г) = д2(г)Л(г) - qiiz),

Diz) = q3iz)Aiz) - q2iz), Eiz) = qiiz)A{z) - qaiz). (8)

Кроме того, имеем e„+i = a„; следовательно, zA(z) = E(z) и

A{z)=q3{z)/{q4iz)-z). (9)

Производящие функции были выражены при помощи д-многочленов, поэтому желательно лучше изучить q. В этом отношении полезно упр. 1.2.9-15, так как оно дает выражение в замкнутом виде:

{iVi + iz)/2)" + {{Vrr-iz)/2f- qm{z) - д== . (10)

Все упрощается, если теперь положить z = 2 sin б:

т m (cos6 + isin6)2"+i--(cos6-isin6)2"+i cos(2m+l)6 ,,,, ""2") - W-= cose •

(Такое совпадение приводит к мысли, что многочлены qm{z) хорошо изучены в математике. Действительно, заглянув в соответствующие таблицы, мы видим, что qmiz), по существу, является многочленом Чебышева второго рода, а именно - {-l)"4l2m{z/2) в обычных обозначениях.)

Теперь можно определить корни знаменателя в (9): уравнение 94(2 sin б) = 2 sin б сводится к

cos 9в = 2 sin в cos в = sin 2в.

Решения этого соотношения получаем, если только ±9в = 2в + (2п - )7г; все такие в дают корни знаменателя в (9) при условии, что cos б ф 0. (Если cos б = О,

то gm(±2) = (2m + 1) никогда не равно ±2.) Следовательно, получаем восемь различных корней: 94(2) - 2 = О при

2 sin fft, 2 sin jtt, 2 sin jtt; 2 sin тг, 2 sin =7Г, 2 sin jjtt, 2 sin тг, 2 sin тг.

Так как 94(2) - многочлен степени 8, значит, учтены все корни. Первые три из этих значений дают 93(2) = О, так что 93(2) и 94(2) - 2 имеют в качестве общего делителя многочлен третьей степени. Остальные пять корней управляют асимптотическим поведением коэффициентов A{z), если разложить (9) на элементарные дроби.

Переходя к рассмотрению общего случая для Т лент, положим = (4fc + 1)тг/ /(4Т -2). Производящая функция A{z) для Т лент каскадных чисел принимает вид

4 V (12)

2Т-1 1-2/(2 sin6fc

(см. упр. 8); следовательно,

-T/2<a<[r/2J

Соотношения (8) приводят теперь к аналогичным формулам:

-r/2<a<.r/2j

Сп =

-r/2<*:<lr/2J

-r/2<fc<lr/2J

и т. Д. в упр. 9 показано, что эти уравнения справедливы для всех п > О, а не только для больших п. В каждой сумме член с /с = О значительно превосходит все остальные члены, особенно если п достаточно велико. Следовательно, "отношение роста" есть

= - - + 15т + (")- (15)

25шво т 48Г

Каскадная сортировка впервые была исследована У. К. Картером (см. W. С. Carter, Ргос. JFJP Congress (1962), 62-66), который получил численные результаты для небольших значений Г, и Дэвидом Э. Фергюсоном [см. Е. Ferguson, САСМ 7 (1964), 297], который открыл первые два члена в асимптотическом поведении (15) отношения роста. Летом 1964 года Р. У. Флойд (R. W. Floyd) получил явный вид 1/(2 sinо) для отношения роста, так что точные формулы могли быть использованы для всех Т. Глубокий анализ каскадных чисел был независимо выполнен Дж. И. Рэйни (см. G. N. Raney, Canadian J. Math. 18 (1966), 332-349), который столкнулся с ними совершенно другим путем, не имея дела с сортировкой. Рэйни заметил принцип "отношения диагоналей" представленный на рис. 73, и вывел много других интересных свойств этих чисел. Флойд и Рэйни в своих доказательствах оперировали матрицами (упр. 6).