УказательРазделыОбозначенияАвторО проекте


Формула включений-исключений

Задача. Пусть даны подмножества A_1,A_2,\dots,A_{\mathfrak r} (необязательно различные) некоторого конечного множества. Найти мощность (число элементов) их объединения

\operatorname{Card}(A_1 \cup A_2 \cup \dots \cup A_{\mathfrak r}) \ .

В качестве первого приближения искомого числа можно принять значение

\operatorname{Card}(A_1) + \operatorname{Card}(A_2) + \dots + \operatorname{Card}( A_{\mathfrak r}) \ ,

однако это число в общем случае слишком большое, так как если A_{j} \cap A_k \ne \varnothing, то элементы этого пересечения учитываются в последней сумме дважды. Для исправления ситуации, вычтем «лишнее»:

\operatorname{Card}(A_1) + \operatorname{Card}(A_2) + \dots + \operatorname{Card}( A_{\mathfrak r}) - \sum_{1\le j_1 < j_2 \le \mathfrak r} \operatorname{Card}(A_{j_1} \cap A_{j_2}) \ .

Эта формула оказывается точной, если только отсутствуют тройки подмножеств A_j, A_k, A_{\ell} со свойством A_j \cap A_k \cap A_{\ell} \ne \varnothing. В последнем случае формулу придется снова корректировать «в сторону увеличения»:

При наличии большего числа множеств процедуру приходится продолжать.

Т

Теорема. Справедлива формула включений-исключений:

\operatorname{Card}(A_1 \cup A_2 \cup \dots \cup A_{\mathfrak r}) =
=\sum_{j=1}^{\mathfrak r} \operatorname{Card}(A_j) - \sum_{1\le j_1 < j_2 \le \mathfrak r} \operatorname{Card}(A_{j_1} \cap A_{j_2}) + \sum_{1\le j_1 < j_2 < j_3 \le \mathfrak r} \operatorname{Card}(A_{j_1} \cap A_{j_2} \cap A_{j_3}) - \dots +
*(-1)^{\mathfrak r-1} \operatorname{Card}(A_1 \cap A_2 \cap \dots \cap A_{\mathfrak r}) \ .

Доказательство. Применим индукцию по числу подмножеств \mathfrak r_{}. При \mathfrak r_{}=2 формула, очевидно, справедлива. Предположим, что формула справедлива для произвольных подмножеств A_1,A_2,\dots,A_{\mathfrak r-1}:

\operatorname{Card}(A_1 \cup A_2 \cup \dots \cup A_{\mathfrak r-1}) =
=\sum_{j=1}^{\mathfrak r-1} \operatorname{Card}(A_j) - \sum_{1\le j_1 < j_2 \le \mathfrak r-1} \operatorname{Card}(A_{j_1} \cap A_{j_2}) + \sum_{1\le j_1 < j_2 < j_3 \le \mathfrak r-1} \operatorname{Card}(A_{j_1} \cap A_{j_2} \cap A_{j_3}) - \dots +
+(-1)^{\mathfrak r-2} \operatorname{Card}(A_1 \cap A_2 \cap \dots \cap A_{\mathfrak r-1}) \ .

Применим эту формулу к сумме

(A_1 \cup A_2 \cup \dots \cup A_{\mathfrak r-1}) \cap A_{\mathfrak r} = (A_1 \cap A_{\mathfrak r}) \cup (A_2 \cap A_{\mathfrak r}) \cup \dots \cup (A_{\mathfrak r-1} \cap A_{\mathfrak r}) \ ,

получаем:

\operatorname{Card} \left( (A_1 \cap A_{\mathfrak r}) \cup (A_2 \cap A_{\mathfrak r}) \cup \dots \cup (A_{\mathfrak r-1} \cap A_{\mathfrak r}) \right)=
\sum_{j=1}^{\mathfrak r-1} \operatorname{Card}(A_j \cap A_{\mathfrak r}) - \sum_{1\le j_1 < j_2 \le \mathfrak r-1} \operatorname{Card}(A_{j_1} \cap A_{j_2} \cap A_{\mathfrak r}) + \dots +
+ (-1)^{\mathfrak r-2} \operatorname{Card}(A_1 \cap A_2 \cap \dots \cap A_{\mathfrak r-1} \cap A_{\mathfrak r}) \ .

Отсюда имеем:

\operatorname{Card}(A_1 \cup A_2 \cup \dots \cup A_{\mathfrak r}) =

(применяем формулу включений-исключений для случая двух подмножеств)

=\operatorname{Card} \left( (A_1 \cup A_2 \cup \dots \cup A_{\mathfrak r-1}) \cap A_{\mathfrak r} \right)=
=\operatorname{Card} \left( A_1 \cup A_2 \cup \dots \cup A_{\mathfrak r-1} \right) + \operatorname{Card} (A_{\mathfrak r}) - \operatorname{Card} \left( (A_1 \cap A_{\mathfrak r}) \cup (A_2 \cap A_{\mathfrak r}) \cup \dots \cup (A_{\mathfrak r-1} \cap A_{\mathfrak r}) \right) =

(применяем индукционное предположение и выведенную из него предыдущую формулу):

\begin{array}{lllll} = \displaystyle \sum_{j=1}^{\mathfrak r-1} \operatorname{Card} (A_j) & - \displaystyle \sum_{1\le j_1 < j_2 \le \mathfrak r-1} \operatorname{Card}(A_{j_1} \cap A_{j_2}) & + \displaystyle \sum_{1\le j_1 < j_2 < j_3 \le \mathfrak r-1} \operatorname{Card}(A_{j_1} \cap A_{j_2} \cap A_{j_3}) & - \dots + & (-1)^{\mathfrak r-2} \operatorname{Card}(A_1 \cap A_2 \cap \dots \cap A_{\mathfrak r-1}) \\ + \displaystyle \operatorname{Card} (A_{\mathfrak r}) &- \displaystyle \sum_{j=1}^{\mathfrak r-1} \operatorname{Card} (A_j \cap A_{\mathfrak r}) & + \displaystyle \sum_{1\le j_1 < j_2 \le \mathfrak r-1} \operatorname{Card}(A_{j_1} \cap A_{j_2} \cap A_{\mathfrak r}) & - \dots & + (-1)^{\mathfrak r-1} \operatorname{Card}(A_1 \cap A_2 \cap \dots \cap A_{\mathfrak r-1} \cap A_{\mathfrak r}) = \\ = \displaystyle \sum_{j=1}^{\mathfrak r} \operatorname{Card}(A_j) & - \displaystyle \sum_{1\le j_1 < j_2 \le \mathfrak r} \operatorname{Card}(A_{j_1} \cap A_{j_2}) & + \displaystyle \sum_{1\le j_1 < j_2 < j_3 \le \mathfrak r} \operatorname{Card}(A_{j_1} \cap A_{j_2} \cap A_{j_3}) & - \dots & + (-1)^{\mathfrak r-1} \operatorname{Card}(A_1 \cap A_2 \cap \dots \cap A_{\mathfrak r}) \ . \end{array}

Результат теоремы можно переформулировать на языке формальной логики:

Т

Теорема. Пусть даны N_{} произвольных объектов. Пусть

  • N_1число тех из них, которые обладают некоторым свойством \alpha_1;
  • N_{2}число тех, которые обладают свойством \alpha_2;
  • …;
  • N_{\mathfrak r}число тех, которые обладают свойством \alpha_{\mathfrak r}.

Аналогично пусть

  • N_{1,2}число тех из этих объектов, которые обладают одновременно свойствами \alpha_1 и \alpha_2;
  • N_{1,3}число тех из этих объектов, которые обладают одновременно свойствами \alpha_1 и \alpha_3;
  • N_{1,2,3}свойствами \alpha_1,\alpha_2 и \alpha_3;
  • N_{1,2,3 \dots,\mathfrak r}свойствами \alpha_1,\alpha_2, \alpha_3 , \dots, \alpha_{\mathfrak r}.

Тогда число объектов, которые не обладают ни одним из свойств \alpha_1,\alpha_2, \alpha_3, \dots , \alpha_{\mathfrak r} равно

N-\sum_{1\le j \le {\mathfrak r}} N_{j} + \sum_{1\le j_1 < j_2 \le {\mathfrak r}} N_{j_1,j_2} - \sum_{1\le j_1 < j_2 < j_3 \le {\mathfrak r}} N_{j_1,j_2,j_3} +\dots +(-1)^{\mathfrak r} N_{1,2,3,\dots,\mathfrak r} \ .

?

После прихода Гитлера к власти, в Германии появился анекдот:

«Такие человеческие качества как ум, честность и членство в NSDAP могут существовать только попарно.»

Пусть в группе из 100 человек 50 человек — умных, 40 — честных, 35 — партийных, 10_{} — умных и честных, 20 — умных и партийных, 15 — честных и партийных, 5 — умных, честных и партийных. Определить количество беспартийных и нечестных дураков в группе.

Источники

[1]. Липский В. Комбинаторика для программистов. М.Мир. 1988


2017/09/09 10:09 редактировал au