Факториал

Материал из Википедии — свободной энциклопедии

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

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

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

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

Иногда словом «факториал» неформально называют восклицательный знак.

[править] Свойства

[править] Комбинаторное определение

В комбинаторике факториал определяется как количество перестановок множества из n элементов. Например, элементы множества {A,B,C,D} можно линейно упорядочить 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

[править] Связь с гамма-функцией

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

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 < 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}$ ,

где произведение берется по всем простым числам.

[править] Обобщения

[править] Двойной факториал

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

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

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

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

[править] Праймориал или примориал

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

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

Первые 15 праймориалов: 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, 6469693230, 200560490130, 7420738134810, 304250263527210, 13082761331670030, 614889782588491410 (последовательность A002110 в OEIS).

[править] Суперфакториал

Суперфакториал числа n определяется как произведение факториалов всех целых чисел от 1 до n включительно.

[править] Субфакториал

Основная статья субфакториал.

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