Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 55
Текст из файла (страница 55)
Пример 3. Пусть Х, У, Е подмножества множества П = = (аы ..., ак), удовлетворяющие условиям Х С (1 О Я) О о"1У, ЯС(ХГ~У)ОХ, УС(ХГ1Я)0л, гдЕ А=Г1А, АЕ(Х,У,Я). Найти число троек (Х, 1', Я). Решение. Для каждого а е П определены три свойства: а е Х, а Е У, а Е Я. Каждый элемент принадлежит одному из восьми типов в зависимости от принадлежности множества Х, У, Е. Очевидно, что включение А С В равносильно тому, что А О В = О. Поэтому условие Х С (У П Я) О У равносильно тому, что Х П (У П Е) О У = = Х П ((1' С1 а) П У) = Х П (л П У) = О.
Два остальных условия равносильны равенствам Я П (У П Х) = И, У 264 Гл. $715 Элеелентм колебинатораки 4) Показать, что Е, = ~ ("„') Яи„ ~и=я 8, = ~ (',",') У . (5) (6) ти=ь 5) Показать, что — (гл+ЦВ -г<Х <В (7) В,„— тЯ,ил1 < Ми, < Я,„. (8) 2.2. Четыре человека сдают свои шляпы в гардероб. В предпо- ложении, что шляпы возвращаются наугад, найти вероятность того, что в точности и. человек получат свои шляпы назад. Рассмотреть все значения и 10 < и < 4). 2.3.
Пусть Е1г, и, ш) ." число способов размещения г различных предметов по п ящикам, при которых имеется ровно гп пустых ящи- ков, а Е(г, п, т) число тех способов размещения, при которых не менее т, ящиков оказываются пустыми. Показать, что: и Ц Е(т, п, О) = ~ ( — Ц" (")1п — й) е; а=о и — т 2) Иг,п,ш) = ( "') ~ ~( — Ц~(а й™)1п — т — й)":, ь=о и — и~ 3) Г(г, пи ш) = ( ) ~~ (-Ць( )~п — т — й)" ь=о 2.4. При обследовании читательских вкусов студентов оказалось, что 60% студентов читают журнал А, 50%о журнал В, 50% журнал С, 30%о — журналы А и С, 20% — — журналы В и С, 40% журналы А и С, 10% -" журналы А, В и С. Выяснить, сколько процентов студентов: Ц не читает ни одного из журналов; 2) читает в точности два журнала; 3) читает не менее двух журналов. 2.5.
На одной из кафедр университета работают 13 человек, при- чем каждый из них знает хотя бы один иностранный язык. Десять человек знают английский, семеро - немецкий., шестеро †. фран- цузский, пятеро знают английский и немецкий, четверо — английский и французский, трос немоцкий и французский. Выяснить: Ц сколько человек знают все три языка; 2) сколько человек знают ровно два языка; 3) сколько человек знают только английский язык.
2.6. Ц Показать, что количество целых положительных чисел, делящихся на п и нс превосходящих х, равно ~т/и]. 2) Найти число целых положительных чисел, не превосходя- щих 1000 и не делящихся ни на одно из чисел 3, 5 и 7. у'у. Возвратные последовательности, производвтие функции 265 3) Найти число целых положительных чисел, не превосходящих 1000 и не делящихся ни на одно из чисел 6., 10 и 15. 4) Показать, что если и = 30т, то количество целых положительных чисел, не превосходящих п и не делящихся ни на одно из чисел 6, 10, 15, равно 22ш. 5) Пусть ры ..., р„все простые числа, не превосходящие и?пш Показать, что число пРостых чисел Р таких, что иси < Р < и., Рав— +~(- Гв,, ° ..
° в,=~(.," . ~ ~(р1 р " ?71 всевозможным ( ) наборам показателей оы..., а„в которых Й из показателей равны 1, а остальные равны О. 6) Найти число простых чисел, не превосходящих 100. 2.7. Пусть ГГ множество из и, (п, > 3) элементов. Ц Найти число пар (Х, У) таких подмножеств множества 5Г, что Х Г1У = И. 2) Найти число таких пар (Х, У), что Х С с?, У С (Г, ~(Х1У) 1д С(У'1Х)~ = 1. 3) Найти число таких троек (Х, У, Е), что Х С (Г, У С Г?, Я С 1?, ХС(УСУ) =ХНУ.
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, р, д - данные числа, является последовательность аи = = оп+ Ь; найти а и Ь; 2) если х = 1 — простой корень многочлена хз + рх + д, то частное решение может быть найдено в виде а„= п(ап + Ь); найти а и Ь; 3) если х = 1 -- кратный корень многочлена хз + рх + 9, то частное решение может быть найдено в виде а„* = пз(ап + Ь): найти а и Ь; 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, 171, Рз, 62 данные числа. Найти выРажениЯ дли ап и Ьп, считая, что а1 и Ь1 заданы. 2) Найти решение системы рекуррентных соотношений апв1 = Зап+ Ь„, Ьп;1 — ап + Ьп а1 = 14, Ь1 = — 6. 3) Найти общее решение системы рекуррентных соотношений ап.„1 = Ьп + 5, Ь„тг = — аз+ 3. 3.7.
Последовательность Фибоначчи 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а„).
В тех случаях, когда ряд А(3) сходится к некоторой функции 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 ) ( ) ( )' Суммирование ведется по всем в, для которых рассматриваемые выражения имеют смысл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
