Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 76
Текст из файла (страница 76)
2) (2'")„. 1.6. ( т ) (, ) . Применяется правило произведения. 1 7 Ц (Л) ( Л )(и — а — )У),-.л-л. 1.8. Ц 4(и — 4). Масть карт можно выбрать четырьмя способами, после чего наименьший номер карты можно выбрать и — 4 способами. 2) 4и(и — Ц. Выбрать номер четырех карт можно и способами, после чего оствшуюся карту можно выбрать 4(тл — Ц способами. 3) 24и(и — Ц.
4) 4(б). в) 4з(и — 4). 6) 4и( 2 ). 7) 12и(2) -т 4из( ). 1.9. 2) 147. 2) 26. Число случаев выпацения одинаковых граней равно 6, число е'61 способов выпадения попарно различных граней равно (3) = 20. 3) 300 -т 300з -'г 300з. Гл. )г111. Элементы комбинаторики 371 1.10.
Ц (,—,) 2) (", '). 3) -'(и2 ) + 2(Г 2 )) (и — (гп — Ц 4 1) 2) (п 4 9) 3) (и-»-й) 1.12. Ц (1+ гг!)(1+ аз)... (1+ г! ). Каждому делителю ро'...р!» (О < 1», < а„! = 1, ..., г) можно взаимно однозначно сопоставить вектор (»»! ., »9,). Лаяео см. задачу 1.4, 2) 2) 2". Каждому делителю р! ! ...р"„'" числа п., не делящемуся на квадрат, можно сопоставить двоичный вектор (»»г, ..., »»,). 3) П(".' '- и -Ц ' ь=! Указание.
Заметить, что после раскрытия скобок в выражении (1 + р! 4-... т р, ' )... (1 -»- р, -и... 4- р„" ) каждый делитель присутствует в качестве слагаемого суммы ровно один раз. Пругое доказательст во. Число („) равно числу спогибов выбора к-элементного подмножества из 5» = (ог, ..., е„). Но каждому )г-элементному подмножеству взаимно однозначно соответствует его дополнение в с», являющееся (и — й)-элементным множеством. 1.15. Ц Решение.
Положим гг„! = ~ 1. Пусть уже определены ~(п — Ц!3 коэффициенты а„г, а„з, ..., гг„,. Тогда т — а„г(п — Ц! — а„з(п — 2)! —... — гг,(п — !)»~ — » г!»вЂ” (и — ! — Ц! Единственность представления докажем от противного. Пусть некоторому т соответствуют два вектора: а(гп) = (аг, ..., аи !) и»э(т) = = (»3», ..., »! — !). Пусть 1 наибольший из номеров разрядов, в которых векторы различаются. Без ограничения общности можно считать, что а! <»3».
Имеем — ! — ! ! †! ! †! 0 = ~г»3,г! — ~ гг,г! > (»1! — а )12 — ~ ~а,гг > »2! — ~ ~! ° »2! > О. =! =! =! =! Пришли к противоречию. 2) Н(4) = (О, 2), а(15) = (1, 1, 2), а(37) = (1, О, 2, Ц. 3)р(0,2,0,4)=100, р(0,2,Ц=10, р(1,2.,3,2)=71. 4) о(2!3,1,4) =8, и(3,5,2, 1,4) =68, о(1!3,3,5,2) =9. 5) Пусть задано число т. Представим его в виде гп = а! 1! + а!. 2! +... ... -»- а г(п — Ц), где а, < 1, 1 < г. '< п. Построение искомой подстановки я равносильно гюстроению вектора (»г(Ц, »г(2), ..., к(п)), Координаты к(1) зададим по индукции.
Положим »г(Ц = а„! -~- 1. Если координаты к(Ц, ..., х(1' — Ц определены, то положим х(1) = а„. + 1+ з(1), где е(1') число тех х(Й), 1 < Й < 1', для которых х(Й) < х(1). б)яг=(2,1,4,3), »г»з=(4,1,2,3), гг»з=(2,1,5,3,4). 1.16. Ц Координаты вектора»3(т) = (»1», ..., Щ,) определяютгя следующим образом: »3! —. наибольшее целое такое, что т > ( я ). Если / »3! '! 24* 372 Ответы, указания, решеннв /5и ..., 55, уже определены, то 55,; 1 --. наибольшее целое такое, что т — ( „з) — ( Я ) —...
— („1 ) > ( *т(). Единственность доказывается так же, как и в задаче 1.15, Ц. 2) а) 55(19) = (6, 4, 1, 0), так как ( ) + ( ) + ( ) + ( ). б) су(25) = (6, 3, 2). в) 55(32) = (6, 5,. 4, Ц . 3) а) т = 18, так как т = ( ) + ( ) + ( ) = 23. б) т=13, в) т=10. 4) Сопоставим вектору Н = (аы ..., ав) из Во сначала вектор 55 = = (550 ..., 55я), в котором 55/ + 1 является номером координаты (к — 1 + Ц-й слева единицы в наборе о, 1 (1 ( й. После этого полагаем и(Н) = д(53) + 1. Например, если Н = (1, О, О, 1, 0), то 55 = (3, 0), ц(Н) = д(/5) + 1 = ( ) + (о) 1.17. При и = 1 равенство (Ц проверяется непосредственно. Пусть равенство доказано для некоторого п ) 1. Имеем Е("~')" = Е (©'(."- ))'ь =Е(".)'"'Е(."- )'" = = ~ ©сь ~-~-(у„')ся" = (1-~с)"-~с(1 ~с).
= (1 ~с)-". ь — — о ь=о 1.18. Ц Положить С = 1 в (Ц. 2) Положить С = — 1 в (Ц. 3) Продифференцировать (Ц по С и положить С = 1. 4) Продифференцировать (Ц дважды и положить С = 1. 5) С использованием Ц и 3) имеем (2й-~- Ц(,) = 2~~ й(„) 5- ~~ („) = п. 2" 5- 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. Ц ~ ~(21) = (1+ Ц" + (1 — Ц" = 2 я 2)4~' (48) =(1-~-Ц +(1+С) +(1+5 ) +(1+3 ) = 2" -1- (1 -~- С)" 5- (1 — 5)" = 2" т (ъ'2)" (соз — -1- С з(п — 1 4 4/ 5-(з/2)в (соз — — Сып -1 = 2о 5- 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), удовлетворяет »Ц. Подставляя а,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
