Литература / Дополнительная литература / Шевелев Ю.П. Дискретная математика Томск Ч.2 2003 130 с
Запишем выражение в развернутом виде и в числителе вынесем за скобки 1 2 3 . ( n − 2) 1 2 3 . ( n − 2) .
Сократим его со знаменателем , тогда получим :
K = n 4 – 2 n 3 + n 2 + n –1.
1. Запишите следующие произведения с использова —
нием знака факториала :
(2 П 2) 1·3·4·6·7·8·9·10;
(8 РЕ ) 1·2·3·…·( n – 4)( n – 3);
(2 Я . РЕ ) 1·2·2·3·…· n ;
(485) 1·2·3·…· n ( n + 1);
( АМИ ) 1·2·3·…·( n –1)( n +1) n ;
2. Упростите и результат запишите с использованием
1 2 3 . n ( n +1)( n + 2)
1 2 2 3 3 4 5 . ( k −1) k 2
[ 1 2 3 . ( k −1) ] k 2
1 2 3 . ( k − 2) ( k −1) 2
1 2 3 . ( k −1)( k +1)
1 2 3 . ( k −1)( k +1)
1 2 3 . k +1 2 3 . ( k +1)
1 2 3 . ( k − 2)( k +1)
4. Вычислите при n = 31:
n ! ( n − 1)! ( n + 1)! n
5. Найдите значение функции при n = 2:
( Т 5 К ) f = ( n –3)!( n –2)( n –1) n .
6. ( ТОТ ). Какими цифрами не может оканчиваться число n !?
7. ( ЯШТ ). Какими цифрами может оканчиваться
число n ! при n > 3?
В общем случае если один элемент множества А 1 мож — но выбрать | A 1 | способами , элемент множества А 2 – | A 2 | способами и так далее до множества А n , один элемент ко — торого можно выбрать | A n | способами , то выбрать n эле — ментов в заданном порядке можно N способами , где
N = | A 1 | · | A 2 | ·…· | A n |.
Пример 1 . Пусть А = <1,2,3,4,5>. Один элемент из этого множества можно выбрать n = 5 способами . Останется четыре элемента . Один элемент из них можно выбрать m = 4 способами . Следовательно , выбор двух элементов возможен 5·4 = 20 способами , список которых имеет вид : 12, 13, 14, 15, 21, 23, 24, 25, 31, 32, 34, 35, 41, 42, 43, 45, 51, 52, 53, 54.
Заметим , что в каждой выборке цифры разные . Пример 2 . В урне пять шаров с номерами 1, 2, 3, 4, 5.
Вынимают один шар и записывают его номер . Шар воз — вращают в урну и наугад снова выбирают один шар и но — мер его записывают справа от первой цифры . Получится двухразрядное число . Сколько возможно таких чисел ?
На первом месте может стоять одна из пяти цифр , т . е . n = 5. На втором месте – также одна из пяти цифр . Следо — вательно , m = 5. Тогда искомое число nm = 5·5 = 25. Среди всех этих 25 выборок ( в отличие от предыдущего примера ) существуют пары с одинаковыми цифрами .
Пример 3 . Вернемся к примеру 2. Пусть шары извле — кают три раза . Сколько получится трехзначных чисел ?
На первом месте может стоять одна из пяти цифр , на втором – также одна из пяти , и на третьем – одна из пяти . Следовательно , число выборок равно 5·5·5 = 125.
Пример 4 . Сколько существует трехразрядных шесте — ричных чисел ?
В шестеричной системе счисления используются цифры 0,1,2,3,4,5. Первую цифру можно выбрать пятью способами , поскольку нуль не используем , так как число , начинающееся с нуля , не является трехразрядным . Вторая цифра может быть любой , в том числе и нулем , следо — вательно , ее можно выбрать шестью способами . То же самое относится и к цифре младшего разряда . Искомое число равно 5·6·6 = 180.
Пример 5 . Сколько существует пятизначных сим — метричных восьмеричных чисел , то есть таких чисел , которые одинаково читаются как слева направо , так и справа налево , например : 23032, 55655, 10001 и т . д .?
Первую цифру ( старшего разряда ) можно выбрать 7 способами , так как с нуля пятизначные числа начинать — ся не могут . Вторую цифру можно выбрать 8 способа — ми , поскольку теперь можно использовать и нуль . Для выбора третьей цифры также существует 8 вариантов . Цифры двух младших разрядов не имеют вариантов для выбора . Они должны повторять первые две цифры . Например , если выбраны цифры 372, то следующей может быть только цифра 7, а после нее – только цифра 3. Таким образом , всего существует 7·8·8 = 448 искомых чисел .
1.2. Правило произведения
Если один элемент множества А может быть вы — бран n способами , а после него второй элемент – m способами , то выбор того и другого элемента в за —
данном порядке может быть осуществлен N способами
1. ( ДЕЗ ). Имеется 10 карточек . На каждой записана гласная буква . Выбирают наугад карточку и к ней справа приставляют вторую , наугад выбранную после первой . Сколько возможно таких двухбуквенных слов ?
2. ( ТР 2). Сколько трехразрядных чисел можно обра — зовать из цифр 3, 4, 5, 6?
3. ( АКИ ). Сколько семизначных чисел можно обра — зовать из цифр 3, 7, 9?
4. ( АРМ ). Из пятизначных десятичных чисел удали — ли все числа , в которые входит хотя бы одна из цифр 0, 3, 7, 8, 9. Сколько чисел осталось ?
5. ( КЭФ )! Город А связан с городом В шестью дорогами . Сколькими способами житель города А может посетить город В , если возврат возможен по той же дороге , что и поездка в город В ? Сколькими способами житель города В может посетить город А , если поездка туда и обратно осуществляется по разным дорогам ?
6. ( УФ 5). Сколько четырехзначных чисел можно со — ставить из цифр 0, 1, 2, 3, 4, 5, если ни одна из цифр не повторяется в числе более одного раза ?
7. (927). Сколько трехзначных чисел можно соста — вить из цифр 1, 2, 3, 4, 5, если цифра младшего разряда каждого числа является четной , а старшего – не — четной ?
8. (296). Сколько существует пятизначных десятич — ных чисел , которые делятся на 5?
9. ( ХТБ ). Сколько существует пятиразрядных сим — метричных десятичных чисел ( которые одинаково читаются как справа налево , так и слева направо ,
например , 39793; 68286)?
10. ( УМС ). Старший разряд двузначного числа неко — торой системы счисления может содержать одну цифру из 7, младший разряд – одну цифру из х . Всего таких чисел существует 84. Найдите х ( десятичное число ).
11. ( ААТ ). Сколько существует трехразрядных семе — ричных чисел , оканчивающихся нечетной цифрой ?
12. ( ОРМ )! Сколько существует трехразрядных деся — тичных чисел , у которых :
– в старшем разряде нет ни одной из цифр 1,2,3,4,5;
– в среднем разряде нет цифр 2,5,7;
– в младшем разряде нет четных цифр и нет цифры 1?
1.3. Правило суммы в комбинаторике
Пусть даны множества Р 1 и Р 2 . Выясним , сколько эле — ментов содержится во множестве Р 1 U Р 2 . Эта задача не
так примитивна , как может показаться на первый взгляд . Она проста только при Р 1 I Р 2 = . В этом случае
| Р 1 U Р 2 | = | Р 1 | + | Р 2 | ,
т . е . если элемент множества Р 1 может быть выбран | Р 1 | способами , а элемент множества Р 2 – | Р 2 | способами , то выбор « либо элемент множества Р 1 , либо элемент мно — жества Р 2 » может быть осуществлен | Р 1 | + | Р 2 | способами .
Это и есть правило суммы [12, с . 250].
Пример 1 . В тарелке лежат 6 яблок и 4 груши . Сколь — кими способами можно выбрать один плод [9, с . 21]?
Если Р 1 – множество яблок , Р 2 – множество груш , то :
| Р 1 U Р 2 | = | Р 1 | + | Р 2 | = 6 + 4 = 10.
Рассмотрим случай , когда Р 1 I Р 2 ≠ Ø. Правило суммы при этом имеет вид :
| Р 1 U Р 2 | = | Р 1 | + | Р 2 | – | Р 1 I Р 2 |.
В [35, с . 140] эту формулу называют формулой вклю — чений и исключений , а в [56, с . 32] используется термин « принцип включения — исключения ». В [42, с . 140] ее на — зывают частным случаем формулы перекрытий .
Пример 2 . Пусть даны множества :
Сколько элементов во множестве Р 1 U Р 2 ? По правилу суммы | Р 1 U Р 2 | = 5 + 5 – 2 = 8.
В случае трех множеств правило суммы имеет вид
| Р 1 U Р 2 U Р 3 | = | Р 1 U Р 2 | + | Р 3 | – |( Р 1 U Р 2 ) I Р 3 | = | Р 1 | + + | Р 2 | – | Р 1 I Р 2 | + | Р 3 | – | Р 1 I Р 3 U Р 2 I Р 3 | = | Р 1 | + | Р 2 | –
– | Р 1 I Р 2 | + | Р 3 | – (| Р 1 I Р 3 | + | Р 2 I Р 3 | – | Р 1 I Р 2 I Р 3 |) = | Р 1 | +
+ | Р 2 | + | Р 3 | – | Р 1 I Р 2 | – | Р 1 I Р 3 | – | Р 2 I Р 3 | + | Р 1 I Р 2 I Р 3 |.
Для четырех множеств получаем аналогично :
| Р 1 U Р 2 U Р 3 U Р 4 | = | Р 1 | + | Р 2 | + | Р 3 | + | Р 4 | – | Р 1 I Р 2 | –
– | Р 1 I Р 3 | – | Р 1 I Р 4 | – | Р 2 I Р 3 | – | Р 2 I Р 4 | – | Р 3 I Р 4 | +
+ | Р 1 I Р 2 I Р 3 | + | Р 1 I Р 2 I Р 4 | + | Р 1 I Р 3 I Р 4 | + | Р 2 I Р 3 I Р 4 | –
– | Р 1 I Р 2 I Р 3 I Р 4 |.
В случае n множеств сумма имеет вид
| Р 1 U Р 2 U … U Р n | = | Р 1 |+| Р 2 |+…+| Р n | – (| Р 1 I Р 2 |+| Р 1 I Р 3 |+
…+| Р n –1 I Р n |)+(| Р 1 I Р 2 I Р 3 |+| Р 1 I Р 2 I Р 4 |+ …+| Р n –2 I Р n –1 I Р n |)–…+(–1) n– 1 | Р 1 I Р 2 I … I Р n |.
Пример 3 . Из 100 студентов английский язык знают 28 человек , немецкий – 30, французский – 42, английский и немецкий – 8, английский и французский – 10, немецкий и французский – 5, все три языка знают 3 че — ловека . Сколько студентов не знают ни одного ино — странного языка [22, с . 15]?
Обозначим : | Р 1 | – число студентов , знающих английс — кий язык ; | Р 2 | – знающих немецкий язык ; | Р 3 | – знающих французский язык . | P 1 | = 28; | P 2 | = 30; | P 3 | = 42.
| Р 1 I Р 2 | = 8 – число студентов , знающих два языка – английский и немецкий ;
| Р 1 I Р 3 | = 10 – число студентов , знающих два языка – английский и французский ;
| Р 2 I Р 3 | = 5 – число студентов , знающих два языка – немецкий и французский ;
| Р 1 I Р 2 I Р 3 | = 3 – число студентов , знающих три языка . По правилу суммы :
| Р 1 U Р 2 U Р 3 | = 28 + 30 + 42 – 8 – 10 – 5 + 3 = 80.
Таким образом , знают хотя бы один иностранный язык 80 студентов , следовательно , ни одного иностран — ного языка не знают 20 человек .
1. ( ОМН ). 30 учащихся сдавали экзамен по физике
и химии . По две отличные оценки получили 9 человек . На « отлично » физику сдали 12 человек , химию – 16. Ско — лько учащихся не получили ни одной отличной оценки ?
2. ( МОК ). 12 туристов взяли с собой по коробке спичек , 19 туристов – по зажигалке . Ни спичек , ни зажигалок не взяли 6 человек . Всего в отряде 27 человек . Сколько человек взяли с собой и спички и зажигалки ?
3. ( ОМТ ). Из 33 учащихся физический кружок посе — щают 11 человек . Из них 4 человека посещают еще и химический кружок . Ни физический , ни химический кружок не посещают 8 человек . Сколько человек посе — щают только химический кружок ?