Изменения
→Беспорядки
Воспользуемся принципом включения-исключения: обозначим за <tex>A_i</tex> — количество перестановок из <tex>n</tex> элементов, в каждой из которых <tex>i</tex>-ый элемент стоит на своём месте. Тогда по формуле включения-исключения имеем:
<tex dpi = "140"> \Big |\bigcap_{i=_1}^n \lnot A_i overline{A}_i \Big| = |U|-\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}| A_1 \bigcap A_2 \bigcap ... \bigcap A_n | </tex>, где универсум <tex>U</tex> — множество из всех перестановок порядка <tex>n</tex>.
<tex>\lnot A_ioverline{A}_i</tex> — количество перестановок, в каждой из которых <tex>i</tex>-ый элемент стоит не на своём <tex>i</tex>-ом месте.
Таким образом <tex dpi = "130">| \bigcap_{i=_1}^n \lnot A_i overline {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 dpi = "130">\binom{n}{1}</tex> — количество способов выбрать одну <tex>i</tex>-ую позицию <tex dpi = "130"> \Rightarrow \sum \limits_{i = 1}^{n} |A_i| = \binom{n}{1} (n-1)!</tex>
Подставляя соответствующие значения мощностей множеств в формулу включения-исключения, получаем:
<tex dpi = "130">| \bigcap_{i=_1}^n \lnot A_i overline{A}_i | = n! + \sum \limits_{k = 1}^{n} (-1)^{k}\binom{n}{k} \cdot (n - k)!.</tex>
Раскрывая <tex dpi = "140">\binom{n}{k}</tex> по общеизвестной формуле, получим требуемое выражение, то есть количество беспорядков порядка <tex>n</tex>.
