Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 79
Текст из файла (страница 79)
Имееът сзгтРс()т.,уг,уз,14)= — сзгт((х->у гг) +З(х-~-утг) (х +у 4-г ) )= 24 = — (,;, -тЗ 2 2) =3. 4.11. Уттт(Х, 1ът, ..., Ж). Следует из теоремы Пойа. 4.14. 1), 2) Пусть з - - некоторая подстановка из тт элементов, имеюптая Ь циклов. Элемент и в ней может образовывать единичный цикл.
Тогда такой перестановке можно взаимно однозначно поставить в соответствие перестановку из и — 1 элементов с Й вЂ” 1 циклами (число таковых равно р(и — й, й — 1)). Если элемент и не образует единичного цикла, то перестановка х может быть получена из некоторой подстановки из и — 1 элЕментов с й циклами каждая путем включЕния элемента в некОторый цикл. Лля фиксированной перестановхи на и — 1 элементах с й пиклами такое включение можно провести и — 1 способами (ставить элемент п на первое место нельзя, так как и — наибольший элемент). Отстода следует, что Р(тт, Ь) = р(п — 1, й — Ц + р(п — 1, й) ° (и — Ц. Умножая равенство на 1 и суммируя по )т, получаем соотношение между производящими функциями ага(1) = (1 -> и — 1) Уе т(1).
Отсюда цо индукции с учетом равенства рт(1) = 1 получаеът, что (тР (1) = 1(1 4- 1)... (1-~- п — 1). 388 Ответы, указания, решения 5.1. Ц Заметим, что п ( (г+ Ц(и — г) <»и+ Ц/2)г при 0 ( г < п. Отсюда и"'"( П (г+Ц(и — г)(т«1(" ' П (г+Ц(п — г)(("+') г<г< тг 1« «г 2) Заметить, что (г + Ц (2п — г) < тг(тг + Ц. П 3) Имеем (1 -~- — ) = ~ ('Й) и < ~ 5—, ( 2 -~- ~ — < 3. « — в «=в «=г 4) Индукция по п.
При и = 1 неравенство верно. Если (итт3)" < и!, то » + Ц)3)" ~ = ( т«3)" » + Цтт )" < ( . 3)) < (пт«3)" ( ф Ц < ( + 1)1 5) Заметив, что (и!) < (2п)! 2 ", воспользоваться результатом задачи 2). ггя ьг . «Вгя ..:и<( + +". гтг, а, > О, и тот фахт, что среднее арифметическое множителей, стоящих в 2 ч .г 2и,-~-1 левой части неравенства, равно т п(п -~- Ц 3 =-. г 7) Положив а„= (2п — Ц у<3п-~-1(2п!!) ', показать, что аг гтта~ < 1. Палее провести индукцию по п. ч и«и" 3) Заметить, что г(2п — г) < ттг при г' < и. 9) в" = «з — > —. И и! г=а 10) При и = 1 неравенство очевидно. Предположим, что (1 ф о) > > 1+ отг для всех — 1 ( тг и некоторого и > 1.
Тогда (1 -г- о)"т~ = = (1 + о)(1 + о)" > (1 + о) (1 -г- оп) = 1 + о(и + Ц + о п > 1 + о(п -г- Ц. 1Ц Разложив обе части неравенства по форму«я. бинома Ньютона, сравним члены разложения с одинаковыми номерами. Имеем („) и = ("+ )(п-~-Ц «при Й= О, 1. Палее, (Й)п «/(и«' )(и,фЦ = (1 — Й/(п+ Ц)(1 — 1«т(п+ Ц) . В силу задачи 10) отношение не превосходит 1. Таким образом, каждое слагаемое разложения (1-~- Ц'и)" не превосходит соответствующего слагаемого из разложения (1 ~-1«т(п+ Ц)"е'. Кроме того, в последнем разложении имеется еще (и+ 2)-е слагаемое, равное (и -Е Ц г"ам > О. Отсюда и вытекает строгое норавенство. /2(п — Й) т «Гпт ат:ьт 5.2.
Ц Положим а« = ( и убедимся, что при Й > 1. С учетом того, что аг < 1, отсюда следует первое неравенство. Второе вытекает из задачи 5.1, 3). т'п'г«(п)« 2) ( — ) ( при 1 ( Й ( и. Второе неравенство можно получить, Й И рассмотрев отношение —, где а« = ( ) Й (и — Й) п .
Имеем а«ег Уи1 «, — « а«.т.т = (1+ (и — Й вЂ” Ц )" (1+ — ) . Поскольку (1+ — ) монотония Й) пг но возрастает с ростом тп (см. задачу 5.1, 1Ц), то > 1 при Й < а«тг и — 1 а«. 2 0тсюда с учетом того, что аг < 1, вытекает справедливость неравенст- 389 Гл, (7111. Элементы номбннаторнна +7) = — ~ ~ехр( — )(14 ехр( )) о — ! = — 2" 4- ~ ехр ( — — ) (1 -1- ехр ( — )) Заметим, что ~ ехр( — 2ягги)й)~ = 1 н Г 2тги1 27ги .. 27ги 1+ ехр ( — ) = 1+ сов — + ! вш й й й яи/ ти ..
яи1 2 сов — (сов — + гейл — ) й) яи 7Г = 2 сов — < 2 сое —. й й Отсюда ь — ! ~ ехр ( — ) (1 -Е ехр ( ~™ )) ~ < (й — 1) (2 сов — ) = О ( — ) . =! 3) Воспользоваться результатом задачи 1,207 1) и заметить, что ~1+ ое~ '1ь~ < 1 — о+ 2п сов — < 1+ и при О < и < й. 4) С использованием задач 1.18, 9) и 5.3, 2) получаем лш (е) Е(л )( ) ( ) Я( ) 2 )(Я Е 7! — 1 и ва аг < 1 для й < . Для й > — неравенство вытекает из соображений 2 2 симметрии.
3) Первое неравенство докажем индукцией по и. При и = 1 неравенство верно. Предполагая его справедливость при некотором и > 1,имеем ( )=2 ( ) 2 2(п-!-Ц1 22п-!-1 72пз 2п+1 4" ) >2 — > и-!-1 и+1 и и-';-1 2!77! > (2п -!- 1) „1 4" > огпп+Т 2~/ 41 Второе неравенство можно цоквзать по индукции с использованием задачи 5.1, 7). 5.3. Ц (2п — 1)9 = (2п)г(77!) '. 2 Зг'2~г(2п)(27!) "е в" (2яп) ~1~а е" 2 "' Г72п" е —" 2".
2) ( ) = (2п)!(и!) и74ягг(2п)~" е з (27гп) х х и з"24" вш(яп) 717 4' 5) (2п)!!((2п — 1)9) ' = (27!)!((2п — Ц!!) з. Далее можно использовать формулу Стирлинга и результат задачи 1). ! 1 2" т! 1 5.4. 1) /(14-1)" Я = (14-1)"+'( = — . С другой стоп-!-1 о -!-1 и-!-1 о о ро., /'(14-1)-41=/'~ (й)1'=~ (й)~1й41=~'„' (й). о о г=о г=о г=о 2) Воспользовавшись результатом задачи 1.19, 3), имеем 390 Отпвгтпы, укагвнпв, решения 5.5.
1) Да. Справедливость неравенств следует из того, что (Ь)а" < ( („)Ьв < (,)с . 2) Нет. Контрпримером может служить последовательность 1Ьь) такая, что Ьь = 2 ° 3 Я при Ь четном, Ьг = 3 1 при Ь нечетном. Полагая о = 1/3 и с = 2/3, имеем 0 < а" < Ьг, < сг < 1. Однако в силу задачи 1.22, Ц получаем ( ць©ь, ~,— ( ц ©(-')'+,',--(,",) ( ) = (1 — — ) 4- — Я1+ — ) + (1 — — ) ) > 11 — а)". 5.6. 1) Имеем Ра = — ~ ~1а, — а) > — 2 1а, — о) > 614 . Отсюда бг < Р /4~ в,=.1 "., )., тд>1 2) Рассмотрим множество А = 1ов7 аг, ..., аг 1), в котором а ЧИСЛО ЕДИНИЦ В ДВОИЧНОМ ВЕКТОРЕ Й = 1О1, ..., 11п), ИМЕЮЩЕМ НОМЕР Ы. 71 Заметим, что а = 2 " ~ ~а = 2 " ~ Ь( ) = —.
Заметим, далее, что 2 в«г" в<1<1 число, стоящее в левой части доказываемого неравенства, равно числу тех а, для которых ~а — а~ > 4 чтть В силу задачи 1) это число не превосходит Ра/14 1/и)г. Но 2"Ра= ~ 1а — а.)г= ~ та~ — а)= — 2"а + ~ Ь~( )= в«г" в«г * в<я< = -2" (-) + (и + и)2" г = п2" Таким образом, 2" Ра/11 з/и)г = 2" ~/4~.
3) Оценка снизу. Положим 4 = 1пи, С учетом задачи 2) имеем ~Х-< Ьг (Ь) ~-~ (Ь) (и/24117и)г г-в (Ь) 4 / „2в') 2в"" > )и — 41 1/п)г ' 11 I 711 Оценка сверху. Заметим сначала., что ( ) < ( — ) в силу задачи 5.2, 1) и („1)/(Ь) = < — при Ь < —. Поэтому К" г(")-' ~: (")' —.' К ©' 4- ( — — 4 з/и) ~ ( ) ( 14е)"~ ~~ 3 ' 4- 1 Ш вЂ” !г~<1„' =о + — (1+(471 11)) 2'<и ~.2"~. 391 Га. 'гИ1, Элементы кожбинагпорики 5.7. 1) Используя формулу (2), имеем ()= ,,/п по (1 -< О(1,~и)) гга>лг ее — )-— Положим х = игг2 — к; тогда полученное выражение можно переписать в Имеем, далее, 4) Положим х| = х -!- 2 ьг!пи, )г(х) = и.а+ х >гйа Тогда а -~- 1 К (".)"= К (".)а+ К ("')а >И*О Ы 1« Ы*г1 >Л1 1 Но ~ ~(и)а' < и( )а", где оо =]й(хг)[, В силу задачи 2) получаем >М*,1 отсюда, что ,г ( )а <ы и(2яиа) ~~з(1-~ а)"~~ ехр( — — 1) = >Ям,1 = и ~ (2я) ~ (1 + а)" 'г ехр ( — — — х чг!и и — 2 1п и) < 2 ~< и '~ (2я) 'г (1+а)'Рые * гз — туг!пх.
(*) С другой стороны, из задачи 3) следует, что (и) (а -!-1)" (е гг е *г1~) зц1« Ы О Из (*) и (**) вытекает искомая опенка. 5.8. 1) Используя неравенство (2) и вытекающее из него неравенство и! > /2яии" е ", получаем 1 (") ч'2хи и" ехр ( — и -1- — ) ег Вз"! < — С(ии Л). лиl 2яизглл(ли)л" (ли)нп ехр( — лп — лиг >гзхилллл"ле" 392 Отпветьь указания, решения С другой стороны, (п) пЛ ъг2яп п" ехр ( — п) 2яп хЛр р(Лп)""(рп)1 ехр ~ — Лп — рп а— 12рп. 12Лп ехр ( — (11(12и))(1!Л а 1)р)) О2ят~ЛрЛЛ рв () 1 1 ) < С(п, Л) ехр Лп! ) 12п 12Лп 12ри 360(Лп)з 360(рп)з ~ 1 1 Без ограничения общности можно считать, что Л > р.
Тогда — < —, 12п 12Лп 1 1 1 1 1 а < < О. Следовательно, 360(Ли)з 360(Рп)з 12рп 180рзпз 12рп (ь) "(и ') 3) используя нижнюю оценку из задачи 2), получаем © > с(и л) х — ( 11 х ехр — (. Но ехр( — (12пЛр) ') > ехр( — (Зп) ') > ехр с — — з > 12иЛр ) 9 > — при и > 3, ехр ) — — ~ > —. При п = 2 и Лп, = рп = 1 выполняется равенство. 4) Верхняя оценка „К © ("п)К(',')'=„',(:.) 5) а) Неравенство легко проверяется в случаях, когда Л = — (поскольку ~ ~("„) < 2" = (-) Н ); ь> /з п — 1 Лп = и — 1 (левая часть есть п -1- 1, а правая равна ( ) и); си — 1/ 3 < п < 5, п/2 < Лп < п — 1 (непосредственно).
Пусть теперь и > 5 < Ли < и — 2. Из задач 4) и Ц следует, что (1) < Л(2Л Ц (Л ) < Л 1 (2Л вЂ” Ц '(2яп(1 — Л)) '1 Л "вр "". б) в) и и/2 к>л Положим у(Л) = Лцз(2Л вЂ” Ц '(2кп(1 — Л)) Пз. Требуется показать, что 1(Л) < 1 при Л Е (1/2 4-е, (и — 2)/и), где е = 1,1п при четных и и 1/(2п) при нечетных и. Дифференцируя по Л., замечаем, что функция 1(Л) выпукла вниз на исследуемом сегменте. Поэтому максимальные значения следует искать на концах сегмента. Имеем ~ ( — -~ е) = )/ — +е (1-~-2е) (2ки ( — — е)) = ((1 — 4е ) 2ки) < ((1 — — ) 2кп) < 1 при всех и > 5. 2) Нижняя оценка вытекает из решения задачи Ц.
Для получения верхней оценки, воспользовавшись неравенствами (2), имеем 393 Гл. '1П1. Элементы комбннаторики Рассмотрим правый конец интервала: при п ) б. Если Л < 1/2, то гг = 1 — Л > 1!г2. б) Поскольку С ) = С ), то с использованием задачи о) получаем,что ~ ~(,)= 2 ( )<р '"Л о<й<Л йг И й — ! гй — ! 59. Ц (п)!. = и П (1 — — ) = и, ехр (~!и (1 — — )), но =о =1 й — 1 й-1 г й — 1 !в(1 — — ) = — ~ ~2 — ( — ) = — ~ ~— ~ ~г .
=1 =1 =1 =! й — 1 2) Очевидно, что (п)й ( пй. С другой стороны, (п)й = П(п — г) > =о ) (п — й) ' = и'(1 — С вЂ” )) > г!'(1 — — ) (так как й = о(й)п!)) п (1— — о(Ц). й-1 3) Воспользуемся тем (см. задачу 5.13, 2))! что ~г г = (и,'- Ц й"+ -й *=1 -й О(й'). Отсюда в силу задачи Ц имеем при й — й оо и й = о(п) (п)й = п" ехр ( — ~ ~(ип") '((р+ Ц 'й"~' -й О(й'))) = =и ехр~ — ~ ~( +О( — ( — ) ))).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
