Факториал

Факториа́л числа n (обозначается n!, произносится эн факториа́л) — произведение всех натуральных чисел до n включительно:

$n! = 1\cdot 2\cdot\ldots\cdot n =\prod_{i=1}^n i$.

По определению полагают 0! = 1. Факториал определён только для целых неотрицательных чисел.

Последовательность факториалов неотрицательных целых чисел начинается так:

1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, … (последовательность A000142 в OEIS)

Факториалы часто используются в комбинаторике, теории чисел и функциональном анализе.

Свойства

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

$n!= \begin{cases} 1 & n = 0,\\ n \cdot (n-1)! & n > 0. \end{cases}$

Комбинаторная интерпретация

В комбинаторике факториал натурального числа n интерпретируется как количество перестановок (упорядочиваний) множества из n элементов. Например, для множества {A,B,C,D} из 4-х элементов существует 4!=24 перестановки:

ABCD  BACD  CABD  DABC
ABDC  BADC  CADB  DACB
ACBD  BCAD  CBAD  DBAC
ACDB  BCDA  CBDA  DBCA
ADBC  BDAC  CDAB  DCAB
ADCB  BDCA  CDBA  DCBA

Комбинаторная интерпретация факториала служит обоснованием тождества 0!=1, т. к. пустое множество упорядочено единственным способом.

Связь с гамма-функцией

Факториал связан с гамма-функцией от целочисленного аргумента соотношением:

n! = Γ(n + 1)

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

Амплитуда и фаза факториала комплексного аргумента.

Путём аналитического продолжения её также расширяют и на всю комплексную плоскость, исключая особые точки при $n=-1, -2, -3\ldots$.

Формула Стирлинга

Формула Стирлинга — асимптотическая формула для вычисления факториала:

$n! = \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \left(1 + \frac{1}{12 n} + \frac{1}{288 n^2} - \frac{139}{51840 n^3}+O\left(n^{-4}\right)\right),$

см. O-большое. Коэффициенты этого разложения дают последовательность A001163 в OEIS (числители) и последовательность A001164 в OEIS (знаменатели).

Во многих случаях для приближённого значения факториала достаточно рассматривать только главный член формулы Стирлинга:

$n! \approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$

При этом можно утверждать, что

$\sqrt{2\pi n}\left(\frac{n}{e}\right)^n e^{1/(12n+1)}< n! < \sqrt{2\pi n}\left(\frac{n}{e}\right)^n e^{1/(12n)}$

Разложение на простые числа

Каждое простое число p входит в разложение n! на простые множители в степени

$\left\lfloor \frac{n}{p}\right\rfloor + \left\lfloor \frac{n}{p^2}\right\rfloor + \left\lfloor \frac{n}{p^3}\right\rfloor + \ldots.$

Таким образом,

$n! = \prod_{p} p^{\lfloor \frac{n}{p}\rfloor + \lfloor \frac{n}{p^2}\rfloor +\ldots},$

где произведение берётся по всем простым числам. Нетрудно видеть, что для всякого простого p большего n соответствующий множитель в произведение равен 1, а потому произведение можно брать лишь по простым p, не превосходящим n.

Другие свойства

• Для натурального числа n

  $n!^2 \geqslant n^n \geqslant n! \geqslant n$

Обобщения

Двойной факториал

Двойной факториал числа n обозначается n!! и определяется как произведение всех натуральных чисел в отрезке [1,n], имеющих ту же чётность что и n. Таким образом,

$(2k)!! = 2\cdot 4\cdot 6\cdots 2k =\prod_{i=1}^{k} 2i = 2^k\cdot k!$

$(2k+1)!! = 1\cdot 3\cdot 5\cdots (2k+1) = \prod_{i=0}^{k} (2i+1) = \frac{(2k+1)!}{2^k\cdot k!} = \frac{(2k+1)!}{(2k)!!}$

По определению полагают 0!! = 1.

Последовательность значений n!! начинается так:

1, 1, 2, 3, 8, 15, 48, 105, 384, 945, … (последовательность A006882 в OEIS)

Кратный факториал

m-кратный факториал числа n обозначается $\textstyle n\underbrace{!!\ldots !}_m$ и определяется следующим образом:

Пусть число n представимо в виде n = mk − r, где $k \in \mathbb{Z}$, $r \in \{0,1,\ldots ,m-1\}$. Тогда

$n\underbrace{!!\ldots !}_m = \prod_{i=1}^k (mi-r).$

Двойной факториал является частным случаем m-кратного факториала для m = 2.

Связь с гамма-функцией

$\prod_{i=1}^{k} (mi-r)=m^k \cdot \frac {\Gamma \left (k-\frac {r} {m} +1 \right )} {\Gamma \left ( 1- \frac {r} {m} \right)}$

Убывающий факториал

Убывающим факториалом (или неполным факториалом) называется выражение

$(n)_k = n^{\underline{k}} = n^{[k]}= n\cdot (n-1)\cdot \ldots\cdot (n-k+1) = \frac{n!}{(n-k)!}$

Убывающий факториал даёт число размещений из n по k.

Возрастающий факториал

Возрастающим факториалом называется выражение

$n^{(k)} = n^{\overline{k}} = n\cdot (n+1)\cdot \ldots\cdot (n+k-1) = \frac{(n+k-1)!}{(n-1)!}$

Праймориал или примориал

Праймориал или примориал (англ. primorial) числа n обозначается n#  и определяется как произведение простых чисел, не превышающих n. Например,

$11\# = 12\# = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 = 2310$

Последовательность праймориалов (включая ${\textstyle{1\# \equiv 1}}$) начинается так:

1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690, … (последовательность A002110 в OEIS)

Суперфакториалы

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

$\operatorname{sf}(4)=1! \times 2! \times 3! \times 4!=288 \,$

В общем

$\operatorname{sf}(n) =\prod_{k=1}^n k! =\prod_{k=1}^n k^{n-k+1} =1^n\cdot2^{n-1}\cdot3^{n-2}\cdots(n-1)^2\cdot n^1.$

Последовательность суперфакториалов чисел n⩾0 начинается так:

1, 1, 2, 12, 288, 34560, 24883200, … (последовательность A000178 в OEIS)

Идея была обобщена в 2000 году Генри Боттомли (англ.), что привело к гиперфакториалам (англ. Super-duper-factorial), которые являются произведением первых n суперфакториалов. Последовательность гиперфакториалов чисел n⩾0 начинается так:

1, 1, 2, 24, 6912, 238878720, 5944066965504000, … (последовательность A055462 в OEIS)

Продолжая рекуррентно, можно определить факториал кратного уровня, где m-уровневый факториал числа n как произведение первых n (m-1)-уровневых факториалов, то есть

$\operatorname{mf}(n,m) = \operatorname{mf}(n-1,m)\operatorname{mf}(n,m-1)=\prod_{k=1}^n k^{n-k+m-1 \choose n-k},$

где $\operatorname{mf}(n,0)=n$ для n > 0 и $\operatorname{mf}(0,m)=1$.

Субфакториал

Субфакториал $!n\!$ определяется как количество беспорядков порядка $\!n$, то есть перестановок $\!n$-элементного множества без неподвижных точек.

Ссылки

• Онлайн Калькулятор Факториалов

См. также

• Факторион