Перестановкой называется упорядоченная запись всех элементов конечного множества без повторений, когда фиксировано взаимное расположение элементов. Различные перестановки совпадают по составу и отличаются позициями своих элементов. Например, из множества трех латинских букв {X, Y, Z} можно получить следующие 6 различных перестановок:

В общем случае для множества из n элементов можно построить n! различных перестановок. При этом значение 0! принимается равным 1, а для любых целых положительных чисел n>0 величину n! можно вычислить по следующему рекуррентному соотношению:

В следующем примере показано использование этого рекуррентного определения факториала для рекурсивного вычисления значения 4!:

Менее известно следующее рекуррентное соотношение для факториалов, по которому можно рекурсивно вычислять их величины при любых значениях n>2:

Следующий пример показывает вычисление величины 4! по этой рекуррентной формуле, где учитываются очевидные значения 2!=2 и 1!=1:

Чтобы определить значение n! по рассмотренным рекуррентным соотношениям, необходимо последовательно вычислить факториалы всех целых чисел от 1 до (n−1). Для непосредственной оценки значения n! без таких промежуточных умножений можно воспользоваться следующей приближенной формулой Стирлинга:

Относительная ошибка вычисления значения n! по формуле Стирлинга равна приблизительно (1/12n). Например, точное значение 8! равно 40320, а вычисления по формуле Стирлинга дает приближенный результат 39902 с ошибкой около 1% (1/96):

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

Вычислительный эксперимент позволяет отметить быстрый рост значения n! с увеличением n. В частности, 10! превышает 3.5 миллиона (3628800), а 1000! представляет собой целое число с более чем 2500 десятичными знаками. Еще один интересный факт заключается в том, что число десятичных цифр в записи n! превышает n, начиная с n=25. В общем случае можно показать, что факториальная функция растет даже быстрее экспоненты. Справедливость такого вывода следует из следующего анализа выражения для квадрата факториальной функции:

(n!)² = n∏k=1k(n - k + 1) ≥ n∏k=1n = nⁿ

Сопоставление левой и правой частей в этом неравенстве дает следующее соотношение между факториальной функцией и экспонентой:

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