Калькулятор субфакториала

Что такое субфакториал и беспорядок

Перестановка писем по чужим конвертам без совпадений

Субфакториал числа n показывает, сколько существует перестановок n различных элементов, при которых ни один элемент не остаётся на исходном месте. Такие перестановки называют беспорядками. Результат обозначают как !n или Dₙ.

Классическая модель задачи связана с письмами и подписанными конвертами. Есть n разных писем и n конвертов, каждому письму предназначен свой конверт. Нужно посчитать способы разложить все письма так, чтобы каждое оказалось в чужом конверте. Обычный факториал n! учитывает все перестановки, включая варианты с одним или несколькими правильными совпадениями. Субфакториал оставляет только варианты без единого совпадения.

Здесь важно различать положение и значение элемента. Если четыре карточки просто перевернуть лицевой стороной вниз, перестановки ещё нет. Нужны четыре различимые карточки и четыре различимые позиции. Условие проверяется для каждой пары: карточка 1 не должна попасть на место 1, карточка 2 на место 2 и так далее.

Формула субфакториала

Калькулятор начинает с двух базовых значений: D₀ = 1 и D₁ = 0. Затем каждое следующее значение получает из двух предыдущих по точной рекуррентной формуле:

D_0=1,\quad D_1=0,\quad D_n=(n-1)(D_{n-1}+D_{n-2})

Множитель n - 1 отражает выбор неправильного места для одного выделенного элемента. После такого выбора оставшаяся задача распадается на два допустимых случая, которым соответствуют Dₙ₋₁ и Dₙ₋₂. Рекуррентный расчёт удобен для больших n: он использует только целые числа и не накапливает ошибку округления.

Ту же величину можно получить точной конечной суммой, основанной на принципе включений и исключений:

D_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}

Сначала учитываются все n! перестановок, затем вычитаются варианты с закреплёнными элементами, возвращаются дважды вычтенные пересечения и так далее. Знаки поэтому чередуются. Формула заканчивается при k = n, то есть это не бесконечное приближение.

Почему !0 равно 1, а !1 равно 0

Пустой набор имеет ровно одну перестановку: пустую. В ней нет элемента, который мог бы нарушить условие, поэтому D₀ = 1. Такое определение сохраняет рекуррентную формулу и комбинаторные тождества без отдельных исключений на каждом шаге.

Для одного элемента ситуация противоположная. Единственная возможная перестановка оставляет его на своём месте, а значит не является беспорядком. Поэтому D₁ = 0. Уже для двух элементов появляется один допустимый вариант: они меняются местами, так что D₂ = 1.

Примеры перестановок без совпадений

Пустой план, n = 0. Если распределять нечего, существует один пустой вариант, поэтому !0 = 1. Практический вывод: нулевая задача имеет корректный результат и не должна считаться ошибкой ввода.

Один именной бейдж, n = 1. Единственный бейдж можно положить только перед его владельцем. Условие отсутствия совпадений невыполнимо, поэтому !1 = 0. Для случайного перераспределения нужен хотя бы второй участник.

Три ключа и три шкафчика, n = 3. Есть ровно !3 = 2 способа положить каждый ключ не в свой шкафчик. Это две циклические перестановки: по кругу в одном или другом направлении.

Четыре участника Тайного Санты, n = 4. Если никто не может получить собственное имя, допустимы !4 = 9 назначений. Организатору всё равно нужно дополнительно исключить пары или другие правила, если они предусмотрены игрой.

Шесть жетонов для мест, n = 6. При условии, что ни один человек не вытянет номер своего места, существует !6 = 265 вариантов. Число уже достаточно велико, поэтому полный перебор вручную становится неудобным.

Десять задач для десяти исполнителей, n = 10. Если каждому нужно выдать не свою исходную задачу, получится !10 = 1 334 961 распределение. Это контрольное значение совпадает с результатом калькулятора для стартового ввода 10.

Вероятность полного беспорядка

Всего для n элементов существует n! перестановок, а благоприятных для условия без совпадений существует !n. Поэтому точная вероятность равна отношению !n / n!. С ростом n это отношение приближается к 1/e, то есть примерно к 0,367879 или 36,79%. Это предел, а не точное равенство для каждого конечного n.

Например, для четырёх участников точная вероятность составляет 9 / 24 = 0,375, или 37,5%. Для десяти элементов отношение равно 1 334 961 / 3 628 800 и уже очень близко к 1/e, но всё ещё задаётся точной дробью. Если нужен знаменатель для другого n, его можно найти в калькуляторе обычного факториала.

Приближение полезно для быстрой оценки: примерно в 37 случаях из 100 случайная перестановка большого набора не оставит ни одного элемента на месте. Для точного количества вариантов калькулятор всегда применяет целочисленную рекуррентную формулу, а не умножает факториал на округлённое десятичное значение.

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

Введите целое число элементов n от 0 до 3000.
Настройте значение вручную, ползунком или кнопками с шагом 1.
Прочитайте точный результат под формой. Пробелы группируют цифры и не меняют число.
Нажмите на результат, чтобы скопировать исходную строку без округления.

Для n = 3000 ответ содержит 9131 цифру. Обычный числовой тип не способен хранить такое значение точно, поэтому расчёт выполняется в формате больших целых чисел. Ограничение 3000 сохраняет форму отзывчивой и позволяет показать результат целиком. Если задача использует произведение чисел одной чётности, выберите двойной факториал; это другая функция и другое обозначение.

Где применяется субфакториал

Субфакториалы встречаются в комбинаторике, теории вероятностей и анализе алгоритмов. Модель подходит для случайного назначения, когда запрещено собственное исходное место: распределения карточек, меток, обязанностей, жетонов или адресатов. Она также помогает оценивать случайные перестановки и проверять программы, которые должны исключать неподвижные точки.

У модели есть строгое ограничение: запрещены только совпадения элемента с его собственной позицией. Она не учитывает дополнительные условия, например запрет взаимных пар в Тайном Санте, разделение участников по командам или ограниченную совместимость задач и исполнителей. При таких правилах простого субфакториала недостаточно, нужен отдельный подсчёт допустимых перестановок.

Вопросы о субфакториале

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

Чем субфакториал отличается от факториала?

Факториал n! считает все перестановки n элементов. Субфакториал !n считает только те перестановки, в которых ни один элемент не остаётся на исходном месте.

Что означают записи !n и Dₙ?

Это два обозначения одной величины: числа беспорядков для n различных элементов. Восклицательный знак перед n нельзя путать с факториалом n!, где он стоит после числа.

Почему субфакториал нуля равен 1?

Пустой набор имеет одну пустую перестановку. В ней нет неподвижных элементов, поэтому условие выполняется, а значение !0 принимают равным 1.

Почему субфакториал единицы равен 0?

Единственный элемент можно поставить только на его собственное место. Ни одной перестановки без совпадения не существует, поэтому !1 = 0.

Всегда ли !n равно n! / e?

Нет. Отношение !n / n! лишь приближается к 1/e с ростом n. Калькулятор находит точное целое значение по рекуррентной формуле и не использует это приближение.

Можно ли вводить отрицательные или дробные числа?

Нет. Количество различимых элементов должно быть целым числом от 0 до 3000. Калькулятор покажет ошибку для пустого поля, дроби и значения вне диапазона.

Почему в длинном результате стоят пробелы?

Пробелы разделяют цифры на группы и облегчают чтение большого числа. При копировании сохраняется исходная точная запись результата без визуальной группировки.

Учитывает ли расчёт дополнительные запреты Тайного Санты?

Нет. Субфакториал запрещает только назначение участника самому себе. Запрет взаимных пар, семейных пар или повторов прошлого года требует отдельной модели.

Есть что добавить?

Напишите своё мнение, комментарий или предложение.