2
правки
Изменения
Нет описания правки
[[Файл:пересечение двух множеств.svg.png|thumb|right|Случай для двух множеств]]
Для случая из двух множеств <texdpi = "140">A, B</tex> формула включения-исключения имеет следующий вид:
<center>
<texdpi = "140"> | A \cup B | = | A | + | B | - | A \cap B |</tex>
</center>
В силу того, что в сумме <texdpi = "140">| A | + | B |</tex> элементы пересечения <texdpi = "140">A \cap B</tex> учтены дважды, то уменьшаем текущее значение суммы на мощность пересечения, чтобы каждый элемент был подсчитан ровно один раз. Для наглядности воспользуемся диаграммой Эйлера{{---}}Венна для двух множеств, приведенной на рисунке справа.
Для случая с большим количеством рассматриваемых множеств <texdpi = "140"> n </tex> процесс нахождения количества элементов объединения состоит в поочередном включений ошибочно исключенного и исключений ошибочно включенного. Отсюда и происходит название формулы.
Сформулируем и докажем теорему для нахождения мощности объединения произвольного количества множеств.
'''II. Доказательство теоремы по индукции.'''
Пусть <tex dpi = "130">~l</tex> {{---}} это количество множеств, мощность пересечения которых мы ищем. Для случая <tex dpi = "130">~l=1</tex> равенство обращается в тривиальное (<tex dpi = "130"> |A| = |A_1| </tex> {{---}} истинно). Для случая <te tex dpi = "130"x>~l=2</tex> справедливость теоремы пояснена выше. Таким образом, <tex dpi = "130">~l=2</tex> {{---}} база индукции.
Предположим, что для <tex dpi = "130">~l=n-1</tex> равенство верно. Докажем, что равенство истинно для <tex dpi = "130">~l=n</tex>
Кроме того, так как формула верна для <tex dpi = "130">~l=2</tex> (из базы индукции), то верно равенство <tex dpi = "130"> | A | = | B | + | A_n | - | B \cap A_n | (*)</tex>. Найдем <tex dpi = "130">~| B \cap A_n |</tex>:
{{Теорема
|id=идентификатор (необязательно), пример: th1.
|statement= Количество беспорядков порядка <tex>n</tex> равно [http://ru.wikipedia.org/wiki/Субфакториал субфакториалу] числа <tex>n</tex> (обозначение: <tex>!n</tex>) и вычисляется по формуле:
<tex dpi = "140"> равно !n = n! - \frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + ... + (-1)^{n}\frac{n!}{n!} = \sum_{k=0}^n(-1)^{k}\frac{n!}{k!} </tex>
Воспользуемся принципом включения-исключения: обозначим за <tex dpi = "130">A_i</tex> — количество перестановок из <tex dpi = "130">n</tex> элементов, в каждой из которых <tex dpi = "130">i</tex>-ый элемент стоит на своём месте. Тогда по формуле включения-исключения имеем:
<tex dpi = "140"> \Big |\bigcap_{i=_1}^n \overline{A}_i \Big| = |U|-\sum \limits_{i} |A_i|+\sum \limits_{i<j} |A_i\bigcap A_j|-\sum \limits_{i<j<k} |A_i\bigcap A_j\bigcap A_k|</tex> <tex dpi = "130">+ ... +(-1)^{n}| A_1 \bigcap A_2 \bigcap ... \bigcap A_n | </tex>, где универсум <tex dpi = "130">U</tex> — множество из всех перестановок порядка <tex dpi = "130">n</tex>.
<tex>\overline{A}_i</tex> — количество перестановок, в каждой из которых <tex>i</tex>-ый элемент стоит не на своём <tex>i</tex>-ом месте.
<tex dpi = "130">|A_i| = (n - 1)!</tex>, так как <tex dpi = "130">i</tex>-ая позиция занята числом <tex dpi = "130">i</tex>. <tex dpi = "130">\binom{n}{1}</tex> — количество способов выбрать одну <tex dpi = "130">i</tex>-ую позицию <tex dpi = "130"> \Rightarrow \sum \limits_{i = 1}^{n} |A_i| = \binom{n}{1} (n-1)!</tex>
Рассмотрим <tex dpi = "130"> |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| </tex>, где <tex dpi = "130"> 1\le leqslant i_1 < i_2 < ... < i_k \le leqslant n </tex>. Так как некоторые <tex dpi = "130">k</tex> позиций <tex dpi = "130">i_1, i_2, ... , i_k </tex> заняты соответствующими числами, то количество способов расставить остальные <tex dpi = "130">n-k</tex> чисел равно <tex dpi = "130">(n-k)!</tex>. То есть <tex dpi = "130"> |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| = (n - k)! </tex> Количество всех способов выбрать <tex dpi = "130">k</tex> позиций <tex dpi = "130">i_1, i_2, ... , i_k </tex> равно <tex dpi = "130">\binom{n}{k} </tex>. Таким образом получаем, что:
<tex dpi = "130">\sum \limits_{1\le leqslant i_1 < i_2 < ... < i_k \le leqslant n}^{} |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| = \binom{n}{k} \cdot(n-k)! </tex>
Подставляя соответствующие значения мощностей множеств в формулу включения-исключения, получаем:
