90
правок
Изменения
→Формула включения-исключения
{{Теорема
|statement=Пусть <tex> A = \bigcup \limits_{i=1}^{n}A_i </tex> , тогда по формуле включения-исключения: <center> <tex> | A | = \sum \limits_{I } (-1)^{k+1} \Big| \bigcap \limits_{ j \in I } A_j \Big| </tex> </center>
Причем <tex> I = (i_1,i_2, \ldots ,i_k) \subset \{ 1,2, \ldots ,n \} </tex>, то есть некоторый набор индексов множеств, пересечение которых мы ищем в текущем слагаемом суммы. За <tex> k </tex> принимаем количество таких индексов в текущем <tex> I </tex>, за <tex> j </tex> индекс текущего множества (причем <tex> j \in I </tex>), которое будет входить в пересечение в текущем слагаемом.
||proof=Будем доказывать, опираясь на метод математической индукции.Для случая <tex>~n=1</tex> и <tex>~n=2</tex> теорема, очевидно, верна.
Теперь рассмотрим <tex>~n>2</tex>:
