11
правок
Изменения
Нет описания правки
Таким образом, для <tex>~l=n</tex> мы доказали, что равенство верно. Значит, индукционный переход верен, то есть теорема доказана.
}}
== Количество беспорядков ==
Попробуем решить следующую задачу: количество перестановок чисел от 1 до n, при которых ни один элемент не стоит на своём месте. Каждая такая перестановка в комбинаторике называется '''беспорядком'''.
Количество всех беспорядков порядка <tex>n</tex> может быть вычислено с помощью принципа включения-исключения и дается выражением:
[[Файл:Formula.png]]
которое называется субфакториалом числа n и обозначается, как !n.
'''Доказательство'''
Обозначим за [[Файл:Formula4.png]] - количество перестановок из n элементов, в которых на i-ой позиции стоит i.
тогда по формуле включения-исключения имеем:
1) [[Файл:Formula2.png]]
ИЛИ
2) [[Файл:Formula3.png]]
Данные формулы эквивалентны! Действительно, если множества [[Файл:Formula4.png]] являются подмножествами некоторого множества [[Файл:Formula5.png]], то в силу правил де Моргана [[Файл:Formula6.png]].
В нашей задаче множество [[Файл:Formula5.png]] - есть количество перестановок из n элементов, т.е. n!. Черта над множеством [[Файл:Formula4.png]] означает дополняющее множество до [[Файл:Formula5.png]] или, в силу определения [[Файл:Formula4.png]], означает количество перестановок, где на i-ой позиции '''НЕ''' i.
Таким образом величина в левой части формулы 2) - есть количество перестановок, где на 1-ой позици '''НЕ''' 1, на 2-ой позици '''НЕ''' 2 и т.д. Т.е. количество искомых беспорядков! Осталось определить величины в правой части:
[[Файл:Formula5.png]] = <tex>n!</tex>
|[[Файл:Formula4.png]]| можно получить зафиксировав число i на соответствующей ей позиции i, а остальные позиции заполнив как угодно остальными числами => |[[Файл:Formula4.png]]| = <tex>(n - 1)!</tex>. Суммирование ведется по всем i => [[Файл:Formula8.png]]
Аналогичными рассуждениями получаем, что сумма пересечений некоторых k множеств - есть все перестановки при зафиксированных k позициях, т.е. [[Файл:Formula7.png]] х <tex>(n - k)!</tex>. Таким образом приходим к формуле:
[[Файл:Formula9.png]] = <tex>n!</tex> + [[Файл:Formula10.png]] х [[Файл:Formula7.png]] х <tex>(n - k)!</tex>
Раскрывая [[Файл:Formula7.png]] по общеизвестной формуле, получим требуемое выражение, т.е. количество беспорядков порядка <tex>n</tex>.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
