Факториалы и субфакториалы. Разбираемся с ними вместе с экспертами ИТ-компании «Криптонит».
Когда человек первый раз встречает восклицательный знак в математических записях, он обычно удивляется. Это выглядит, словно цены на распродаже: 50! 80! 100!
На самом деле запись вида n! называется факториал и означает произведение всех натуральных чисел от 1 до n. Например: 5! = 5 × 4 × 3 × 2 × 1 = 120.
Идея факториала встречалась ещё в Древней Индии, а современное обозначение n! ввёл французский математик Кристиан Крамп в 1808 году.
Функция вычисления факториала есть во многих математических библиотеках. Она применяется, в частности, при анализе алгоритмов сортировки для определения верхней границы их сложности.
В общем случае факториал n! показывает количество всех возможных перестановок ИЗ n элементов. Например, из трёх элементов [A, B, C] всего может быть 6 перестановок: ABC, ACB, BAC, BCA, CAB, CBA, т.е. 3! = 6.
Дальнейшее развитие идеи привело к появлению субфакториала.
Он обозначается !n и показывает число перестановок n элементов, в которых ни один элемент не остаётся на своём месте.
Для тех же трёх элементов [A, B, C] субфакториал записывается как !3 и равен двум, поскольку возможны только две комбинации, в которых каждый элемент меняет своё положение: [B, C, A] и [С, A, B].
Факториалы и субфакториалы используются в разных разделах математики.
В комбинаторике они выражают количество перестановок, в теории чисел их изучают в контексте делимости, в теории вероятностей — для подсчёта элементарных исходов.
