Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 54
Текст из файла (страница 54)
3.4. Доказать, что: Ц если х — 1 не является корнем многочлена хз + рх+ 4, то частным решением рекуррентного соотношения "отг+Ра из+Чаи = пи+А (3) где а, 13, р, д - данные числа, является последовательность аи = = оп+ 6; найти а и Ь; 2) если х = 1 — простой корень многочлена хз + рх + д, то частное решение может быть найдено в виде а„= п(ап + 6); найти а и Ь; 3) если х = 1 -- кратный корень многочлена хз + рх + 9, то частное решение может быть найдено в виде а„* = пз(ап + 6): найти а и 6; 4) в каждом из предыдущих случаев найти общее решение соотношения (3).
3" Х Возвропгные последовательности, производлигос фгиннции 267 3.5. Решить рекуррентные соотношения: 1) апег — ап = п„аг = 1; 2) аплз+ 2ап 1 — 8ап = 27 5", ао = О, аг = — 9; 3) аггтз — 2 оп 1+ 2ап = 2", ао — — 1, аг — — 2; 4) ап 32+ апв1 — 2 аз = п, ао — — 1, аг — — — 2; 5) а оз — 4а„1+ 4ап = 2"г ао = 1, аг = 2; 6) аптз+ апаг — бап = 5 2п" 1, ао = 2, аг = 1.
3.6. 1) Пусть 1ап) и 1Ь„) - две последовательности, члены которых связаны соотношениями сгпл 1 = Р1 ап + Д1 Ьп, Ь - 1 = Рза, + г72Ьггг 2.3 = ргдз — рзог и- О, где Р1, 71, Рз, 62 данные числа. Найти выРажениЯ дли ап и Ьп, считая, что а1 и Ь1 заданы. 2) Найти решение системы рекуррентных соотношений апв1 = Зап+ Ь„, Ьп;1 — ап + Ьп а1 = 14, Ь1 = — 6. 3) Найти общее решение системы рекуррентных соотношений ап.„1 = Ьп + 5, Ь„тг = — аз+ 3. 3.7. Последовательность Фибоначчи 1гп) задается рекуррент- ным соотношением К„.ьз = Р„ег + г'„и начальными условиями г'1 = = гз = 1.
Показать, что: 1) для любых натуральныз гп и и Е„тт —— гп гг + Е„рте 1, 2) для любых пз и и = Ьт число г„делится на г', 3) дна СОСЕДНИХ ЧИСЛа Г'„И Гпл.г ВЗаИМНО ПрОСтЫ; 4) всякое натуральное число 131 (Х > 1) может быть однозначно представлено в виде суммы чисел Фибоначчи такой, что каждое число входит в сумму не более одного раза и никакие два соседних числа не входят вместе; г) е 6) ~1 + 3 + + г 2гг-1-1 г'згг-~-2 7) 1+ рз+Е~+ .
+ Б~п = рзп.1', с'3 + се р'3 С КажДОй ПОСЛЕДОВатЕЛЬНОСтЬЮ аО, агг ..., ап, ... МОЖНО СВЯ- зать ряд А(3) = аз + а13+... + ап3" +, .. г назъгваемый производящей функцией для последовательности 1а„). В тех случаях, когда ряд А(г) сходится к некоторой функции 7'13), функцию Д3) также называют производящей для 1а„). В задачах на нахождение произ- водящей функции для последовательности 1ап) обычно подразуме- 268 Глк $775 Элементы комбинаторики аА(1) + ДВ(1) = оао + ДЬо+ (паз + 1316)1+... + (аап+ ДЬп)1" +...
А(1) В(1) = аиЬе+ (аоЬ| + азЬе)1+ + (аед +азЬ„з+... +а„Ье)1п+ .. Коли Е,(1) и Ез(1) зкспоненциальные производящие функции соответственно для последовательностей (ап) и (Ьп), то сложение и умножение на константу определяются так же, как для обычных производяп1их функций, а их произведение определяется как Еп(1) Еь(1) = со + с11+...
+ — ", /и1 /иц где сп = аеЬп+ ( )азЬп ~+... + ( )аьЬ вЂ” я+ ° ° +а Ьо. 3.8. Найти производящую функцию 1(1) для последовательности (ап), если; Ца„=1 привсех о)0; 2) а„= 1 пРи 0< и <Я и ап = 0 пРи и) Дс; 3) а, =а"; 4) а„=а"/и1; 5) оп=( — Ц'; 6) оп=и; 7) ап = и(и — Ц; 8) а„= (™), т натуральное число; 9) ап = ( ), а действительное число; 1Ц а„= з1п ои; 12) и„= соз ои.
10) ап = из, 3.9. Найти экспоненциальные производящие функции Е(1) для последовательности (а„), если: Ц а„=1; 2) ап=о; 3) ап=и; 4) ап=и(и — Ц; 5) а„= (ьч)„; 6) ап = и.-'. 3. 10. С помощью тождеств, связывающих производящие функции, вывести следующие тождества для биномиальных коэффициентов: ь Ц (1+1).(1+1)- = (1+1) ™, ~ ("')(,"и ) = ("",""); н=о 2) (1 1) — 1 — п(1 1) — 1 — т (1 1) — 2 — и — т ~ ~~ (и+ з) (т -Ь Ь вЂ” з) (и -'и т -Ь й -Ь 1) н=о вается нахождение функции 1(1), ряд Маклорена которой есть А(г). Эксноненциальиой ироизеодян1ей функцией для (а„) называется ряд Е(1) = ае+ а~(1) +... + ап(1)/и! +...
Можно определить операции сложения, умножения на константу для производящих функций, рассматривая их как формальные ряды. Пусть А(1) и В(1) производящие функции для последовательностей (ап) и (Ь„) соответственно, а а, 11 " константы. Тогда у У. Воэвратпьсе последовательности, производящие 7«7уияииа 269 3) (1 -и «)п(1 + «) — пс (1 + «)п — пс я.-с (77) (7п+ «7 в — 1) (и — ш) 7=0 „ц (1 «) — с — п(1+ «) — 1 — и (1 «з) — с — п )с 77-р в) (77-р 2к — в) (и+ «7) с=о 5) (1+ «)п(1 — «З) " = (1 — «)п (в!О1 ~~ ~ п( и ) (77+ в — 1) (п+ «7 — 1) 7=.0 6) (1 + «)п(1 «)п (1 «2)77 ( 1)с( и ) (и) ( — 1) (й«2)7 и четно, 7=0 ( О, й нечетно.
3.11. Найти общий член ап последовательности, для которой функция А(«) является производящей. 1) А(«) = (7«+ р«)т; 2) А(«) = (1 — «) 7; 3) А(«) = ь«Т — «; 4) А(«) = «(1 — «); 5) А(«) = («+ «з + + «7) 6) А(«) = (1+ — ): 7) А(«) = (1+ 2«) с«з(1 — -) 8) А(«) = «з(1 — «)(1+ 2«) "', 9) А(«) = 1п(1+ «); 10) А(«) = агс«я«, 1Ц А(«) = агся«п«; 12) А(«) = е 13) А(«) = ~е * с«я; 14) А(«) = ( — ) о 3.12. Вывести тождества*): ' К -' " "(".) (™.
3) = (."-С ) 2) ~ ~( — Цс( ') ( ™ ) — ( — 1)77( ) )7( ш ) (17 л-в) (7п — и — 1) Е(2)(2 — 2) (2 ) ( ) ( )' Суммирование ведется по всем в, для которых рассматриваемые выражения имеют смысл. 270 Гл. $7Ы Элементы комбинаторики 5) 2 ~ (п+ 2е) (п -'е 2т — 2е Ч- 1) (2п -'с 2т, -'е 2) 6) ~ ~< — 1)" '4'( 2 ) =п,+1. л=а 3.13. Пусть А<1) и Е<1) являются соответственно обычной и экспоненциальной производящими функциями последовательности <о„). 1) Используя равенство и.
'= /е 'х" е1х,показать,что о А<1) = ~е иЕ<хц) е1х. <4) о 2) Убедиться, что формула (4) справедлива для производящих функций А<1) = <1 — 1) з и Е<1) = ее последовательности аа = аз = =аз=...=1. 3) То же, что и в задаче 2), но для последовательности с общим членом О, п(у, <и), и >11 3.14. 1) Пусть <а)„= о<а — 1)... <а — п+ 1). Доказать, используя экспоненциальные производящие функции, что и <а + Ь) а = ~~~ ( „) <а) и ь <6) ы У к а з а н и е. Использовать тождество < 1 + 1) " ' е = < 1 + 1) ' < 1 + 1) е, 2) Пусть <а)„и = п<а — 6)... <а — 6<п — 1)). Показать, что и <а+6)пь = ~ ( )<о)н — на<6)ьр.
я=о 3.15. Пусть <и„), <Ьп) последовательности, Ь 1 = О, А<1) и В<1) -- соответствующие производящие функции. Показать, что; 1) если ап = ܄— Ьа м то А<1) = В<1)<1 — 1); 2) если аи = Ьпл 1 — 6„, то А<1) = ВЯ вЂ” ' — ьа1 1 — 1 3) если а = дал з+ Ьниз+..., оа = В<1), то А<1) = В<1) — ВП) 1 — 1 4) если ан = пЬ„, то А<1) = 1 — В<1); Ж 5) если а„= пзЬ„, то А<1) = 1 — (2 — В<1)); с~ б е1 41<, бе 6) если определить операцию ол <Ь > 0) над последовательностью <д„) с помощью соотношения В':<Ьп) = Ьп+ (') Ьи, +... + ("+'.
') Ь„, +... + ("+ ') Ьа и положить а„= За<ба), то А<1) = <1 — 4) ~В<1); у" Х Возвратные ноеледовотельноети, нроизводвтие ер1рнниии 271 7) если ао = Ьзю то А(1) = — (В(1112) + В( — 1172)); 8) если ао = Ьо + Ь, +... + Ьи 1, ао = О, то А(1) = В(1)1(1 — 1) 3.16. Пусть А(1) и В(1) — производящие функции последователь- ностей (аи) и (Ь„) соответственно,и пусть А(1) В(1) = 1. Найти (Ьн) и В(1) по заданной последовательности (а„): 1) ао = ( ); 2) а„ = а"; 3) а„ = п + 1; 4) ао — — аз — — 1, а„=О при пФО,2; 5) а„= ( — 1)"; 6) ан = ( — 1)" ( )4 3.17. Пусть последовательность (а„) удовлетворяет рекуррент- ному соотношению анлз+ ра„ь1 + да„= О.
1) Показать, что А(1) = ао+ (а1+ рао)1 1 + ре -Ь о12 2) Пусть 1+ р1+ до~ = (1 — Л11)(1 — Л21), Л1 ф Лз. Показать, что Л7 — Л", Л вЂ” Л Л вЂ” Л 1 Л2 1 2 3) Выразить ао в случае, когда 1+ р1+ фз = (1 — Л1) . 3.18. Пусть "=к("") = к(гз) з=о 1=О и А(1), В(1) - — соответствующие производящие функции. 1) Показать, что а„и Ьо связаны соотношениями вида ап-~1 — — а„+ Ьие1, Ь 2-1 =б +а„по=1, .Ьо=О. 2) Показать, что А(1) и В(1) удовлетворяют системе уравнений А(1) — 1 = 1А(1) + В(1), В(1) = 1А(1) + СВ(С). 3) Найти А(1) и В(1). 4) Показать, что ( 2 ) 1+ьев ( 2 )" 1 1пп ( ) ао= 1нп ( ) Ь„= —.
(3+ йбг "' 2йб ' (3+ ь25) " ьеб 3.19. Пусть члены последовательности (а„) удовлетворяют соот- ношению ан — иоан — 1 + а111н — 2 + ° + ап — 1ао ао 1) Показать, что производящая функция А(1) = ~ аоби удовлетп=о воряет равенству 1А2(1) = А(1) — ао, или, с учетом начального усло- 1 — ьеГ: 41 вия равенству А(1) = 21 272 Гл. 1711 Элелентег нолбинаторггки 2) Разлагая Агг) в ряд по степеням 1, показать, что ап= — ( ). 3) Найти последовательность (ап), члены которой удовлетворяют соотношениям аоип г + игал †+ .
+ ггп — гао = 2пап, ао = аг —— 1. 3.20. Вывести рекуррентное соотношение для последовательности чисел (ап) и разрешить это соотношение, если: 1) ап --- число способов разбиения выпуклого (гг+ 2)-угольника на треугольники диагоналями, не пересекающимися внутри этого многоугольника; 2) ап число таких способов расстановки скобок в выражении Ьг . Ьэ .,...
Ьплг, при которых получающиеся выражения имеют смысл. 3.21. Используя метод математической индукции, найти последовательность (ап) по рекуррентному соотношению и начальным условиям: 1) а„пг = (и -и 1)ап, ао = 1; 2) па„лг + ап = О, аг = 1; 3) (и + 2)(п + 1)апе.я — п ип, ао = О, аг = 1; 4) (гг + 2)~алла + ап = О, ао = 1, аг = 0; 5) паап,з + (и + 2)зап — — О, аг — — 1, аг — — 0; 6*) а~юг — апа пз — — ( — 1)п г, ао = 1, аг = 1. 3.22.
Пусть А„гг) = ~ а(п, Ь)1' ь=о последовательности, удовлетворяющей соотношению а1гг, Й) = = а(п, Ь вЂ” 1) + а(п — 1, й) с начальными условиями а(п, 0) = 1, а(0, й) = 0 при й ) О. Показать, что: 1) 1 — 1)Апгг) = Ап г(1); 2) А„гг) = (1 — 1) 3) а(п, Ь) = ( ' ). 3.23. 1) Сколькими способами можно разменять 10-копеечную монету монетами в 1, 2, 3 и 5 копеек. 2) Та же задача, что и 1), при условии, что каждая из разменных монет присутствует в двух экземплярах. 3) Та же задача, что и 1), при условии, что имеются четыре копеечные монеты, три монеты достоинством 2 копейки, две трехкопеечные монеты и одна пятикопеечная. 3.24.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
