Факториал

Факториа́л числа 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-большое. Во многих случаях для приближенного значения факториала достаточно рассматривать только главный член формулы Стирлинга:

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;
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home