Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 79
Текст из файла (страница 79)
Имеем ',"'--(1) = ',"'1~ (-Ц" 'Ь(й)(1-И) '= г=! =К(-ц '(~-')',:.",'=~(-ц '(" )("-'",:,",) = — 1 — ьт! (гг — 1) (и ь)г ~ ~( ц — я — ! (н — 1) (1 ) — ! ь=! = ег„,(1), 4.1. Ц (О, О, О, Ц. 2) (2, 1, О, 0). 3) (О, О, 2, О, О, 0). 4) (2, О, О., О, О, 1, О, 0). 4.2. Транспозицию элементов ! и 1 обозначим парой (г, 1).
'Тогда (2, 3, 4, Ц = (1, 2)(2, 3)(З, 4), (4, 2, 3, Ц = (1, 4)(1, 2)(1, 3)! (3, 4, 5, 6, 1, 2) = = (1, 5)(2, 6)(3., 5)(4, 6), (8, 2., 1, 7, 4, 6., 3, 5) = (1, 3)(1, 7)(4, 5)(4, 8)(1, 4). 4.3. Ц Существуют четыре поворота квадрата в плоскости, переводящие квадрат в себя: на 0', на 90', на 180', на 270'. Этим поворотом соответствуют подстановки (1, 2, 3, 4), (2, 3, 4, Ц, (3, 4, 1, 2), (4, 1, 2, 3). Первая из подстановок имеет тип (4, О, О, 0), остальные .. тип (О, О, О, Ц. Никловой индекс: Рп(гг, ег, гз., 1л) = (1! 4- Згл)гг4. 2) Кроме подстановок задачи Ц появляются еше четыре: (1, 4, 3, 2), (3, 2, 1, 4), (2, 1, 4, 3), (4, 3, 2, Ц, соответствующие поворотам квадрата вокруг диагоналей и осей. Лве из них имеют тип (2, 1, О, 0), а две другие тип (О, О, О, Ц.
Отсюда Рп = (1~! + 31! + 21!го + 21!~)/8. 3) Существует 12 вращений тетраэдра! тождественное; восемь вращений на 120* вокруг оси, проходящей через вершину и середину противоположной грани; три врагдения вохруг оси, проходящей чероз середины противоположных ребер. Отсюда Ро = (1л! + 81!ге + 31!~)/12. 4) Рс = (1! + 81з+ Зггз!)!!12 5) Ра = (1! + 81ггз+ 31з)гг12. 6) Ро = (1!~+ 31!1!+21з)ггб 7) Рп = (1~!+ 81!1!+313!)!12. 4.4.
Ц Покажем это утверждение непосредственно и с помощью леммы Бернсайда. Группа С состоит из подстановок я! = (1, 2; 3, 4), яг = (2. 3, 4, Ц, ггз = (3, 4, 1, 2), ял = (4, 1, 2, 3). Непосредственно видно, что для любой пары 1 ( г, у < 4 существует подстановка я такая, что я, =1. Таким образом, все элементы эквивалентны. Имеется один класс эквивалентности. Теперь получим тот же результат с помощью леммы Бернсайда. Имеем (С~ = 4, Ьз(гг!) = 4, Ьг(гг,) = 0 при ! = 2, 3, 4.
Отсюда о(С) = = (4+ О+ О+ 0)гг4 = 1. 2) Заметим, что элементы 1 и 2 переводятся один в другой перестановкой яз, а перестановка я! переводит друг в друга элементы 3 и 4, 25 Г. П. Гаврилов, А. А. Сапоженко 386 Ответы, указания, решения но ни одна из перестановок не переводит элементы множества (1, 2) в элементы множества (3, 4). Таким образом, имеются две орбиты. Применим лемму Бернсайда: (С! = 4, Ьг( гг) = 4, Ьг(ггз) = Ь(кз) = 2, Ьг(ггг) = О, а(С) = (4+ 2+ 2+ 0)гг4 = 2. 4.5.
Требуется доказать, что /С/к (С) = ~ ~Ьг(гг), где /С/ —. порядок са (число элементов) группы С, а(С) -. число классов С-эквивалентности (орбит) на множестве Я„, Ьг (к) -- число элементов, которые подстановка к оставляет на месте. Положим Си, — — (я б С: ку = х). Если М С 8„ некоторая орбита и х б М, то С = Ц Св „. При этом, очевидно, С„, П уем ПСв г, = гу при и ф у.
Заметим, что ~Св г,~ = ~С г ~, если у х, т.е. если у принадлежит той же орбите, что и х. В самом дело, если гг б Св, и С вЂ”, = (ггг, ..., гг ), то (аггг, ..., ак ) б Си-,, причем афпг, ф ак, при г' ф 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+ сов — + ! вш й й й яи/ ти ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
