В комбинаторике беспорядком называется перестановка без неподвижных точек.
Количество всех беспорядков порядка n может быть вычислено с помощью принципа включения-исключения и дается выражением:
которое называется субфакториалом числа n.
Количество беспорядков удовлетворяет рекурсивным соотношениям
и
где и
В виду того, что , значение с ростом ведет себя как . Более того, при его можно представить как результат округления числа .
Вычисление количества беспорядков является популярной задачей в олимпиадной математике, которая встречается в разных формулировках таких как задача о беспорядке, задача о письмах, задача о встречах и т. д.
Ответ дается выражением
Таким образом, ответ слабо зависит от количества конвертов и примерно равен константе .
Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её. |
Задача о беспорядках.