Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 81
Текст из файла (страница 81)
5.16. Указание. Показать сначала, что С(С) = О(С) при С вЂ” С со. Тогда исходное равенство можно будет записать в виде всНс1 = С+ о(С). Пользуясь этим неравенством, показать, что С" (С) = 0(1), и преобразовать с.С С с! 1и С исходное равенство в е Н = С+ 0(1). Наконец, доказать, что у(С) = — + 0(-,') 5.1У. 1) Разложим А(С) на простые дроби: А(С) = + +... Лс — с Лз — с -1- В(С), где В(С) многочлен. Для нахожцения коэффициен— О(с) та сс умножим А(с) на Лс — С.
Тогда (Лс — С) А(С) = (с — Лэ)... (с — Л,„) ' — с)(л ) При С = Лс левая часть равна сс, а правая, . Таким образом, сс = Р'(Лс) — с)(л ) . Аналогично можно вычислить и коэффициенты с, (с = 2, ... Р'(Л ) 1 ..., т). Дробь можно разложить в геометрическую прогрес- 1 — С!Л„ 397 Гл. 1715 Элементы номбинагпорини сию (1 — — ) = ~ ~( — ) . Получаем А(С) = ~ — * ~ ( — ) -~- В(С).
=.о =о Отсюда для больших и имеем а„„„, + „, т ...->, „, сзЛ, сз сз сы 2) Рассмотрим сначала случай, когда Р(С) не имеет корней, кроме Лм а СС(С) имеет степень меньшую, чем степень Р(С), и Л~ не является кор— 1 нем СС(С). Тогда Р(С) = (С вЂ” Лс)", Я(С) = ~ ИС'. Разложение Р '(С) по =о степеням имеет вид ~-'()=(-» Л; ( — —,') =(- — „') ~(„") —,'„ =о А(С) = = ( — — ) ~ ( — ) ~ Ц,(~ С)Л',. Отсюда а„= ( — 1)" Л, бл "~ ~ д,(п ",.)Лм В обшем случае А(С) = Аь(С)-~- , где Аз(С) — многочлен, Я,(С) — многочлен степени меньС1,(с) 2.(С Л,.
ше г,. В этом случае асимптотическое значение для а„определяется козффипиентом при Со в разложении дроби СсЗз(С)С(С вЂ” Лз)"'. Задача сводится к уже рассмотренной. 5.18. 1) 2 . 3". Воспользуемся результатами задачи 5.17, 1). Многочлен Рз(С) = ЗС вЂ” 41+ 1 имеет корни Лз = — и Лз = 1. Положим Се(С) = — (1+ С), 3 1 1 3 3 Р(С) = Сз — — С 4- —. Тогда 3 3 с)(1/3) с1~ " с 4/9 Р'(1/3) 13/ 2/3 — 4/3 2) а„— — ( — ) ) . Ваименьшнй по модулю корень многочле- 13 (,2,) на 6Сз + 5С вЂ” 6 равен 21'3.
Используя задачу 5.17, Ц, получаем результат. »-~-з 3) ао — — С вЂ” ) (. 4) аз„= О, аг„ез ( — Ц" 2" 13 12) 5) Указание. 6С вЂ” 17С + 351 — 221+4 = 6 (С вЂ” -) ~С вЂ” — ) (С вЂ” 1-> 4 з з 2 3 + С чсЗ) (С вЂ” 1 — с чсЗ), и„— 3". 31 6) — 2" ~' 15 7) ( )(чсЗ вЂ” 1) " . Корни уравнения Сз+ 21 — 2 есть Лз = з/3 — 1, го С Лз = — ъ'3 — 1. Представив А(С) в виде аС -Е Ь сС + 4 (С вЂ” Л,)з (С вЂ” Л,)-" 398 Ответы, указания, решенпв найдем методом неопределенных коэффициентов, что а = О, Ь = 1.
С ис- пользованием задачи 5.17, 2) получим, что а„= (-1)гЛ," г (6( ) +Л1а( )) = !АЗ вЂ” 1) ( ). /10з +г е — зз 8) а„! — ) ) ). Наименьший по модулю корень знаменателя 7 равен 0,7 и имеет кратность 2. Заметим, что Е-!-1 2 Н вЂ” 0,7)г зег -!- 1 С использованием задачи 5.17, 2)получаем а„ ! †) 5.19. 1) а„! — 3( — 2)"). Пусть А!!) = ~~> а„!". Умножая обе части =в соотношения на !" н складывая, получаем, что А!!) — аг! — ав+ »эг -!- 3!(А(!) — ав) -!- 2!гА(!) = О. Отсюда с учетом того, что ав = 1, аг = 2, имеем А!!) = Г1 — !)Д2! + Зе+ Ц.
Корни знаменателя есть Лг = — 1)2, Лг = — 1. Используя задачу 5.17, 1), получаем, что а„! — 3( — 2)"). 2) 1)2. Так же, как и в задаче 1), находим, что А(!) = (2(1 — !)) ' -!- -г (2(1 — (д — р)!)) '. Поскольку д -~- р = 1, р, д > О, то !у — р~ < 1. Корнями знаменателя являются Лг = 1 н Л = 0 — р, !Лг! < !Лг!. Теперь с использованием задачи 5.17, 1) илн непосредственно получаем, что а„1)2. 3) а = !з!и — — з!и — ). 4) а 3".
5) а п 2" ,з1 з з) 5.20. 1) Наводящее соображение; если предел аэ существует и равен а, то нз рекуррентного соотношения получаем, что а = !а -Е 6)а)/2, или а = ъ Ь, так как а > О. Если ив = эгь, то а~ = (ав+ 6)ав))2 = = (ьгь-Е эгь))2 = ъ'Ь. По индукции легко получим., что а„= ъ'Ь. Рассмотрим случай, когда ав > Ь (случай ав < Ь аналогичен).
Покажем, что в этом случае а„убывает и а„> эгь при всех п > О. Если а„> ъ'Ь при некотором п>О,то а„~.~ — а = ((а„+ — ) /2) — а„= " < О. Таким образом, а„убывает с ростом п, а„— Ь= — (а„+ — ) — ГЬ= " >О. ! / 6 Л <а.— 6)' 2 ~, ав) 2а„ Следовательно, а„убывает и ограничено снизу. Значит, существует предел а = !!ш а„. Как мы убедились, этот предел равен ьеьй з- 2) Как и в задаче Ц, если предел аэ существует, то он равен чЬ. Рассмотрим случай ав < чь.
Так же, как н в задаче 1), доказывается, ззе. что а, монотонно возрастает и а„< убь при всех п. Отсюда следует существование предела а,. Если !!пг аэ = а, то., переходя к пределу в зрекуррентном соотношении, получаем, что а = чЬ. 399 Гл. )г111, Элементы комбонагоороко Отсюда вытекает, что если а„< 1/8, то и а„ог ( 1/8 при и > 3. 2) Пользуясь тем, что а„< 1/8, выведем из (4) новое неравенство: 131 "' Отсюда по индукции а < 9 ( — ) 4 1 гзз тг 3) Используя задачу 2), выводим из (4) а,ег < зз + бба„( — ) Пользуясь последним, получаем, что а = 2 (1+ О (( — ) )).
~~4 5.22. Индукцня по п. При п = 1 имеем аг = аг 1. Если а„< аг ° п, то а„+г < а„-6 ог ( аг(п -!-1). 1(п, й+1) и — й г. 5.23. Ц Рассмотрим отношение аь = ' = 2 . Ес- 1(п, й) й+1 ли й < (!о871обгп), то аь > 1, если же й > (!обо 1обгп), то ае < 1. Следовательно., максимальное значение /(п, й) достигается либо при й = = (!обг !обг п), либо пРи й = (!обг 1обг п) -!- 1. 2) Тот же результат, что и в задаче 1). 5.24.
Заметим, что Л(п, г, й) = /(по г+ 1, й)//(п, г, й) = (й — г) х х 2 '/(г -!- 1) и что Л(п, г, й) > 1 прн й > г > О. Следовотепьнсз /(п, г. й) возрастает по г. Отсюда шах/(п, г, й) = /(п, й, й) = (й)2 ж, пцп/(п, г, й) = 2(„). 5.25. 1) 2"т'/пз если [!обг и) > !обг(п — 1обг и), (2" /п) (1+ 2г ), если 1о г(п — !обг п) ( (1обг п) ~ ()о8,(п — 1обг п — !обг 1обг и), 2" !"кг"!, если (!08 и) < !обг(гг — 1об, и — !08 )обо п).
д(п) 6 — ог — Ь вЂ” Ьг 3) чг1 -6 Ь вЂ” 1. Заметим, что аг — ао = — ао = < О и аг = 2 2 Ь вЂ” Ьг Ь вЂ” ог Ь -!- Ьг аг — Ьг >О,т.е. О<аг<ао Пшгое, аг — аз= '-!- = ' > 2 2 2 2 Ь вЂ” аз~ Ь аз > О, а аг — ао = — — = — — ' < О. Отсюда аг < аг < ао. Вообще 2 2 2 г г а„— о„+г а„тг — о„= . Отсюда по индукции следует, что (аг ) возрастает 2 и а„г < ао при всех п > 1, (аг„ег) убывает и аг„зл > аы Следовательно, существуют пределы с = 1пп ог и Н = 1пп аготы Переходя к пределу в рекуррентном соотношении, получаем с = (Ь вЂ” оа) и г! = (Ь вЂ” сг).
Отсюда (с — б)(2 — с — д) = О, а посхольху с < Ь/2 < 1/2 и д < Ь/2 < 1/2, то 2 — с — е! > О; следовательно, с = д. Отсюда с = з/1+ Ь вЂ” 1. 5.21. 1) С помощью соотношений (3) и (4) получаем, что аз = 9/128, а4 < 11/128. При п > 3 неравенство (4) можно переписать в виде 17 1 323 а„тг < — + а„ ( — + а„) . 1024 1024 400 Отиветы, указания, решения Функция !(п, й) как функция действительного аргумента й выпукла вниз, /1окг иМ пРичем минимУм достигаетсЯ пРи й = й' = 1обг (и — !обг и+ О ( ' )!г!. Положим йо = (!об и].
Очевидно, что либо д(и) = у(п, йо), либо д(п) = = Д(и, йо — Ц, Лля нахождения д(и) нужно выбрать минимум из )(п, йо) )(~, йо — Ц. ПУсть э) !обг и > йо > 1обг(и — !обг и). Тогда ~(и, йо — Ц = 2" о~' -!- 2 2"~'гги, Пусть 6) !обг(гг — !обг и) ~ )йо > !обо\и — 1обг и — !обг !окг и).
Тогда 2" гоо 2" гоо — мог~ — < ог )З 2ото Д(и, йо) — +2 = — (1+2 ), Д(и, йо — Ц и и и Следовательно, д(и) у(п, йо). Пусть в) йо < !обг(гг — !ояг п — !обг !ояг и). Тогда ((п йо) 2 — о ! 2г" 2» — ьо 2мзг о — во ~(п, йо — Ц ~ 32' "+' > Д(п, йо). Отсюда у(и, йо) д(п) = 2" "'. 2) д(п) 2" (2 ~"1+ 2 Ш1), где о(и) = 1обг п — (!оя п), если а(гг) < < Ц2, д(и) 2" (2' 60 + 2" 00 ~), если п(п) > 1/2. 6.1. Ц Граф с и помеченными вершинами без петель и кратных ребер полностью определяется множеством ребер. Поэтому число таких графов равно числу подмножеств ( ) — — элементного множества, т.е, равно 2 (2) 6.2.
Ц 2(г), еиз т 2) ( ). Число равно числу выборок из иг возможных дуг (включая (,т)' петли) по т. 6.4. Коли р(О) — число различных помеченных графов из 'бэ, изоморф- ных графу О, а оп'„множество всех неизоморфных и-вершинных графов, то !'Й„( < и! !'й*„!, поскольку р(О) < и.'. 6.5. Ц Воспользоваться результатом задачи 6.1, 2) с учетом того, что число гл, ребер связного и-вершинного графа без кратных ребер и петель удовлетворяет неравенствам и — 1 < т < ( ). 2) Воспользоваться тем, что (('г) ) < (( г ) ), (( 'г ) ) < т т (!( +ц) 6.8. Ц См. рис. 0.8.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
