Беспорядок (перестановка)
Материал из Википедии — свободной энциклопедии
- У этого термина есть другое значение - см. Инверсия (перестановка).
В комбинаторике беспорядком называется перестановка без неподвижных точек.
Количество всех беспорядков порядка n может вычислено с помощью принципа включения-исключения и дается выражением:
которое называется субфакториалом числа n.
В виду того, что , значение !n с ростом n ведет себя как . Более того, при n > 0 его можно представить как результат округления числа .
Вычисление количества беспорядков является популярной задачей в олимпиадной математике, которая встречается в разных формулировках таких как задача о беспорядке, задача о письмах, задача о встречах и т. д.
[править] Задача о письмах
Если n писем случайным образом положить в n различных конвертов, то какова вероятность, что какое-то письмо попадет в свой конверт? Ответ дается выражением
Таким образом, ответ слабо зависит от количества конвертов и является почти постоянной вероятностью.
[править] См. также
[править] Ссылки
- Р. Стенли Перечислительная комбинаторика. — М.: Мир, 1990. — С. 107-108.
Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её. |