Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 81
Текст из файла (страница 81)
Если ив = эгь, то а~ = (ав+ 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. 461 Гл. 1711. Элементы комбннатаорики 6 2 4 б 7 9 8 3 3 1 Рис. 0.8.1 2) Алгоритм восстановления вектора Х = (1и 12, ..., 1 з) таков: координата П равна наименьшему числу из множества Ж = (1, 2, ..., и), не входящему в наборб = (1~, ул ..., 1„), Проведем ребро (зы 11) и положим № = Х~((з ), Л = (ум, з -з) Далее положим (з равным наименьшему числу из №, не входящему в Оы Проводим ребро ((з, у ) и т.
д. Последними соединяются ребром две вершины, оставшиеся в Ж„ 3) Утверждение вытекает из того, что соответствие между векторами л = (уы уз, ..., у -з) и нумерованными п-вершинными деревьями взаимно однозначно, а число векторов равно п 6.9. Использовать задачи 6.4, 6.8 и формулу Стирлинга. 6.15. Ц Провести доказательство индукцией по числу вершин. 3) Вывести из рекуррентного соотношения для числа 1 дихотомических деревьев следующее соотношение для производящей функции Т(х): Т(х) — 1 = хТ'(х). Отсюда Т(х) = (2х) '(1 — чг1 — 4х).
Разлагая Т(х) в ряд, получаем, что ем=2( — 4) (' )= ( и). 6.18. 1) Число графов С из ейо таких, что для фиксированной пары вершин (г, 1) в С отсутствуют цепи длины меньше 3, равно 3" з х л)-зщ-з1-з х 2(з' . Поэтому р(п) = 2 (') ~ ~3" з 2(а) = — (' ) (-) 14,<з< 2) Из того,что 1пп р(п) = О,вытекает,что р(С) = О для почти всех графон.
Отсюда следует, что диаметр почти всех графов меньше 3. 3) Пусть рз(С) . число вершин степени п — 1 в графе С из 'Й„, а р,(п) = 2 заз ~ ~рз(С). Тогда р,(п) = п. 2 "м'. Отсюда следует, ие з что рз(С) = О для почти всех графов, а значит, радиус их не меньше 2. Теперь с учетом задачи 2) получаем утверждение. 6.19. Число гамильтоновых диклов в полном графе из 'Й„рав- 1 но — (и — 1)!.
Доля графов, у которых присутствует заданный гамильтонов 2 цикл., равна 2 6.26 Ц р( ) = (",) 2) Тур(и) = — (3) 2 з+ ( )(п — 2)(п — 3) 2 3) Вытекает из неравенства Чебышева с учетом того, что Ср(п) < и" = = о((р(п)) ). 26 Г. П. Гаврилов, А. А. Сапоженко 402 Ответы, указания, решения 6 21 1) Р(ггг ) = (З) (т)з/((2)) 6.22. ( ).2 628. ( )((з)и " )((,'„)) Глава 1Х 1.2. 1) Если множество (гг,..., гь) зафиксировано, то число граней В","; " равно числу двоичных наборов (егг... тг), т.е.
равно 2 . 2) Если Н б В",'"„' „' " Ез В„",*"„",„* 'г, то аг = гг, ..., гтя = тя, а следовательно, грани совпадагот. Приходим к противоречию. 3) Вытекает из задач 1) и 2) с учетом того, что В",""'„'"' = 2' /и1 4) Число способов выбора направления (гг, ..., гь) равно (й). Теперь утверждение следует из задачи 1).
б) Следует из задачи 4). 6) Если Н б В","';,*", то вектор (ггг...ггг) однозначно определяется вектором Н и множеством (гг, ..., гя), Последнее можно выбрать ( ) способами. 7) Код грани О размерности и, содержащей заданную грань Н размерности 1,получается из кода грани Н расстановкой Й вЂ” 1 прочерков среди и — 1 координат, имеющих значение 0 или 1.
8) Лля символов ег и гЗ из множества (О, 1, —.) введем операцию полагая: и 11 = ог если ег = 17; ег В = гг (сг гиз = )г), если о б (О, 1); (соответственно если г8 б (О, 1), о = —.-), значение ег )1 неопределенно, если о ~ )г и щ Д б (О, 1).
Естественным образом операция распространяется на векторы из О". Нетрудно убедиться в том, что если Н и В -- коды граней Е и Н, то вектор Н,9 определен тогда и только тогда, когда Е С Н ф Я. В последнем случае Н 3 является кодом грани, совпадающей с Р С Н. 9) Вытекает из задачи 7). 1.4. Положим 1, = и — и,. Тогда числа 1, удовлетворяют неравенству Макмиллана <з 2 ' < 1. Поэтому существует префиксныи двоичныи 1« . код с длинами кодовых слов 1г, ..., 1,. Пополним каждое кодовое слово ю, длины 1, прочерками в количестве и — 1,.
Тогда каждое из так полученных слон ю, можно рассматривать как код грани размерности и — 1, = и,. То, что грани попарно не пересекаются, следует из префиксности кода. 1.5. 1) Рассмотрим множество всех интервалов Ли, В) таких, что Н б Вги~зр )г б В„" Ог7зр ЛлЯ каждой из () ) )) веРшин ег б В~"„7з~ сУществУет ( ~„7 ) ) веРшин В б В„г„гз~ таких, что о < В. Таким обРазом, / и — )гг/3) 'г число пар (Л, ег) указанного вида, а значит, и число интервалов Ца, г8) рав- Ря. 1Х. Минимизация бувевь х функций п 1 'п — Ги,»31» но () ) )) ( ~ ) ) ). Нетрудно видеть, что все они попарно несравнимы.
2) Аналогично задаче 5.19.1 из гл. П. 1.6. Ц 2. 2) 3. 3) 2. 4) 3. 5) 2. 6) 3. 1.7. Ц 2. 2) 4. 3) 3. 4) 3. 5) 2. 6) 3. 1.8. Ц 2. 2) 1. 3) 1. 4) 2. 5) 5. 6) 4. 1.9. Ц 2. 2) 1. 3) 3. 4) 5. 5) 5. 6) 4. 1.10. 2) Рассмотреть матрицу вила»Р»-»1 — »вЦ, где Р»» . матрица размерности Гп — к+ Ц х Гк — Ц, состоящая сплошь из единиц, а 1„»э» единичная матрица размерности»п — Ге + Ц х»п — й + Ц. 1.11. Пусть А множество векторов»базисных) линейного»п, 1)-кода.
Тогда ~А~ = й и А покрытие. Последнее вытекает из следующих соображений. Пусть утй столбец имеет единицу в»-й координате. Поскольку »-я строка является линейной комбинацией базисных строк, то существует базисный вектор, имеющий единицу в блм разряде. 1.12*.
Ц Пусть Л» — семейство всех Ге-элементных подмножеств строк матрицы М. Лля Р 6 Н» обозначим через н»Р) множество столбцов, не покрытых строками из Р, и пусть й» = (в) ~ иГР) среднее число ген» непокрытых вершин по подмножествам Р из й».. Пусть»' — множество столбцов матрицы М, а рГи) число тех Р из Л», которые не покрывают столбец и, а пГ»») число строк, .покрывающих столбец и. Тогда й»=( ) ~р»и)=(„) ~(™ )< <и( )ГГ( ) <п(1 — — ) <пе Лля всякого натурального Й имеем 6(М) ( Й+ р». Поэтому, полагая Й = 1»п вп Г т еви = ] — 1п — ~, получаем СГМ) < 1 ~- — 1п —.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
