Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 77
Текст из файла (страница 77)
Подставляя п(ап 4- Ь) вместо а в равенство а ег -~- +ра„ег — (р+ Ца„= пи+(), получаем, что а = аД2(р+ 2)); Ь = = (211(р -Ь 2) — а(р -Ь 4))Д2(р 4- 2) ). 3) Поскольку х = 1 является кратным корнем многочлена х + рх+ д, г то р = 2, д = 1. Подставляя пг(пи+ Ь) вместо а„в равенство а„ег+ + 2а ег + а„= оп + 13 и сравнивая коэффициенты при и, п, п, п, полуз г е чаем, что коэффициенты при пз и иг равны О и а = а/6, Ь = (гд — а)/2. 4) обзцее решение дпя задачи Ц а„= сг Л" ,+ сгЛг' + аггД1 + р+ д) + -Ь (ег(1 4-д -Ь р) — а(р Ь 2))/(1-Ьр 4-д)г), где Л11 гг = ( — р х;/р' — 4д)/2; для задачи 2) а„= сг( — р — Ц" + с + агг/(2(р+ 2)) + (2)3(р+ 2) — а(р х х 4))/2(р -Ь 2) г); для задачи 3) а„= пг((ап/6) т (11 — а)/2) + сгп + сг.
3.5. Ц а.„= 1 4- ( 2) . Общее решение рекуррентного соотношения епЛ а тг — ав = О есть произвольная константа с. Частное решение соотношения Ц будем искать в виде а,', = п(аи+Ь). Подставляя его в соотношение Ц, получаем, что а,*, = п(п — 1)/2. Обгнее решение соотношения Ц имеет вид а = а' 4-с. Из условия аг = 1 находим, что с = 1, а следовательно, а = 1 -1- п,(п — Ц/2. 2) а = 2( — 4)" — 3 2" 4- 5". Общее решение однородного соотношения а„вг + 2а„ег — 8а = О имеет вид сг( — 4)' + сг 2". Частное решение неоднородного соотношения 2) будем искать в виде а*„= д.
5". Подставляя а," вместо а, (г = и, п+ 1, п+ 2) в соотношение 2), получаем, что е( = 1. Общее решение неоднородного соотношения 2) сг( — 4)" -Ь сг . 2 + 5"; из начальных условий находим, что сг = 2, сг = — 3. 3) 2" ','-(ьг2)" '. 4) — -Ь вЂ” ( — 2)" 4- . 5) 2" з(иг — -~-8). 27 27 18 6) ( — -ь п)2" -ь — ( — 3)". 3.6. Ц Невырожденным является случай, когда либо дг р О, либо рг Ф ф О.
Если дг = рг = О, то, очевидно, и„= сгрг, Ь„= сгдг. Пусть дг ~ О. Тогда Ь, = 17(дг(а„ег — рга„)), Ь„ег = 1Ддг(аюы — р~аты)). Подставляя Ь„хг и Ь„во второе соотношение, получаем а вг + ( — рг — дг)а„ег + + (рпдг — ргдг)а„= О. Задача сведена к задача 3.1. а) а„= (5-ь 2п) 2"., Ь = — (1-ь 2и) 2". 3.7. Ц Индукция по и. При гг = 2 соотношение Гге,„= РгР„, -Ь + ГгГ, ег = Г + Р тг верно ддя всех гп > 1. Индуктивный переход п-гп+1: Г„ег< = Г„т +Г„„, г = Г, гГ +Єà вг+Р„гГ + +Г„,Р „=Äà +Г„„Г,„„. 2) Провести индукцию по Ь. 3) Если бы Г„ег и Г„имели общий делитель е( > 1., то и Г„г и Г„ имели бы тот же общий делитель., поскольку Р г = Р ег — Г„. По индукции отсюда вытекало бы, что и Рг и Гг имели бы делитель е(.
4) Способ представления. Если Х = 2, то Х = Гг -'г Гп Если гЛе > 2, то выбираем нанбодыпее гг~ такое, что Г„, ( Х, затем наиболынее т~г такое, что Г„г ( гЛе — Г„,, и т.д. Тогда Х = Г„, + Г„+... Поскольку Г„< г > Г„при п > 1, то представление не может содержать двух чисел с одним и тем же индексом п > 2. Представление не можот содержать двух соседних чисел Г„и Г,, г, поскольку Г„4- Г тг = Г„ег, Гл.
)г111, Элементы комбинагпорики 379 и, значит, на том шаге, когда было выбрано Р„еы должно было быть выбрано Г лз. 5) Общее решение рокурронтного соотношения Р„лз = Г„ез + Ро дано в задаче 3.2. 3) Используя начальные условия, получаем результат. б), 7) Показательство индухцией по и. 8) Применяя дважды тождество из задачи Ц, имеем Рз = Ро — 1Рз т ГвРз ез — à — 1(Р— 1Г т Г г л1) т Г (Г т Р ез)— = Р,',,Г„-ь Р„, ЄÄ., -~- Р,', —,— Р,'„,(Г„е, — Р„,) = з,з = Ктг ЬРо л à — 11'" +Р езР— з(Р Р ез) = =Р.„-:-Р.
-~Р. зР.-Г.~.Р., =Р;е, ~-Р;. -Р. з з 3 3 3 3 з з 3.8. Ц (1 — Ц '. 2) 1-~-С-Ь... -Ь С = (С' ~' — ЦДС вЂ” Ц. 3) (1 — оС) '. 4) е '. 5) (1-Ь С) '. б) С(1 — С) з. 7) 2Сз(1 — С) 8) (1-~- С) . 9) (1-~- С) . 10) С(С -~- Ц(1 — С) 1Ц Св1по(1 — 2Ссово+Сз) '. 12) (1 — Ссово)(1 — 2Ссово+Сз) 3.9. Ц е'. По определению Е(С) = ~ ",' = ~ ~—,. Этот ряд сходится к е'.
2) е '. 3) Се". 4) Сзе'. 5) (1-> С) . По определению Е(С) = ~ ~( " = 'у (т)С" — (1 л Ц" б) е'(С -~- С). 3.10. Ц .6) Сравнить хоэффициенты при С~. 311 Ц( )~д™ 'р" 2)1 3)( — Ц"( l) 4)( — Цо '"( ) ) (- ).--~. (- )"'-"(;) („.-'",„) я 8)( 2) 2и — ( 2) 2" . 9)( — Цо 'и ( — цп-' С 10) . Воспользуемся тем, что 11, = агсв8 С. Имеем 2п — 1 1 -~- вз е (1+ я ) ' = ~ ~( — Ц" л ". Интегрируя левую и правую части в пределах ( ц Сз.ез от 0 до С, получаем, что вгс18 С = з 2п+ 1 1 3 ... (2п — Ц 1 1 би 1Ц ''' ..
Указание. 11 = вгсзш 2 4 ... 2п 2па1 зСТ-.Ф о (-2)" Сз 12) при четных и и 0 при нечетных и. (и 12)! ( — цнС' 13) при четных и и 0 при нечетных п. (и/2 -~- Ц! 14) ( — Ц (т 1). 380 Отпветьь указания, реьхеннх 3.12 1) Сравним коэффициенты при 1" в тождестве (1 + 1) *(1+1) ~ = (1+4)" з.
С одной стороны, этот коэффициент равен 2) Рассмотреть тождество (1-~1) (1 — 1) = (1 — 4з)'" и сравнить коэффициенты при 1 ". 3) Рассмотреть тождество (1 — 4 ~)"' *(1 — 1) " ' = ( — 1)"'1 "'(1— — 1) " и коэффициенты прис 4) Рассмотреть тождество ((1 -1- 1)" 4- (1 — 1)" ) з = (1 -~- $) " 4- 2(1 — 1~)" ф -Ь (1 — 1) " и коэффициенты при 1 Ь) Рассмотреть тождество ((1 + 1) " -Ь (1 — 1) " )((1+ 1) — (1 — 1) "' ) = (1+1) " — (1 — 1) "и коэффициенты при 1" б) Рассмотреть тождество (1 — Х)з" (1+ 24(1 — 1) )" = (1 +Ьз)" и коэффициенты при 1 '". 3.13. 1) А(4) = ~ ~о„с" = ~ ~—" 1" /е 'х" бх = /е *) — ", (х1)" бх = =о о о = / е 'Е(х1) Их. о х = Ге "с1н = (1 — 1) 1 — С/ о о 3) Для последовательности а„из условия имеем А(1) = ~ (л)з1", Е(1) = з< о<э<- о<э< Палее, е'Е(хс) Их = ~ е ~ ~бх = Г (хс)" (п — 1)! о о э=о ( е 'х" Их = ~> (и) 1" = А(1).
э=а 3.14. Ц Воспользоваться тождеством (1 + 1)'+~ = (1 ф 1) . (1 Ь 1)~. Сравнивая коэффициенты при 1", получаем, что Умножая обе части на и!, получаем доказываемое равенство. 2) Положим а' = о/Ь, Ь' = Ь/Ь. Применяя тождество, доказанное в задаче 1), к а' и Ь', получаем, что (о' 4- Ь')„= ~ (',) (а')„я(6')ь, Умножая обе части на Ь", получаем доказываемое тождество (ибо (о'), Ь' = (а), ь). Гл, )г111. Элементы номбннатпорнни 381 3.15.
Ц Умножим равенство а„= ܄— Ь„г на 1" и просуммируем по и. В области сходимости рядов ~ ~а„1" и ~~ Ь„В' справедливы тождества =о ° =о а 1~ ~ ~(Ь Ь ЦП ~ ~Ь Ьг ~ Ь ге В(1)(1 1) =о =о =о »=1 2) Умножим равенство а = Ь тг — 6„на 1"т' и просуммируем по п в пределах от О до ж. Получим 1А(1) = В(1) — Ьо — 1В(1). 3) Заметим, что Ь„= сг„г — а,. Отсюда В(4) = — А(Ц(1 — С) + а причем а г = В(Ц. 4) Умножая равенство а = пб„на 1" и суммируя., получаем А(1) = пЬ 1' = 1 — В(4).
=1 6) Аналогично задаче 4). б) Сравним коэффициенты при 1" в равенстве А(1) = (1 — 1) ЯВ(1). Этот коэффициент ддя левой части равен по определению а„а ддя правой (-Ц'(,") Ь„, = , '("+,'. ') Ь„., = Вь(6„). г=о г=о 7) Имеем В(1иг) = ~> Ь„с" ~, В( — 1П') = ~ ~( — Ц" 6„1'о . Умножая =о =о сумму этих рядов на 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
