Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 54
Текст из файла (страница 54)
Всякой подстановке к взаимно однозначно соответствует вектор к = (к(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) Найти число всех таких слов длины ти в и-буквенном алфавите, в которых каждая буква алфавита встречается из раз.
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, ..., и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
