Калькулятор беспорядков (субфакториал)

Добро пожаловать в Калькулятор беспорядков (субфакториал) — комплексный инструмент комбинаторики, который вычисляет количество беспорядков для любого набора из n элементов. Беспорядок — это перестановка, при которой ни один элемент не оказывается на своем исходном месте, обозначаемая !n или D(n). Независимо от того, изучаете ли вы комбинаторику, решаете классическую задачу о шляпах или исследуете теорию вероятностей, этот калькулятор предоставляет подробные пошаговые решения с интерактивной визуализацией.

Что такое беспорядок?

Беспорядок (также называемый субфакториалом) — это перестановка элементов множества, при которой ни один элемент не оказывается на своем первоначальном месте. Количество беспорядков n элементов записывается как !n (с восклицательным знаком перед n) или D(n).

Например, рассмотрим три предмета на позициях {1, 2, 3}. Всего существует 3! = 6 перестановок, но только 2 из них являются беспорядками:

• (2, 3, 1) — предмет 1 переходит на позицию 2, предмет 2 — на позицию 3, предмет 3 — на позицию 1
• (3, 1, 2) — предмет 1 переходит на позицию 3, предмет 2 — на позицию 1, предмет 3 — на позицию 2

Таким образом, !3 = 2.

Формулы беспорядков

Формула включений-исключений

Самая фундаментальная формула выводится на основе принципа включений-исключений:

Рекуррентная формула

Беспорядки также могут быть вычислены рекурсивно:

с базовыми случаями: !0 = 1, !1 = 0.

Формула ближайшего целого числа

Для \(n \geq 1\), субфакториал равен ближайшему целому числу к \(n!/e\):

Задача о проверке шляп

Самое известное применение беспорядков — задача о шляпах (problème des rencontres): если n гостей сдают свои шляпы в гардероб и шляпы возвращаются случайным образом, какова вероятность того, что ни один гость не получит свою шляпу?

Ответ: \(!n / n!\), который удивительно быстро сходится к \(1/e \approx 0.3679\). Это означает, что примерно 36.8% всех случайных перестановок являются беспорядками, независимо от количества предметов.

Как пользоваться этим калькулятором

1. Введите n: Введите количество элементов (от 0 до 170). Используйте кнопки быстрых примеров для проверки часто встречающихся значений.
2. Рассчитать: Нажмите «Рассчитать !n», чтобы вычислить число беспорядков.
3. Просмотрите результаты: Увидите !n, n!, вероятность беспорядка и отношение к 1/e.
4. Изучите анимацию: Для малых n воспользуйтесь визуальной анимацией, чтобы увидеть, как работают беспорядки.
5. Изучите шаги: Ознакомьтесь с подробным разбором по методу включений-исключений и таблицей беспорядков.

Первые 15 чисел беспорядков

Применение беспорядков

Тайный Санта / Обмен подарками

При организации обмена подарками «Тайный Санта» каждый участник вытягивает имя. Успешный розыгрыш, при котором никто не выбирает собственное имя, является беспорядком. Для группы из 10 человек существует 1 334 961 правильный вариант из 3 628 800 возможных.

Криптография и теория кодирования

Беспорядки появляются при анализе шифров подстановки и кодов с исправлением ошибок. Концепция «отсутствия неподвижной точки» фундаментальна для понимания криптостойкости и шифрования на основе перестановок.

Тасование карт и игры

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

Теория вероятностей

Беспорядки представляют собой элегантный пример принципа включений-исключений и иллюстрируют, как вероятности могут сходиться к простым пределам (в данном случае к 1/e).

Ключевые свойства

• Отношение \(!n/n!\) сходится к \(1/e \approx 0.367879\) при \(n \to \infty\)
• Сходимость происходит чрезвычайно быстро — точность до 6 знаков после запятой достигается уже при n = 10
• \(!n\) удовлетворяет рекуррентному соотношению: \(!n = n \cdot !(n-1) + (-1)^n\)
• Экспоненциальная производящая функция равна \(e^{-x}/(1-x)\)
• \(!0 = 1\) (пустая перестановка тривиально считается беспорядком)

Часто задаваемые вопросы

Что такое беспорядок?

Беспорядок — это перестановка множества, при которой ни один элемент не появляется в своей исходной позиции. Например, если элементы помечены {1, 2, 3}, перестановка (2, 3, 1) является беспорядком. Количество беспорядков n элементов обозначается !n (субфакториал n).

Какова формула для субфакториала !n?

Субфакториал !n можно рассчитать по формуле включений-исключений: \(!n = n! \times \sum_{k=0}^{n} (-1)^k / k!\). Его также можно вычислить рекурсивно: \(!n = (n-1)(!(n-1) + !(n-2))\), где !0 = 1 и !1 = 0. Другая полезная формула: \(!n = \text{round}(n! / e)\) для \(n \geq 1\).

Какова вероятность того, что случайная перестановка является беспорядком?

Вероятность того, что случайная перестановка n предметов является беспорядком, приближается к \(1/e \approx 0.3679\) по мере роста n. Даже для малых n это приближение удивительно точно. Для n = 5 точная вероятность составляет 44/120 ≈ 0.3667, что уже очень близко к 1/e.

Что такое задача о шляпах?

Задача о шляпах (также известная как problème des rencontres) — классическая вероятностная задача: если n человек сдают свои шляпы в ресторане, а шляпы возвращаются случайным образом, какова вероятность того, что никто не получит свою шляпу обратно? Ответ — это количество беспорядков !n, деленное на общее количество перестановок n!, что приближается к \(1/e \approx 36.79\%\).

Какова связь между беспорядками и факториалом?

Беспорядки (!n) и факториалы (n!) тесно связаны: \(!n = n! \times \sum(-1)^k/k!\) для k от 0 до n. Отношение !n/n! дает вероятность беспорядка, сходящуюся к 1/e. Кроме того, !n — это ближайшее целое число к n!/e для \(n \geq 1\), что делает n!/e очень полезным приближением.

Дополнительные ресурсы

• Принцип включений-исключений — Википедия
• OEIS A000166 — Последовательность субфакториалов