Дискретная математика. Азарнова Т.В - 27 стр.

UptoLike

Комбинаторика
27
Комбинаторика
§1
.
Общие правила комбинаторики
1.
Правило суммы
.
Пусть объект
a
можно выбрать
m
способами, объект
b
-
n
способами, не совпадающими со способами выбора объекта
a
. Тогда
выбор «либо
a
, либо
b
» можно осуществить
nm
+
способами.
Это правило справедливо и для большего числа объектов.
Если среди способов выбора объектов
a
и
b
есть
k
общих, то
указанный выбор можно осуществить
knm
+
способами.
Задача 1
. Имеется 10 билетов денежно-вещевой лотереи и 15 билетов
художественной лотереи. Сколькими способами можно выбрать один
лотерейный билет?
Решение
.
Билет денежно-вещевой лотереи можно выбрать 10
способами (все билеты различны), билет художественной лотереи15
способами. По правилу суммы выбор одного лотерейного билета можно
осуществить 10+15=25 способами.
Задача 2
. Сколькими способами из 28 костей домино можно выбрать
кость, на которой есть 1 или 2?
Решение
.
Выбрать кость, содержащую 1, можно 7 способами,
содержащую 2 – тоже 7 способами, но среди этих способов есть один общий
это выбор кости 1:2. Значит, общее число способов выбора нужной кости
считается как 7+7-1=13.
2.
Правило произведения
.
Если объект
a
можно выбрать
m
способами, а объект
b
можно
выбрать
n
способами, то выбор пары «
a
и
b
» можно осуществить
nm
способами.
Задача 3
. Из города А в город В идет 5 дорог, из В в С – 4 дороги.
Сколько путей, проходящих через В, ведут из А в С?
Решение. Весь путь их А в С состоит из 2 частейиз А в В и из В в С.
Из города А в город В можно выйти 5 способами, из города В в город С – 4
способами. Общее число путей, ведущее из А в С, 2045
=
.
Задача 4.
Сколькими способами можно выбрать гласную и согласную
букву из букв слова «компьютер»?
Решение
.
Гласную букву можно выбрать 3-мя способами. После
любого выбора гласной согласную можно выбрать 5-ю способами. По