Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 52
Текст из файла (страница 52)
Показать, что: 1)Р(п,г)=п"; 2)С(п,г)=( ): 3)С(п,г)=( ). 1А. Найти число векторов а = (аы ..., аа), координаты которых удовлетворяют условиям; 1) а; е (О, 1....., к — 1) (1 = 1, ..., п):, 2)ае5(0,1,...,к,— Ц (в=1,...,.п); 3) а, й (О, 1) (1 = 1, ..., и) и а1 +... + аа = г. 1.5. Ц Каково число матриц из п строк и гп столбцов с элементами из множества (О, 1)? 2) То жс при условии, что строки матрицы попарно различны? 256 Гл. гП1, Элементы комбинаторики 1.6. Нано т предметов одного сорта и и другого. Найти число выборок, составленных из г предметов одного сорта и з предметов другого сорта.
1.7. Из п букв, среди которых а встречается о раз, буква 5 встречается ?1 раз,. а остальные буквы попарно различны, составляются слова. Сколько среди них будет различных г-буквенных слов, содержащих 6 раз букву и и ь' раз букву Ь? 1.8. Имеется колода из 4п ?п > 5) карт, которая содержит карты четырех мастей по п карт каждой масти, занумерованных числами 1, 2, ..., п. Подсчитать, сколькими способами можно выбрать пять карт так, что среди них окажутся: 1) пять последовательных карт одной масти: 2) четыре карты из пяти с одинаковыми номерами; 3) три карты с одним номером и две карты с другим: 4) пять карт какой-нибудь одной масти; 5) пять последовательно занумерованных карт; 6) в точности три карты из пяти с одним и тем же номером; 7) не более двух карт каждой масти.
1.9. Применяя правило суммы и правило произведения, решить следукещие задачи. 1) Сколькими способами из 28 костей домино можно выбрать две кости так, чтобы их можно было приложить друг к другу (т, е, чтобы некоторое одинаковое число очков встретилось на обеих костях)? 2) Бросают три игральные кости. Сколькими способами они могут упасть так,что все оказавшиеся сверху грани либо одинаковы, либо попарно различны? 3) У англичан принято давать детям несколько имен. Сколькими способами можно назвать ребенка, если ему дадут не более трех имен, а общее число имен равно 300? 1.10. 1) Сколькими способами можно число п представить в виде суммы й натуральных слагаемых? (Представления, различающиеся лишь порядком слагаемых, считаются разными.) 2) Сколькими способами число 7" можно представить в виде трех сомножителей? (Представления, различающиеся лишь порядком сомножителей, считаются разными.) 3) Решить задачу 2), если представления, различающиеся лишь порядками, разными не считаются и и ~ Зеь 1.11.
1) Сколькими способами можно расставить п нулей и к. единиц так, чтобы между любыми двумя единицами находилось не менее ш нулей? 2) Сколько существует неотрицательных целых чисел, не превышающих 10", цифры которых расположены в неубывающем порядке? 3) Карта города имеет вид прямоугольника, разделенного улицами на квадраты. Таких квадратов в направлении с севера на юг ровно и, а в направлении с востока на запад ровно к.
Сколько имеется кратчайших маршрутов от северо-восточного конца города до юго-западного? 257 7" 1. Переавлноени и сочетания 1.12. Пусть и = ро'...р„" разложение числа и в произведение простых попарно различных чисел. Найти: 1) число всех натУРальных делителей числа 1н)я; 2) число всех делителей, не делящихся на квадрат никакого целого числа, отличного от 1; 3) сумму делителей числа н. 1.13.
Доказать следующие свойства биномиальных коэффициен- ' (".) =(-"-.) ' ©(.") =("'.")(".) 3)( )=( )+( 1); 4) ~й/ /и — гз г =-О й (и -~- 1'1 1.14. Доказать, что: 1) (я ) возрастает по и при фиксированном /е; /и1 /и — г'г 2) ) ) убывает по с при фиксированных и и к; 3) если п фиксировано, то („") возрастает по а при а < ~ — ! и ~23 убывает при й > 1 — ~; 1 2 1' 4) щах (')=(,' ); иг ие /и,1 5) минимальное значение суммы ( ! + ( ) +... + ( ') при /о ~11 Ги1 Условии ,'г и; = п Равно 1е — г)(~ ) +г) ~ в ), где и = ~ — ~, г = (г/ ( Й )' е г=л =п — е~ — ~; 6) максимальное значение суммы ( ) + („) +...
+ ( ) при условии О</ез «...Йг <и 11<з<п+Ц равно у ( ); (у/ и — е п-'-г — </<— 2 2 7) при простом р и любом р > /е > 1 число ( ) кратно р; /р1 17 Г. П. Гаврилов, А. А. Сапоженяо 258 Гп. $7Ы Элементы комбинаторики 8) П р, < ( „), где произведение берется по всем простым /2пй п<т<зп числам р, (и < р, < 2п).
1.15. Ц Пусть т . целое неотрицательное число, а п = Гг(ггг) минимальное целое число такое, что т < и.'. Показать, что можно (и притом единственным способом) сопоставить числу т такой вектор а(т) = (аг, аз, ..., а, 7), что т, = аг 1! +аз 2. '+... ... + а„г(77 — 1)!, 0 < а, < 7 (Г = 1....., п — Ц. 2) Пусть р(а) число такое, что а = а(р(а)). Найти вектор а(т) для т=4,15,37.
3) По вектору а найти р(а), где: а) а = (О, 2, О, 4); б) а = (О, 2, 1): в) а = (1, 2, 3, 2). 4) Подстановкой на множестве з„= (1, 2, ..., п) называется произвольное отображение з„на себя. Всякой подстановке к взаимно однозначно соответствует вектор к = (к(1), ..., к(п)), в котором координата я(7) указывает место элемента 7. каждой подстановке к поставим в соответствие число 77(к), 0 < и(к) < и.', называемое номером подстановки. Лля этого сначала построим вектор а, = (аг, аз,... ..., а„г), Положим а„г = Гг(1) — 1.
Нели ап Г, ..., ап уже оп- РЕДЕЛЕНЫ И В(У) = ~(7 < У ~ К(7) < К(Я)~, тО ПОЛОЖИМ ап . = к(у + 1) — в(у + 1) — 1. Номер и(к) определим как р(а ). Например, если к = (3, 4, 2, 1), то а„= (1, 2, 2), 77(я) = 1+ 2. 2! + 2. 3! = 17. ПО подстановке 7Г, заданной некто?)ом 7Г, найти номе?7 77(7Г) 7 а) я = (2, 3, 1., 4), :б) к = (37 5, 2, 1, 4); в) к = (1, 37 4, 5, 2). 5) Лать алгоритм гюстроения подстановки к по ее номеру и(я).
6) По числУ т найти поДстановкУ к на множестве зп, гле и.' > > 777, > (Гà — 1)!, такую, что и(7г) = т: а)т=7; б)т=18; в)т=28. 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) Найти число всех таких слов длины ти в и-буквенном алфавите, в которых каждая буква алфавита встречается из раз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
