Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 53
Текст из файла (страница 53)
1.16. 1) Пусть Й, и, — — натуральные числа. Показать, что любому целому т (О < т < ( )) можно сопоставить (и притом единственным образом) целочисленный вектор 77(ги) = (777, 772, ..., 7777), удовлетворяющий условию и > ??7 > Нз »... Д > О, т = ( 7) -Ь /??7 з + ? ' ~Г +... + ( "'1. Число т в этом случае будем называть номером набора Д (обозначение; т = Ггф)). 2) Лля заданных Ги, п, к построить вектор ??(т); а)т=19,п=7, й=4: б)т=25, п.=7, к=3; в) т=32, и,=8, 1=4. 3) По заданному вектору ?? = (67, ..., Г?„) построить число иГ,, удовлетворяющее условию задачи 1): а) Д = (6, 3, О); б) 6 = (5, 4, 3, 1); в) Д = (6, 4, 3, 2., 1).
259 1 1. Пелевин»новая я сочетания 4) Пусть В„" подмножество всех векторов длины и с и единицами и и — )е нулями. Опираясь на задачу 1), построить нумерацию всех наборов из В" числами от 1 до ( '), т.е. взаимно однозначное отображение и множества В" на множество (1, 2, ..., ( ) ). /и-ь 11 1.17. Индукцией по и с использованием соотношения = ( ) + ( ) доказать тождество (1+1)" = ~ (",)1". (1) »=о 1.18. Пусть и и ьч целые положительные числа.
С использованием тождества»1) или иным способом доказать следующие ра; венства: 1) ~~~ ( ') = 2": 2) ~~~ ( — 1)»( ) = 0; 3) ~~~ й( ) = и2" »=о »=-о » — -» п в 4) ~к)к — 1)(~) = и»и — Ц2" з; 5) ~(2Й+ 1)(~) = »и+ 1)2"; »ся я=о п в 6) ~~ — ( ) = — (2вт~ — 1): 7) ~ ~( — 1)» — ( ) =— ь=о ь=о 8) ~ ( ) =1+ — +...+ —; »=1 ) ~(™,Н '-'.) =(и:е) ) Е(") =(':) 11)~ ' =( ); 12)~ ~ ~( Н )=3; 3) Е(-1) - (;) =Ь-1)-- - (;), ") Е ("".Н™.) = (™и-'и): "'~ -" "».)»7) =( 1.19.
Доказать тождества; ') к( ) = к(»"+ ) =' ' 17* 260 Рл, 1лЖ. Элементы комбинаторики 2) 4 ~~ ( ~ = 2и + 2и7з ' ~ соз— (4к) 4 ' т — 1 3) если 0 < г < т, тот~ ( ) = ~ е з "'Ди(1+ е~""7 )", о=а где г~ = — 1; 4) ~~ (4„) = — (2и + 2 и ~~~ соя( — (п — 2г)) ), 0 < г < 3; ь 5)если 0<г<т, т)1,то — (1 — (т — 1)соз" — ) < ~ ~( ) < — (1+(т — 1)сози — ). 1.20. 1) Доказать, что т — 1 тал л 1 и 1 к — злюло/т (1 + злю/т) и \;7пк+ г/ и=О С помощью тождества из и. 1) вычислить; 2) ~3 (2й)' 3) Е( — 1)"2 (4й 1)' 4) ~ ~( — 1) 3'(2~ 1). 1.21. Определить, сколько рациональных членов содержитсн в разложении: Ц (н2+ оеЗ); 2) (кеЗ+ Я) 3) (Я+ Я) 4) (/Г2+ Я) 1.22.
Найти коэффициент при оь в разложении: 1) (1+ 2à — Зео)а, й = 9; 2) (1 — О+ 21о)~о, к = 7; 3) (2+1 — 21з)1о Ю=ол. 4) (2+1'+Р')" йт17. 1.23. Доказать, что при целых т ) О, п ) О справедливы тождества: п 1) ~ — =, т)п, (и)ь т+ 1 (та)е еи — ге+ 1' о=о ~ (т -'л й — 1) з-~~ (и л й 1) ь=о ь=о 261 1 1. Перестановки и сочетания 1.24. Пусть а, Ь действительные, й, т, и, и целые неотрицательные числа. Показать,что: (:) (.
) = ( й 1) . т~ (:) « я=о 3) ( ) т1-1) ( „), а>0:, ~~» (а — й) (а -> 1) (а — и в=о 7 ~ (и+и — й — 1)(Ь+й — 1) (а+Ь+и — 1) в=о к (:Н,')(.-'-,) =(",',") О(ь,е<и 9) ~( — О ( 1Я т ~/ —; 1в) ~ ( 1'Е-1 твь — '3; т — 1 11) из з / о 1Ьтлв-е ~~, ' е — 2леел/т(1+ Ье2лелри)а ~-~ (шй в- и) .=-о 1.25. 1) Найти число всех таких слов длины ти в и-буквенном алфавите, в которых каждая буква алфавита встречается из раз. 2) Сколькими способами множество из и элементов может быть разбито на з подмножеств, из которых первое содержит 13 элементов, второе Йз элементов и т.д.? 3) Исходя из комбинаторных соображений, показать, что для любых целых неотрицательных йы йз, ..., Й„и таких, что йе + кз +...
... + Й, = и, справедливо равенство ( и) (и — /се) (и — йе — йе —... — й, е) и! 4) Индукцией по в доказать тождество и! (1, + 1, +... + 1,.)и = ~~~ 1",1,"... 1' . 1 ° 2. /си ..,е, ее-,—.. те.=и 5) ~ ь=о 6) я=о ( ) ( „) = ( ) 1теорема сложения); — "(:) = ('.') 262 Рл, Ъ'Ш. Элементы комбинаторики 8 2. Формула включений и исключений Пусть имеется лч' предметов и и свойств АЛ, ..., А„. Каждый из этих прецметов может обладать или не обладать любым из этих свойств. Обозначим чорез 1'1'1, Л„число предметов, обладающих свойствами А„, ..., Аи (и, может быть, некоторыми другими).
Тогда число Лло предметов, не обладающих ни одним из свойств АЛ, ... ..., Аи, определяется равенством 1уо ~0 ~1+Эз +1 1) ~а~ гдЕ ЯО = ЛЗЛ, а Эл — ~' 1'н,, м (2) 1<и «...Ле <и Формула Л1) называется формулой включений и исключений. П ример 1. Пусть колода состоит из п карт, пронумерованных числами 1,...,и. Сколькими способами можно расположить карты в колоде так, что ни для одного 1 Л1 < 1 < и) Карта С НОМЕрОм 1' НЕ занимает 1-0 место? Решение. Имеется п свойств о, вида «1-я карта занимает в колоде 1-е место». Число всевозможных расположений карт в колоде равно н).
Число 1ун ц расположений, при которых карта с номером 1, занимает место 1, (н = 1, й), равно (и — й)!. Тогда Яо=и!, БЛ= ~ 1Уи м=( )(и — к)!= —;. 1<6 «...м <и Используя формулу Л1), получаем, что число 110 расположений, при которых ни одно из свойств ае не выполняется, равно п и ~(-1)'Э, = .~ (-1)" — ',. 1=.0 ь=о В случае, когда свойств немного, для решения задач подобного сорта удобно пользоваться так называемыми кругами Эйлера.
Пример 2. В группе студентов 25 человек. Среди них 20 сдали сессик1 успешно, 12 занимаются в спортивных секциях, причем 10 а из них сдали сессию успешно. Сколько неус- певающих студентов не посещает спортивных У С секций? УЛЗ С Решение. Изобразим Лрис. 8.1) множество студентов, успешно сдавших сессию, кругом, Рис. 8.1 помеченным буквой У, а множество тех, кто занимается в секциях, кругом, помеченным буквой С. Пересечение кругов соответствует множеству успевающих студентов, занимающихся спортом, а объединение множеству студентов, которые учатся успешно или посещают секции.
Число таких студентов рав- 263 2" Я. Формула включений и исключений У П (Х О Я) = О. На диаграмме (рис. 8.2) 1' это соответствует тому, что соответствую- Х щие клетки пусты. Таким образом, Х, У, Я Х И тогда и только тогда удовлетворя|от условиям задачи, когда среди элементов множест- Я л У ва о' = (аы ..., ам) нет элементов трех ти: ХУг, ХУг и ХУХ Произвольный элеРнс. 8.2 мент из Г может принадлежать любому из остальных пяти типов. Отсюда число искомых троек равно 5~.
2.1. 1) Доказать по индукции формулу (1). 2) Пусть Хы — число предметов., обладающих в точности щ свойствами из и. Доказать,что и-т У„= ~ (-1)" ("'+")В „. ь=о (3) 3) Пусть Х„-- число предметов, обладающих в точности не менее чем т свойствами из п. Доказать, что и — ып Л = ~ '(-Ц"(™ '+,")В „. я=о (4) но 20 + 12 — 10 = 22. Число тех неуспевающих студентов, которые не посещают секций, равно 25 — 22 = 3. При решении задач, связанных с подсчетами числа элементов из множества П = (аы ..., ан), обладающих заданными свойствами, используются диаграммы Пенна.
Яиагр мма Венна для п свойств представляет собой прямоугольник, разбитый на 2" клеток. Каждая клетка соответствует одному типу элементов. Тип элемента определяется тем, что для каждого 1 (1 ( г ( и) известно, обладает элемент 1-м свойством или нет. Поэтому тип и соответствующую ему клетку удобно кодировать двоичным вектором (оп ..., оп), в котором а, = 1, если г-е свойство выполнено для данного типа элементов, и аы = 0 в противном случае (1 = 1, ..., и). Пример 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?, ХС(УСУ) =ХНУ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
