С.В. Яблонский - Введение в дискретную математику (1060464), страница 31
Текст из файла (страница 31)
1»-й Л/3 2й — 1 2й — 3 1 ( и (2й — !) (2й — 3)...1 2й 2й — 2'''2,) 2 2й(2й — 2) ...2 3 и при и 2й+$ л/й л/й з(п х/1х — ~ 31п хдх * 3»+1 2й ( 2»+1 ) 3 3 Л/3 2й 2й — 2 2 ( . 1 2й(2й — 2) ...2 2й+ 1 2й — 1 ' ' ' 3 ) (2й + 1), (2й — 1) ... 3' 3 Отсюда получаем л/й (л/й » -1 Х» ~ зйпй х/)х~ ) з1п хг(х) 1» Г ° 3»+1 3 3 (2й+ 1)Г(2й — 1) (2й — 3) ...1]3 2 ( 2й(2й — 2) ... 2 Поскольку в процессе интегрирования О я х < п/2, то 0( з(пх<1. Мы имеем з(п'»+йх Я; з(пй»х ~ 31пй» 'х Л/3 л/й Я13 ) з(п'"+'хай~ ) 31пй»хй:~, ') шпй» 'хдх. 3 3 Оценим величину Х»1 л/3 Г л/3 '( -1 1~2.»- ~ з(пй»хй(х~ ~ з(пй»+йх )х~ 3 3 Я/й ! л/3 -1 3 ~з(пй» 'х/1х~ ~ з(пи'+'х/1х) -1+ — „.
1 3 ч. 11. комвггнзтогныя лнллггз 2!1 Отсюда следует, что Х,- 1 [при /е- ), ~у- [. 1 2/с(2/г — 2) ... 2 „'~.[/ь- (2а — ц (2а-з) ...! ! [2л (2а — 2) ... 2[г л~ » [/ь (2/г)! и, значит, 2гг (/ г)9 = Ипг — ' л г/л (2/г) ! Теорема доказана. Теперь остается вычислить константу а. Возьмем вы- ражение ! 2гл (и!)г лл / л! ~г -[/2л (2л)гле-гл / (2л) ! )/2 )//и (2гг) ! л „Г'2 Мы имаем л„л г [[гп = ~ ~~„Р2 а с другой стороны, в силу формулы Валлиса лл Пто " Ул.
,„')/2 () л) л! [/тл лл "'(" — ")~ г ию~-~~ ~'( — л"- В частности, при четном и и /е - и/2 имеем () .=- 2л ) — [вариант формулы Валлиса). л/2) ~~/йл/и 2. Если взять й ° (/г/2)+т, где [т[ <а[и)уи, то при определенном ограничении на рост а[/г) можно асимпто/л) тическому выражению для (а/! придать более компактный внд. Теорема 11. При [т[ ( а [и) У/г, еде а (/г) = о [/г"'), и/аеет лгесто соотношение ([л/2[+ т ) )/л гг/2 Отсюда а г/2и.
Асимптотика (/г) 1. При л- и и — й- из формулы Стирлинга получаем ч. Б. комвинлтогный лнллиз га Доказательство. Положив 2 +г р~+ г, выполним преобразования 1нй" (л — й)" " ( — "+ г')1н( — "+ г')+( —" — г')1в(-" — г') -(-,в+") 1в-2" +(++г)1о(1+")+ +(в,)1 в +(в ~)1 (1 2г) Множители вида 1п(1+ х) заменим куском ряда так, чтобы погрешность была о(1). Для этого достаточно взять разложение .В 1в(1+ х) х —,— + 0(х'), так как ло( — "',) -О( — "';) 0(1).
Тогда, учитывая также, что !г — г'1<1 и г о(л'"), получим ась ( Цв-л 1н в +(в + ') (1+2')+ (Ф вЂ” ')1 ( 2"') +(- —. )( —,)+о(1)- в 2г'з в 2гз л 1п — + — + о (1) = л 1н — + — + о (1). 2 в 2 в Отсюда получаем в 1 2в „3/ Теорема доказана.
ч. и. комвинлтовный лнллиэ 212 Т е о р е м а 13. Пусть а ( Ь. Тогда — (ь)-~е * '()з. [;— ]+ — '," лье[-", ]+"— " Д о к а з а т е л ь с т в о. Пользуясь теоремой 11 и по2г 2 (Ь вЂ” (л(2О лагая з — = ~/л )гл , получим [-", ]+' —," ллл[-,"]+ —," [з]+'— "лзл[;"]+~— ," гз/з 2 е ь чллз -зз/3 1 -Мз Ы+' — ","азл["-,]+"— '"," 2(г+ Ц 2г 2 так как Ьг — ., „, ,-. Теорема доказана.
)г л )гл (гл 3 а м е ч а н и е. Доказательство теоремы может быть обобщено на случай, когда о =-а(п) и д = а(п) (а(п)- ). Тогда 4:» (",)- -]-а(л) — лзл[-]+а(л)— а(л) +щ Г,з(з 1 Г,зй — е ()з — ) е Ыг * 1. ')/2п ° ~(2п 3 Аенмптотпка Ф (п). При нахождении асимптотики для Ф(п) можно исходить из представления Ф(п) в виде бесконечного ряда (формулы Добинского) или иа выражения Ф(п) в виде многочлена (30). Запишем формулу (30) несколько иначе: л Ф()-))",(2 — — +--... +(-1)— 1 1 лА 1 1л 1( г( (л — л)( ) )(( ' ь 1 2!7 ч. и.
комвиеьтовныи Анализ !п (й+ !) Поскольку Функция о 1, монотонно возрастаю1п ~1+ — ~ щая по й, то в случае: /Р (й+ 1)" 1и (й+ 1) )и й а) — „( + имеем и) ) й ( ) 111+1) 1~1+ ! ) 1пй / (й — 1)" )Р т. е. и) ~поэтому „( — ! и т. д.); 1+~=-)) ' т. е. !и (й ! 2) / (й ! !)и (й ! 2)о ! ! 1 1 1 (й 7- 1)! (й + 2)! ' '" )' 1п ~1+ — ~ й+ 11 в) — — из строгой монотонности й" (й+ 1)" 1п (й+ !) й! (й+ 1)! ! 1! 1п~( + — ) й! (й — 1)" йо (й+ П" (й+ 2)" следует, что -~ — ( — и — ) — и т.
д. ( — 1)! И (Ф+ !)! (й+ 2)! Обозначим через й, наибольшее значение Й, для которого й"/й! максимально. Произведем оценку числа Йо. Очевидно, (йо !) йо (йо + 1) (йо 1)! йо! (йо + !)! и 1п (1+ — ) ) 1п й„ 1 о и 1п (1 + †„ ) ( 1п (йо + 1). 11 о Так как (см. (3)) 1п (1+ — ) ( — „ то и '()оо — 1)1п)оо >()оо — 1)1п(й, — 1), 2И ч.
и. БомнннАТОРный Анализ а так как (см. (4)) 1п(1+ — ) ) о ), 1 е 2 то и((йе+ —,) 1П(Ье + 1) ((/с, + 1)1п(йд + 1). Поэтому из монотонности функции х1пх следует, что й, отличается от единственного решения г уравнения п х1пх менее чем на 1, т. е. )г — й,! <1 или в силу целочисленности й, й, = [г~ либо й, ]г~. Положим далее а(п) г- )и и Ь(п) г+ уп. В силу того что г ° 1 „(1 + о(1)), при достаточно больших и будет 1 < а (и) < Ь(п) < и. Условия а(п)- и и — Ь(и) ° также выполнены. Сначала займемся изучением Ф.(.) --, Х Я а(а) аз еще) Заменим в Ф,(п) члены й"/Ь1 их асимптотическими выражениями, получающимися по формуле Стирлннга: 1 аа "ьз) — =й 'е (1+ о(1)), )/2п и положим е й — г (здесь параметр е может стать не целочисленным, но Ле Лй 1).
Тогда получим 1 аа а-й— Х вЂ” „— Х Ь йей(1+ 0(1)) а~и)сьамп) ~ ~-1пеьс~+)ги 1 — (г (- е) 'е"+'(1+ о(1)). -у аа)атз ч. н. комвннАТОРныи АИАлиз 219 Заметим, далее, что г + 8 — ехр(1п (г + 8)) ехр ~1П г ~1 + — 1) ехр(1П г + 111 ~1+ — )). (1и е 1 Учитывая соотношение ~ — „~ 0~~ -), разложим в ряд 1п ((+ — „) и оставим в разложении столько членов, чтобы опт%ток, умноженный на~я — г — 8 — 2) п, был бы равен о(1). Для етого достаточно взять два первых члена разложения, т.
е. 1 и ( 1 + ) ь ~ ~ + 0 1 ~ ) ибо ПΠ—, О = о(1). Таким образом, мы получаем 1 ьь — г ь ь+ь (г+ 8) е 8 1 ьз) / ь 'ь ехр((1пг+ — — — — ) ~п — г — 8 — -)+г+8+ о (т)), 2,8) ~ г/ Проиаведем далее преобразованпе показателя: с 8 ! 1811' 11 1пг+- — — — ) ~п — г — 8 — — )+г+8 2 гз,)~ 2! ьью аь ь П1П Г + — — — — Г1Пà — 8 + — — 81ПГ— 21~ 2г 8 Э 8 ЬЗ вЂ” — + — — —,1пг — — + — + г+ 8.
г 281 2 2. 4„8 В нем, в силу соотношения г1п г= и, выполняется рань и' ь ь венство — — 81пг, а члены — „— и —,, равны о(1). Г 2гз 2Г 4гь 220 ч. и. НОМБНИАтоэный АнАлиз Продолжив преобразование, получим ез /л и(1пг+ — — 1) — — 1пг — — ( — + 1) + о(1). !лг / 2 2г(,г В результате получаем ехр (л (1в г + — 1) — 1) +1 л 3 — г+1 Х ~~~~~ ехР( — — ', ( — "г + 1)) ", (1+ о(11). -УйеееУй В последней сумме произведем замену переменной, взяв 1/г-"„+1 /-"+ 1/ „1/„ г г г и перейдем к интегралу: -р(л(1о г+,—.'г-1) — 1) ~'л ) е * /ее(з((+о(1)). '"-~-(-") В силу соотношения )г — ( — + (г1 —, 1п и интеграл, г г г деленный на У2я, стремится к 1, и поэтому е р(~(1в + 1„г — 1) — 1) Ф, (и) У вЂ” "+1 Г г е лег " 1/1п л Суммы Ф,(и] и Ф,(и) оцениваются стандартным образом: каждый член заменяется на максимальный, который находится из условия того, что (й"//еИ унимолальна и ее максимум достигается в интервале (г — Уи, г+ Уи).
ч. 11. Номкинатоэный АнАЛиз Поэтому Ф, (и)- — )„—, - —,~~ — < — — '(т — Уи) ~ А=1 А-1 ехр(л(1п т+ 1— — 1)~ ехр(л(1п т+)пг — 1) — 1) атее )à — + 1 ~/' л '~Б Хехр( — -( — "+ 1)) Ф,(и) $/ — ехр( — —,— "(-"-1-1)) ° о (Фв (и)), Аналогично ал ал Ф,(и) <в ~' —, в,)'„А1 <е — „',(и — т — ртй)к-,, ь>е+ул ь "е е*р (" (1п г+ )и „вЂ” 1) ) 1 л ~, ив, ехр( — — — (- + 1)) 1 'ф/ и вхр(л(1пг+1— — 1) — 1) в л хе — +1 ЮВ 1~-+ — Х г Х ехр( + 1 Фв(и) — у и!пиХ Х ехр( к — ( — + 1)) о(Ф (и)).
Таким образом, мы доказали теорему. г' тле Теорема 14. Ф(и) =, здв т-корень рравр'1п л ненни х1пх и. ЧАСТЬ ГП ГРАФЫ И СЕТИ Теория графов и сетей может быть отнесена к конечной геометрии. Геометрическая интуиция играет в ней существенную роль как в предвидении, так и в получении реаультатов. В данной части содержатся некоторые факты из трет направлений: проблемы реализуемости одного класса объектов в другом, метрические вопросы, касающиеся графов и сетей, и структурные особенности »тих объектов.
Глава 1 ГРАФЫ 3 1. Реализация в евклидовом пространстве. Изоморфиам В.дальнейшем мы часто будем пользоваться понятиямп «множество» и «набор». Термин «множество» имеет общепринятый смысл. Под «набором» здесь мы понимаем неупорядоченную систему объектов из некоторого множества, в которой один и тот же объект может встречать-' ся несколько раз. Определение. Множество й (ае а„...) и набор И неупорядоченных пар объектов (а,„, а;») из й называется гра«бом Г. Объекты множества й называются вери«иноки граЯа, а объекты набора И вЂ” ребрами граЯа. Про ребра (ае а,) будем говорить, что они соединяют вершины а~ и а~. П р и м е р 1. Пусть й = (а„а„а„а„а„а„о«), И ° ((ао а«), (а„а,), (а„а,), (а„а,), (а„а,), (а„, а,), (а„а,)).
Тогда й и И определяют граф. В случае, если мнок«ество й и набор. И состоят нз конечного числа объектов и пар, то граф Г называется конечным. 223 гл, ь РРАФы Пусть а, и а, — произвольные вершины графа Г. О п р е д е л е н н е. Система ребер графа Г А...з ((а<,, а<,), (ачо а; ), ..., (а..., а,,)», где а,, а, и а,, а„называется путем, соединяющим вершины а, и аь Для любого ребра, принадлежащего пути А«Г<З< МЫ буДЕМ ГОВОРИТЬ, Что ПУТЬ Аа<щ ПРОХОдит Чзрзг зто ребро.
Аналогично, если вершина а принадлежит некоторому ребру пути Ад я < то говорим, что путь А, проходит через вершину а. Определение. Путь А,,„,, не проходящий дважды через одно ребро, называется циклом, если а< = а„В частностн, цикл ((а„а<)) будем называть петлей. Определение. Граф Г называется связным, если для любых двух различных вершин а, и а< графа Г существует путь, соединяющий зги вершины. Легко видеть, что граф из примера 1 является конечным, несвязным и содержащим петли.
(Ясно, что свяаный граф не содержит «изолированных» вершин, т. е. каждая его вершина прпнадлежит по крайней мере одному его ребру.) Введенное нами понятна графа является весьма абстрактным. Оно родственно понятию одномерного комплекса в топологии. Для последующих рассмотрений желательно иметь какую-либо наглядную интерпретацию графа. С этой целью будем рассматривать в евклидовом пространстве фигуры определенного вида. Как<лая из таких фигур 8 состоит из различных вершин Ь„Ь„... и кривых (являющихся либо дугами окружностей, либо отрезками прямых), каждая из которых соединяет некоторые пары вершин (Ь<, Ь,) (возможно и вырождение Ь, Ь<).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
