Изменения
→Беспорядок
{{Определение
|id=идентификатор (необязательно), пример: def1.
|definition='''Беспорядок'''(''Disturbance)''' ) — это перестановка чисел от <tex>1</tex> до <tex>n</tex>, в которой ни один элемент не стоит на своём месте.
}}
{{Теорема
<tex>\lnot A_i</tex> — количество перестановок, в каждой из которых <tex>i</tex>-ый элемент стоит не на своём <tex>i</tex>-ом месте.
Таким образом <tex dpi = "130">| \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>). <tex dpi = "130">\binom{n}{1}</tex> — количество способов выбрать одну <tex>i</tex>-ую позицию <tex dpi = "130"> \Rightarrow \sum \limits_{i = 1}^{n} |A_i| = \binom{n}{1} (n-1)!</tex>
Рассмотрим <tex dpi = "130"> |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 = "130"> |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> равно <tex dpi = "130">\binom{n}{k} </tex>. Таким образом получаем, что:
