Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 54
Текст из файла (страница 54)
4) Найти число таких пар (Х, У) подмножеств множества ГГ, что Х Г1 У = О, (Х! > 2, (Ц > 3. 5) Найти число таких пар (Х, У), что Х С о', У С 5Г., )(Х1У) 0 С (У'1Х)! = 1, (Х) > 2, )У! > 2. 6) Найти числотаких троек (Х, У, с ), что Х С (Г, У С (?, Л С (?, ХС(УСЯ) =ХНУ, )Х(>1, ~У! >1, (г( <1. 2.8. Задача мажордома. К обеду за круглым столом приглашены и пар враждующих рыцарей (и > 2). Требуется рассадить их так, чтобы никакие два врага не сидели рядом. Показать, что зто можносделать ~ ( — Ц" ( 1п.2" '(2п — к — Ц! способами. ~Й/ у=в 2.9.
3 ад а ч а о с у и р у ж е с к и х п ар а х. Сколькими способами можно расположить за круглым столом шесть супружеских пар так, чтобы мужчины и женщины чередовались и никакие двое супругов не сидели рядом? 3 3. Возвратные последовательности, производжцие функции, рекуррентные соотношения Последовательность ао, аь ..., ап, ...
называется возвратной, если для некоторого й и всех п выполняется соотношение вида апль+рза -ьь-з+. +рви =О, (Ц 266 Гт $715 Эзеиенты комбинаторики где коэффициенты р, (г' = 1, ..., Й) не зависят от п. Многочлен Р(,х) = х~ + рзхя +... + рь (2) называется характеристическим для возвратной последовательности. 3.1. Ц Доказать, что возвратная последовательность полностью определяется заданием ее первых Й членов и соотношением (Ц. 2) Пусть Л является корнем характеристического многочлена. Показать,что последовательность 1сЛ"), где с.- константа, удовлетворяет соотношению (Ц.
3) Доказать, что если Лы ..., Ли простые (нс являющиеся кратными) корни характеристического многочлена (2), то общее решение рекуррентного соотношения (Ц имеет вид аи = сзЛ," +... +сьЛ~г 4) Пусть Л, является корнем кратности г, (з = 1,..., з) характеристического многочлена (2). Доказать, что тогда общее решение рекуррентного соотношения (Ц имеет вид а, =~~ (ел+с,зп+...+с,„,п ' 1)Л,, где с,,~ (г = 1, ..., з, у = 1, ..., г,) --. некоторые константы. 3.2.
Найти общие решения рекуррентных соотношений; Ц а„, з — 4а„т1 -ь За„= 0; 2) а„.ьз -ь За„= 0; 3) аоиз — а„из — а„=О; 4) а„из+2а,,тз+а„=О; 5) а„из + 10 а„из + 32 а„тз + 32 а„ = 0; 6) а из+За„из+За„из+а„= О. З.З. Найти о, по рекуррентным соотношениям и начальным условиям: Ц а„из — 4а„из + За„= О, ао = 10., аз = 16; 2) аотз За„из + аииз — За„= О, ао = 3, аз = 7, аз = 27; 3) а„-,з — 3 а„т, + 2 а„= О, аз = а, аз = Ь, аз = с; 4) а„, з — 2 соз аа„,з з + о,„= О, ао — — 1, аз — — соз еб 5)а„~ьз — а„=О, ао=О, аз=2; 6) а„из — 6 а,.ь, + 9 а„= О, ао = 6, а1 = 6.
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)...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
