Изменения

== Количество беспорядков Беспорядки ==Попробуем решить следующую задачу: количество перестановок '''Беспорядком''' в комбинаторике называется перестановка чисел от <tex>1 </tex> до <tex>n</tex>, при которых в которой ни один элемент не стоит на своём месте. Каждая такая перестановка в комбинаторике называется '''беспорядком'''. {{ТеоремаКоличество всех беспорядков порядка <tex>n</tex> может быть вычислено с помощью принципа включения-исключения и дается выражением|id=идентификатор (необязательно), пример:th1.

|statement=Количество всех беспорядков порядка <tex>n</tex> или [http://ru.wikipedia.org/wiki/Субфакториал субфакториалом] числа <tex>n</tex> (обозначение: !<tex>n</tex>) может быть вычислено по формуле: [[Файл:Formula.png]]

'''Доказательство:'''

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

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

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

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

[[ФайлТаким образом величина в левой части формулы 2) — есть количество перестановок, где на 1-ой позици '''НЕ''' 1, на 2-ой позици '''НЕ''' 2 и т.д. То есть количество искомых беспорядков. Осталось определить величины в правой части:Formula5.png]] = <tex>n!</tex>

|[[Файл:Formula4Formula5.png]]| можно получить зафиксировав число i на соответствующей ей позиции i, а остальные позиции заполнив как угодно остальными числами => |[[Файл:Formula4.png]]| = <tex>(n - 1)!=</tex>. Суммирование ведется по всем i => [[Файл:Formula8.png]]Аналогичными рассуждениями получаем, что сумма пересечений некоторых k множеств - есть все перестановки при зафиксированных k позициях, т.е. [[Файл:Formula7.png]] х <tex>(n - k)!</tex>. Таким образом приходим к формуле:

|[[Файл:Formula9Formula4.png]] = | — количество перестановок с уже занятой позицией <tex>n!i</tex> + <math>\Rightarrow</math> |[[Файл:Formula10Formula4.png]] х | <tex>=</tex> <tex>(n - 1)!</tex>. Суммирование ведется по всем <tex>i</tex> <math>\Rightarrow</math> <tex>\sum \limits_{i = 1}^{n} |\lnot </tex>[[Файл:Formula7Formula4.png]] х <tex>|</tex> <tex>=</tex> <math>\binom{n}{1}</math><tex>\cdot</tex><tex>(n - k1)!</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>  [[Файл:Formula7Formula9.png]] <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>.