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

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

В комбинаторике беспорядком называется перестановка без неподвижных точек.

Количество беспорядков[править | править исходный текст]

Количество всех беспорядков порядка n может быть вычислено с помощью принципа включения-исключения и дается выражением:

!n = n!-\frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+\dots +(-1)^n\frac{n!}{n!} = \sum_{k=0}^n(-1)^k\frac{n!}{k!}

которое называется субфакториалом числа n.

Количество беспорядков !n = d(n) удовлетворяет рекурсивным соотношениям

d(n) = (n-1)[d(n-1) + d(n-2)]

и

d(n) = n d(n-1) + (-1)^n

где d(1) = 0 и d(2) = 1

В виду того, что \sum_{k=0}^\infty(-1)^k\frac{1}{k!} = \frac{1}{e}, значение !n с ростом n ведет себя как \frac{n!}{e}. Более того, при n>0 его можно представить как результат округления числа \frac{n!}{e}.

Задача о письмах[править | править исходный текст]

Вычисление количества беспорядков является популярной задачей в олимпиадной математике, которая встречается в разных формулировках таких как задача о беспорядке, задача о письмах, задача о встречах и т. д.

Если n писем случайным образом положить в n различных конвертов, то какова вероятность, что какое-то письмо попадет в свой конверт?

Ответ дается выражением

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

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

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]

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