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