Дискретная математика. Элементы теории задачи и упражнения. Булгакова И.Н - 27 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

2. КОМБИНАТОРИКА
2.1 Основные правила комбинаторики
Правило суммы:
Правило суммы для двух объектов: Пусть объект a можно выбрать
m способами, объект b – n способами, и существует k общих способов вы-
бора объектов a и b , тогда один из объектов “a или b” можно выбрать m
+ n -- k способами.
Пример 1. Сколькими способами из 28 костей домино можно вы-
брать кость, на которой есть "2" или "5".
Решение. Выбрать кость, содержащую "2", можно 7-ю способами,
содержащую "5" - тоже 7-ю способами, но среди этих способов есть один
общий - это выбор кости "2 : 5". В соответствии с правилом суммы общее
число способов выбора нужной кости можно осуществить 7+7-1 = 13 спо -
собами.
Правило суммы можно сформулировать для произвольного числа
объектов. Для этого достаточно использовать формулу для мощности объ -
единения конечного числа множеств. В случае трёх объектов формула
имеет вид :
|A
CB UU
| = |A| +|B| +|C| - |A
I
B| - |A
I
C| - |B
I
C| +|A
I
B
I
C|.
Правило суммы для 3-х объектов:
Если объект а можно выбрать n
1
способами, объект b – n
2
спосо -
бами, объект с – n
3
способами, и известны n
12
общих способа выбора од-
ного из объектов а и b , n
13
общих способа выбора одного из объектов а и
с, n
23
общих способа выбора одного из объектов b и с, а также известно
n
123
общих способа выбора одного их объектов а, b и с , то число всех спо-
собов выбора одного из объектов “а или b или с” вычисляется по формуле:
n
1
+ n
2
+ n
3
- n
12
- n
13
- n
23
+ n
123
(1)
Пример 2. В ходе экзаменационной сессии 12 студентов получили
оценки "отлично” , 12 - "хорошо", 13 - "удовлетворительно” , 5 - "хорошо" и
"отлично", 7 - "хорошо" и "удовлетворительно", 8 - "удовлетворительно" и
"отлично". У трех студентов все виды оценок. Сколько студентов в группе ,
если известно, что все они сдали сессию ? Сколько отличников в группе ?
Сколько в группе "чистых" троечников?
Решение. В условиях задачи n
1
= 12, n
2
= 12, n
3
= 13, n
12
= 5, n
23
= 7,
n
13
= 8, n
123
= 3. По формуле (1) находим общее число студентов в группе :
12+13+12-5-7- 8+3 = 20 ; число отличников в группе равно: n
1
– (n
12
+ n
13
) +
n
123
= 12 - (5+8) + 3 = 2; число “чистых” троечников равно n
3
– (n
13
+ n
23
) +
+ n
123
= 13 - (8 + 7) + 3 =1. 
                          2. КОМБИНАТОРИКА

                     2.1 Основные правила комбинаторики


      Правило суммы:
       Правило суммы для двух объектов: Пусть объект a можно выбрать
m способами, объект b – n способами, и существует k общих способов вы-
бора объектов a и b , тогда один из объектов “a или b” можно выбрать m
+ n -- k способами.

       Пример 1. Сколькими способами из 28 костей домино можно вы-
брать кость, на которой есть "2" или "5".
       Решение. Выбрать кость, содержащую "2", можно 7-ю способами,
содержащую "5" - тоже 7-ю способами, но среди этих способов есть один
общий - это выбор кости "2 : 5". В соответствии с правилом суммы общее
число способов выбора нужной кости можно осуществить 7+7-1 = 13 спо-
собами.
       Правило суммы можно сформулировать для произвольного числа
объектов. Для этого достаточно использовать формулу для мощности объ-
единения конечного числа множеств. В случае трёх объектов формула
имеет вид:
       |A  B  C | = |A| +|B| +|C| - |A  B| - |A  C| - |B  C| +|A  B  C|.
        Правило суммы для 3-х объектов:
        Если объект а можно выбрать n1 способами, объект b – n2 спосо-
бами, объект с – n3 способами, и известны n12 общих способа выбора од-
ного из объектов а и b , n13 общих способа выбора одного из объектов а и
с, n23 общих способа выбора одного из объектов b и с, а также известно
n123 общих способа выбора одного их объектов а, b и с , то число всех спо-
собов выбора одного из объектов “а или b или с” вычисляется по формуле:
                           n1 + n 2 + n3 - n12 - n13 - n23 + n123        (1)

       Пример 2. В ходе экзаменационной сессии 12 студентов получили
оценки "отлично”, 12 - "хорошо", 13 - "удовлетворительно”, 5 - "хорошо" и
"отлично", 7 - "хорошо" и "удовлетворительно", 8 - "удовлетворительно" и
"отлично". У трех студентов все виды оценок. Сколько студентов в группе,
если известно, что все они сдали сессию? Сколько отличников в группе?
Сколько в группе "чистых" троечников?
       Решение. В условиях задачи n1 = 12, n2 = 12, n 3 = 13, n12 = 5, n23 = 7,
n13 = 8, n123 = 3. По формуле (1) находим общее число студентов в группе:
12+13+12-5-7- 8+3 = 20 ; число отличников в группе равно: n1 – (n12 + n13) +
n123 = 12 - (5+8) + 3 = 2; число “чистых” троечников равно n3 – (n13 + n 23) +
+ n123 = 13 - (8 + 7) + 3 =1.

Страницы