Изменения

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

|proof=}}

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

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

<tex>|</tex> <math>\mathbf{S}</math> <tex>|</tex> <tex>=</tex> <tex>|</tex> [[Файл:Formula5.png]] <tex>U</tex> <tex>|</tex> — <tex>|</tex> <math>\lnot</math><math>\mathbf{S}</math> <tex>|</tex>.

В данной задаче множество [[Файл:Formula5.png]] <tex>U</tex> — есть количество перестановок из <tex>n</tex> элементов, т.е. <tex>n!</tex>. Верхнее подчеркивание или символ , а <math>\lnot</math> перед <math>\mathbf{S}</math> означает дополняющее множество до [[Файл:Formula5.png]] <tex>U</tex> <math>\Rightarrow</math> <math>\lnot</math> [[Файл:Formula4.png]] <tex>U</tex> — количество перестановок, где <tex>i</tex>-ый элемент стоит '''НЕ''' на своём <tex>i</tex>-ом месте.

[[Файл:Formula5.png]] <tex>U</tex> <tex>=</tex> <tex>n!</tex>.

|[[Файл:Formula4.png]]| <tex>Ai</tex> — количество перестановок с уже занятой позицией <tex>i</tex> <math>\Rightarrow</math> |[[Файл:Formula4.png]]| <tex>Ai</tex> <tex>=</tex> <tex>(n - 1)!</tex>. Суммирование ведется по всем <tex>i</tex> <math>\Rightarrow</math> <tex>\sum \limits_{i = 1}^{n} |\lnot </tex>[[Файл:Formula4.png]]<tex>U</tex><tex>|</tex> <tex>=</tex> <math>\binom{n}{1}</math><tex>\cdot</tex><tex>(n-1)!</tex>

Производя аналогичные рассуждения, получаем, что сумма пересечений некоторых <tex>k</tex> множеств (то есть сумма всеx перестановки перестановок при некоторых зафиксированных <tex>k</tex> позициях) — есть <tex>(n-k)!</tex>. Количество способов выбрать <tex>k</tex> позиций — <math>\binom{n}{k}</math> <math>\Rightarrow</math> Количество перестановок с <tex>k</tex> неподвижными точками: <math>\binom{n}{k}</math><tex>\cdot</tex><tex>(n-k)!</tex>

[[Файл:Formula9.png]] <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>