Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 79
Текст из файла (страница 79)
Заметим, что ~Св г,~ = ~С г ~, если у х, т.е. если у принадлежит той же орбите, что и х. В самом дело, если гг б Св, и С вЂ”, = (ггг, ..., гг ), то (аггг, ..., ак ) б Си-,, причем афпг, ф ак, при г' ф 11 С другой стороны, если Си, . —— (аг, ..., аь) и гг б Св „, то (гг ггг, ..., о оь) С С, и сг гг, ~ гг ггг при г ф у.
Отскгда вытекает, — 1 — г что ~Сз „~ = ~С, г„~. Пусть теперь Мг, ..., М,еегг орбиты и х, б М,. Тогда Егг> Еоб ~ Ьг(гг) = ~ /С, „/ = тз ~ ~/Св г,/ = ~ /С/ = /С! и(С). ех, =г геьг, =г 4.6. 1) Каждую подстановку к из Я„, имеющую тип Ъ = (Ьг, Ья, ..., 6 ), можно представить в виде произведения циклов так, чтобы длины циклов не убывали: х = (1г)(1з).
(гзл)(гьгег, гьгэз)... Лве такие записи могут задавать, вообще говоря, одну и ту же подстановку. Это может произойти в двух Случаях: а) когда одинаковые циклы стоят в этих записях на разных местах; б) когца циклы хотя и равны (как циклы подстановки), но их записи начинаются с разных элементов (например, (1 2 3) и (2 3 1)). Первая причина приводит к повторению одной и той же подстановки П Ьь!, вторая к повторению П Ь " раз. Эти причины действуют независимо. тт ь„ ь=г 2) По определению имеем — ьгь> ь,гг ев = (й) 'Е Е 1"' " 1': = ( ') 'ЕЬ(Ъ) Пь~з ь елью ь =1 3) Имеем ,з ьь ь ехр(1гх -~-ьз — + ьз — +... ) = П ехр~ — ) = 2 3 Ь ь=г =й(Е -4'-" -) ь=г ьь=о Коэффициент при х" равен сумме по всевозможным целым неотрицательным числам Ьг, Ьз, ...
таким, что 6г + 26з +... + цЬ„= и, слагаемых выла Пь."(Ььгй ') ь=г Гл. )т111. Элементы хомбннатаорики 387 4.7. Заметим, что цикл четной длины является нечетной подстановкой, а цихл нечетной длины . четной подстановхой. В выражение Рз„(тт, — тг, ..., ( — 1)" Ч„) каждая нечетная подстановка типа (Ьт, ..., Ь„) дает вклад, равный .—. 1 ' ... 1„", а в выражение Ря„(1т, ..., 1„) --- вклад, равный 1,' ...1„". Поэтому слагаемые правой части доказываемого равенства, соответствующие нечетным подстановкам, взаимно уничтожаются, а слагаемые, Соответствующие четным подстановкам, удваиваются. Кроме того, как легко видеть, ~А„~ = ~Эе ~тт2 = (и!) тт2. Отсюда и вытекает утверждение.
4.8. 1), 2) Очевидно. 3) По определению Ри. 4.9. 1) 20. Ожерелье из семи бусин можно окрасить в два цвета 2 = 128 способами. Имеется множество С из семи различных поворотов хт, ..., ят, переводящих ожерелье в себя. Тип тождественной перестановки есть (7, О, О, О, О, О, 0), тип каждой из остальных подстановок имеет вид (О, О, О, О, О, О, Ц. Цикловой индекс есть Ри(1т, ..., Ьт) = (т~т 4- бтт)/7. По теореме Пойа число различных классов эквивалентности равно Ро(2, 2, 2, 2, 2, 2, 2) = 20.
2) Цикловой индехс ость Р(тт, ..., 1 ) = (тт 4- (и — 1)1„)1п. Число ожерелий равно Р(Ь, ..., Ь) = (й" 4- (и — 1)й),тп. 4.10. 1) Цикловой индекс равен (см. задачу 4.3, 3)) Ри = (1т -~ 81ттз 4- + Зтз)/12. По теореме Пойа число окрасок равно Рл(2, 2, 2, 2) = 5. 2) Цикловой индекс Ри найден в задаче 4.3, 9). Число окрасок равно Ро(3, 3, 3, 3, 3, 3) = 57. 3) Пусть М вЂ”.
множество граней куба, С вЂ” группа вращений, тт' .. множество, состоящее из трех цветов: красного, синего и белого. Придадим вес х красному цвету, вес у синему и г белому. Цикловой индокс (см. задачу 4.3, 8)) есть Ри = (1", 4-31тЬг -~-61',тъ 4-61з, -~-81з)),т24. По теореме Пойа перечисляющий ряд для функций равен Рот((т, уг, 1з, Я, где 1ъ = х -> 4-уъ' 4-зъ (й = 1, 2, 3, 4). Тахим образом., Рот((т, ттг, (з, ~ъ) = — ((х-|-у4- 24 + г)о + З(х + у + г)г(хг + у + гг)г + 6(х + у + г)г(хл + ул + гл) + 6(хг+ +уз + гг)з + 8(хт + уз + гз) ).
Число различных окрасок, при которых три грани окрашены в красный цвет, две — — в синий и одна -- в белый, равно коэффициенту сзд,т(Ро) при хзугг' в Ро()т, 1г, )з, тл). Имееът сзгтРо()т.,уг,уз,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п), ИМЕЮЩЕМ НОМЕР Ы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
