Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 78
Текст из файла (страница 78)
сг сг сг 3) Представим А(С) в виде -~-, . Из равенства 1 — Лс (1 — ЛС)г ' ' 1 — Лс сг ао -~- (ас — 2Ласс)С „ас ас найдем, что сс = — — -~- 2ао, сг = — — ао. Н вЂ” ЛС)г (1 — ЛС)г ' ' ' Л ' Л Разлагая А(С) в ряд., получаем А(С) = ~ ~(ссЛ" -Е сг(п ~- Ц Л )С", а =о = (а,+н( — ' — аэ))Л". 3.13. 1) Ук аз ание. Использовать тождество из задачи 1.15, 3). 2) Умножим каждое из соотношений задачи 1) на Сэ+' и просуммируем по и от О до со. С использованием начальных условий получаем соотношения между производящими функциями. 1 — С ') А(') —,.
з„,г: В(') —, з„,г г 3 -~- с/5 4) Корнями уравнения 1 — 3С + С = О являются Лс = иЛг= 2 5 — /5 а Ь . Выразим А(с) в виде А(С) = + . Поскольку А(с) = 2 1 — ЛСС 1 — Лго 1 — С то приравняв правые части, получим равенство (1 — л, с) Н - л,с) ' а (1 — Лгс) + Ь (1 — ЛсС) = 1 — С. Отсюда а = = ьУо, Ь = Л, — 1 1-Е с/5 Лс — Л 2 о/5 5— 1 1 /1-~- г/5 с/5 — 1Л = 1 — а = ь/ог.
Таким образом, А(с) = 2 2с/5 1 — Лсо 1 — Л»С 1 / 1 1 Аналогично находим В(С) = — ( — 1. Разлагая А(С) и В(С) в ос5 1 — Лсг 1 — Лгг/ ряд по степеням С, получаем, что а„= (2с/5)' ((1+ л/5)лс + (л/5 — 1)Лг), Ь„ = (з/сб) (Л", — Лг'). С учетом неравенств О < Л„ < Лс получаем, что 3.10. 1) Умножа» на С" и гуммиру» исходное соотношение, получаем А(с) - " = сА'(с) 2) Имеем А(с) = (2С) (1 — (1 — 4С) / ) = (2С) (1 — ~ ( — 1)»( с )(4С)') = =о = 2~ ( — 1)н ( с )(4С)н = ~ ~( )С".
=1 =о 3) Умножа» на С" и суммируя по н, получаем для производящей функции А(С) = ~ ~а„с" функциональное уравнение А (С) = А(2С). Будем ис- 383 Гл. 71П. Элементы комбинаторики кать его решение в виде А(1) = е"'. Эта функция, очевидно, удовлетворяет функциональному уравнению. Учитывая, что а~ = 1, находим, что а = 1, откуда а„= 1/ий Единственность решения вытекает из исходных соотно- шений. 3.20. Ц Пронумеруем вершины (и+ 2)-угольника числами 1, 2.....
..., и 4- 2 по часовой стрелке. Возможны два случая. Первый случай. Через вершину и. -1-2 не проходит ни одна диаго- наль. Тогда должна существовать диагональ между вершинами 1 и и Ч- 1, а число способов разбиения равно а, В т о р о й с л у ч а й. Существует диагональ, исходящая из верши- ны ич-2. Пусть й - наименьший номер такой, что вершина й+1 сое- динена диагональю с вершиной и+ 2. Если й > 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 ) — ! ь=! = ег„,(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„ некоторая орбита и х б М, то С = Ц Св „. При этом, очевидно, С„, П уем ПСв г, = гу при и ф у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
