Изменения
Нет описания правки
{{Теорема
|id=идентификатор (необязательно), пример: th1.
|statement= <tex> !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>
|proof=
Воспользуемся принципом включения-исключения: обозначим за <tex>A_i</tex> — количество перестановок из <tex>n</tex> элементов, в каждой из которых <tex>i</tex>-ый элемент стоит на своём месте. Тогда по формуле включения-исключения имеем:
<tex>|U| = n!</tex>, т.е. количество перестановок из <tex>n</tex> элементов. Откуда следует, что <math>\lnot</math><tex>A_i</tex> — количество перестановок, в каждой из которых <tex>i</tex>-ый элемент стоит не на своём <tex>i</tex>-ом месте.
Таким образом <tex>| \bigcap_{i=_1}^n \lnot A_i |</tex> - — количество всех перестановок, в каждой из которых <tex>i</tex>-ый элемент <tex>\neq</tex> <tex>i</tex>,т.е. количество искомых беспорядков. <tex>|A_i| = (n - 1)!</tex> (т.к. <tex>i</tex>-ая позиция занята числом <tex>i</tex>). <math>\binom{n}{1}</math> — количество спосбов выбрать одну <tex>i</tex>-ую позицию <math>\Rightarrow</math> <tex>\sum \limits_{i = 1}^{n} |A_i| = </tex> <math>\binom{n}{1}</math><tex> (n-1)!</tex>
Рассмотрим <tex>|A_iA_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| = (</tex>, где <tex> 1\le i_1 < i_2 < ... < i_k \le n - 1)!</tex> (т.к. Так как некоторые <tex>ik</tex>-ая позиция занята числом позиций <tex>ii_1, i_2, ... , i_k </tex>). Суммирование ведется по всем заняты соответствующими числами, то количество спосбов расставить остальные <tex>in-k</tex> чисел равно <mathtex>\Rightarrow(n-k)!</mathtex> . То есть <tex>|A_{i_1} \sum \limits_bigcap A_{i = 1i_2}^\bigcap ... \bigcap A_{ni_k} |A_i| = (n - k)! </tex> Количество всех способов выбрать <tex>k</tex> позиций <tex>i_1, i_2, ... , i_k </tex> равно <math>\binom{n}{1k}</math><tex> (n-1)!</tex>. Таким образом получаем, что:
<tex> \sum \limits_{1\le i_1 < i_2 < ... < i_k \le n}^{} |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| = (n - k)! </tex>, где <texmath> 1\le i_1 < i_2 < ... < i_k \le binom{n }{k}</texmath>. Так как позиции <tex>i_1, i_2, ... , i_k \cdot(n-k)!</tex> заняты соответствующими числами.
Подставляя соответствующие значения мощностей множеств в формулу включения-исключения, получаем:
}}
== Ссылки ==* [[wikipedia:ru:Беспорядок_(перестановка)|Википедия — Беспорядок]] * [[wikipedia:ru:Субфакториал|Википедия — Субфакториал]]
== Литература ==
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
