Беспорядок в комбинаторике — перестановка без неподвижных точек; количество беспорядков заданного числа  — его субфакториал .

Пример задачи, где требуется вычислить число всех беспорядков — задача о письмах, считающаяся классикой олимпиадной математики: если писем случайным образом положить в различных конвертов, то какова вероятность, что какое-нибудь из писем попадёт в свой конверт? Ответ даётся выражением: , при этом при увеличении n вычитаемое стремится к пределуР. Стенли. Перечислительная комбинаторика. — М.: Мир, 1990. — С. 107–108.

Таким образом, ответ почти не зависит (при ) от количества писем и конвертов и примерно равен константе .

Теорема Количество беспорядков порядка равно субфакториалу числа и вычисляется по формулеВиленкин Н. Я., Виленкин А. Н., Виленкин П. А. Комбинаторика. — 4-е изд., испр. — М.: МЦНМО, 2013. — ISBN 978-5-89492-018-4.:

Доказательство Воспользуемся принципом включений-исключений. Обозначим через множество перестановок элементов, в которых -й элемент стоит на своём месте. Тогда:

где — множество всех перестановок порядка , а — множество перестановок, в которых -й элемент не стоит на своём месте. Величина есть искомое число беспорядков.

Поскольку (позиция зафиксирована), получаем:

Аналогично, для пересечения множеств имеем , а число способов выбрать позиций равно , откуда:

Подставляя в формулу включений-исключений и раскрывая биномиальный коэффициент, получаем:

Рекуррентные соотношения Число беспорядков удовлетворяет двум рекуррентным соотношениям:

при начальных условиях , .

Доказательство рекуррентных соотношений Второе соотношение. Так как , перепишем формулу субфакториала:

Первое соотношение. Пусть первый элемент занял место с номером ( вариантов, так как место 1 запрещено). Далее возможны два случая: Элемент занимает место 1. Остаются элемента и мест — задача сводится к беспорядкам. Элемент не занимает место 1. Это равносильно задаче для элементов (место 1 запрещено для -го элемента) — задача сводится к беспорядкам. Так как оба случая не пересекаются, суммируя и учитывая вариантов для выбора , получаем первое соотношение.

Примечания

Ссылки

Категория:Перестановки