Изменения

Для случая из двух множеств <texdpi = "140">A, B</tex> формула включения-исключения имеет следующий вид:

<texdpi = "140"> | A \cup B | = | A | + | B | - | A \cap B |</tex>

В силу того, что в сумме <texdpi = "140">| A | + | B |</tex> элементы пересечения <texdpi = "140">A \cap B</tex> учтены дважды, то уменьшаем текущее значение суммы на мощность пересечения, чтобы каждый элемент был подсчитан ровно один раз. Для наглядности воспользуемся диаграммой Эйлера{{---}}Венна для двух множеств, приведенной на рисунке справа.

Для случая с большим количеством рассматриваемых множеств <texdpi = "140"> n </tex> процесс нахождения количества элементов объединения состоит в поочередном включений ошибочно исключенного и исключений ошибочно включенного. Отсюда и происходит название формулы.

|statement=Пусть <tex dpi = "140"> A = \bigcup \limits_{i=1}^{n}A_i </tex> , тогда по формуле включения-исключения: <center> <tex dpi = "140"> | A | = \sum \limits_{I \in 2^N-1} (-1)^{|I|+1} \left| \bigcap \limits_{ j \in I} A_j \right| </tex> </center>Причем <tex dpi = "140"> N = \{ 1,2, \ldots ,n \} </tex>. Здесь за <tex dpi = "140"> 2^N - 1 </tex> обозначим множество всех непустых подмножеств <tex dpi = "140"> N </tex>.

<tex dpi = "140">k = (-1) ^ {t + 1} {t \choose t} + (-1) ^ {t} {t \choose {t - 1}} + \ldots + (-1)^2 {t \choose 1} + (-1) {t \choose 0} = -\sum \limits_{j = 1}^{t} (-1)^j {t \choose j} </tex><tex dpi = "140"> = {t \choose 0} - \sum \limits_{j = 0}^{t} (-1)^j {t \choose j} </tex>

Пусть <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=2</tex> (из базы индукции), то верно равенство <tex dpi = "130"> | A | = | B | + | A_n | - | B \cap A_n | (*)</tex>.   Найдем <tex dpi = "130">~| B \cap A_n |</tex>:

|statement= Количество беспорядков порядка <tex>n</tex> равно субфакториалу <ref>[http://ru.wikipedia.org/wiki/%D0%A1%D1%83%D0%B1%D1%84%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B0%D0%BB Википедия {{---}} Субфакториал субфакториалу] </ref> числа <tex>n</tex> (обозначение: <tex>!n</tex>) и вычисляется по формуле:

<tex dpi = "140150"> равно !n = n! - \frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + ... + (-1)^\frac{n!}\frac{n!}(-1)^{n!} = \sum_{k=0}^n(-1)^{k}\frac{n!}{k!}(-1)^{k} </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 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>

Также количество === Рекурретное соотношение для нахождения количества беспорядков === {{Утверждение|statement = Количество беспорядков удовлетворяет рекурсивным соотношениям:

|proof =1) Докажем второе соотношение: Так как <tex dpi = Примечание "140"> d(n)=!n </tex>, то можно переписать эту формулу, как <tex dpi = "140"> !n=n!(n-1)+(-1)^{n} </tex> По формуле субфакториала <tex dpi = "140"> !n=n!(\sum \limits_{k = 0}^{n-1} \frac {(-1)^{k}}{k!} + \frac {(-1)^{n}}{n!})=n!\sum \limits_{k = 0}^{n-1} \frac {(-1)^{k}}{k!}+(-1)^{n}=n \times !(n-1)+(-1)^{n}</tex> 2) Докажем первое соотношение: У нас есть <tex> n </tex> чисел и столько же мест. Мы должны найти количество способов разместить эти числа так, что ни одно из чисел не оказалось на месте с таким же номером. Предположим, что первое число оказалось на месте с номером <tex> i </tex>. Это можно сделать <tex> n-1 </tex> способами, так как первое число может оказаться на любом месте, кроме первого. Теперь есть 2 варианта, зависящие от того, окажется ли число с номером <tex> i </tex> на первом месте или нет. * Число <tex> i </tex> на первом месте. Остается <tex> n-2 </tex> мест и <tex> n-2 </tex> чисел. То есть количество беспорядков от <tex> n-2 </tex>* Число <tex> i </tex> не может оказаться на первом месте. Это эквивалентно решению задачи с <tex> n-1 </tex> местами и <tex> n-1 </tex> числами (первое число уже заняло место, а остальные еще нет): у каждого числа будет одно запрещенное место (у числа с номером <tex> i </tex> запрещенным будет первое место). Получается количество беспорядков от <tex> n-1 </tex>. Эти 2 случая не пересекаются и поэтому суммируются. В первом случае число <tex> i </tex> занимает первое место, затем идет распределение остальных чисел, не зависящее от первого и <tex> i </tex>-го чисел. Во втором же случае число с номером <tex> i </tex> попасть на первое место не может, а значит займет какое-то другое место, и распределение остальных чисел уже будет другое. В итоге получается необходимая формула. }} == Задача о перестановках == Сколько есть перестановок чисел от <tex> 0 </tex> до <tex> 9 </tex> таких, что первый элемент больше <tex> 1 </tex>, а последний меньше <tex> 8 </tex>? Посчитаем количество "плохих" перестановок, то есть таких, у которых первый элемент <tex> \leqslant 1 </tex> (множество таких перестановок обозначим <tex> X </tex>) и/или последний <tex> \leqslant 8 </tex> (множество таких перестановок обозначим <tex> Y </tex>). Тогда количество "плохих" перестановок по формуле включений-исключений равно: <tex> |X|+|Y|-|X \cap Y| </tex> Проведя несложные комбинаторные вычисления, получим: <tex> 2 \times 9!+2 \times 9! - 2 \times 2 \times 8! </tex> Отнимая это число от общего числа перестановок <tex> 10! </tex>, получим ответ. == Задача о нахождении числа взаимно простых четвёрок ==  Дано <tex> n </tex> чисел: <tex> a_1, a_2,..., a_n </tex>. Необходимо посчитать количество способов выбрать из них четыре числа так, что они будут взаимно простыми, то есть их НОД равен единице.  Посчитаем число "плохих" четвёрок, то есть таких, в которых все числа делятся на число <tex> d > 1 </tex>. Воспользуемся формулой включений-исключений, суммируя количество четвёрок, делящихся на <tex> d </tex> (но, возможно, делящихся и на больший делитель). <tex> answer=\sum \limits_{d>1} (-1)^{deg(d)-1} \times f(d) </tex>, где <tex> deg(d) </tex> — это количество простых в факторизации числа <tex> d </tex>, <tex> f(d) </tex> — количество четвёрок, делящихся на <tex> d </tex>. Чтобы посчитать функцию <tex> f(d) </tex>, надо просто посчитать количество чисел, кратных <tex> d </tex>, и с помощью биномиальных коэффициентов посчитать число способов выбрать из них четвёрку. Таким образом, с помощью формулы включений-исключений мы суммируем количество четвёрок, делящихся на простые числа, затем отнимаем число четвёрок, делящихся на произведение двух простых, прибавляем четвёрки, делящиеся на три простых, и т.д. == См. также ==* [[Производящая функция]]* [[Лемма Бёрнсайда и Теорема Пойа]] ==Примечания== <references />== Источники информации ==