Изменения
Нет описания правки
{{Определение
|id=идентификатор (необязательно), пример: def1.
|definition='''БеспорядкомБеспорядк(Disturbance)''' называется — это перестановка чисел от <tex>1</tex> до <tex>n</tex>, в которой ни один элемент не стоит на своём месте. }}{{Определение|id=идентификатор (необязательно), пример: def1. |definition=[http://ru.wikipedia.org/wiki/Субфакториал Субфакториал] числа <tex>n</tex> (обозначение: !<tex>n</tex>) определяется как количество беспорядков порядка <tex>n</tex>, то есть перестановок порядка <tex>n</tex> без неподвижных точек.
}}
{{Теорема
|id=идентификатор (необязательно), пример: th1.
|statement=Количество беспорядков порядка <tex>!n = n! - \frac{n</tex> или [http://ru!}{1!} + \frac{n!}{2!} - \frac{n!}{3} + ..wikipedia.org/wiki/Субфакториал субфакториалом] числа <tex>+ (-1)^{n}\frac{n!}{n!} = \sum_{k=0}^n</tex> (обозначение: -1)^{k}\frac{n!<tex>n}{k!} </tex>) вычисляется по формуле: [[Файл:Formula.png]]
|proof=
Воспользуемся принципом включения-исключения: обозначим за <tex>A_i</tex> — количество перестановок из <tex>n</tex> элементов, в каждой из которых <tex>i</tex>-ый элемент стоит на своём месте. Тогда по формуле включения-исключения имеем:
1) [[Файл:Formula2<tex>\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>- .png]].. +(-1)^{n-1}| A_1 \bigcap A_2 \bigcap ... \bigcap A_n | </tex>
Данные формулы эквивалентны. Действительно, если некоторое множество <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|</mathtex> , где <tex>|U</tex>— универсальное множество.
Таким образом <tex>| \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>i</tex> <math>\Rightarrow</math> <tex>\sum \limits_{i = 1}^{n} |A_i| = </tex> <math>\binom{n}{1}</math><tex> (n-1)!</tex>
<tex> |A_{i1i_1} \bigcap A_{i2i_2} \bigcap ... \bigcap A_{iki_k}| = (n - k)! </tex>, где <tex> 1\le i1 i_1 < i2 i_2 < ... < ik i_k \le n </tex>. Так как позиции <tex>i1i_1, i2i_2, ... , ik i_k </tex> заняты соответствующими числами.
<tex>\sum \limits_{1\le i1 i_1 < i2 i_2 < ... < ik i_k \le n}^{} |A_{i1i_1} \bigcap A_{i2i_2} \bigcap ... \bigcap A_{iki_k}| = </tex> <math>\binom{n}{k}</math><tex>\cdot(n-k)!</tex>, т.к. количество способов выбрать <tex>k</tex> позиций <tex>i1, i2, ... , ik </tex> равно <math>\binom{n}{k}</math>.
Подставляя соответствующие значения мощностей множеств в формулу фключениявключения-исключения, получаем:
<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>
Раскрывая <math>\binom{n}{k}</math> по общеизвестной формуле, получим требуемое выражение, то есть количество беспорядков порядка <tex>n</tex>.
}}
== Литература ==
