Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Возьмем две (не обязательно целочисленные) функции а(п) и Ь(п) таких, что
1 < а(п) <Ь(п)< н,
а (п) -+? оо) п — Ь (п) -* оо? /г -> оо|
и разобьем сумму на три части;
Ф (к) — Ф2(и)+ Ф3(п),
где
]<й<й(л}' I
фЛ")= 2 (l-ji + .... )~,
?(,n)?k<b{n) ' і
Фз(”) = 2 (і - Ті + ... + ( — І)71-* ^ТГЩ-) V-
Ь(тїХ/і<йк
Поскольку гс Ь (п)оо, то для к^Ь[п) имеем п — к> > п — Ь{п) и
І 1 » л. (_ І)71“*----\^ ±
г ,А1 Т • • • "Г V Ч (п—к)\ е *
Мы получаем
1 2 *n
1 «Ku(n)
_ ?_
е ,*l'
ф2и~~ 2
а(7і)<&<Ь(ії} '
».ex 2 (?+і+...+-5І8Г)г<- 2 г
b(r»Xfc<« y Ь(и)<Х»
Во всех суммах присутствует член вида &"/&! Покажем, что последовательность (AVA!) унимодальна. Сравним два соседних члена кп/к\ и (к + 1) V (А +-1)! Легко видеть, что
**_< {Ъ±1Г _ п> ln (ftН- 1)
W > {к -г 1)1 <1п|
(*+т)
(данная запись — сокращенная запись для трех условий).
Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ 217
_ _ 1п(А--И)
Поскольку функция / рт монотонно возрастаю-
гцая по к, то в случае:
ч *?" ^ 4-1)" 1п ГА н-1) 1п *
а) *Г< (ЗьТЩ- имееы ?г>~
т. е. п>—, 1п\ , (поэтому с ~ ИТ. дф
ь(1 + г4-1)
кп + 1п (к 4) 1л (к _|_ 2)
б> Ж>1Гр[)Г имееи —“<'
1п(1 + т) 1п(1 + гп)
т. е.
1п (к 4-
п <
111
т- 2) / , (й-+1)п ^ (к-\-2)п N
-гг (ПО0ТОму Т^П)Г>1ггтж и т'я']:
. кп (к+1)п „ 1п(Ь+1)
в) ГГ = - ; , ИЗ строгой МОНОТОННОСТИ ---7---—Г—
к I 4 1)1 / 1 \
1п(1 + Т]
(* - 1)" ^ кП № 4- 1)п ^ (к + 2)п
следует, что -г_1уг<-хг и ^-пуг>^ж и т.д.
Обозначим через к0 наибольшее значение к, для которого кп/к\ максимально. Произведем оценку числа к0. Очевидно,
(ко — *)* ^о1 ^{ко+*)1*
/г1п(1 + 1п/г01
п 1п ^1 + у-| < 1п (й0 + 1).
Так как (см. (3))
1п(1 + *Г^)<^’
то
п > (ка — 1)1п Д'о > (&„ — 1)1п(&о — 1)">
218
Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ
а так как (см. (4))
то
и < (+ у ) ln {к0 + 1) < (к0 + 1) ln {к0 -f 1).
1
Поэтому из монотонности функции xlna: следует, что к0 отличается от единственного решения г уравнения
Положим далее а(п)~ г~ Уп и Ь(п) = г + Vn. В силу
Условия а (и)-* со и п — Ь(и) -> °=> также выполнены. Сначала займемся изучением
а\п)<к^СЬ(п)
Заменим в Фг(п) члены кп/к\ их асимптотическими выражениями, получающимися по формуле Стирлинга:
и положим а== к — г (здесь параметр 5 может стать не целочисленным, но Д® — ДА: = 1). Тогда получим
а(п)<Н<СЬ{п)
r-,YrnCti <г+\ггi
Ч. И. КОМБИНАТОРНЫЙ АНАЛИЗ 219
Заметим, далее, что
г + s — ехр{1п (г + х)} = exp |ln г ^1 + j =
= exp|lnr + III ^1 -f ~jj.
I S I Г /^n n \
Учитывая соотношение | —| = разложим в ряд
In ^1 + ~j и оставим в разложении столько членов, чтобы остаток, умноженный на^гс — т — х—1") был бы
равен о(1). Для этого достаточно взять два первых члена разложения, т. е.
1п(1 + т)”т-І7 + 0Ш'
ибо
п0(7)=0(|^)“о(1)-
Таким образом, мы получаем
71 — T--S 1 Г+J
(г + s) 2е =
= expj(lnr +f-'4"2)(n”r~5~l) + r + 5+0 ї1)}*
Произведем далее преобразование показателя:
(inr + y —Y^-)(n—г —s —-j) + r +
1 , пи пь . , а ,
= П In /? Н---------5—rlnr — Х-Ьт slur —
г 2 г
2 3 л 2
s 8 1 , S S
~ “ 53 ~ Tln г" гГ + р + г+ *•
В нем, в силу соотношения г In г — гс, выполняется ра-
нн 3 2
ПА 1 & S S /-14
венство — = s ш гх а члены — 9 — и —= равны о{ 1).
г 2 г 2г 4 г
220 Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ
Продолжив преобразование, получим
п(1пг + іЬ-1)-т1пг--^(т + 1) + 0(1)-
В результате получаем
1
Ф,(п) = —4-і X
у± + V*
х 2 ехр{”'5?(т + *)} У ~у— а + ал-
В последней сумме произведем замену переменной, взяв
г = $
,Л + 1 і/- +1
и перейдем к интегралу:
1 / 1 \ Ч +Г^Г“-( "Г + 1)
ехр {в(іп Г + —1 ) — 1 } , Лг
Ут + 1 V лП~'
!= Г е-*г/г*(1 + о(1)).
2 л _А____
-/Кг«)
п ( п , л\ п ,
В силу соотношения У “\у + 11 ~ ~ т п интеграл,
деленный на У2л, стремится к 1, и поэтому
вХрМіпГ + ^-О-і і .г„ег-„-Ф.(П)----------( 4 71--------------
У "г
+ 1
1
У ІП Я *
Суммы Ф,(п)' и Ф3(п) оцениваются стандартным обра-8ом: каждый член заменяется на максимальный/который находится из условия того, что {кп/к\} унимодальна и^ее максимум достигается в интервале (г — Уд, г+Ул).
Ч. II. КОМБИНАТОРНЫЙ АНАЛИЗ 221
Поэтому
<»>- 4Т У- Т 2 7 ?< Т ? (Г - УЪ <
Ь=1 Ь=1
<Т^ЬИ1..4ЧН^-)1
ехр|п (ь г +К7— і) — і| У г + і
1^7 + 1 У^Н
X
х«р{-4т(7+ 0}~ф.(»)/5«4.{-тт(т+ 01-
«=о(Фа(п)).
Аналогично
Ф,(«)<е 2_Ж“е2 Ж<егМ--1'-У'1^<
к~>г + Уп ^ ^2 2
^ ехр{Л(Ьг + 1~-1)} , , п, р
УГУН 2 г ІТ + V/
ехр{«(1пг+1~-1)-1} ,2 Л |/у 4-1 ^
_ ^
У у+і 1/2я
х кр{-у7(7 + *)}~ф‘^Уя Уп]г>" х
X ехр{-{у(і+ і)} =» о(Фг(п)).
Таким образом, мы доказали теорему.
Теорема 1 нения х 1и х == н.
У*' с
Теорема 14. Ф(п) ~ ~7==^-, где г — корень упав-
у 1й п
ЧАСТЬ III ГРАФЫ И СЕТИ
Теория графов и сетей может быть отнесена к конечной геометрии. Геометрическая интуиция играет в ней существенную роль как в предвидении, так и в получении результатов.
В данной части содержатся некоторые факты из трех направлений: проблемы реализуемости одного класса
объектов в другом, метрические вопросы, касающиеся графов и сетей, и структурные особенности этих объектов.
Глава 1
ГРАФЫ
§ 1. Реализация в евклидовом пространстве.
Изоморфизм
В дальнейшем мы часто будем пользоваться понятиями «множество» и «набор». Термин «множество», имеет общепринятый смысл. Под «набором» здесь мы понимаем неупорядоченную систему объектов из некоторого множества, в которой один и тот же объект может встречаться несколько раз.
