Научная литература
booksshare.net -> Добавить материал -> Математика -> Яблонский С.В. -> "Введение в дискретную математику " -> 58

Введение в дискретную математику - Яблонский С.В.

Яблонский С.В. Введение в дискретную математику — Наука , 1986. — 384 c.
Скачать (прямая ссылка): vvedenievdiskretnuyum1986.djvu
Предыдущая << 1 .. 52 53 54 55 56 57 < 58 > 59 60 61 62 63 64 .. 104 >> Следующая

Я/2
\ sin” xdx=*
V
о
ST/2
«= — sin71”1 X COS X J" 2 + {n — 1) j sin”'2 X COS2 X dx =
0
ЗТ/2 Я./2
?= (n — 1) I* sin"”2# da: — (ft — 1) j* si nna: da:.
о я/i
Разрешая полученное равенство относительно J sin” x dx,
a
14 G. В- Яблонский
210 Ч. II. КОМБИНАТОРНЫЙ АНДЛИЗ
/
получим 1.7
Я/2 Я/2/
^ в! пТ1 хйх — П п ^ ^ втп~2х (1х. о о
Данное рекуррентное соотношение дает при п = 2к
Л/2 Л/2
Г * 2^ э 1 Г ? 2/;—2 1
I вт хах «= —^— I 81п х ах — ., й
о о
я/2
2Л- — 1 2А: — 3 1 С _ л (24—1) (2А — 3)...1
2А- 2Аг - 2 * * • 2 Л ЙХ 2 2/с (2к - 2) ... 2 о
и при п = 2к + 1
Я/2 Я/2
j 81Пгк**хйх = 2^71 J .
о о
Я/2
2к (2/с — 2) ... 2
2/с 2/с — 2 2 1.
2ft +,1 2ft - 1 * ‘ ' 3 J 8Ш Х dx — (2
(2*+ 1). (2ft —1) ... 3' о
Отсюда получаем
Я/2 /Л/2 \-1
— j siii2fta; dx I | sin2fe+1 xdx 1 =
0
= |(2fe+ 1)[Щ
— 1) (2ft — 3) ... 1
2ft (2ft — 2) ... 2
Поскольку в процессе интегрирования 0 < х < я/2, то G ^ sin х ^ 1. Мы имеем
sin?ft+* х < sin2k X sin2k_i X
и
Я/2 я/2 я/2
j* sins?l+1 j sin2hxdx^ j sinik~xxdz.
0 0 0
Оценим величину Xh;
Я/2 /Я/2 \— 1
1 ^ 13 j* sinEfe x dx f J sin2fe+1 x dx) ^
Я/2 ! л/2 \ —1
^ j ^ sinaA+1a;d:M = 1 +
0 ' 0 /
M. 11, rtyjyibUiiAiUFilbdH АНАЛИЗ 211
Отсюда следует, что К 1 (при ft-*- °°), а, значит,
1. 1 2А (2к — 2) ... 2
Vn = lim —гг -777------------.. 7777 0;-г =
к — 1) (2it 3) ... 1
i \2к (2k ~2) ... 2|а 22ft<Ar])3
= Urn -рг-!—5—-ту-; — = hm -.
. fe^colГк (2А-)! ft^«,VfcC2A)l
Теорема доказана.
Теперь остается вычислить константу а. Возьмем выражение
\2 УТп (2п)2Пе~*п 1 22п (п!)а
__ ( п] V _
V V2 \ "j/я ппе—fl / (2«)! 1/2 l/« (2ft)!
Мы имеем
„2
lim
«-*00 ?2ftV2 1/2
а с другой стороцы, в силу формулы Валлиса
а\ г~
lim /л.
71-» оо а2П у Z
Отсюда а = У2л.
Асимптотика
1.При ft -? оо и гс — ft -*• 00 из формулы Стирлжзнга получаем
= ftl _ Уй пп
W *1 (« — А)! ~ У‘2кк {п — к) кк(п — k)n~h *
В частности, при четном пик — гс/2 имеем
/ п \ 2П
| | ZS/ —^ (вариант формулы Валлиса).
\n/zj 1/дп/2
2. Если взять ft = [n/2]-fr, где Ir!<ct(rc)Vrc, то при определенном ограничении на рост а(гс) можно асим лто-
тнческому выражению для j придать более коми акт-ный вид.
Теорема 11. При !г|<а(гс)Тгс, где а (га) = о(ж1/6), имеет место соотношение
Ч. 11. ДШЬИЙАіиґИШІ АНАЛИЗ
Доказательство. Положив у + г’ = |^у| -Ь г2 выполним преобразования
Ь А»(» - к)~* = + Г')1п(| + г') + (|_г')1п(|-г') =
-(т+-'),”Т + (т +''М‘ + ?) +
+ (т-'-’М + (т-''М1-*}
Множители вида 1п(1 + :г) заменим куском ряда так, что-бы погрешность была о(1). Для этого достаточно взять разложение
1п (И-з)«*-^- + 0(*»),
так как
Тогда, учитывая также, что 1г — г'|<1 и г —о(пг/3), получим
Ыкк(п-к)п^ =
_„1п!+(? + г'М1 + ? )+(|-Г')1п(1-^)-
-пЪ^ + [т + г’)[^~гУ) +
— п 1п у + 4- О (1) = п 1п ~ -ь —? +0 (1).
Отсюда получаем
у пп/2
( П \ 271 — 2гУп
Ми/21 + г / ~ *1/^72
Теорема доказана.
Ч. II. комбинаторный анализ 213
Часто вместо величины г берут г = 2г/Уп. Мы приходим к соотношению
([?
П j _!_ "1/° 5Г I V31п№
2П -*2/а е <
С).
Асимптотика для суммы
Сначала установим один результат, характеризующий распределение вершин и-мерного единичного куба но слоям.
Теорема 12. Пусть а (и)—произвольная (сколь угодно медленно) растущая положительная функция. Тогда
Ь2 _(*)-*•
[?т]—
Доказательство, Пусть &с. 5* п/2. Тогда
л — к
2
Т<
<
К
2к0-,г
ко
С другой стороны {см. рис. 8), из сравнения площадей имеем
(О (2А'° ~п) < (п ?- 0 + (»-к+0 +'" + 0 < 2"
Отсюда
П ! \
2(:
К 2”
<
Й1Ч
ч. 1л. пшьишнигшаи а л а. ни
Положим къ = |^21 + |а(и) V п|. Тогда
2" .2 ( * ) ^ 8аЗ (п) °*
В силу симметрии
П-Ь#,
2* 2 (<)<8<Л» ^0'
Отсюда, учитывая, что 2 ( /) = 2", получаем требу
емое.
Доказанная теорема утверждает, что почти все точки п-мерного единичного куба сосредоточены в слоях с номерами к такими, что
[т] — а (”) 1^п < & + а(п)Уп,
где офг)“Данная фиксированная растущая (сколь угодно медленно) функция, т. е. в слоях, «близких» к среднему слою.
Более точные оценки получаются, если использовать асимптотическое выражение для (д.).
Ч. П. КОМБИНАТОРНЫЙ АНАЛИЗ 215'
Теорема 13. Пусть а < Ь. Тогда
ь
2п
2 СИл
[?ИгЧг1-"'
1+^
Доказательство. Пользуясь теоремой 11 и по-2г 2 {А- — |п/2|)
лагая 2 — =-----—7=---г получим
у п у п
— У 1п\ ~ — У 2пе~г*/*
2”гп] аУП Гп] луД*' 2П\*\.аУЪ Гп] ьГп Упп12
1т]+—*лк<Ьг~г И—
в V е-#к _2_ _
“у2я[тНМг]+^ У:"
- -4= У е~г2/2 д2 -+ -4= Г е-г?/2^.
42лт 0уи г«] ь/п ^2ла
[2]+-Т* [а]““Т"
А 2(г+1) 2г 2
так как Дг = ———----~у= = гт=*. Теорема доказана.
р гс у гс р гс
Замечание. Доказательство теоремы может быть
обобщено на случай, когда а=*—а(п) и Ь = а(п) (а («)->• -*-«>). Тогда
2 Д)~
а(гс) +оо
~гт= ( е-А',йг ~ г4= Г е'^Чг-и
УЫ .) ч У2п ^
—сс(п) —со
Асимптотика Ф (га).
При нахождении асимптотики для Ф(га) можно исходить из представления Ф (га) в виде бесконечного . ряда
(формулы Добпнского) или из выражения Ф{га) в виде
многочлена (30). Запишем формулу (30) несколько иначе:
ф(")“2(1 — ТГ + Щ--"- +(-1)п_* [п-к)\)ж-
216 Ч. П. КОМБИНАТОРНЫЙ АНАЛИЗ
Предыдущая << 1 .. 52 53 54 55 56 57 < 58 > 59 60 61 62 63 64 .. 104 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed