Факториал

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

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

$n! = 1\cdot 2\cdots 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! = \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 из Энциклопедии целочисленных последовательностей
Последовательность A001164 из Энциклопедии целочисленных последовательностей

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

$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=1}^{k} 2i+1 = \frac{(2k+1)!}{2^k k!}$

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

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

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

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

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

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

[править] Примеры вычисления

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

С методической точки выбор факториала для обучения программированию крайне неудачен, так как значение факториала быстро растёт и приводит к переполнению, что затрудняет верификацию программы при работе с учащимися.

Вот как будет выглядеть рекурсивный вариант функции вычисления факториала на языке Haskell:

       factorial :: Int -> Int
       factorial 0 = 1
       factorial n = n * factorial (n — 1)

На языке Пролог:

       factorial(0,1) :- !.
       factorial(X,Y) :- X-1 is X1, factorial(X1,Y1), Y1*X is Y.

На языке C:

В нерекурсивном виде:

       int factorial (const int x)
       {
         int n;
         int prod = 1;
         
         for (n = 2; n <= x; n++)
           prod *= n;
         
         return prod;
       }

В рекурсивном виде:

       int factorial (const int x)
       {
         return (x == 0 ? 1 : x * factorial (x - 1));
       }

На языке Scheme (диалект Лиспа):

       (define (factorial n)
         (if (> n 1)
             (* n (factorial (- n 1)))
           1))

На языке Ruby:

В рекурсивном виде:

       def fact (n)
         n == 0 ? 1 : n*fact(n - 1)
       end

В нерекурсивном виде:

       def fact (n)
         m = 1
         (2 .. n).each {|e| m *= e }
         m
       end

       def fact (n)
         n.zero? ? 1 : (1..n).inject(1){ |fctr, e| fctr * e }
       end

На языке Глагол:

В рекурсивном виде:

 ЗАДАЧА Факториал(Число: ЦЕЛ): ЦЕЛ;
   ЕСЛИ Число = 0 ТО ВОЗВРАТ 1 ИНАЧЕ ВОЗВРАТ Число * Факториал(Число - 1) КОН
 КОН Факториал;

В нерекурсивном виде:

 ЗАДАЧА Факториал(Число: ЦЕЛ): ЦЕЛ;
 ПЕР
   ч, р: ЦЕЛ;
 УКАЗ
   р := 1;
   ОТ ч := 1 ДО Число ВЫП
     р := р * ч
   КОН;
   ВОЗВРАТ р
 КОН Факториал;

На языке Pascal:

В рекурсивном виде:

function f(var n:longint):longint;
begin
 if n=0 then f:=1
        else f:=f(n-1)*n
end;

В нерекурсивном виде:

function f(var n:longint):longint;
var i:longint;
begin
 f:=1;
 for i:=1 to n do 
  f:=f*i
end;

Категории: Целочисленные последовательности | Теория чисел | Комбинаторика