Просмотр кода страницы Мощность объединения множеств

{{Пример
|content=Пусть $A_1$, $A_2$, ..., $A_k$ {{---}} конечные множества.
Пусть $A = A_1\cup A_2\cup ...\cup A_k$.
Требуется найти мощность $A$, если известны $|A_i|$, $i=\overline{1,k}$, и 
$|\bigcap_{i\in I} A_i|$, $I\subseteq \{1,2,...,k\}$.
}}

Пусть $S = \{1,2,...,k\}$ и $T\subseteq S$. 
Будем говорить, что $x\in A$ обладает свойством $i$, если $x\in A_i$.

Обозначим  $f_=(T)$ {{---}} число элементов из $A$, обладающих всеми свойствами из $T$
и не обладающих другими свойствами из $S$;

$f_\geq(T)$ {{---}} число элементов из $A$, обладающих всеми свойствами из $T$.

Очевидно, $f_\geq (T) = |\bigcap_{i\in T} A_i|$, если $T$ не пусто и $f_\geq (\varnothing) = |A|$

Тогда можно использовать формулу включения-исключения.
{{Утверждение
|statement=<math>|A_1\cup A_2\cup ...\cup A_k| =
\sum_{i=1}^{k}|A_i| - \sum_{1\leq i_1 \lt i_2\leq k} |A_{i_1}\cap A_{i_2}| +
+ \sum_{1\leq i_1 \lt i_2 \lt i_3\leq k} |A_{i_1}\cap A_{i_2}\cap A_{i_3}|
- \cdots + (-1)^{k+1}|A_1\cap A_2\cap ... \cap A_k|.
</math>
|proof=Поскольку каждый элемент из $A$ обладает хотя бы одним свойством из $S$, то $f_=(\varnothing) = 0$.
С другой стороны, из формулы включения-исключения получаем
<math>
0 = f_=(\varnothing)= \sum_{Y\subseteq S} (-1)^{|Y|} f_\geq(Y) =
|A| +  \sum_{\substack{Y\subseteq S,\\|Y|\geq 1}} (-1)^{|Y|} |\bigcap_{i\in Y} A_i| =
</math>
<math>=|A|- \sum_{i=1}^{k}|A_i| + \sum_{1\leq i_1 \lt i_2\leq k} |A_{i_1}\cap A_{i_2}| -
\sum_{1\leq i_1 \lt i_2 \lt i_3\leq k} |A_{i_1}\cap A_{i_2}\cap A_{i_3}| +  \cdots + (-1)^{k}|A_1\cap A_2\cap ... \cap A_k|.
</math>
Перенесем все слагаемые, кроме первого, за знак равенства и получим  искомое утверждение.
}}

[[Файл:p31-01-union-cardinality.svg|frame|none|900px|alt=Три пересекающихся множества с числами по областям; формула 17−7+1=11|Рис. 1. Сумма мощностей <math>6+4+7=17</math> считает парные пересечения дважды, а тройное — трижды; вычитаем пары <math>2+3+2=7</math> и прибавляем тройное <math>1</math>. Получаем <math>|A\cup B\cup C|=17-7+1=11</math>.]]

Конспект: [[Дискретная математика]]

[[Категория:Дискретная математика]]