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

UptoLike

ВУЗ: 

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

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

Рубрика: 

20
Пример. Имеются цветы трех видов: 10 васильков, 15 незабудок,
12 ромашек. Требуется разложить их на 2 букета. Васильки на 2 букета
можно разложить 11 способами, незабудки – 16, ромашки – 13 способа-
ми. Поскольку расклад каждого вида цветов выполняется независимо,
то общее число вариантов расклада будет: 11 ⋅ 16 ⋅ 13.
Обобщим полученный результат. Пусть имеется n
1
предметов 1-го
типа, n
2
– 2-го, ... n
k
– k-го. Требуется разложить эти предметы
на 2 кучки.
Тогда полное число вариантов расклада равно (n
1
+1)(n
2
+1)...(n
k
+1).
Пусть имеется некоторое число N. Требуется определить количе-
ство делителей N.
Решение. Представим N в канонической форме, т. е.
12
11
,...,
k
n
nn
k
Npp p
=
.
Тогда задача о нахождении числа делителей N сводится к задаче рас-
кладки степеней простых чисел на 2 делителя: т. е. решение будет:
(n
1
+1)(n
2
+1)...(n
k
+1).
Пример. N = 600 = 2
3
3
1
5
2
. Число делителей равно (3+1)(1+1)(2+1) = 24.
Упражнения
1. Сколько делителей имеют числа: 1350, 1617, 8280, 10013?
2. Сколько вариантов при раскладке в домино?
3. Сколько разных ожерелий можно составить из 5 изумрудов, 4 ру-
бинов и 6 сапфиров?
4. В вагон международного поезда, в купе которого имеется 2 дива-
на по 5 мест на каждом, входит 10 пассажиров. Из вошедших 4 челове-
ка хотят сидеть по ходу поезда, 3 против хода, а остальным – безразлично.
Сколько вариантов рассадки пассажиров имеется у проводника вагона?
При решении комбинаторных задач для нахождения числа благопри-
ятных комбинаций иногда удобнее вычислить число неблагоприятных
комбинаций и вычесть их количество из общего числа комбинаций.
Пример 1. Из n различных чисел требуется отобрать k таких,
чтобы в выбранное множество не входили s конкретных чисел. Общее
число выборов из n по k:
()
!
!!
k
n
n
C
knk
=
−
Выберем теперь s конкретных чисел и остальные доберем
−
−
способами. Это будет число неблагоприятных комбинаций. Число бла-
гоприятных комбинаций определится разностью

Страницы