Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 78
Текст из файла (страница 78)
Если й > 2, то сугцествует диаго- наль вида (1, й+ Ц. Тогда число разбиений исходного (и+ 2)-угольника равно числу разбиений (й+ Ц-угольника с вершинами 1, 2, ..., й + 1, ум- ноженному на число разбиений (и — й 4- 2)-угольника с вершинами й 4- 1, й 4-2, ..., ич-2, т.е. равно ая га„ь (2 ( й ( и). Естественно считать, что ао = 1. Тогда имеем а = ~ ~ая га„.ю Так же, как в зацаче 3.19, я=~ 12и1 находим, что а и -~- 1 1 12из 2) а = ( ).
Решается аналогично задаче Ц. и -~- 1 3.21. Ц и!. 2) ( — Ц" ',1(и — Цй 3) 1г 3 .... (и — 2)~/и! при нечетных и, О при четных л,. 4) 0 при нечетных и, ( — Ц "1г 2 "((и/2)() ' нри четных и. 5) ( — Ц1 01гиг при нечетных и, 0 при четных и. 6) а„= Го, где (Гч) = 1, 1, 2, 3 — — последовательность Фибоначчи. Докажем сначала, что если последовательность (а„) удовлетворяет соот- ношению а„ег = а„тг -'га„, ао = аг = 1, (е) то она удовлетворяет соотношению г — 1 а„е, — а„а„тг = (-Ц, ао = аг = 1. (ея) При и = О, 1 утверждение справедливо.
Индуктивный переход: г а„т г — и т га„~-з = а„тг — а„.~.~ (а„, г + а„ег) = »ег = а„тг(а„тг — а„< г) — а„~.г —— а„ега„— а„ы — — ( — Ц" Таким образом, (Е„) удовлетворяет (ья). Других решений соотношение (ле) не имеет в силу того, что (ья) вместе с начальными условиями определяет а„ единственным образом. 3.22. Ц Умножая рекуррентное соотношение на 1~ и суммируя по й, получаем, что (1 — 1)А (1) = А ег(1). 2) Поскольку а(0, 0) = 1 и а(0, й) = 0 при всех й > О, то Ае(1) = 1. Индукцией по и с использованием задачи Ц получаем, что А (1) = (1 — 1) 3) Разлагая и(и, й) в ряд, получаем, что а(и, й) = ( „) ( — Ц" = (и -~- й — 1) 3.23.
Ц 20. 3) 6. 3) 10. 384 Ответы, указания, решенпв 3.24. Ц А11) = 11 — 1~) ' 11 — ез) ' 11 — Ев) 3.25. Ц Заметим, что А1у71) = П(1 — 9 " .1) = А(1Н1 — 91) и, слеь=! довательно, А11) = А191И1 + 91). Коэффициент при Р* и левой части равен по определению а„, и правой а„д" — а„гд . Отсюда индукцией по и получаем, что а = д"~"~ ~~ П19 — Ц 1п = 1, 2, ..., ао = Ц. в=о 2) См, решение задачи 3.24, Ц, 3.26.
Ц,2) Я(гбй,1+Ц=~ 1 — Ц" '~(" ) — ( ' )) х =о тз х 7гз+ 1+1)ь = — ~ 1 — Ц"~~ "(и ) 1и ->1)~ + =1 + ~ (-Ц"-" (",) ( + 1) ь = -Я( + 1, й, 1) 4- Я(п, й, 1). =1 3) Я1п, й +1, 1) = ~ 1 — Ц" (,г)1и+1) 1м +1) = .=-о = ~-1-Цо--и(и-1)1.+1)'+1Я1п й Ц = =о = ~о1-Ц"- ((",) — (".')) е1Я~и,й, П= = (и -~-1)47(п, й, 1) -~- пЯп — 1, й, 1). 4) Локазательстно индукцией по й с использованием задачи 3). Лля любых 1 и п > 1 имеем ЯЕп, О, 1) = ~ ~1 — Ц" "(„) = О.
Пусть утверждение =о верно для некоторого й > О, любых и > й и любых 1. Пусть й -~-1 < и,. Из задачи 3) имеем Я1п, й+ 1, 1) = 1п+ 1)Я1п, й, Ц+ пЯ1п — 1, й, 1). Поскольку й < и — 1, то в силу предположения индукции Я7п, й, П = = Я7п — 1, й, 1) = 0 и, следовательно, Я1и, й -Е 1, 1) = О. 5) Индукции по и. Имеем Я10, О, 1) = 1о = 1 = О!. Пусть Я(п, п, 1) = тй для некоторого п > 0 и всех 1. Используя задачи 3) и 4), получаем Я1п+ 1~ ге + 1, 1) = 17з + 1 + 1)Я17з + 1, и, 1) + 1и -е ЦЯ1п, п, 1) = = 1п + ЦЯ(и, и, 1) = 1и + Ц!.
6) Индукция по й. В силу задачи 5) имеем Я1и, и,1) = и! > 0 при всех и, и нссх 1. Пусть Я1и, й, 1) > 0 для некоторого й > п и любых п и й Воспользооашиись задачей 3), имеем Я1и, й -~ 1, 1) = 1и+ 1)Я1п, й, 1) -Е -~-геЯ171 — 1) й~ 1) > О.
7) Вытекает из задач Ц, 2) и 6). 8) Вытекает из задач 3) и 5). 9) Может быть выведено из задач 3) и 4) индукцией по й. 3.27. Ц В силу задачи 3.26, 9) имеем аз11) = ~ ~Я(1, й, 0)1о = ~ ь=о ь — 1 = 111 — 1) '. Палее и силу задачи 3.26, 3) имеем Я1п, й+ Ц = ге$7п, й)+ 385 Гл. 1г111. Элементы номбинагаорини +нЯ(п — 1, Ь).
Умножая обе части равенства на еат~ и суммируя по Ь, получаем оо(1)(1 — пг) = нсо„г(1). Теперь утверждение доказывается индукпией по и. 2) При л = 1 правые части формул из задач Ц и 2) для гт совпадают. Если будет доказано, что для о„(4) =4~ ( — Ц" й~ (1 — ЙФ) 'гй) ь=! справедливо рекуррентное соотношение о.„! (1) = И1 — нг) /(ггг)) . о„(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 ( г, 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г, )з, тл).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
