Изменения
Нет описания правки
Где <tex>U</tex> — универсальное множество. <tex>|U| = n!</tex>, т.е. количество перестановок из <tex>n</tex> элементов. <math>\lnot</math><math>S</math> означает дополняющее множество до <tex>U</tex>. Откуда следует, что <math>\lnot</math><tex>A_i</tex> — количество перестановок, в каждой из которых <tex>i</tex>-ый элемент стоит не на своём <tex>i</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>| \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>.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
/tex>
