Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 76
Текст из файла (страница 76)
Ц Положить С = 1 в (Ц. 2) Положить С = — 1 в (Ц. 3) Продифференцировать (Ц по С и положить С = 1. 4) Продифференцировать (Ц дважды и положить С = 1. 5) С использованием Ц и 3) имеем (2й-~- Ц(,) = 2~~ й(„) 4- ~~ („) = п. 2" -н 2" = (ив- Ц 2". ь=о о=о я=о 6) Проинтегрировать тождество (Ц по С от 0 до 1. 7) Проинтегрировать тождество (Ц по С от — 1 до О. 8) Провести индукцию по п с использованием задач 1.13, 2) и 1.17, 7).
9) Сравнить коэффициенты при Сь в левой и правой частях тождества (1+ 4)" (1+ Ц'" = (1+ С) 10) Положить в задаче 9) й = и = т. 1Ц Лелением на ( ) свести задачу к зацаче 10). /2п1 1.19. Ц ~ ~(2й) = (1+ Ц" + (1 — Ц" = 2 я 2)4~' (48) =(1-~-Ц +(1+С) +(1+С ) +(1+3 ) = 2" -1- (1 -~- С)" -~- (1 — ()" = 2" т (ъ'2)" (соз — -1- С з(п — 1 4 4/ 4-(э/2)в (соз — — Сып -1 = 2о 4- 2"/з 2 сов ™ .
4 4/ 4 374 Отпее7лы, указания, решенвя 2.1. 1) Доказательство. При л = 1 17!о = 1!7 — 17'1 = оо — О1, формула (Ц, очевидно, справедлива. Пусть формула справедлива для и — 1 свойств, и пусть 17'-, —, число предметов, не обладающих ни одним из свойств 1м ..., 7ю Имеем =1 1«,1<„-! — Х: ~чья + + (-1) -'~1 ,--1 (*) 1«1<1<„-1 Эта формула справедлива и для совокупности предметов, обладающих свОЙствОМ 71: Й77 †„ , „ = Ж„ — ~ 1Уь„ + ... 4-( — 1)ч 'Й77„ „, 1э„ (ея) 1« — 1 где 1771 †„ , „ ".число предметов, обладающих свойством п,но не обладаюпзйх ни одним из свойств 1,...,п — 1.
Ясно,что Вычитая формулу (**) из (*), получаем формулу (Ц. 2) Формулу (3) в соответствии с определением запишем следующим образом: У„,=~ (Ц( ~) ~ жч, 1< 1<,,,«,„э„< Докажем, что каждый предмет, обладающий гл свойствами, будет учтен в ней ровно один раз, а все другие -- ни разу.
В самом деле, элементы, обладающие э < ш свойствами, не учитынаются очевидным образом. Элемент, обладающий заданными э = т+ 1 свойствами, будет учитываться 77п+!1 во внутренней сумме ( й))! раз. Но (, т -!- я ) 1)1( ье)( 4!) (шэС)С,"( 1)1(С) ~ пйи ь=о ь=о Таким образом, в (3) ровно по одному разу учитываются элементы., обладающие в точности ш свойствами, а остальные но учитываются. 3) заметим, что х .11 = х — х„„и докажем (4) индукцией по т. По определению Хэ = 117 = оо Тогда )У1 = оо — (эо — о1 т эз — .) = ( — 1)1 'О1.. Тем самым (4) выполняется для т = 1. Пусть тождест1=1 во (4) справедливо при некотором ш 3 1.
Тогда 375 Гл. УП1. Элементы комбанаторики 2.2. Общее число способов выдачи шляп равно 4! = 24. Вероятность того, что ровно пг человек получат свои шляпы, равна Ж„,/4), где !У определяется формулой (3) при и. = 4. Имеем гуо = Яо — Ег +  — Яз + Ял = 4!— — 4 3!+6 2! — 4 1)-!-1=9, ро=З/8; № =Ег — 2~г.(-ЗЯз — 4Ел=4 3!— — 2 6 2)-!-3 4 — 4 1=8, рг=1/3, рг=1/4, рз=О, р4=1/24.
2.3. Ц Число распределений предметов, при которых данные й ящиков остаются пустыми, равно (п — й)', Яь =, (п — й)'. Остается применить (Ь) формулу (Ц. 2) Я, ея = ( )(гг — т — Ь)", Е(г,п,т) =Ж, = ~ ( — Ц" ( ' ) х ь=о х( Ь)(гг — т — к) = ( ) ~~' ( — Ц ( Ь™)(гг — гп — й) о=о 3) Использовать формулу (4) задачи 2.1, 3). 2.4. Указание. Использовать круги Эйлера. Ц 20% 2) 60% 3) 70% 2.5. Ц 2.
2) 6. 3) 3. 2.6. 2) 457. Используя формулу (Ц, получаем Яг = 675, Яг = 141, Яз = 9 гУо = 457. 3) 734. 4) Имеем М = Яо = ЗОт, Яг = 10т, Яг = Зиг, Яз = т, !Уо = Яо — Яг + + Лг — Яз = 22т. 2.7. Ц 3". Каждый элемент независимо от распределения других элементов может принадлежать одному из множеств*) ХУ ХУ или ХУ. 2) п 2". Один элемент из (1 принадлежит множеству ХУ 0 ХУ. Остальные элементы принадлежат одному из множеств ХУ или Х У. 3) 3 .
Равенство Х 0 Уь = Х 0 У равносильно равенству ХУ 0 0ХУЯ = (1. Таким образом, каждый элемент из (1 содержится ровно в одном из трех множеств ХУЯ, ХУ 2, ХУТ 4) 3" — (гг+ 2)2" + а(п+ Ц+ 1. 5) п(2" — 2п). 2.9. 4п ~ ~( — Ць(Ь)(2п — lг — Цз г[(гг — й)!)г. о<э< * 3 3 3.1. Ц Индукция. Числа ао, аы ..., аь г определены по следуюгдему условию: если все члены а, при ! < п уже определены, то с помощью (Ц получаем а„ег = — рга„— рга„г —... — рьа„геь 2) Требуется похавать, что сЛ"еь -Ь ргсЛ"~ Я ' -1-...
-Ь рьсЛ" = О, или, что то же самое, сЛ" (Л з-ргЛь г -1-... -!- ря) = О. Поскольку Л является корнем многочлена (2), то выражение в скобках обращается в О. 3) То, что о,„= сгЛг -Ь... -Ь сьЛг удовлетворяет соотношению (Ц, следует из задачи 2) и из того, что если последовательности а„и Ь„удов- *) Выражение «элемент о принадлежит множеству ХУ» здесь и далее понимается в смысле е 6 Х О ((уз,У), а о 6 ХУ равносильно о б б ((1З,Х) П (Ег1У). 376 Ответы, уназання, решеннк летворяют соотношению»Ц, то и последовательность »1 = аа„+ >УЬ„ему удовлетворяет при всех а и )>. Покажем теперь, что любая последовательность а , удовлетворяющая »Ц, может быть представлена в виде а = с>Л> -'т...
4- с»Л'„', где с, -- подходящие константы. В силу задачи Ц любая последовательность ач, удовлетворяющая 1Ц, полностью определяется своими первыми членами ае, аг, ..., а» г. Таким образом, остается показать, что для любых ае, ..., а» г сушествун>т сг, ..., с» такие, что с>+сг+...+с». =ао, с>Л> + с>Лг +... + саЛа = аг, с»Л, т с>Л> -'т ...-'т с»Л», , = а» >. » — г».— > » — 1 Определитель системы»г) является определителем Вандермонда »смс Кррош А.Г.
Курс высшей алгебры. -- Изд. 6. —. Мс »Ризматгиз, 1959). Он равен ϻ˄— Л>) и не абра»дается н нуль, если Л, ф Л при 1«><в г ф у . Следовательно, система 1г) имеет 1и притом единственное) решение. 4) Чтобы показать, что вякая последовательность указанного в условии вида удовлетворяет 1Ц,достаточно показать,что последовательность а„ = п Л", где Л вЂ” корень кратности т > ш многочлена 12), удовлетворяет »Ц. Подставляя а,. = в"'Л' 1в = и, ..., и -~- Ь) в левую часть»Ц и полагая ре = 1, получаем Цп) = »п4- й)">Л™в»+ рг»п 4-й — Ц" Л"" -т...-~р»п'"Л" = =Л" (~ „,( +й-1)-Ль-") =Л" (' ,Лв-'~,~ (,.)<Ь-Р --*) = >=о >=о =е = Лапы (~ ( . )п '~> р>Л '>»ь' — г)') = Лапы(~~ ( .
)гг 'Р,(Л)), =о >==о >=О где Р,1х) = ~ ~р 1/с — у) х >. Заметим, что Ро»х) = Ргх), где Р - мно>=о гочлен 12). Поскольку Л является т-кратным корнем многочлена Ре, то Регх) — 1х — Л)'Цо»х), где»ве некоторый многочлен. Нетрудно прова»» рить, что Р,г >1х) = х — Р,1х). Поэтому Р, = 1х — Л) '»в',1х), где Щ Йх многочлен.
Отсюда следует, что Р,1Л) = О при всех г < гт Следовательно, ЦЛ) = О. Тем самым»Ц выполнено для последовательности гг'"Л" при гп < т, а тем самым и для последовательностей указанного в условии вида. Докажем теперь, что любая последовательность а„, удовлетворяюп»ая 1Ц при условии, что Л, является корнем кратности т, »г = 1, ..., в) много- члена»2)> имеет вил, указанный в формулировке задачи. При этом без ограничения общности будем полагать, что р» ~ О, т.е. что нуль не является корнем характеристического многочлена. 1Если р» = О, то можно упростить 1Ц.) Для доказательства 1см.
решение задачи 3)) достаточно 377 Гл. 1'111. Элементы комбанаторики показать, что для любых ао, аг, ..., аь г система сг,г -с... -~- с,,г = ао, (сгд -~ сг,г 4-... -~- сг,„)Лг л-... 4- (емг 4-... л- с. г. ) Л, = аг, (сгд+ сг г(Ь вЂ” Ц+... +сгл,(Ь вЂ” Ц"')Л, '+... ... Ч- 1'смг -~ с.,г(к — Ц + ... + с„,„.(Ь вЂ” Ц'*)Л~ ' = аь имеет решение. Пля этого достаточно показать, что ее определитель не равен нулю, иличтовекторы Ло, ..., Лг ы где Л, = (Лг, гЛ*„..., г" Л'„...
..., Л'„гЛ'„..., г"'Л',) (г = О, ..., Ь вЂ” Ц, линейно независимы. Предположим противное. Тогда существуют константы бо, о1ы ..., дя ы не все рано-1 ные нулю, такие, что Л = о1оЛо +... + Оз-гЛь-г = О Пусть Я(х) = )~ Ах' *=о 41 и Л оператор такой, что г51(х) = х —.
Положим гЛ~ 7 = гз(гЛь ~Д. Ых То Л = (О<Л ), ЛС)(Л,), ..., Л"' г®Л ), ..., ®Л,), ...., Л"-' 'ЕЛ,)). Заметим, что Я(Л) = Лс~(Л) = ... = Л' СГ(Л) при Л = О тогда и только тогда, когда Л является корнем кратности г многочлена Я(х). Таким образом, Л = О означает, что Лг является хорнем кратности гг, Лг является корнем кратности гг, наконец, Л, является корнем кратности г, многочлена С1(х). Но гг 4- гг + ... + г, = К, а С1(х) является многочленом степени меньше к и, следовательно, не может иметь к корней.
Пришли к противоречию. Таким образом, система (л) имеет и притом единственное решенно. 3.2. Ц сг + сг 3". Характеристический многочлен хг — 4х+ 3 имеет корни Лг = 1 и Лг = 3. С использованием задачи 3.1, 3) получаем общее решение с~ Л7 + со Л",. 2) сг( — 3) И'+сг( — Ц" ( — 3)"1г. 3) сгИ14- чг5)г2)" Ч-сги1 — чгб)!2)'. 4) ( — Ц"(сг+ сои). 5) (сг+сггг)( — 4)" +сз( — 2)". 6) ( — Ц" (сг 4- с п 4- сгпг). 3.3. Ц 74-3". Общее решение сг 4-с 3" 1см. задачу 3.2, Ц). Из начальных условий имеем сг + Зсг = 10, хг+ 9сг = 16.
Отсюда сг = 7, сг = 1, ао = 7+ 3". 2) 3" + (~/ — Т)" + ( — з/ — Ц". 3) сг ->сгп.-~аз( — 2)", где сг = (14 — Ь вЂ” 4с)/9, сг = (Ьч-с — 2а)гг3, сз = (2Ь вЂ” с — а)/18. 4) сов огг. Корнями характеристического многочлена являются Лг,г = = е ' = сова хаша. Общее решение а, = сгЛг -> сгЛг. Из равенств аг = = сова, а = сов 2о находим сг = сг = 1/2. Отсюда а = (Лг 4- Лг)/2 = = сазан.
5) 1 — (-Ц". 6) 3" (1+и). 3.4. Ц Подставляя ап+ Ь в (3) вместо а„, получаем, что а(п Ч-2) 4- Ь- 4+ (а(п+ Ц + Ь) + д(оп + Ь) = па + гг. Сравнивая коэффициенты при п в левой и правой частях, а также свободные члены, получаем, что а = = пД1 4- р -~- д), Ь = Я1 -~- р -~ д)13 — п(2 4- р)) Д1 4- р -~- 9) г. 378 Ответы, указания, решенпя 2) Из того, что х = 1 является корнем многочлена х + рх+ д, следует, что р = — 1 — д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
