Изменения

|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 = "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>

== Рекурсивная формула = Рекурретное соотношение для нахождения количества беспорядков ===

1) Сначала докажем Докажем второе соотношение:

2) Докажем первое соотношение: У нас есть <tex> n </tex> чисел и столько же мест. Мы должны найти количество способов разместить эти числа так, что ни одно из чисел не оказалось на месте с таким же номером. Предположим, что первое число оказалось на месте с номером <tex> i </tex>. Это можно сделать <tex> n-1 </tex> способами, так как первое число может оказаться на любом месте, кроме первого. Теперьесть 2 варианта, используя вторую формулузависящие от того, докажем первую:окажется ли число с номером <tex> i </tex> на первом месте или нет.

Так же, как и первом случае, напишем формулу через субфакториал:* Число <tex dpi = "140"> !n=(n-1)[!(n-1)+!(n-2)] i </tex>Заметим, что если умножить на первом месте. Остается <tex dpi = "140"> n -2 </tex> на мест и <tex dpi = "140"> !(n-1) 2 </tex>, то получим часть второй формулы, а значит оставшиеся части формул будут равны:чисел. То есть количество беспорядков от <tex dpi = "140"> !n=n \times !(n-1)-!(n-1)+(n-1) \times !(n-2) </tex>Распишем субфакториалы от * Число <tex dpi = "140"> n-2 i </tex> и не может оказаться на первом месте. Это эквивалентно решению задачи с <tex dpi = "140"> n-1 </tex>: местами и <tex dpi = "140"> (n-1) \times </tex> числами (n-2первое число уже заняло место, а остальные еще нет)!\sum \limits_{k = 0}^{n-2} \frac {: у каждого числа будет одно запрещенное место (-1)^{k}}{k!}-(n-1)!\sum \limits_{k = 0}^{n-1} \frac {(-1)^{k}}{k!}=(-1)^{n} у числа с номером <tex> i </tex>запрещенным будет первое место). Получается количество беспорядков от <tex dpi = "140"> (n-1)!\sum \limits_{k = 0}^{n-2} \frac {(-1)^{k}}{k!}-(n-1)!\sum \limits_{k = 0}^{n-2} \frac {(-1)^{k}}{k!}+ \frac {(-1)^{n-1}}{(n-1)!}=(-1)^{n} </tex>.Субфакториалы от Эти 2 случая не пересекаются и поэтому суммируются. В первом случае число <tex dpi = "140"> n-2 i </tex>занимает первое место, умноженные на затем идет распределение остальных чисел, не зависящее от первого и <tex dpi = "140"> n-1 i </tex>, сокращаются, остается верное равенство -го чисел. Во втором же случае число с номером <tex dpi = "140"> -(-1)^{n-1}=(-1)^{n} i </tex>попасть на первое место не может, а значит займет какое-то другое место, и распределение остальных чисел уже будет другое. В итоге получается необходимая формула.

Сколько есть перестановок числе чисел от <tex> 0 </tex> до <tex> 9 </tex> таких, что первый элемент больше <tex> 1 </tex>, а последний меньше <tex> 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>, и с помощью биномиальных коэффициентов посчитать число способов выбрать из них четвёрку. Таким образом, с помощью формулы включений-исключений мы суммируем количество четвёрок, делящихся на простые числа, затем отнимаем число четвёрок, делящихся на произведение двух простых, прибавляем четвёрки, делящиеся на три простых, и т.д.