Дискретная математика. Ерош И.Л - 81 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

81
Упражнения.
1. Сколько разных делителей имеют числа: 1350, 1617, 8280,
10013?
2. Сколько разных делителей, кратных 102, имеют число 62424?
При решении комбинаторных задач для нахождения числа благо
приятных комбинаций иногда удобнее вычислять число неблагопри
ятных комбинаций и вычитать его из общего числа комбинаций.
Пример 1. Из n различных чисел требуется отобрать k таких, что
бы в выбранное множество не входили s конкретных чисел. Общее число
выборов из n по k определяется формулой
!
.
!( )!
k
n
n
С
kn k
1
2
Возьмем s конкретных чисел и остальные доберем
ks
ns
С
способами.
Это будет число неблагоприятных комбинаций. Число благоприятных
комбинаций определится разностью
.
kks
nns
CС1
Пример 2. Из группы в 15 человек нужно отобрать бригаду, в кото
рую должно входить не менее 5 человек. Сколько имеется вариантов
выбора?
Подсчитаем число неблагоприятных комбинаций:
1
15
C
+
2
15
C
+
3
15
C
+
+
4
15
C
= 15 + 105 + 455 + 1365 = 1940. Общее число комбинаций равно
2
15
– 1 = 32767. Тогда число благоприятных комбинаций равно 32767–
– 1940 = 30827.
Упражнение.
Обобщите решение последней задачи, если выбор выполняется из n
человек, а в бригаду должно войти не менее k человек.
4.3.3. Раскладка предметов по k ящикам
Рассмотрим следующую задачу. Трое мальчиков собрали 40 яблок.
Сколько существует вариантов раздела яблок между ними?
Запишем 40 единиц и добавим к ним два нуля. Будем переставлять
полученную комбинацию всеми возможными способами. Каждой пе
рестановке взаимно однозначно будет соответствовать способ раздела
40 яблок на три кучки. Следовательно, число способов раздела равно
P(40, 2) =
42!
40!2!
42 41
2
1
22
861.
Если требуется разложить n предметов по k ящикам, то число спо
собов раскладки будет равно P(n, k–1) =
(1)!
!( 1)!
nk
nk
12
2
. Если же требуется

Страницы