Изменения
Нет описания правки
|id=идентификатор (необязательно), пример: def1.
|definition='''Беспорядок(Disturbance)''' — это перестановка чисел от <tex>1</tex> до <tex>n</tex>, в которой ни один элемент не стоит на своём месте.
}}
{{Теорема
|id=идентификатор (необязательно), пример: th1.
|statement= Количество беспорядков порядка <tex>n</tex> или [http://ru.wikipedia.org/wiki/Субфакториал субфакториал] числа <tex>n</tex> (обозначение: <tex>!n</tex>) <tex dpi = "150"> равно !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>-ый элемент стоит на своём месте. Тогда по формуле включения-исключения имеем:
1) <tex dpi = "150">\Big |\bigcup_{i=_1}^n A_i \Big| = \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-1}| A_1 \bigcap A_2 \bigcap ... \bigcap A_n | </tex>
Данные формулы эквивалентны. Действительно, если некоторое множество <math>S</math> является подмножеством некоторого множества <tex>U</tex>, то, в силу законов де Моргана:
<tex>|S| = |U| - |\lnot S|</tex>, где <tex>U</tex> — универсальное множествоколичество перестановок из <tex>n</tex> элементов.
<tex>|U| = n!</tex>, т.е. количество перестановок из <tex>n</tex> элементов. Откуда следует, что <math>\lnot</math><tex>A_i</tex> — количество перестановок, в каждой из которых <tex>i</tex>-ый элемент стоит не на своём <tex>i</tex>-ом месте.
