Mostrar código-fonte de Fatorial

{{Sem fontes|data=março de 2019}}
{| class="wikitable" style="margin:0 0 0 1em; text-align:right; float:right;"
|+ Fatoriais selecionados; valores em notação científica são arredondados
|-
! <math>n</math>
! <math>n!</math>
|-
| 0 || 1
|-
| 1 || 1
|-
| 2 || 2
|-
| 3 || 6
|-
| 4 || 24
|-
| 5 || 120
|-
| 6 || 720
|-
| 7 || {{val|5040|fmt=gaps}}
|-
| 8 || {{val|40320}}
|-
| 9 || {{val|362880}}
|-
| 10 || {{val|3628800}}
|-
| 11 || {{val|39916800}}
|-
| 12 || {{val|479001600}}
|-
| 13 || {{val|6227020800}}
|-
| 14 || {{val|87178291200}}
|-
| 15 || {{val|1307674368000}}
|-
| 16 || {{val|20922789888000}}
|-
| 17 || {{val|355687428096000}}
|-
| 18 || {{val|6402373705728000}}
|-
| 19 || {{val|121645100408832000}}
|-
| 20 || {{val|2432902008176640000}}
|-
| 25
| style="text-align:left" | {{val|1.551121004|e=25}}
|-
| 50
| style="text-align:left" | {{val|3.041409320|e=64}}
|-
| 70
| style="text-align:left" | {{val|1.197857167|e=100}}
|-
| 100
| style="text-align:left" | {{val|9.332621544|e=157}}
|-
| 450
| style="text-align:left" | {{val|1.733368733|e=1000|fmt=gaps}}
|-
| {{val|1000|fmt=gaps}}
| style="text-align:left" | {{val|4.023872601|e=2567|fmt=gaps}}
|-
| {{val|3249|fmt=gaps}}
| style="text-align:left" | {{val|6.412337688|e=10000}}
|-
| {{val|10000|fmt=gaps}}
| style="text-align:left" | {{val|2.846259681|e=35659}}
|-
| {{val|25206|fmt=gaps}}
| style="text-align:left" | {{val|1.205703438|e=100000}}
|-
| {{val|100000|fmt=gaps}}
| style="text-align:left" | {{val|2.824229408|e=456573}}
|-
| {{val|205023|fmt=gaps}}
| style="text-align:left" | {{val|2.503898932|e=1000004}}
|-
| {{val|1000000|fmt=gaps}}
| style="text-align:left" | {{val|8.263931688|e=5565708}}
|-
| [[googol|{{val|e=100}}]] ||10<sup>{{val|e=101.9981097754820}}</sup>
|}
Na [[matemática]], o {{PU-AO45|fatorial|factorial}} de um [[número natural]]&nbsp;{{mvar|n}}, denotado por&nbsp;{{math|''n''!}}, é o produto de todos os naturais menores ou iguais a {{mvar|n}}. O fatorial de {{mvar|n}} também é igual ao produto de {{mvar|n}} e o fatorial de seu antecessor:
<math display=block>
\begin{align}
n! &= n  \times  (n-1)  \times (n-2)  \times  (n-3) \times \cdots \times  3 \times  2 \times  1 \\
   &= n\times(n-1)!\\
\end{align}</math>
Por exemplo,
<math display=block>5! = 5\times 4! = 5  \times  4  \times  3  \times  2  \times  1 = 120. </math>
O valor de 0! é 1, conforme a convenção para um [[produto vazio]].<ref name=gkp>{{citar livro|primeiro1=Ronald L.|último1=Graham|autorlink1=Ronald Graham |primeiro2=Donald E.|último2=Knuth|autorlink2=Donald Knuth|primeiro3=Oren|último3=Patashnik|data=1988|título=Concrete Mathematics|publicado=Addison-Wesley|local=Reading, MA|isbn=0-201-14236-8|títulolink=Concrete Mathematics|página=111}}</ref>

Fatoriais foram descobertos em diversas culturas antigas, notavelmente na [[matemática indiana]], nas obras canônicas da literatura de [[Jainismo|Jain]], e por míticos judeus no livro Talmude ''[[Sêfer Yetzirá]]''. A operação fatorial é encontrada em diversas áreas da matemática, notavelmente na [[combinatória]], onde seu uso mais básico é contar as diferentes [[sequência]]s possíveis — as [[permutações]] — de {{mvar|n}} distintos objetos: existem&nbsp;{{math|''n''!}}. Na [[análise matemática]], fatoriais são usados nas [[série de potências]] para a [[função exponencial]] e outras funções. Eles também possuem aplicações na [[álgebra]], [[teoria dos números]], [[teoria das probabilidades]] e [[ciência da computação]].

Muita da matemática das funções fatoriais começou a ser desenvolvida no final do século XVIII e início do XIX. A [[aproximação de Stirling]] gera uma aproximação precisa para fatoriais de números grandes, mostrando que ele cresce mais rápido que o [[crescimento exponencial]]. A fórmula de Legendre descreve os exponentes de números primos numa [[Fatoração de inteiros|decomposição em fatores primos]] dos fatoriais, e pode ser utilizada para contar os zeros à direita dos fatoriais. [[Daniel Bernoulli]] e [[Leonhard Euler]] [[Interpolação|interpolaram]] a função fatorial para uma [[função contínua]] de [[números complexos]], exceto nos inteiros negativos, chamada de [[função gama]] (deslocada).

Várias outras funções e sequências numéricas importantes estão intimamente relacionadas aos fatoriais, incluindo os [[coeficientes binomiais]], [[Duplo fatorial|duplos fatoriais]], [[primoriais]] e [[Desarranjo|subfatoriais]]. Implementações da função fatorial são comumente usadas como exemplo de diferentes estilos de [[programação de computadores]] e estão incluídas em [[calculadora científica|calculadoras científicas]] e bibliotecas de software de [[computação científica]]. Embora calcular diretamente fatoriais grandes usando a fórmula do produto ou recorrência não seja eficiente, algoritmos mais rápidos são conhecidos, combinando, num fator constante, o tempo para [[algoritmos de multiplicação]] rápidos para números com o mesmo número de dígitos.

== Definição ==

A [[função (matemática)|função]] fatorial é normalmente definida por:

:<math>n!=\prod_{k=1}^n k  = n \times (n-1) \times (n-2) \times  ...  \times 3 \times 2 \times 1,\qquad\forall n\in\mathbb{N}</math>

Por exemplo, <math>5! = 5 \times 4 \times 3 \times 2 \times 1 = 120</math>. Como o fatorial de um número é uma [[multiplicação]] de 1 até <math>n</math>, <math>n!</math>, pode ser definido pelo produto de <math>n</math> com o fatorial de seu antecessor. Logo, <math>5! = 5 \times 4! = 120</math>. De forma geral:

:<math>n! = n \times (n-1)!</math>

que pode ser reescrito da seguinte forma:

:<math>(n-1)! = \frac{n!}{n}</math>

Portanto:
:<math>3! = \frac{4!}{4} = \frac{4 \times 3!}{4} = 6</math>
:<math>2! = \frac{3!}{3} = \frac{3 \times 2!}{3} = 2</math>
:<math>1! = \frac{2!}{2} = \frac{2 \times 1}{2} = 1</math>

Esta definição implica em particular que <math>0! = 1</math>, pois

:<math>0! = \frac{1!}{1} = \frac{1}{1} = 1</math>

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

:<math>z!=\Gamma(z+1)=\int_{0}^{\infty} t^z e^{-t}\, dt</math>

A sequência dos fatoriais {{OEIS|A000142}} para ''n''&nbsp;=&nbsp;0, 1, 2,... começa com:
:1, 1, [[dois|2]], [[seis|6]], [[vinte e quatro|24]], [[cento e vinte|120]], 720, {{fmtn|5040}}, {{fmtn|40320}}, {{fmtn|362880}}, {{fmtn|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ção|permutações]]) E o número de opções que podem ser escolhidos é dado pelo [[coeficiente binomial]]. Veja também [[binômio de Newton]].
:<math>{n\choose k}={n!\over k!(n-k)!}.</math>

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ência]]s em ''x''. A razão principal é que o ''n'' derivativo de ''x''<sup>''n''</sup> é ''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''&nbsp;(''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!&nbsp;>&nbsp;[[googol|10<sup>100</sup>]].

Quando ''n'' é grande demais, ''n''! pode ser calculado com uma boa precisão usando a [[Fórmula de Stirling|aproximação de Stirling]]:

:<math>n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n.</math>

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:

:<math>\left({n \over 3}\right)^n <n! < \left({n \over 2}\right)^n\ \mbox{se}\ n\geq 6.</math>

== 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:

:<math>\ln(n!)=\sum_{k=1}^n{\ln(k)}</math>

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

[[Imagem:Log-factorial.PNG|300px|thumb|right]]

:<math>\ln(n!) \approx n\ln(n) - n + \frac {\ln(n)} {2} + \frac {\ln(2 \pi)} {2}.</math>

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

== Generalidades ==
=== A função gama similar ===
{{AP|[[Função gama]]}}
A função gama Γ(''z'') é definida para todos os [[número complexo|números complexos]] ''z'' exceto os inteiros não positivos (''z''&nbsp;=&nbsp;0,&nbsp;−1,&nbsp;−2,&nbsp;−3,&nbsp;...). Relaciona-se aos fatoriais pelo fato de que satisfaz um relacionamento recursivo similar àquele da função fatorial:

:<math>n!=n(n-1)!</math>
:<math>\Gamma(n+1)=n\Gamma(n)</math>

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

:<math>\Gamma(n+1)=n!\qquad\forall n\in\mathbb{N},n\ge1.</math>

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

:<math>
  n!! =
  \left\{
   \begin{matrix}
    1,\qquad\quad\ &&\mbox{se }n=0\mbox{ ou }n=1;
   \\
    n(n-2)!!&&\mbox{se }n\ge2.\qquad\qquad
   \end{matrix}
  \right.
</math>

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:
:<math>n!=n!!(n-1)!!</math>

:<math>(2n)!!=2^nn!</math>

:<math>(2n+1)!!={(2n+1)!\over(2n)!!}={(2n+1)!\over2^nn!}</math>

:<math>\Gamma\left(n+{1\over2}\right)=\sqrt\pi{(2n-1)!!\over2^n}</math>

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''!<sup>(''k'')</sup>, é definido recursivamente como

:<math>
  n!^{(k)} =
  \left\{
   \begin{matrix}
    1,\qquad\qquad\ &&\mbox{se }0\le n<k;
   \\
    n(n-k)!^{(k)},&&\mbox{se }n\ge k.\quad\ \ \,
   \end{matrix}
  \right.
</math>

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

:<math>
  H(n)
  =\prod_{k=1}^n k^k
  =1^1\cdot2^2\cdot3^3\cdots(n-1)^{n-1}\cdot n^n
</math>

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 é
:<math>\mathrm{sf}(4)=1!\times 2!\times 3!\times 4!=288</math>
No geral,
:<math>
  \mathrm{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.
</math>
A sequência de superfatoriais começa (de ''n''=0) como:
:1, 1, 2, 12, 288, 34560, 24883200, ... {{OEIS|A000178}}

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, ... {{OEIS|A055462}}
e aí em diante, [[recursão|recursivamente]] para todos os '''fatoriais múltiplos''', onde o ''m''-factorial de ''n'' é o produto dos primeiros ''n'' ''(m-1)''-factoriais, i.e.
:<math>\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}</math>
onde <math>\mathrm{mf}(n,0)=n</math> para <math>n>0</math> e <math>\mathrm{mf}(0,m)=1</math>.

=== 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
:<math>n\$=n^{(4)}n</math>
onde a notação científica <sup>(4)</sup> denota o operador [[hyper4]], ou usando a [[notação da seta de Knuth]],
:<math>n\$=(n!)\uparrow\uparrow(n!)</math>
Esta sequência de superfatoriais começa quando se usa:
:<math>1\$=1</math>
:<math>2\$=2^2=4</math>
:<math>3\$=6\uparrow\uparrow6=6^{6^{6^{6^{6^6}}}}</math>

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

:<math>\sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor</math>

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|se, e somente se]], ''p'' for um [[número primo]].

== [[Algoritmo]] ==
Um exemplo clássico do cálculo de fatorial na [[linguagem de programação]] [[C (linguagem de programação)|C]]/[[Java (linguagem de programação)|Java]]

=== [[Recursivo]] ===
<syntaxhighlight lang = "C">
int fatorial (int numero) {
    return numero == 0 ? 1 : numero * fatorial(numero - 1);
}
</syntaxhighlight>

=== Iterativo ===
<syntaxhighlight lang = "c">
int fatorial (int numero) {
    int resultado = numero;
    if (numero == 0) resultado++;
    while (numero > 1) resultado *= --numero;
    return resultado;
}
</syntaxhighlight>

== Ver também ==
* [[Função digama]]
* [[Função gama]]
* [[Fórmula de Stirling]]
* [[Desarranjo]]
* [[Número triangular]]

{{referências}}

== Ligações externas ==
*{{Link||2=http://factorielle.free.fr |3=Guia de referencia para o factorial n! (em inglês)}}
* {{Link||2=http://www.luschny.de/math/factorial/FastFactorialFunctions.htm |3=Algoritmos interessantes }}
* {{Link||2=http://www.elektro-energetika.cz/calculations/faktorial.php?language=portugues |3=Cálculo do fatorial (N≤40000)}}

{{funções}}
{{Séries (matemáticas)}}
{{Portal3|Matemática}}

{{DEFAULTSORT:Factorial}}
<!-- [[Categoria:Matemática]]
 -->
[[Categoria:Teoria dos números]]
[[Categoria:Funções matemáticas]]
[[Categoria:Combinatória]]