== Формула включений-исключений== **Задача.** Пусть даны подмножества $ 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 $, то элементы этого пересечения учитываются в последней сумме дважды. {{ 2sets_1.jpg |}} Для исправления ситуации, вычтем "лишнее": $$ \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 $. В последнем случае формулу придется снова корректировать "в сторону увеличения": {{ 3sets_2.jpg |}} При наличии большего числа множеств процедуру приходится продолжать. !!Т!! **Теорема.** //Справедлива// **формула включений-исключений**: $$ \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}) \ . $$ **Доказательство.** Применим ((:basics:induction индукцию)) по числу подмножеств $ \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} \ . $$ !!?!! После прихода Гитлера к власти, в Германии появился анекдот: //"Такие человеческие качества как ум, честность и членство в// ((http://ru.wikipedia.org/wiki/NSDAP NSDAP))// могут существовать только попарно."// Пусть в группе из $ 100 $ человек $ 50 $ человек --- умных, $ 40 $ --- честных, $ 35 $ --- партийных, $ 10_{} $ --- умных и честных, $ 20 $ --- умных и партийных, $ 15 $ --- честных и партийных, $ 5 $ --- умных, честных и партийных. Определить количество беспартийных и нечестных дураков в группе. ==Источники== [1]. **Липский В.** //Комбинаторика для программистов.// М.Мир. 1988