ны и в связи с другими вопросами; поэтому конец раздела мы посвятим анализу асимптотического поведения i„.

Первый шаг в анализе асимптотического поведения (41) состоит в выделении слагаемых, делающих основной вклад в сумму. Поскольку

Uk + l) {п-2к){п-2к-1) tn{k) 2{к + 1)

можно видеть, что слагаемые постепенно возрастают от А; = О до tn{k + 1) w tn{k), когда к приблизительно равно {п - у/п), а затем убывают до нуля, когда к достигает значения, равного примерно п. Ясно, что основной вклад вносят члены в окрестности значения к = \{n-s/n). Для анализа, однако, удобнее, чтобы основной вклад достигался при значении О, поэтому представим к в виде

k=\{n-V)+x (44)

и исследуем величину tn{k) как функцию от х.

Чтобы избавиться от факториалов в tn{k), полезно воспользоваться формулой Стирлинга 1.2.11.2-(18). Для этой цели удобно (как мы вскоре увидим) ограничить область изменения х промежутком

<х< n+i/" , (45)

где 6 равно, скажем, 0.001, так что можно включить слагаемое погрешности. После довольно трудоемких вычислений, которые автор в середине бО-х годов выполнил ручкой на бумаге и которые теперь могут быть реализованы средствами компьютерной алгебры, получается формула

tn{k) = exp(nlnn - \п + \/п - jlnn - 2х7\/"- j - 1п7г

- xVn + 2x/v+ i/V- fxVnv-f 0(71-/")). (46)

Ограничение (45) на х оправдывается тем, что можно положить х = ±71+/* для получения верхней оценки всех отброшенных слагаемых, а именно

ехр(п1п n-in + v-ilnn-i-iln7r + 0{п-/)). (47)

Если же умножить это на п, получится верхняя оценка суммы исключенных слагаемых. Верхняя оценка имеет меньший порядок, чем те слагаемые, которые вычислим для X в ограниченном промежутке (45), благодаря множителю ехр(-2п), намного меньшему любого полинома от п..

Очевидно, можно отбросить в сумме множитель

exp(nlnn -\п + \/п - jlnn-j-jlnTT-f \1\/п), (48)

после чего нам останется только просуммировать

exp(-2x7v/ - х7п + 2x1 - хУп + 0{п-/*))

/-2х2\ / 4x3 8х«\/ „X х\

по всем х = а, а+1, ..., /9-2, где -а и /3 (необязательно целые) равны приблизительно п/. Если сместить интервал суммирования, то формулу суммирования Эйлера (1.2.11.2-(10)) можно записать в виде

е Л) = f f{x)dx-\f{x)

а<х<0

2 " 1!

+ + В

, 1 - т+1 1

m-1-l т!

+ (50)

Здесь < (4/(27r)")/f /(")(x)da;. Если положить /(х) = ехр{-2хУ,/), где i - фиксированное неотрицательное целое число, найдем из формулы суммирования Эйлера асимптотический ряд для f{x) при п оо, поскольку

/W(x)=n(-")/V"(n-/), 9{у) = уе-У • (51)

И5(у) - хорошая функция, не зависящая от п. Производная р*"*(у) равна е", умноженному на полином от у. Следовательно, = 0(п+~"/) \9-"Ну)\dy = 0(п+~"/). Далее, поменяв а и /3 на -оо и --оо в правой части уравнения (50), мы сведем ошибку к величине, не превышающей 0(ехр(-2п)) в каждом члене. Таким образом,

/оо /(х) dx + Oin") для всех m > 0. (52)

На самом деле при этом конкретном выборе /(х) существен только интеграл! Интеграл нетрудно вычислить (см. упр. 26), значит, мы можем выполнить умножение и сложение в формуле (49) и получить л/7г/2(п/ - п~/ + 0{п~)). Таким образом,

" n"/2e-"/2+v-i/4(1 + V2 + 0(п-/)). (53)

В действительности члены с О должны еще содержать дополнительно 9б в экспоненте, но из наших выкладок ясно, что величина 9 б должна исчезнуть, если произвести вычисления с большей точностью. В принципе, этот метод можно расширить и вместо 0(п~/) получить 0(п~*) при любом к. Этот асимптотический ряд для tn впервые нашли (другим способом) Мозер (Moser) и Уаймэн (Wyman) [Canadian J. Math. 7 (1955), 159-168].

Метод, использованный при выводе соотношения (53), представляет собой исключительно полезную методику асимптотического анализа, которая была предложена П. С. Лапласом [см. Р. S. Laplace, Memoires Acad. Sci. Paris (1782), 1-88]; она также анализируется в CMath §9.4 под наименованием "trading tails". Другие примеры и развитие метода, примененного для вывода формулы (53), приводятся в конце раздела 5.2.2.

УПРАЖНЕНИЯ

1. [16] Какие диаграммы (Р, Q) соответствуют двухстрочному массиву

2345678 ,6495712837

: построении из теоремы А? Какой двухстрочный массив соответствует паре диаграмм

2. [М21] Докажите, что {q,p) принадлежит классу t относительно массива (16) тогда и только тогда, когда t равно максимальному числу индексов ii,..., п, таких, что

Рп <Pi2 < < Pit - Р, gii <qi2 < < Ян = q-

► 3. [М24] Покажите, что соответствие, определенное в доказательстве теоремы А, можно также установить, построив следующую таблицу:

Строка О 1 3 5 6 8

Строка 1 7 2 9 5 3

Строка 2 00 7 00 9 5 .

Строка 3 00 00 7

Строка 4 00

Здесь в строках О и 1 записан заданный двухстрочный массив. При к > 1 строка к + 1 образуется из строки к следующим образом.

a) Присвоить р 00.

b) Пусть столбец j - крайний слева столбец, в строке к которого содержится целое число < р, а соответствующее место в строке к + 1 не заполнено. Если такого столбца нет и р = 00, то формирование строки к + 1 на этом завершается; если такого столбца нет и р < 00, то возвратиться к (а).

c) Вставить р в столбец j в строке к + 1, присвоить р значение элемента столбца j и строки к и вернуться к (Ь).

После того как таблица таким образом построена, строка к диаграммы Р составляется из тех целых чисел строки к этой таблицы, которые отсутствуют в строке (к + 1); строка к диаграммы Q строится из тех целых чисел строки О, которые находятся в столбцах, содержащих оо в строке к + 1.

► 4. [МЗО] Пусть oi ... Oj-i Oj ... an - перестановка различных элементов и 1 < j < п. Перестановка oi... оу 2 aj aj-i aj+i... an, получающаяся из исходной, если поменять местами Oj-i и Oj, называется допустимой, если либо

i) J > 3 и aj-2 лежит между aj-i и aj, либо

ii) j < п и Oj+i лежит между Oj-i и Oj.

Например, в перестановке 15 4 68 3 7 можно выполнить ровно три допустимые замены; можно поменять местами 1 и 5, поскольку 1 < 4 < 5; можно поменять местами 8 и 3, поскольку 3 < 6 < 8 (или 3 < 7 < 8); однако нельзя менять местами 5 и 4 или 3 и 7.

a) Докажите, что при допустимой замене не меняется диаграмма Р, которая получается из перестановки путем последовательной вставки элементов 01,02,..., Оп в первоначально пустую диаграмму.

b) Обратно, покажите, что можно преобразовать одну в другую любые две перестановки, которые соответствуют одной и той же диаграмме Р, выполнив одну или более допустимых замен. [Указание. Покажите, что если диаграмма Р имеет форму (п1,П2,... ,Пт), то любую соответствующую ей перестановку при помощи последовательности допустимых замен можно преобразовать в "каноническую перестановку"

Pml • • . Pmnjn • . P2I Р2п2 Pll Plni-]