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

UptoLike

Комбинаторика
34
§3. Формула включений и исключений
В основе решения многих комбинаторных задач лежит так называемая
формула включений и исключений.
Пусть
n
Χ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
Χ
,...,,
21
- подмножества некоторого множества
Χ
ΧΧ
Χ
, тогда
число элементов в объединении множеств
+++=
nn
Χ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
Χ
......
2121
21
Χ
ΧΧ
ΧΧ
ΧΧ
Χ
+
nn
Χ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
Χ
131
...
++++
nnn
Χ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
Χ
12321
...
()
n
n
Χ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
Χ
++
+
...1...
21
1
,
число элементов в множестве
Χ
ΧΧ
Χ
, не принадлежащих объединению множеств
n
Χ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
Χ
,...,,
21
+=
nn
Χ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
Χ
...)...(\
2121
++
21
Χ
ΧΧ
ΧΧ
ΧΧ
Χ
++
nn
Χ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
Χ
131
...
nnn
Χ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
Χ
12321
...
()
n
n
Χ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
Χ
++
...1...
21
.
Эти формулы носят название формул включений и исключений.
Приведем наиболее часто используемую интерпретацию данных
формул. Пусть
Χ
ΧΧ
Χ
- конечное множество, состоящее из
Ν
ΝΝ
Ν
элементов,
n
ααα
,...,,
21
- некоторые свойства , которыми могут обладать или не обладать
элементы из
Χ
ΧΧ
Χ
. Введем
{}
ni
,...,2,1
множество
{}
ii
свойствомобладаетxx
α
=
:
Χ
ΧΧ
ΧΧ
ΧΧ
Χ
. Обозначим для любого набора
()
nkiii
k
,...,2,1,...,,
21
=
через
()
kk
iiiiii
Χ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΧ
ΧΝ
ΝΝ
Ν
=
...,...,,
2121
ααα
- число
элементов в множестве
Χ
ΧΧ
Χ
, обладающих одновременно свойствами
k
iii
ααα
,...,,
21
. Тогда, в соответствии с приведенными выше формулами
включений и исключений, число элементов
0
Ν
ΝΝ
Ν
в множестве
Χ
ΧΧ
Χ
, не
обладающих ни одним из свойств
n
ααα
,...,,
21
, равно
()
n
n
Ζ
ΖΖ
ΖΖ
ΖΖ
ΖΖ
ΖΖ
ΖΝ
ΝΝ
ΝΝ
ΝΝ
Ν
1...
210
++=
,
где
(
)
.,...,2,1,,...,
...1
1
1
nk
nii
iik
k
k
==
ααΝ
ΝΝ
ΝΖ
ΖΖ
Ζ
Задача 1
. В студенческой группе 30 человек. Из них 15 человек знают
английский язык, 10 - французский, 6 - немецкий, 5 - английский и
французский, 3 - английский и немецкий, 3 - французский и немецкий, 2 -
английский, французский и немецкий. Сколько человек в данной группе не
знают ни одного языка?