Изменения

== Беспорядки Беспорядок ==

|definition='''Беспорядком(Disturbance)''' в комбинаторике называется перестановка чисел от <tex>1</tex> до <tex>n</tex>, в которой ни один элемент не стоит на своём месте.

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

Воспользуемся принципом включения-исключения: обозначим за <tex>AiA_i</tex> — количество перестановок из <tex>n</tex> элементов, в каждой из которых <tex>i</tex>-ый элемент стоит на своём месте. Тогда по формуле включения-исключения имеем:

Данные формулы являются эквивалентнымиэквивалентны. Действительно, если некоторое множество <math>S</math> являются подмножествами является подмножеством некоторого множества <tex>U</tex>, то, в силу законов де Моргана :

В данной задаче множество Где <tex>U</tex> — есть количество перестановок из универсальное множество. <tex>|U| = n!</tex> элементов, т.е. количество перестановок из <tex>n!</tex>, а элементов. <math>\lnot</math><math>S</math> означает дополняющее множество до <tex>U</tex> <math>\Rightarrow</math> . Откуда следует, что <math>\lnot</math> <tex>AiA_i</tex> — количество перестановок, где в каждой из которых <tex>i</tex>-ый элемент стоит '''НЕ''' не на своём <tex>i</tex>-ом месте.

Таким образом величина в левой части формулы 2) — есть <tex>| \bigcap_{i=_1}^n \lnot A_i |</tex> - количество всех перестановок, где на 1в каждой из которых <tex>i</tex>-ой позици '''НЕ''' 1ый элемент <tex>\neq</tex> <tex>i</tex>, на 2-ой позици '''НЕ''' 2 и т.де. То есть количество искомых беспорядков. Осталось определить величины в правой части:

<tex>U|A_i| = (n - 1)!</tex> (т.к. <tex>i</tex>-ая позиция занята числом <tex>i</tex>). Суммирование ведется по всем <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>Ai</tex> — количество перестановок с уже занятой позицией <tex>i</tex> <math>|A_{i1} \bigcap A_{i2} \bigcap ... \Rightarrow</math> <tex>Ai</tex> <tex>bigcap A_{ik}| =</tex> <tex>(n - 1k)!</tex>. Суммирование ведется по всем <tex>i</tex> <math>\Rightarrow</math> , где <tex>\sum \limits_{i = 1}^{n} |\lnot le i1 </tex>i2 <tex>U</tex>... <tex>|</tex> <tex>=</tex> <math>ik \binom{le n}{1}</math><tex>\cdot. Так как позиции </tex><tex>(n-1)!i1, i2, ... , ik </tex>заняты соответствующими числами.

Производя аналогичные рассуждения, получаем, что сумма пересечений некоторых <tex>k\sum \limits_{1\le i1 < i2 < ... < ik \le n}^{} |A_{i1} \bigcap A_{i2} \bigcap ... \bigcap A_{ik}| = </tex> множеств (то есть сумма всеx перестановок при некоторых зафиксированных <texmath>\binom{n}{k}</texmath> позициях) — есть <tex>\cdot(n-k)!</tex>, т. Количество к. количество способов выбрать <tex>k</tex> позиций — <math>\binom{n}{k}</math> <math>\Rightarrow</math> Количество перестановок с <tex>ki1, i2, ... , ik </tex> неподвижными точками: равно <math>\binom{n}{k}</math><tex>\cdot</tex><tex>(n. Подставляя соответствующие значения мощностей множеств в формулу фключения-k)!</tex> исключения, получаем: