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

Понимание факториалов

Факториал положительного целого числа n, записанный как n!, — это произведение всех положительных целых чисел от 1 до n. Определение: n! = n × (n−1) × (n−2) × ... × 2 × 1. Специальный случай: 0! = 1 по определению (не по расчету) — это требуется для работы комбинаторных формул.

Факториалы растут чрезвычайно быстро — быстрее, чем любая полиномиальная или даже большинство экспоненциальных функций. 5! = 120; 10! = 3,628,800; 15! = 1,307,674,368,000; 20! ≈ 2,43 × 10^18; 100! ≈ 9,33 × 10^157. Число 170! примерно 7,26 × 10^306, которое является наибольшим факториалом, представимым в виде 64-разрядного двоичного числа (двойной точности). Наш калькулятор использует арифметику BigInt для точных целочисленных результатов до 170!

Рекурсивное определение факториала: n! = n × (n−1)! для n > 0, с 0! = 1 в качестве базового случая. Эта рекурсивная структура делает факториал классическим вводным примером в информатике для обучения рекурсии, динамической программированию и кэшированию. Вычисление факториала с помощью итерации также является стандартным: инициализируйте результат = 1, а затем умножьте на каждое целое число от 2 до n.

Нотация «n!» была введена Кристианом Крампом в 1808 году как удобная сокращенная запись часто встречающегося произведения 1 × 2 × 3 × ... × n. До этого использовались различные другие записи. Сегодня n! широко признан во всех математических традициях.

Факториалы в комбинаторике и вероятности

Факториал является основой комбинаторики — раздела математики, занимающегося счетом, расположением и выбором. virtually каждая задача счета в вероятности и статистике в конечном итоге включает факториалы.

Пермутации (упорядоченные расположения): Количество способов расположить n различных объектов в ряд — это n! — так называемые n-факториальные перестановки. С 4 книгами на полке: 4! = 24 расположения. С 10 бегунами в гонке, количество возможных расположений для 1-го, 2-го и 3-го места — P(10,3) = 10!/(10−3)! = 10!/7! = 720.

Формула частичной перестановки: P(n,r) = n!/(n−r)! подсчитывает упорядоченные выборки r предметов из n. Формула полных перестановок n! является специальным случаем r = n.

Комбинации (неупорядоченные выборки): C(n,r) = n!/(r!(n−r)!), также записывается как ⁿCᵣ или «n выберите r» или как биномиальный коэффициент. Это подсчитывает количество способов выбрать r предметов из n, где порядок не имеет значения. Из 52 карт, количество 5-карточных рук = C(52,5) = 52!/(5!×47!) = 2,598,960. Вероятность получить королевский флеш = 4/2,598,960 ≈ 0,000154%.

Мультиномиальные коэффициенты: n!/(n₁! × n₂! × ... × nₖ!) подсчитывает расположения n предметов, где n₁ — типа 1, n₂ — типа 2 и т. д. Расположение букв в MISSISSIPPI: 11!/(1!×4!×4!×2!) = 34,650 различных расположений.

Таблица факториалов: n! для n = 0 до 20

Вот полная таблица факториалов для малых значений n. Памятование первых 10 факториалов полезно для быстрого расчета комбинаторных задач.

Эксплозивное рост — впечатляющий: от 10! = 3,6 миллиона до 20! = 2,4 квинтиллиона за 10 шагов. Этот быстрый рост объясняет, почему факториал появляется в знаменателях рядов Тейлора (обеспечивая сходимость) и в нормализующих факторах распределений вероятности.

Аппроксимация Стирлинга и большие факториалы

Для больших n вычисление точных факториалов нецелесообразно — 100! имеет 158 цифр. Аппроксимация Стирлинга обеспечивает превосходное приближение: n! ≈ √(2πn) × (n/e)^n, где e ≈ 2.71828 — число Эйлера.

Точность аппроксимации Стирлинга: для n=10, точное значение = 3,628,800; Стирлинг дает ≈ 3,598,696, относительная ошибка меньше 1%. Для n=100 относительная ошибка меньше 0,1%. Чем больше n, тем точнее приближение становится — относительная ошибка приближения O(1/n).

Логарифм-факториал ln(n!) = Σ ln(k) для k=1 до n (сумма логарифмов) имеет важное значение в вычислениях. В статистике и машинном обучении используются логарифм-вероятности вместо raw вероятностей, чтобы избежать числового подпрыжка (множение многих малых чисел вместе быстро приводит к 0 в арифметике с плавающей запятой). Лог-функция Гамма расширяет это до нецелых аргументов.

Функция Гамма Γ(n) — это продолжение факториала на все комплексные числа, кроме неотрицательных целых чисел: Γ(n) = (n−1)! для положительных целых чисел. Это появляется в распределениях вероятностей (распределение Гамма, распределение Хи-квадрат, распределение Бета) и многих физических формул. Некоторые калькуляторы могут вычислить Γ(1,5) = √π/2 ≈ 0,886 — «факториал» 0,5.

Факториалы в распределениях вероятностей

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

Биномиальное распределение: P(X = k) = C(n,k) × p^k × (1−p)^(n−k). Моделирует количество успехов в n независимых испытаниях с вероятностью p каждый. C(n,k) = n!/(k!(n−k)!) — комбинаторный коэффициент. Сумма по всем k этих членов равна 1 (общая вероятность).

Распределение Пуассона: P(X = k) = (λ^k × e^(−λ)) / k!. Моделирует количество редких событий, происходящих в фиксированном интервале, когда средняя скорость равна λ. k! в знаменателе нормирует распределение. Используется для: приездов в больницу в час, страховых случаев в день, мутаций в репликации генома.

Нормальное распределение и аппроксимация Стирлинга глубоко связаны. Центральное теорема о приближении — что суммы независимых случайных величин приближаются к нормальному распределению — можно доказать с помощью аппроксимации Стирлинга n!. Эта связь между дискретным (факториал) и непрерывным (нормальное распределение) мирами — один из глубочайших результатов в теории вероятностей.

Задача о дне рождения: Вероятность того, что все 23 человека в комнате имеют разные дни рождения = 365!/(365−23)! ÷ 365^23 ≈ 49,3%. Следовательно, существует более 50% вероятность того, что хотя бы два человека делятся днем рождения — знаменитый противоречивый результат, использующий частичные перестановки.

Факториал в теории чисел: конечные нули и теорема Вилсона

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

Конечные нули в n!: Количество конечных нулей в n! равно количеству множителей 10, что равно количеству множителей 5 (поскольку множители 2 всегда более обильны). Формула: count = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ... (сумма, пока степень 5 ≤ n). Для 100!: ⌊100/5⌋ + ⌊100/25⌋ = 20 + 4 = 24 конечных нули.

Формула Лежандра: Наивысшая степень простого числа p, делящая n!, равна ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ... Это говорит вам о точной простой факторизации n!, которая необходима в теории чисел и комбинаторике.

Теорема Вилсона: Целое число p > 1 является простым, если и только если (p−1)! ≡ −1 (mod p). Для p=5: 4! = 24 ≡ 4 ≡ −1 (mod 5) ✓. Для p=6 (составное): 5! = 120 ≡ 0 (mod 6) ✗. Хотя теорема Вилсона красиво теоретически, она не практична для больших чисел, поскольку вычисление (p−1)! экспоненциально дорогостояще.

Факториальные простые числа: Факториальное простое число — это простое число вида n! + 1 или n! − 1. Примеры: 2! − 1 = 1 (не простое), 3! − 1 = 5 (простое), 3! + 1 = 7 (простое), 4! − 1 = 23 (простое). Поиск больших факториальных простых чисел является активной областью исследований в рекреационной и компьютерной теории чисел.

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

Введите неотрицательное целое число n (от 0 до 170) и нажмите «Рассчитать». Калькулятор возвращает точное значение факториала в виде целого числа с помощью JavaScript BigInt для больших значений, избегая ошибок, вызванных нецелочисленными точками, которые будут коррумпировать результаты для n ≥ 19.

Примечания:

• Вход должен быть неотрицательным целым числом. Калькулятор отбрасывает десятичные числа до ближайшего целого числа.
• Максимальное значение n = 170 для точного вычисления (170! ≈ 7,26 × 10^306, что находится в пределах диапазона двойной точности для отображения).
• Для n = 0, результат равен 1 (по определению).
• Для очень больших факториалов (n > 100), результат — число с 150+ цифр — отображается в полном объеме нашим реализацией BigInt.
• Для приложений, требующих ln(n!), используйте тождество: ln(n!) = Σ ln(k) для k=1 до n.

Факториалы в Информатике: Алгоритмы и Сложность

Факториал тесно связан с теорией сложности вычислений — изучением того, как сложны задачи для решения алгоритмически. Понимание факториала помогает объяснить, почему определенные проблемы являются "трудными" в точном математическом смысле.

Задача Туристического продавца (TSP) спрашивает: дано n городов и расстояния между каждой парой, найдите наименьший путь, посещая все города ровно один раз. Напрямую brute-force подход проверяет все возможные порядки: (n−1)!/2 маршрутов (деление на 2 для симметрии, фиксируя стартовый город). Для n=20 городов: 19!/2 ≈ 6 × 10^16 маршрутов. даже при 1 триллионе маршрутов/секунду, это займет 60 000+ лет. Этот факториальный взрыв является причиной того, что TSP является "NP-трудной" и почему в практике используются градиентные алгоритмы (а не точные решения) для больших экземпляров.

Задача сортировки имеет факториальные связи также: n! — это количество возможных порядков n элементов. Оптимальный алгоритм сравнения по сортировке должен различать все n! случаи, требуя хотя бы log₂(n!) сравнений. По приближению Стирлинга, log₂(n!) ≈ n×log₂(n), поэтому теоретический минимум сравнений для сортировки — O(n log n) — достигается алгоритмом merge sort и heap sort.

В динамической программировании, факториальные подзадачи можно кэшировать: когда вы вычисляете k!, вы можете получить (k+1)! = (k+1) × k! без повторного вычисления с нуля. Это уменьшает стоимость вычисления всех факториалов от 1 до n с O(n²) до O(n), ключевая оптимизация в приложениях, требующих многих факториальных значений, таких как генерация таблиц вероятностей.