1632
правки
Изменения
м
Так же, как и первом случае, напишем формулу через субфакториал:У нас есть <tex dpi = "140"> !n=(n-1)[!(n-1)+!(n-2)] </tex>чисел и столько же мест. Мы должны найти количество способов разместить эти числа так, что ни одно из чисел не оказалось на месте с таким же номером. ЗаметимПредположим, что если умножить первое число оказалось на месте с номером <tex dpi = "140"> n i </tex> на . Это можно сделать <tex dpi = "140"> !(n-1) </tex>способами, так как первое число может оказаться на любом месте, то получим часть второй формулыкроме первого. Теперь есть 2 варианта, зависящие от того, а значит оставшиеся части формул будут равны:окажется ли число с номером <tex> i </tex> на первом месте или нет. * Число <tex dpi = "140"> !n=n \times !(n-1)-!(n-1)+(n-1) \times !(n-2) i </tex>Распишем субфакториалы от на первом месте. Остается <tex dpi = "140"> n-2 </tex> мест и <tex dpi = "140"> n-1 2 </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> i </tex> не может оказаться на первом месте. Это эквивалентно решению задачи с <tex dpi = "140"> (n-1)!\sum \limits_{k = 0}^{</tex> местами и <tex> n-2} \frac {(-1)^{k}}{k!}-</tex> числами (n-1первое число уже заняло место, а остальные еще нет)!\sum \limits_{k = 0}^{n-2} \frac {: у каждого числа будет одно запрещенное место (-1у числа с номером <tex> i </tex> запрещенным будет первое место)^{k}}{k!}+ \frac {(-1)^{n-1}}{(. Получается количество беспорядков от <tex> 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>попасть на первое место не может, а значит займет какое-то другое место, и распределение остальных чисел уже будет другое. В итоге получается необходимая формула.
rollbackEdits.php mass rollback
{{Теорема
|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"> x \in \bigcup \limits_{i=1}^{n}A_i </tex>. Пусть <tex dpi = "140"> x \in \bigcap \limits_{j=1}^{t}A_{i_j} </tex>. Тогда найдем число вхождений элемента <tex dpi = "140"> x </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 = "140"> \sum \limits_{j = 0}^{t} (-1)^j {t \choose j} = 0</tex>
}}
=== Формула нахождения числа беспорядков Явная формула с использованием принципа включения-исключения ===
{{Теорема
|id=идентификатор (необязательно), пример: th1.
|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 = "150"> равно !n = n! - \frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + ... + \frac{n!}{n!}(-1)^{n}= \sum_{k=0}^n\frac{n!}{k!}(-1)^{k} </tex>
|proof=
Воспользуемся принципом включения-исключения: обозначим за <tex dpi = "130">A_i</tex> — количество перестановок из <tex dpi = "130">n</tex> элементов, в каждой из которых <tex dpi = "130">i</tex>-ый элемент стоит на своём месте. Тогда по формуле включения-исключения имеем:
}}
=== Рекурсивная формула Рекурретное соотношение для нахождения количества беспорядков ===
{{Утверждение
где <tex dpi = "140"> d(1)=0 </tex>, а <tex dpi = "140"> d(2)=1 </tex>
|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) Теперь, используя вторую формулу, докажем первуюДокажем первое соотношение:
}}
