Изменения

|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> 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 dpi = "140"> !n=(n-1)[!(n-1)+!(n-2)] i </tex>Заметимзанимает первое место, затем идет распределение остальных чисел, что если умножить не зависящее от первого и <tex dpi = "140"> n i </tex> на -го чисел. Во втором же случае число с номером <tex dpi = "140"> !(n-1) i </tex>, то получим часть второй формулыпопасть на первое место не может, а значит оставшиеся части формул будут равны:<tex dpi = "140"> !n=n \times !(nзаймет какое-1)-!(n-1)+(n-1) \times !(n-2) </tex>Распишем субфакториалы от <tex dpi = "140"> n-2 </tex> то другое место, и <tex dpi = "140"> n-1 </tex>: <tex dpi = "140"> (n-1) \times (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>распределение остальных чисел уже будет другое.<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>Субфакториалы от <tex dpi = "140"> n-2 </tex> сокращаются, остается верное равенство <tex dpi = "140"> -(-1)^{n-1}=(-1)^{n} </tex>В итоге получается необходимая формула.