Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 56
Текст из файла (страница 56)
Показать, что: и — 1 ') "-"и(') = П('+ ') =о 2) р(в, Й) = р(п — 1, Й вЂ” 1) + (и — 1)р(п — 1, Й). 3 5. Асимптотические оценки и неравенства При оценке роста функций употребляются следующие обозначения. Запись !р(и) = 0(ар(и)) при т е Х означает, что существует константа с такая, что ~~р(и)~ ( с~ца(и)~ для и Е Х. Если !р(и) = = 0(1р(т)) и ф1(и) = О(!р(т)) при и Е Х, то пишут !р(х) ~ф(л) при и Е Х. Запись 1р(и) = о(ф(и)) при л — э а означает, что Нп! = О. с — аа ф(я) 278 Гл. 1Ш. Элементы комбииатиорики Говорят, что функции у(х) и ф(х) асимптотически равны (обозначение: ~р(х) уз!х)) при х — ! а, если у(х) = ф(х) + о(ф(х)) при х — ) а.
При разного рода оценках полезна формула Стирлинга и! '— чг2хп пас Лля более точных оценок используются неравенства ъ'2хпп" ехр( — и+ —, ~ < и! <,(2хпп" ехр( — и+ ~. 12) 5.1. Локазать неравенства.*): 1) пп~з < и! < ( — ) при и > 2; 2) !2п)! < !и!и+ 1))п; 3) (1+ — ) <3! 4) ( — ) <и!; 5) (~!)~ < ( ), >1; 8) (2п — 1)!! < и"., и > 1; 9) и! > е "и" 10) (1 + о) и > 11 + ап) при — 1 < а, и, > 1; ( —;".',)и". ( — ".') 5.2.
Локазать неравенства: 1)(2 — ) <( )< — ( — ), п>й>1; 2) ( — ) <( )<,, п>й>0; 5.3. Используя формулу Стирлинга, показать, что при и — ~ со справедливы асимптотические равенства: 1) (2п — 1)0 — у'212п)пе "; 2) ! ) — 4"; п l з/ппп п! 2„ГЗ Зп ([ — )!) (п — 2[ — ))! (т+1)(т+2)...(т+п) 14 4) ' ' ' ' — ', и'" для целых неотрицательных Й и т; (2п) !! /и (2п — Ц!! Ч 2 ") Символом !2п — 1)0 обозначается число 1. 3. б .... (2п — Ц, а (2п)!! = 2 4. 6....
(2п). 279 у" Ь. Асннптогпнчесние оценка и неравенство 5.4. Показать, что при и — ~ оо справедливы следующие асимптотические равенства: о г 1)~ 1 (и) 2 2)~( п ) 1 2о я=1 е 3) ~ ~( )о'гян †„ « + о)", О < г < к; и 4) г Ь( ) — ~.4". такие числа, что О < а~ < Ья < сь < 1. 5.5. Пусть Ье, Ьг, ..., Ь, Выяснить, верно ли, что: 1) «~а)" <~н©Ь.<«+ )"; я=о и 2) «с)п<~;( 1) (п)Ь,<«а)п 5.6. 1) Показать неравенство Чебышева в следующей форме.
1 Пусть А = (аы аг, ..., ап) совокупность чисел, а = — у аг, п о г=г Ргг = — гг (аг — а) . Тогда доля Ьг тех а„для которых )аг — и~ > 1, г=г не превышает Ра,ге~. 2) Используя неравенство Чебышева, показать, что (п) Е (1) ' — ') 0<ь<пгг — г нгг ог'гьг;/о<я<о 3) Показать, что ~ — ( ) 2 ЬЫ я=г 5.7.
С помощью формулы Стирлинга показать, что: 1) если к — — = о(ггг1~) при п — г оо, то 2 ()- "" п') 2"г' — ггь — ~'Пг г "/ нг2яп 2*) если а > О и й — — = о(пгрз) при п — г оо, то а -~- 1 п1 г„. «В- а)"г' 1 (й(а+ Ц вЂ” ап)г 1 () = )а ехр г— г х нГ2я па 1 2 ап х (1+ Р(1+ (й('+ ') 'и) )) 280 1"л. 1гЖ. Эаементы комбинаторики 3 ) если а>0, й<т, Ь=, ил=(й — — )6, тт= и а-Ь1 р на ,/агг а г- 1 (- ) т — ~й, ть — ~со, т„,й-+О, т — Й вЂ” ~ос при и-+оо, то а -~- 1 ) ~и (.) . (.
Е"' (е ~л* е=ь 4) если а > О, х — л оо и х = о1п~ге) при и — > оо, то )а' е ' ~ 11+а)и. оа геа и> -~-г ~-1 а-~-1 5.8. Пусть 0 < Л < 1, Л„целое, р = 1 — Л, и пусть С1п, Л) = Л-л — о . С помощью формул 11) и 12) показать, что: 1г л,г22кХри 1) (Л ) С1п, Л) при п — ~ оо; 2) С1га Л) ехр ( — ) < ( „) < С1п, Л); 3) — С1п, Л) < ( ) при гг > 2; '( ) к©. (") "."- л=.ли 5) ~ ( )<Л л"р "" при Л>-; л=ло, б) ~~~ ( )<Л л"р ои при Л< —. о<ь<ла 5.9.
ПУсть й и и натУРальныо числа 1й < п). Показатли что: оо й — 1 1) 1п)л = пл ехр и=г г=г 2) если /с = о1~/й) при п -+ со, то 1п)ь — и"; 3) если й = оЯ при и — л оо, то для всякого т, > 1 е е 1п)л, = п~ ехр — ~~~ + 0( ) ,,И +Ц кг бе 4) при п — ~ со и й = о1пз'4) 1п)ь = и" ехр — — — — +о11) 2" биг 5.10.
1) Пусть й = й1гг) и е = е1п) таковы, что при и — > оо е = о1лг%). Показать, что (". ')/©-(-.")о 281 2) Показать, что если в = о(й"Д'ва!), то 5.11. Пусть в = в(н) и й = й(н) целочисленные неотрицательные функции натурального аргумента. Показать, что: 1) если в+ Й = о(пз7~) при н — з сю, то (.— )И-и) [-"- ""[ 2) если хз + !сз = о(п) при и -+ оо, то ( .')/©-' и р[ —" — '— ", — ',) (",")/(!),(-'— '), н) й+2в. 5.12. Пусть Д(х) -- непрерывная, монотонно возрастающая на отрезке [п, т) функция. Показать, что 5.13.
Используя предыдущую задачу, показать, что при т — ! оо справедливы следующие соотношения: 1пй т1пт — т+О(!пт); !ен = ти"т~ + 0(т"), и ) 1; 1 и -1- 1 с — константа: ' =1и +0(ч. 1) ~ 2) ~~~ й=.1 з) ~ ь=з 4) ~~~ 5) ~~ ь=-1 5) ~ ь=и 7) ~~ 2" о. Асимптотинесние оценки и неравенства 2 (и) < ~~~ Д(Й) — /Дх) с!х < ~(т). и.=о 1 = 1п1п1пт+ с+ 0 ( ), / 1 Й 1п Й 1и !п Й т 1п т 1п !п т 108 Й 1 2 /!Окт ~ = — !о8 т+с+ 0 ~ 8 ), с - - константа; й 2 т.
1 1 / 1 — с + — + 0 с. константа й!пад !пгп (,т!нет)' 282 Гл. 1 Пй Элементы холгбинаторггки 5.14. Последовательность 7р„) определяется рекуррентным соотношением р„= р„г — арг„' „ро = 1, О < а < 1, Р > 1. Показать, что; Ц О < ри < 1 (гг > Ц; 2) р„монотонно убывает с ростом п; 3*) Р„(а(13 — Цп)'Д' Лг при п — э со.
У к а з а н и е. Воспользоваться норавснствами н Р и Ря-г Ря < / егя < Ч ~ Ре Рг-г и = -Š—. ~', Е ,'г я=г ар — ат' — ар 5.15. Ц Показать, что решение уравнения хе' =1 имеет вид 2) Показать, что решение уравнения е'+ 1пх =1 при 4-+ со имеет вид (~ы )') и=1п1— 2) если Лг действительный корень кратности г и 4) П) г) П)П вЂ” л )' П вЂ” Лг)" РП) многочлены, Яг(1) = де+ дг1+... + е„гр ', то г — 1 а„( — Ц"(Лг) " '~~г пг( .)Лг.
где Щ (е), 7,ге (1) при п — г оо г=е 5.18. Пусть А(1) -- производящая функция последовательнос- ти (ои). Найти асимптотическое поведение а„при и -э со; Ц А(1) = .,; 2) А(1) =, .; 3) А(1) = 2Р 41г+ 1' ) 614 171з+361г 221+4' 5.16. Пусть Р"1х) > О и е'71г1 = Х(е) -~-1-~-0(Ц, О < 1 < оо. Показать, что 7(е) = — + 0(г ) при 1 — г со.
1п1 5.17. Пусть производящая функция А(1) последовательности 1вн) имеет вид А1е) = с2Я!РЯ, где Я(г) и РЯ многочлсны с действительными коэффициентами. Пусть Лг — наименьший по абсолютной величине корень многочлена Р11). Доказать, что: Ц если Лг .-- простой (не являющийся кратным) действительный корень, то при п -э со ( Л ) г егг е=л, ' 283 2" 8. Асимптотипесиие оиеиии и иеравеисгпва 1 — зс 21~ -~- 44 -1- 8 6) А(1) — (8сз 1)(сг ц г 7) А(1) = (сг + 24 2)г г 2зз — 1г84 — 0,02 (2зг -Ь 1)(ег -Ь 1,44 -Ь Ог49) 5.19. По заданному рекуррентному соотношению и начальным условиям найти асимптотическое поведение а„при п — ) со: 1) а„ег + Заве с + 2а„= О, ао = 1, аз — — 2; 2) а„= да„, + р(1 — а„,'), ао = 1, р+ д = 1, р, д > О„ 3) а„е.г+2а„4г+4ап = О, ао =О, ас = 2; 4) апз з — 9ап, г + 26а„ез — 24ап = О, ао = а, = 1, аг = — 3; 5) апе4 — 4ап-;я+ 4ап = 2, ао = 1, аг = О, аг = 2, аз = О.
5. 20. Найти предел последовательности (ап), заданной рокуррентными соотношениями: 1) апсз =(ап+Ь/а,„)/2, Ь>О, ас >О; 2) ап+з — — (2а„+ Ь/аг,)/3, Ь > О, ае > О; 3) ап сз = (Ь вЂ” аг)/2, О < Ь < 1г ао = Ь/2. 5.21. Пусть а, удовлетворяет соотношениям ап>2 " г+(и — 1) 4 и-~-г ап+г<2 з+(п+1) 4 и з+ап(( — ) + + (и + 2) 2п+г + 4а ), аг — — О, аг = 1/16.
Показать, что; 1) ап < 1/8; 2) ап < 9(3/4)"; 3) ап = 2 " ~(1+ 0((3/4)")). 5.23. Пусть Ь, п целые. С точностью до 1 вычислить Ь = Ь(п), при котором функция /(и, й) принимает максимальное значение: 1)/(п„й)=( )2 г 2)/(п,й)=( )2" Я г (1 — 2 г)" 5.24. Найти минимальное и максимальное значения выражения кнк функции от с (О < т < Ь < и); с, й, и целые.
5.25. Найти асимптотическое поведение при и — в сю величины д(п) = шш /(и, й), Й целое, осли; 0<з<гг 1) /(и, Ь) = 2" " + 2г; 2) /(и Ь) = Ь 2" + — 2гп 1 Ь 5.22. Пусть последовательность (а„) удовлетворяет условию агг-сгп < а„ + а„„ аз > О. Наказать,что а„ < азп при п > 1. 284 Гл, гШ. Элементы комбинаторика 3 6. Оценки в теории графов и сетей Помеченным или нумерованным здесь мы будем называть граф, веРшинам котоРого пРиписаны пометки 1номеРа). ЧеРез 'Мп бУдем обозначать множество всех и-вершинных графов 1п-графов), вершины которых помечены числами от 1 до п. Через 'ае„„будем обозначать множество тех графов из 'йп, которые имеют в точности т ребер.
ГРаф из множества 'Уеьт бУдет называтьсЯ кРатко 1и, т)-еуафом. Графы С и 0 из 'йп считаются различными, если существуют две вершины у и Й, смежные в одном из графов, но не смежные в другом. ПУсть ~Рп1Р) обозначает число всех гРафов из 'лап, обладающих свойством Р. Говорят, что почти все графы обладают свойствами Р, если Ппз (1о„,(Р)ДЯ„~) = 1. Пусть т = т1п) целочисленная нси — и пп отрицательная функция, а 1о„т(Р) - число всех графов из 'Й„„„ обладаязщих свойством Р.
Говорят, что почти все 1п, т1п))-графы обладают свойством Р, если ч -и-1Р) еп1 6.1. Показать, что: 1) ~'6„~ = 2~а~;. 2) ~ '6„„, ~ = ( ~ е ) ) 6.2. 1) Найти число различных турниров с и вершинами, пронумерованными числами 1, 2, ..., и. 2) Найти число ориентированных псевдографов с и нумерованными вершинами и т дугами. 6.3. 1) Показать, что число графов в 'йп, у которых заданные а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
