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

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

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

$1-\frac{!n}{n!}\approx 1-\frac{1}{e}$,

таким образом, ответ слабо зависит от количества писем и конвертов и примерно равен константе $1-e^{-1}\approx 0,63212$.

Другой пример — задача о проверке работ; четыре студента A, B, C и D проверяют контрольные друг друга так, чтобы не проверять свою контрольную, соответственно, возможны только !4=9 беспорядков: BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA.

Ссылки

• Шаблон:Книга