Изменения
Нет описания правки
}}
== Беспорядки Беспорядок ==
{{Определение
|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>) может быть вычислено вычисляется по формуле: [[Файл:Formula.png]]
|proof=
Воспользуемся принципом включения-исключения: обозначим за <tex>AiA_i</tex> — количество перестановок из <tex>n</tex> элементов, в каждой из которых <tex>i</tex>-ый элемент стоит на своём месте. Тогда по формуле включения-исключения имеем:
1) [[Файл:Formula2.png]]
2) [[Файл:Formula3.png]]
Данные формулы являются эквивалентнымиэквивалентны. Действительно, если некоторое множество <math>S</math> являются подмножествами является подмножеством некоторого множества <tex>U</tex>, то, в силу законов де Моргана :
<tex>|</tex> <math>S</math> <tex>|</tex> <tex>=</tex> <tex>|</tex> <tex>U</tex> <tex>|</tex> — <tex>|</tex> <math>\lnot</math><math>S</math> <tex>|</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>| \bigcap_{i=_1}^n \lnot A_i |</tex> <tex>=</tex> <tex>n!</tex> <tex>+</tex> <tex>\sum \limits_{i = 1}^{n} (-1)^{n}(n - k)!</tex><tex>\cdot</tex><math>\binom{n}{k}</math>