Конечные множества. Правила суммы для конечных множеств

Комбинаторика - это раздел математики, посвященный способам подсчета числа элементов в конечном множестве. В этом параграфе все множества предполагаются конечными, то есть в них конечное число элементов. Будем обозначать |Х| число элементов множества X.
В качестве аксиом в комбинаторике принимаются следующие:
1) Отрезок натурального ряда {1,2,...,п} содержит п элементов.
2) Если существует биективное отображение φ: X → Y, то |Х| =|Y| .
3) |Ø| = 0.
Если |Х| = п, то элементы множества X можно пронумеровать, то есть определить биективное отображение φ : {1,2,...,п}→ Х и обозначить φ(1) = х1 φ(2) = х2,..., φ(п) = хп. Ясно, что нумерация не однозначна.
Теорема 1.19. Пусть X uY - конечные множества и X ∩ Y = Ø. Тогда |X Y| = |Х| + |Y|.
Доказательство. Действительно, если X = {х1,х2, ...,хп}, Y = {у1,у2, ...,ут}, то X Y =
{х1, ...,хп, у1,..., ут}. (Мы пронумеровали множества X и Y и воспользовались тем, что
xi ≠ xj для любых i {1,…,n}, j {1,…,m}.
Теорема 1.20 (Правило суммы). Пусть X u Y - конечные множества. Тогда |X Y| = |X| + |Y| - |X ∩ Y|
Доказательство. Очевидно, что X Y = X (Y \ X) и X ∩ (Y \ X) = Ø. Тогда |Х Y| = |X| + |Y \ X| по предыдущей теореме. Аналогично, |Y| = |Y \ Х| + |У ∩ Х|. Следовательно |Y \ X| = |Y| - |Y ∩ X| и |X Y| = |X| + |Y| - |X ∩ Y|. Теорема доказана.
Теорема 1.21. Пусть A1,A2,... ,Ап - конечные множества. Тогда
|A1 A2 . . . An| = |A1| + |A2| + . . . + |An| -
- (|A1 ∩ A2| + |A2 ∩ A3| + . . . + |An−1 ∩ An|)+
(|A1 ∩ A2 ∩ A3| + . . . + |An−2 ∩ An−1 ∩ An|)+
. . . + (−1)n−1 |A1 ∩ A2 ∩ . . . ∩ An| .
Теорема доказывается с помощью индукции и использования предыдущей теоремы.

Задача. В студенческой группе 25 человек. 14 студентов изучают английский язык, остальные 16 студентов изучают немецкий язык. Сколько студентов изучают два языка: английский и немецкий?
Решение. Обозначим через X множество студентов, изучающих английский язык, через Y - множество студентов, изучающих немецкий. Тогда |Х| = 14, |Y| = 16, |Х Y| = 25. Следовательно 25 = 14+16 - |Х∩Y| и количество студентов, изучающих два языка равно |Х∩Y| = 5.

Powered by Drupal - Design by artinet