Дискретная математика. Азарнова Т.В - 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-ю способами. По 
                                    27
Комбинаторика
                             Комбинаторика


                   §1. Общие правила комбинаторики

1. Правило суммы.
       Пусть объект a можно выбрать m способами, объект b - n
   способами, не совпадающими со способами выбора объекта a . Тогда
   выбор «либо a , либо b » можно осуществить m +n способами.
       Это правило справедливо и для большего числа объектов.
       Если среди способов выбора объектов a и b есть k общих, то
указанный выбор можно осуществить m +n −k способами.

      Задача 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 » можно осуществить m ⋅ n
способами.

     Задача 3. Из города А в город В идет 5 дорог, из В в С – 4 дороги.
Сколько путей, проходящих через В, ведут из А в С?
     Решение. Весь путь их А в С состоит из 2 частей – из А в В и из В в С.
Из города А в город В можно выйти 5 способами, из города В в город С – 4
способами. Общее число путей, ведущее из А в С, 5 ⋅ 4 =20 .

     Задача 4. Сколькими способами можно выбрать гласную и согласную
букву из букв слова «компьютер»?
     Решение. Гласную букву можно выбрать 3-мя способами. После
любого выбора гласной согласную можно выбрать 5-ю способами. По

Страницы