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

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

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

Примеры[править | править вики-текст]

Проверка работ[править | править вики-текст]

Допустим, профессор дал четырем студентам (назовем их A, B, C и D) контрольную, а затем предложил им проверить её друг у друга. Естественно, ни один студент не должен проверять свою контрольную. Сколько у профессора вариантов распределения контрольных, в которых ни одному студенту не достанется своя работа? Из всех 24-х перестановок (4!) для возврата работ, нам подходят только 9 беспорядков:

   BADC, BCDA, BDAC,
   CADB, CDAB, CDBA,
   DABC, DCAB, DCBA.

В любой другой перестановке этих 4-х элементов, как минимум один студент получает свою контрольную на проверку.

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

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

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

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

Таким образом, ответ слабо зависит от количества писем и конвертов и примерно равен константе .

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

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

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

Количество беспорядков удовлетворяет рекурсивным соотношениям

и

где и

В виду того, что , значение с ростом ведет себя как . Более того, при его можно представить как результат округления числа .

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

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