Fatorial

$n$	$n!$
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5.040
8	40.320
9	362.880
10	3.628.800
15	1.307.674.368.000
20	2.432.902.008.176.640.000
25	15.511.210.043.330.985.984.000.000
50	3,0414093201713378044 × 1064
70	1,19785717... × 10100
450	1,73336873... × 101.000
3.249	6,41233768... × 1010.000
25.206	1,205703438... × 10100.000
100.000	2,8242294079... × 10456.573

Na matemática, o fatorial (AO 1945: factorial) de um número natural n, representado por n!, é o produto de todos os inteiros positivos menores ou iguais a n. A notação n! foi introduzida por Christian Kramp em 1808.

Definição

A função fatorial é normalmente definida por:

$n!=\prod _{k=1}^{n}k\qquad \forall n\in \mathbb {N}$

Por exemplo,

$5!=1\times 2\times 3\times 4\times 5=120$

Note que esta definição implica em particular que

$0!=1$

porque o produto vazio, isto é, o produto de nenhum número é 1. Deve-se prestar atenção neste valor pois este faz com que a função recursiva

$(n+1)!=n!\times (n+1)$

funcione para n = 0.

A função fatorial também pode ser definida (inclusive para não-inteiros) através da função gama:

$z!=\Gamma (z+1)=\int _{0}^{\infty }t^{z}e^{-t}\,dt$

A sequência dos fatoriais (sequência A000142 na OEIS) para n = 0, 1, 2,... começa com:

1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,...

Aplicações

Os fatoriais são importantes em análise combinatória. Por exemplo, existem n! caminhos diferentes de arranjar n objetos distintos numa sequência. (Os arranjos são chamados permutações) E o número de opções que podem ser escolhidos é dado pelo coeficiente binomial. Veja também binômio de Newton.

${n \choose k}={n! \over k!(n-k)!}.$

Os fatoriais também aparecem em cálculo. Por exemplo, no teorema de Taylor, que expressa a função f(x) como uma série de série de potências em x. A razão principal é que o n derivativo de xⁿ é n!. Os fatoriais também são usados extensamente na teoria da probabilidade.

Os fatoriais são também frequentemente utilizados como exemplos simplificados de recursividade, em ciência da computação, porque satisfazem as seguintes relações recursivas: (se n ≥ 1):

n! = n (n − 1)!

Como Calcular Fatoriais

O valor numérico de n! pode ser calculado por multiplicação repetida se n não for grande demais. É isto que as calculadoras fazem. O maior fatorial, que a maioria das calculadoras suportam é 69!, porque 70! > 10¹⁰⁰.

Quando n é grande demais, n! pode ser calculado com uma boa precisão usando a aproximação de Stirling:

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

Esta é uma versão simplificada que pode ser provada usando a matemática básica do ensino secundário; a ferramenta essencial é a indução matemática. Esta é aqui apresentada na forma de um exercício:

$\left({n \over 3}\right)^{n}<n!<\left({n \over 2}\right)^{n}\ {\mbox{se}}\ n\geq 6.$

Logaritmo de Fatorial

O logaritmo de um fatorial pode ser usado para calcular o número de dígitos que a base de um fatorial irá ocupar. ln(n!) pode ser facilmente calculado da seguinte forma:

$\ln(n!)=\sum _{k=1}^{n}{\ln(k)}$

Note que esta função, demonstrada graficamente, é quase linear para valores baixos; mas o fator ${\ln(n!)} \over n$ cresce de maneira arbitrária, embora vagarosa. Por exemplo, este é o gráfico de seus primeiros 20 mil valores:

$\ln(n!)\approx n\ln(n)-n+{\frac {\ln(n)}{2}}+{\frac {\ln(2\pi )}{2}}.$

Uma boa aproximação para ln(n!) é fazer o logaritmo da fórmula de Stirling.

Generalidades

A função gama similar

Ver artigo principal: Função gama

A função gama Γ(z) é definida para todos os números complexos z exceto os inteiros não positivos (z = 0, −1, −2, −3, ...). Relaciona-se aos fatoriais pelo fato de que satisfaz um relacionamento recursivo similar àquele da função fatorial:

$n!=n(n-1)!$

$\Gamma (n+1)=n\Gamma (n)$

Junto com a definição Γ(1) = 1 isto gera a equação

$\Gamma (n+1)=n!\qquad \forall n\in \mathbb {N} ,n\geq 1.$

Devido a este relacionamento, a função gama é frequentemente tida como uma generalização da função fatorial para o domínio dos números complexos. Isso é justificado pelas seguintes razões:

• Significado compartilhado — a definição canônica da função factorial é o relacionamento recursivo mencionado, compartilhado por ambos.
• Unicidade — a função gama é a única função que satisfaz o relacionamento recursivo mencionado para o domínio dos números complexos e é holomórfica e cuja restrição ao eixo positivo real é convexa no log. Ou seja, é a única função que poderia ser uma generalização da função fatorial.
• Contexto — a função gama é geralmente usada num contexto similar ao dos factoriais (mas, é claro, onde um domínio mais geral for de interesse).

Multifactoriais

Uma notação relacionada comum é o uso de múltiplos pontos de exclamação para simbolizar um multifactorial, o produto de inteiros em passos de dois (n!!), três (n!!!), ou mais.

n!! denota o factorial duplo de n e é definido recursivamente por

$n!!=\left\{{\begin{matrix}1,\qquad \quad \ &&{\mbox{se }}n=0{\mbox{ ou }}n=1;\\n(n-2)!!&&{\mbox{se }}n\geq 2.\qquad \qquad \end{matrix}}\right.$

Por exemplo, 8!! = 2 · 4 · 6 · 8 = 384 e 9!! = 1 · 3 · 5 · 7 · 9 = 945. A sequência de factoriais duplos para n = 0, 1, 2,... é :1, 1, 2, 3, 8, 15, 48, 105, 384, 945, 3840, ...

Algumas identidades envolvendo factoriais duplos são:

$n!=n!!(n-1)!!$

$(2n)!!=2^{n}n!$

$(2n+1)!!={(2n+1)! \over (2n)!!}={(2n+1)! \over 2^{n}n!}$

$\Gamma \left(n+{1 \over 2}\right)={\sqrt {\pi }}{(2n-1)!! \over 2^{n}}$

Deve-se ser cuidadoso para não interpretar n!! como o factorial de n!, que deveria ser escrito (n!)! e é um número muito maior (para n>2).

O factorial duplo é a variante mais comumente usada, mas pode-se definir o factorial triplo do mesmo modo (n!!!) e assim por diante. Em geral, o k-ésimo factorial, notado por n!^(k), é definido recursivamente como

$n!^{(k)}=\left\{{\begin{matrix}1,\qquad \qquad \ &&{\mbox{se }}0\leq n<k;\\n(n-k)!^{(k)},&&{\mbox{se }}n\geq k.\quad \ \ \,\end{matrix}}\right.$

Hiperfactoriais

Ocasionalmente o hiperfactorial de n é considerado. É escrito como H(n) e definido por

$H(n)=\prod _{k=1}^{n}k^{k}=1^{1}\cdot 2^{2}\cdot 3^{3}\cdots (n-1)^{n-1}\cdot n^{n}$

Para n = 1, 2, 3, 4,... os valores de H(n) são 1, 4, 108, 27648,...

A função hiperfactorial é similar à factorial, mas produz números maiores. A taxa de crescimento desta função, contudo, não é muito maior que um factorial regular.

Superfactoriais

Neil Sloane e Simon Plouffe definiram o superfactorial em 1995 como o produto dos primeiros n fatoriais. Assim, o superfatorial de 4 é

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

No geral,

$\mathrm {sf} (n)=\prod _{k=1}^{n}k!=\prod _{k=1}^{n}k^{n-k+1}=1^{n}\cdot 2^{n-1}\cdot 3^{n-2}\cdots (n-1)^{2}\cdot n^{1}.$

A sequência de superfatoriais começa (de n=0) como:

1, 1, 2, 12, 288, 34560, 24883200, ... (sequência A000178 na OEIS)

Esta ideia pode ser facilmente estendida para superduperfatorial como o produto dos primeiros n superfactoriais (iniciando com n=0), assim

1, 1, 2, 24, 6912, 238878720, 5944066965504000, ... (sequência A055462 na OEIS)

e aí em diante, recursivamente para todos os fatoriais múltiplos, onde o m-factorial de n é o produto dos primeiros n (m-1)-factoriais, i.e.

$\mathrm {mf} (n,m)=\mathrm {mf} (n-1,m)\mathrm {mf} (n,m-1)=\prod _{k=1}^{n}k^{n-k+m-1 \choose n-k}$

onde $\mathrm {mf} (n,0)=n$ para $n>0$ e $\mathrm {mf} (0,m)=1$.

Hiperfatoriais (definição alternativa)

Clifford Pickover, no seu livro Keys to Infinity, de 1995, define o superfactorial de n, escrito comodidade n$ (o $ deveria, na verdade, ser um sinal de fatorial ! com um S sobrepusto) como

$n\$=n^{(4)}n$

onde a notação científica ⁽⁴⁾ denota o operador hyper4, ou usando a notação da seta de Knuth,

$n\$=(n!)\uparrow \uparrow (n!)$

Esta sequência de superfatoriais começa quando se usa:

$1\$=1$

$2\$=2^{2}=4$

$3\$=6\uparrow \uparrow 6=6^{6^{6^{6^{6^{6}}}}}$

Fatoração prima de fatoriais

A potência de p que ocorre na fatoração prima de n! é

$\sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor$

Esta fórmula permite que fatoriais grandes sejam fatorados eficientemente.

O Teorema de Wilson diz que (p-1)! + 1 é um múltiplo de p se, e somente se, p for um número primo.

Um método alternativo

É possível calcular o expoente de um número primo $p$ na decomposição de $n!$ escrevendo-se o número $n$ como a soma das potências de $p$ (de modo semelhante ao usado na Conversão entre sistemas numéricos), e depois substitui-se cada uma dessas potências pelo somatório de todas as potências menores de $p$, incluindo-se $p^{0}=1$ e calcula-se o resultado. Vejamos alguns exemplos para melhor clareza:

1) Qual é o expoente de 2 na fatoração prima de $14!$?

$14=8+4+2={\color {blue}2^{3}}+{\color {blue}2^{2}}+{\color {blue}2}$.

Substituindo-se $2^{3}$ por $(1+2^{1}+2^{2})=7$,

e depois $2^{2}$ por $(1+2^{1})=3$ e

$2^{1}$ por $1$ (pois é igual a $2^{0}$) e calculando, obtemos:

$7+3+1=11$. Logo $14!$ é múltiplo de $2^{11}$ na sua decomposição em fatores primos.

Outro exemplo:

2) Se $n!$ em sua fatoração prima é múltiplo de $5^{2016}$, determine o menor valor possível de $n$.

O caminho é o inverso: escreve-se 2016 como a soma dos somatórios de potências de 5 (dados pela tabela abaixo) e depois substitui-se cada um desses somatórios pela menor potência de 5 que é maior que o somatório.

n	$5^{n}$	$\sum _{k=0}^{n-1}5^{k}$
0	1	$-$
1	5	1
2	25	6
3	125	31
4	625	156
5	3125	781
$\cdots$	$\cdots$	$\cdots$

Então temos:

$2016=2\cdot {\color {blue}781}+2\cdot {\color {blue}156}+4\cdot {\color {blue}31}+3\cdot {\color {blue}6}$

Substituindo-se os números em azul pelas potências de 5 correspondentes na tabela acima e calculando-se, vem: ${\color {red}3125}\cdot 2+{\color {red}625}\cdot 2+{\color {red}125}\cdot 4+{\color {red}25}\cdot 3=2\cdot 5^{5}+2\cdot 5^{4}+4\cdot 5^{3}+3\cdot 5^{2}=8075$.

O que significa que $8075!$ em sua fatoração prima é múltiplo de $5^{2016}$.

Algoritmo

Um exemplo clássico do cálculo de fatorial na linguagem de programação C.

Recursivo

int fatorial (int numero) {
    return numero == 0 ? 1 : numero * fatorial(numero - 1);
}

Iterativo

int fatorial (int numero) {
    int resultado = numero;
    if (numero == 0) resultado++;
    while (numero > 1) resultado *= --numero;
    return resultado;
}

Ver também

• Função digama
• Função gama
• Fórmula de Stirling
• Desarranjo
• Número triangular

Ligações externas

• «table of 2! - 256! (exata)» 
• «Guia de referencia para o factorial n! (em inglês)» 
• «O dicionário dos números grandes» 
• «Algoritmo factorial»  - Pascal
• «Algoritmos interessantes» 
• «Cálculo do fatorial (N≤40000)»