Изменения

|statement= Количество беспорядков порядка <tex>n</tex> или равно [http://ru.wikipedia.org/wiki/Субфакториал субфакториалсубфакториалу] числа <tex>n</tex> (обозначение: <tex>!n</tex>) может быть вычисленно и вычисляется по формуле:

<tex dpi = "150140"> равно !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>

<tex dpi = "150140"> 2) \Big |\bigcap_{i=_1}^n \lnot 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>+ ... +(-1)^{n}| A_1 \bigcap A_2 \bigcap ... \bigcap A_n | </tex>   Данные формулы эквивалентны. Действительно, пусть <tex>U - </tex> универсальное множество, а <math>S</math> его некоторое подмножество, тогда, в силу законов де Моргана:  <tex>|S| = |U| - |\lnot S|</tex>, где универсум <tex>U</tex> — количество множество из всех перестановок из порядка <tex>n</tex> элементов.

<mathtex>\lnot</math><tex>A_i</tex> — количество перестановок, в каждой из которых <tex>i</tex>-ый элемент стоит не на своём <tex>i</tex>-ом месте.

Таким образом <tex dpi = "150130">| \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 tex dpi = "150130">\binom{n}{1}</mathtex> — количество способов выбрать одну <tex>i</tex>-ую позицию <math>\Rightarrow</math> <tex dpi = "150130">\Rightarrow \sum \limits_{i = 1}^{n} |A_i| = </tex> <math dpi = "150">\binom{n}{1}</math><tex> (n-1)!</tex>

Рассмотрим <tex dpi = "150130"> |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| </tex>, где <tex> 1\le i_1 < i_2 < ... < i_k \le n </tex>. Так как некоторые <tex>k</tex> позиций <tex>i_1, i_2, ... , i_k </tex> заняты соответствующими числами, то количество способов расставить остальные <tex>n-k</tex> чисел равно <tex>(n-k)!</tex>. То есть <tex dpi = "150130"> |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| = (n - k)! </tex> Количество всех способов выбрать <tex>k</tex> позиций <tex>i_1, i_2, ... , i_k </tex> равно <math tex dpi = "150130">\binom{n}{k} </mathtex>. Таким образом получаем, что:

<tex dpi = "150130">\sum \limits_{1\le i_1 < i_2 < ... < i_k \le n}^{} |A_{i_1} \bigcap A_{i_2} \bigcap ... \bigcap A_{i_k}| = </tex> <math dpi = "150">\binom{n}{k}</math><tex>\cdot(n-k)!</tex>

<tex dpi = "150130">| \bigcap_{i=_1}^n \lnot A_i | = n! + \sum \limits_{k = 1}^{n} (-1)^{k}(n - k)! \cdot</tex><math dpi = "150">\binom{n}{k}\cdot (n - k)!.</mathtex>

Раскрывая <math tex dpi = "150140">\binom{n}{k}</mathtex> по общеизвестной формуле, получим требуемое выражение, то есть количество беспорядков порядка <tex>n</tex>.