- Беспорядок (перестановка)
-
Не следует путать с Инверсия (перестановка).
В комбинаторике беспорядком называется перестановка без неподвижных точек.
Содержание
Количество беспорядков
Количество всех беспорядков порядка n может быть вычислено с помощью принципа включения-исключения и дается выражением:
которое называется субфакториалом числа n.
В виду того, что
, значение
с ростом
ведет себя как
. Более того, при
его можно представить как результат округления числа
.
Задача о письмах
Вычисление количества беспорядков является популярной задачей в олимпиадной математике, которая встречается в разных формулировках таких как задача о беспорядке, задача о письмах, задача о встречах и т. д.
- Если
писем случайным образом положить в
различных конвертов, то какова вероятность, что какое-то письмо попадет в свой конверт?
Ответ дается выражением
Таким образом, ответ слабо зависит от количества конвертов и примерно равен константе
.
См. также
Ссылки
- Р. Стенли Перечислительная комбинаторика. — М.: Мир, 1990. — С. 107-108.
Категория:- Комбинаторика
Wikimedia Foundation. 2010.