Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Положим f(x)~g{x) при х-*а, если существует функция ф(ж) такая, что в некоторой окрестности а, исключая, быть может, а,
f(x) = <р(я)#(ж) и <р(ж)->1 при х-+а.
В этом случае говорят, что f(x) эквивалентна (асимптотически равна) функции ?(т) при х а.
Пример ы: sin х ~ х при х -»? 0, ех ~ 1 — х при х -*? 0.
В случае, если ?(я)=5*0 (или /(ж) =5*0) в некоторой окрестности а (исключая, быть может, о), то условие I{x)~g(x) при х~*-а эквивалентно условию
/ И ^
i-7V -? 1 при х а.
в (х)
Легко видеть, что условие f(x)~g{x) при х-^а эквивалентно условию
f{x) = g(x)+ o(g(x)) при х-+а.
Замечание. Из условия / (т) = g (т) + о (1)' при х -*? а следует, что еПх) ~ eg{x) при х -*? а.
В то же время, если f(x)~g(z) п|ш х ^ а} то отсюда не следует, что etM ~ esix) при х -*? а.
Пример. Пусть & — множество натуральных чисел и а = +°°. Пусть f{n) = n и g{n) = пЛ- с (с АО). Ясно, что f(n) ~ g(rc) при п -*? а
еп
= е А 1 при + оо,
Введем- отношения f(x)<g(x) при х-+а и f(x) < ^?(,г) при х о , которые тесно связаны с предыдущими и являются естественными обобщениями отношения ^,
Положим } (ж) < g{x) при x -*? а, если существуют такие положительные константы Сj и С% (Ci > 1, С2<1) и окрестность точки а, в которой (кроме, быть может, самой точки а)
f(x)<C(x)g{x),
где
f С* при g (ж) > О*
С (ж) = 1 при g (ж) — 0Г
I С2 при g (х) < 0.
Из определения следует, что график функции /(ж)' лежит не выше графика функции #(ж), поднятого вверх в С(х) раз.
Если при х -+? а одновременно / {x)<g (ж) и g{x)<f (x)s то пишем
/(ж)Х^(ж) при х~+а.
Покажем, что в этом случае функции f(x) и #(ж)'
имеют один и тот же порядок и одинаковый знак. Дей-
ствительно, при этом условии в некоторой окрестности а (исключая, быть может, а) одновременно выполняются неравенства
f{x)<C'(x)g{x) и g(x)<C" (x)f{x).
Из них получаем
/(ж) ^ С' (x)g(x) < С' (ж) С " (ж) f(x)
и
g (ж) < С" (ж)/(ж) < С" (ж) С' (ж) g (ж).
Отсюда следует, что в указанной окрестности:
1. Функции /(ж) и g{x) обращаются в 0 в одних и тех же точках.
2. В ненулевых точках функции /(ж) и g(x) имеют один знак и в них
fix)
С'<
(х)
< с\
т. е. /(ж)== 0(^(ж)) и g(x)=0(f(x)) при ж->-а. Следовательно, при х-+а условие f(x)Xg{x) влечет условие ^(x)^g(x).
Положим f(x)*ъgfix) при х^а, если для любого е > 0 существует окрестность ТОЧКИ Й, в которой (кроме.
Сыть может, точки а)
где
СЕ (л-) =
1+в при ?(ж)>0, 1 при g (ж) = О,
1 — е при ? (ж) < О.
Ясно, что из /(ж)<?(ж) при х -? а вытекает, что 1 {х)< 8 {х) при х -? а. Поэтому все сказанное выше об отношении < справедливо и для отношения К. В частности, в случае, когда при х~+а одновременно 1(х)1? ^В(х) и д(х)*ъ {(х), функции /(ж) и ё{х) обращаются в 0 в одних и тех же точках и в ненулевых точках выполняются неравенства (при е<1):
т. е. f(x)~g (ж) при х -*? а.
Теперь перейдем к рассмотрению асимптотики (предельных теорем) для ряда комбинаторных чисел.
У,
О
Ц 2 3 и ц ц*1 х
Рис. 5
Асимптотика 1п га! Порядок п\
Теорема 8.
Доказательство. Возьмем выражение
71
1п в! = 2 **
Р=1
ч. и, Комбинаторный анализ 207
Рассмотрим график функции у~\пх (см. рис. 5).
П
Сумму 21° * можно рассматривать как площадь прямого!
угольников, вписанных в кривую у = 1п х. К этой величине добавим площадь треугольников (см. рис. 6), т. е. сумму
п
2 4 (1п (I + 1) — 1п I) = -11п (п + 1).
1=1
Получим
п+1
1п п! + 1п (п+ 1) <С J 1п хйх =* л+пя — я!?*1 “
= {п + 1) 1п (II + 1) — п.
Отсюда
1п п! <; 1п (п + 1) — п.
С другой стороны, рассмотрим фигуру, образованную отрезками касательных в точках х = 1, 2,...
..«, ограниченными прямыми х = 1 у,
2 ___,п + ~- и осью х (см, рис. 7).
Очевидно, что она составлена из тре-1
угольника с площадью и трапеции со
средними линиями в точках х = 2, 3, ...
..п, площади которых равны соответственно 1п 2, ..1п п. Очевидно,
п ”
•— + 2ь I > | 1п х йх + ?— 1п п.
1=1 1
Отсюда
1 1 / 1 \ 7
1п п! > п 1п п—п+1 + — 1п п — = [ п + у ) 1п п—п +
Таким образом,
ZUM Ч. П. КОМБИНАТОРНЫЙ АНАДЙЗ
t 7
Разделив на + yj In пг получим J^u. также (3))
1 - 7 1 n“8 ^ Inn! <
—jfj lnn ^n + -yjlnn
(»+?)»? (*+т) —
< 1 +
Т. Є.
In nl
(" + т)1ип
Теорема доказана.
1+0
+ 4*)^° п
Ш-
Рис. 7
Замечание. Из доказательства теоремы вытекает также, что
е7/8 У'п тгпе~п < и! < Уп + 1 ппе~п ~ еУпппе~п1
(31)
т. е.
гс! X У пппе~п.
Асимптотика п I
Теорема 9 (формула Стирлинга). п\ аУп
Ч. И. КОМБИНАТОРНЫЙ АНАЛИЗ 209
Доказательство. Положим
п!
Уп ппе- п *
Рассмотрим отношение
fl«+i (п 4- 4)! Упппе~п е
ап “ "ук+1(п + i)'H-ie-(n+u "я! ^ТТХуГЖ *
Учитывая (4), получаем
ип
Значит, последовательность {а„) убывающая и ограничен' ная снизу, и поэтому она сходится к некоторому числу а. В силу неравенств (31)
е7/в < а < е.
В частности, а Ф 0. Следовательно, установлена асимптотика _
к| ~ аУп ппе~п.
Для вычисления константы а нам понадобится формула Валлиса, которая является содержанием следующей теоремы.
Т е о р е м а 10. Vn — litH г4- ~72?ТГ '
П-»оо У П (^Г‘)‘
Я/2
Доказательство. Возьмем J sin" х dx(п^2) и
о
проинтегрируем его по частям;
