Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 57
Текст из файла (страница 57)
константа й!пад !пгп (,т!нет)' 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) Показать, что число графов в 'йп, у которых заданные а. п — и) вершин являются изолированными, равно 2 2) Показать, что число графов без изолированных вершин в 'М„, и и — я равно ~1 — 1)ь( ')2~ а=о 3) Показать, что почти все и-графы не имеют изолированных вершин.
6.4. Пусть подмножество '6 с 'б„состоит из Х попарно различных графов. Показать, что число попарно неизоморфных графов в '6 не меньше Х(п!. 6.5. Пусть ф„, -- число попарно неизоморфных связных графов с т ребрами. Показать, что: 1) 1б1т) < ~~~ ((')); 1 — ( З -~- Л -~- п ы ] < п < пй-1 2 2) У(пе) < (2т)'и при т — ~ оо. 6.6.
Показать, что число попарно неизоморфных псевдографов, не имеющих изолированных вершин и обладающих т ребрами, не превосходит (от)п', где с константа, не зависящая от т. 286 Гл. 7Ш. Элементы комбинвторини Плоское ориентированное корневое дерево, в котором дуги ориентированы к корню, называется дихотомическим, если степень полузахода каждой вершины либо равна О 1такие вершины будем называть висячими), либо равна 2 (такие вершины будем называть внутреннимн).
6.15. Ц Доказатгч что каждое дихотомическое дерево с т внутренними вершинами имеет ровно т + 1 висячих вершин. 2) Пусть 1 число попарно различных дихотомических деревьев с т внутренними вершинами. Доказать, что 1в — — 1г — — 1, а при т > 1 = ~1ь1 в=в 3) Доказать,что йы = ~ '). 1 /2тд т+1 гп Плоское ориентированное корневое дерево будем называть почти дихогпомическим, .если все дуги ориентированы к корню, степень полузахода каждой вершины находится в пределах от О до 2, каждая вершина с полустепеныо захода, равной 1, является концом дуги, исходящей из висячей вершины (т.
е. вершины с полустепенью захода, равной О). Вершина почти дихотомического дерева называется внутренней, если степень полузахода отлична от О. Пусть 1 я число попарно различных почти дихотомических деревьев с т внутренними вершинами, Й из которых имеют полустспень захода, равную 1, и пусть 1,„число попарно различных почти дихотомических деревьев с т внутренними вершинами. 6.16. 1) Показа~в, что 1 я =1 ь~ ' ), где 1 вели/т — й -Ь 11 чина, определенная в предыцущей задаче.
2) Доказать,что 1ы < 2""', где 2 < с < 3. Обозначим через Фп множество всех попарно различных формул над множеством связок 11~, йе, †) и множеством переменных Х" = = 1ехм хг, ..., хл). ФоРмУлы считаютсЯ Различными, если они пРедставляют собой различные слова в алфавите 1Ч, й, —, 1,), хы хг,... ..., хп). Пусть Фп лг подмножество тех формул из Фп, которые содержат ровно гп связок и в которых отрицания встречаются только над символами переменных. Пусть Т„п, .
множество почти дихотомичсских деревьсв, имеющих т внутренних вершин, и таких, что каждая висячая вершина помечена символом алфавита Хп = 1хы хг, ..., х„), каждая внутренняя вершина, имеющая полустепень захода, равную 1, помечена символом —, а каждая из остальных внутренних вершин — символом из алфавита 1Ч, й ). 6.17. 1) Установить изоморфизм между множествами Ф„,„н Т„ 2) Доказать, что ~Фп,„~ < (сп) ы., где с --. константа, не зависЯщаЯ отп ит. 288 1"ж 'ыП1.
Эеементм комбинаторики 1".) 1".) 1.") ~ Р~1С) = ~ ~ ди(и, и) = ~ д Д,и, и) + 2~ ди1,и, и). с низ ы=з р=г ы=1 ы<р (г)-г Но д„1и, р) = 2'г), если и ~ д. Поэтому Ррып) = — (2) + 4 (2) ((2) 1) (2 (2)) 4 (2) Полагая в 12) д = ЗУпр(п), получаем, что доля тех графов С й 'Ми, 1 для которых р1С) — — ) ) > ~) — — ( ), не превосходит —. Отсюда 1ГпЗ вытекает, что для почти всех графов р1С) = — (2)11+ е„). где 2 ~,2г' 1пп еи = О. 6.18. Пусть р1С) число пар различных вершин графа С из 'йо, для которых не существует цепи длины меньшей, чем 3, соединяющей /оЗ эти вершины. Пусть р1п) = 2 1гг ~ р1С).
ОеМы 1 и. 3 1) Показать, что р1п) = — ( ') ( ) 2) Показать, что у почти всех и-графов отсутствуют вершины, расстояние между которыми больше 2. 3) Используя результаты задачи 6.18, 2), показать, что у почти всех п-графов радиус и диаметр равны 2. 6.19. Показать, что среднее число гамильтоновых циклов в графах С из ейи равно (п — 1)!/2нт". 6.20. 1) Найти среднее число р1п) циклов длины 3 для графов С из 'эи. 2) Найти дисперсию Рр1п) числа циклов длины 3 для графов С из '6„. 3) Показать,. что для почти всех графов С Е 'еа, число р1С) циклов длины 3 удовлетворяет асимптотическому равенству р1С) р1п) при и -з со.
6. 21. 1) Найти среднее число р1п, пе) циклов длины 3 для графов С из и)о 2) Показать, что дисперсия Рр1п, т) числа циклов длины 3 для графов С из 'йи „, удовлетворяет неравенству Р(р)1п, т) < п~1ти/и), где гу = (2). 3) Показать, *его если т = т1п) и 1пп 1т/п) = оо, то для почти всех гРафов С из 'йт число Р1С) циклов длины 3 УдовлетвоРЯет асимптотическому равенству зз р1С) — ( — ) при и — ~ со. 3) .) у б. Опенка е тпеораи ерайтое и еетпей 289 6.22. Найти среднее число й-вершинных независимых множеств в графах С из 'й, 6.23. Пусть р(С) целочисленный неотрицательный параметр, а Р(п) его сРеднее значение длЯ гРафов С из тйп.
Показать, что если 11ш р(п) = О, то для почти всех графов р(С) = О. 6.24. Используя неравенство Чебышева (2), показать, что у почти всех (и, т(п))-графов, где ти(п) = [п,т1п(п1тттт)), число изолированных вершин равно п(1 — е(п)), где 11ш е(п) = О. Глава 1Х МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ О 1. Структура граней и-мерного куба. Покрытия и тесты для таблиц Гранью единичного и-мерного куба В" называется множество В",'"''„"' = ((оы ..., о„) е В": ов = оы ..., оа = он).
Множество (3е,, 3„) называется направлением, число Й " рангом, а число и — й — размерностью грани В";" „" ". Кооом грани С = = В","; '" называется вектор у(С) длины и, в котором у„= = оз, ..., у,„= пь, а остальные координаты есть --. Например, у(В,",; ' ) = (О 1 ). Одномерные грани называются ребрами куба. Обозначим множество векторов длины п, с координатами из множества (О, 1, ---) через Са. На множестве С" зададим частичный порядок, полагая б < Д, если вектор 13 может быть получен из Н путем замены некоторых (быть может, ни одной) координат набора Н, равных О или 1, на --.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
