Беспорядок (перестановка)

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Пример задачи, где требуется вычислить число всех беспорядков — задача о письмах, считающаяся классикой олимпиадной математики: если писем случайным образом положить в различных конвертов, то какова вероятность, что какое-нибудь из писем попадёт в свой конверт? Ответ даётся выражением:

, при этом при увеличении n вычитаемое стремится к

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

  • Р. Стенли. Перечислительная комбинаторика. — М.: Мир, 1990. — С. 107—108.