Дискретная математика. Элементы теории задачи и упражнения. Булгакова И.Н - 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.