Fatorial

Assuntos Relacionados: Matemática

Sobre este escolas selecção Wikipedia

Crianças SOS, uma instituição de caridade educação , organizou esta selecção. SOS mães cada um cuidar de uma família de crianças apadrinhadas .

$n$	$n!$
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40320
9	362880
10	3628800
15	1307674368000
20	2432902008176640000
25	15511210043330985984000000
50	3.04140932 ... × 10 ⁶⁴
70	1.19785717 ... × 10 ¹⁰⁰
450	1.73336873 × 10 ... ¹⁰⁰⁰
3249	6.41233768 ... × 10 ^10.000
25206	1,205703438 ... × 10 ¹⁰⁰⁰⁰⁰
47176	8,4485731495 ... × 10 ^200,001
100000	2,8242294079 ... × 10 ^456,573

Os primeiros selecionados e membros maiores da seqüência de fatoriais (sequência A000142 em OEIS )

Em matemática , o fatorial de um não negativo inteiro n, denotado por n!, é o produto de todos os números inteiros positivos menos do que ou igual a n. Por exemplo,

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

$6! = 1 \ 2 \ times vezes 3 \ \ vezes 4 vezes 5 vezes 6 = \ 720 \$

em que n! representa n fatorial. A notação n! foi introduzido por Christian Kramp em 1808 .

Definição

A função fatorial é formalmente definido pela

$n! = \ Prod_ {k = 1} ^ nk \ qquad \ forall n \ in \ mathbb {N}. \!$

A definição acima incorpora a instância

$0! = 1 \$

como um exemplo do facto de a produto de nenhum número em tudo é 1. Este fato para fatoriais é útil, porque

o relação recursiva $(N + 1)! = N! \ Times (n + 1)$ trabalha para $n = 0$ ;
essa definição faz com que muitas identidades em combinatória válidos para zero de tamanhos.
- Em particular, o número de permutações ou combinações de um conjunto vazio é, simplesmente, uma.

Aplicações

Os fatoriais são usados na análise combinatória . Por exemplo, existem $n!$ caminhos diferentes de arranjar n objetos distintos em uma seqüência. (Os arranjos são chamados permutações ). E o número de maneiras se pode escolher k objetos de entre um dado conjunto de n objetos (o número de combinações), é dada por o chamado coeficiente binomial

${N \ escolher k} = {n! \ Over k! (N-k)!}.$

Em permutações , se $r$ objectos pode ser escolhido a partir de um total de n objectos e dispostos de maneiras diferentes, em que R ≤ n, então o número total de permutações diferentes, é dada por:

${} _nP_r = \ Frac {n!} {(N-r)!}.$

Os fatoriais também aparecem em cálculo . Por exemplo, o teorema de Taylor expressa uma função f (x) como uma série de potências em x, basicamente porque o ^n-ésimo derivado de ^N x N é!.

Os fatoriais também são usados extensivamente na teoria da probabilidade .

Os fatoriais são usados frequentemente como um exemplo simples, juntamente com números de Fibonacci , ao ensinar recursão em ciência da computação , porque satisfazem a seguinte relação recursiva (se n ≥ 1):

$n! = N \ times (n-1)!. \,$

Teoria dos números

Fatoriais têm muitas aplicações em teoria dos números . Em particular, n! é necessariamente divisível por todos os números primos até e incluindo n. Consequentemente, n> 5 é uma número composto se e apenas se

$(N-1)! \ \ Equiv \ 0 \ ({\ rm mod} \ n).$

Um resultado mais forte é Teorema de Wilson, que afirma que

$(P-1)! \ \ Equiv \ -1 \ ({\ rm mod} \ p)$

se e somente se p é primo.

Adrien-Marie Legendre descobriu que a multiplicidade do primo p que ocorre na fatoração em primos de n! pode ser expresso como exatamente

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

que é finito desde o função do assoalho remove todos $p ^ i> n.$

A única fatorial que também é um número primo é 2, mas há muitos números primos da forma $\ Scriptstyle n! \, \ Pm \, 1$ , Chamada primes fatorial.

Todos fatoriais maior que 0! e 1! são ainda, uma vez que são todos os múltiplos de 2.

Taxa de crescimento

Lote de o logaritmo natural do fatorial

Como n cresce, o fatorial n! torna-se maior do que todos os polinômios e funções exponenciais em n.

Quando n é grande, n! pode ser calculada com muita precisão usando Aproximação de Stirling:

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

A versão fraca que pode ser facilmente comprovado com indução matemática é

$\ Left ({n \ over 3} \ right) ^ n <n! <\ Left ({n \ over 2} \ right) ^ n \ \ mbox {if} \ n \ geq 6. \,$

O logaritmo do fatorial pode ser usada para calcular o número de dígitos numa dada base o factorial de um determinado número vai tomar. Ela satisfaz a identidade:

$\ Log n! = \ Sum_ {k = 1} ^ n {\ log k}.$

Note que esta função, se graficamente, é de aproximadamente linear, para valores pequenos; mas o factor ${\ Log n!} \ Over n$ , E, assim, a inclinação do gráfico, não cresce arbitrariamente grande, embora bastante lentamente. O gráfico de $log (n!)$ para $n$ entre 0 e 20.000 é mostrado na figura da direita.

Uma aproximação simples para

baseado em Aproximação de Stirling é

$\ Log n! \ Approx n \ log n - n + \ frac {\ log n} {2} + \ frac {\ log (2 \ pi)} {2}.$

Uma muito melhor aproximação para

foi dada por Srinivasa Ramanujan:

$\ Log n! \ Approx n \ log n - n + \ frac {\ log (n (1 + 4n (1 + 2 N)))} {6} + \ frac {\ log (\ pi)} {2}.$

Pode-se ver a partir disso que

é Ο (n log n). Este resultado desempenha um papel fundamental na análise do complexidade computacional algoritmos de ordenação (ver ordenação por comparação).

Computação

O valor de $n!$ pode ser calculada pela multiplicação se repetiu $n$ não é muito grande. O maior fatorial que a maioria das calculadoras pode suportar é 69 !, porque 70! > 10 ¹⁰⁰ (exceto para a maioria das calculadoras HP que podem lidar com 253! Como seu expoente pode ser de até 499). A calculadora visto no Mac OS X, Microsoft Excel e Google calculadora pode processar factoriais até 170 !, que é o maior fatorial menos do que 2 ¹⁰²⁴ (10 ¹⁰⁰ em hexadecimal ) e corresponde a um número inteiro de 1024 bits. Os valores 12! e 20! são os maiores fatoriais que podem ser armazenados em, respectivamente, os números inteiros de 32 bits e 64 bits comumente usados em computadores pessoais. Na prática, a maioria dos aplicativos de software irá calcular estes pequenos fatoriais por multiplicação direta ou pesquisa de tabela. Valores maiores são frequentemente aproximado em termos de estimativas de ponto flutuante do Função gama, geralmente com A fórmula de Stirling.

Para número teórico e combinatórias cálculos, muito grandes fatoriais exatos são muitas vezes necessários. Fatoriais Bignum pode ser calculado através da multiplicação direta, mas multiplicando a sequência 1 × 2 × ... × n de baixo para cima (ou de cima para baixo) é ineficiente; é melhor para dividir de forma recursiva a sequência de modo a que o tamanho de cada subproduto é minimizado.

A eficiência asymptotically-melhor é obtido calculando n! a partir do seu primeiro-factorização. Como documentado por Peter Borwein, fatoração privilegiada permite $n!$ a ser calculado em tempo O (n (log n log log n) ^2), desde que um rápido algoritmo de multiplicação é utilizado (por exemplo, a Algoritmo Schönhage-Strassen). Peter Luschny apresenta código fonte e valores de referência para vários algoritmos eficientes fatorial, com ou sem o uso de um peneira prime.

A função gama

A função Gamma, como aqui plotados ao longo do eixo real , estende-se o fatorial de uma função suave definido para todos os valores não-inteiros.

A função fatorial também pode ser definida para valores não-inteiros, mas isso requer mais ferramentas avançadas de análise matemática . A função que "preenche" os valores do fatorial entre os números inteiros é chamado o Função gama, denotada $\ Gamma (z)$ para inteiros z não menos do que 1, definida pela

$\ Gamma (z) = \ int_ {0} ^ {\ infty} t ^ {z-1} e ^ {- t} \, \ mathrm {d} t. \!$

Euler fórmula original para a função Gamma foi

$\ Gamma (z) = \ lim_ {n \ to \ infty} \ frac {n ^ zn!} {\ Prod_ {k = 0} ^ n (z + k)}. \!$

A função Gamma está relacionada com fatoriais na medida em que satisfaz um relacionamento recursivo semelhante:

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

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

Juntamente com $\ Gama (1) = 1$ isto resulta da equação para qualquer número inteiro não negativo $n$ :

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

$\ Left (\ frac {1} {2} \ right)! = \ Frac {\ sqrt {\ pi}} {2}$

Com base no valor da função Gamma para 1/2, a exemplo específico de fatoriais semi-inteiros é resolvido para

$\ Left (n + \ frac {1} {2} \ right)! = \ Sqrt {\ pi} \ times \ Prod_ {k = 0} ^ n {2k + 1 \ over 2}.$

Por exemplo

$3.5! = \ Sqrt {\ pi} \ cdot {1 \ over 2} \ cdot {3 \ over2} \ cdot {5 \ over2} \ cdot {7 \ over2} \ approx 11,63.$

A função Gamma é na verdade definida para todos os números complexos $z$ exceto os inteiros não positivos $\ Scriptstyle (z \, = \, 0, \, -1, \, -2, \, \ dots)$ . Ele é muitas vezes visto como uma generalização da função fatorial para o domínio complexo, o que se justifica pelas seguintes razões:

Significado compartilhado. A definição canônica da função factorial compartilha a mesma relação recursiva com a função Gamma.
Contexto. A função gama é geralmente utilizado num contexto semelhante ao dos factoriais (mas, naturalmente, onde um domínio mais geral é de interesse).
Singularidade ( Teorema Bohr-Mollerup). A função Gamma é a única função que satisfaz a relação recursiva acima mencionado para o domínio dos números complexos, é meromorfa, e é log-convexo no eixo real positivo. Isto é, é a única, função log-convexa suave que podia ser uma generalização da função factorial para todos os números complexos.

Euler também desenvolveu uma aproximação convergente para o produto factoriais de números não inteiros, o que pode ser visto como sendo equivalente à fórmula para a função gama acima:

$n! \ Approx \ left [\ left (\ frac {2} {1} \ right) ^ n \ frac {1} {n + 1} \ right] \ left [\ left (\ frac {3} {2} \ right ) ^ n \ frac {2} {n + 2} \ right] \ left [\ left (\ frac {4} {3} \ right) ^ n \ frac {3} {n + 3} \ right] \ dots$

Ele também pode ser escrita como se segue:

$n! = \ Prod_ {k = 1} ^ \ infty {\ frac {{(k + 1)}} {{(k - 1)!! (N + k)}}}.$

O produto converge rapidamente para pequenos valores de n.

Aplicações da função gama

O volume de de um n - dimensional hypersphere é

$V_n = {\ pi ^ {n / 2} R ^ n \ over \ Gamma ((n / 2) + 1)}.$

Fatorial produtos semelhantes

Existem várias outras sequências de números inteiros semelhantes para o factorial que são usados em matemática:

Primorial

O primorial (sequência A002110 em OEIS ) é semelhante ao fatorial, mas com o produto tomada apenas sobre os números primos .

Fatorial duplo

$n !!$ denota o duplo fatorial de $n$ e é definida recursivamente

$n !! = \ begin {cases} 1, & \ mbox {if} n = -1 \ mbox {} ou n = 0 \ mbox {} ou n = 1; \\ N (n-2) !! & \ Mbox {if} n \ GE2. \ Qquad \ qquad \ end {cases}$

Por exemplo, 8 !! = 2 · 4 · 6 · 8 = 384 e 9 !! = 1 · 3 · 5 · 7 · 9 = 945. A sequência dos fatoriais duplos (sequência A006882 em OEIS ) para $n = 0, 1, 2, \ dots$ começa como

1, 1, 2, 3, 8, 15, 48, 105, 384, 945, 3840, ...

A definição acima pode ser utilizado para definir factoriais duplos de números negativos:

$(N-2) !! = \ frac {n !!} {n}$

A sequência dos fatoriais duplos para $n = -1, -3, -5, -7, \ \ pontos,$ começa como

$1, -1, 1/3, -1/15 \ dots$

enquanto o duplo fatorial de negativos inteiros pares é infinito.

Algumas identidades envolvendo factoriais duplas são:

$n! = !! N (n-1) !! \,$

$(2n) = !! 2 ^ nn! \,$

$(2n + 1) !! = {(2n + 1)! \ Over (2m) !!} = {(2n + 1)! \ Over2 ^ nn!}$

$(2n-1) !! = {(2n-1)! \ Cima (2n-2) !!} = {(2n)! \ Over2 ^ nn!}$

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

$\ Gamma \ left ({n \ over2} 1 \ right) = \ sqrt {\ pi} \, \, {n !! \ over2 ^ {(n + 1) / 2}}$

onde $\ Gamma$ é o Função gama. A última equação acima pode ser utilizado para definir a factorial duplo como uma função de qualquer número complexo $n \ neq 0$ , Assim como a função Gamma generaliza a função fatorial. Deve-se ter cuidado para não interpretar $n !!$ como o fatorial de $n!$ , O que seria escrita $(N!)!$ e é um número muito maior (por $n> 2$ ).

Multifatoriais

Uma notação relacionada comum é a utilização de vários pontos de exclamação para denotar um multifactorial, o produto de inteiros em passos de duas ( $n !!$ ), Três ( $n !!!$ ), Ou mais. O duplo fatorial é a variante mais comumente usado, mas pode-se definir o fatorial triplo ( $n !!!$ ) E assim por diante. Em geral, o ^k-ésimo fatorial, denotada por $n! ^ {(k)}$ , É definida recursivamente como

$! n ^ {(k)} = \ \ left {\ begin {matrix} 1, \ qquad \ qquad \ && \ mbox {if} 0 \ le n <k; \\ N (nk)! ^ {(K)}, && \ mbox {if} n \ ge k. \ Quad \ \ \, \ end {matrix} \ right.$

Alguns matemáticos têm sugerido uma notação alternativa de $n! _2$ para o duplo fatorial e da mesma forma $n! _k$ para outros multifatoriais, mas isso não entrou em uso geral.

Fatorial Quádruplo

O fatorial quadruple, no entanto, não é um multifatorial; É um número muito maior dada por $\ Frac {(2m)!} {N!}$ .

Superfactoriais

Neil Sloane e Simon Plouffe definido o superfactorial em 1995 como o produto do primeiro $n$ fatoriais. Assim, o superfactorial de 4 é

$\ Mathrm {sf} (4) = 1! \ Times 2! \ 3 vezes! \ times 4! = 288 \,$

Em geral

$\ Mathrm {sf} (n) = \ Prod_ {k = 1} ^ n k! = \ Prod_ {k = 1} ^ nk ^ {n-k + 1} = 1 ^ n \ ^ {cdot2 n-1} \ cdot3 ^ {n-2} \ cdots (n-1) ^ 2 \ n cdot ^ 1.$

A seqüência de superfatoriais começa (a partir de $n = 0$ ) Como

1, 1, 2, 12, 288, 34560, 24.883.200, ... (sequência A000178 em OEIS )

Esta ideia foi prorrogado em 2000 por Henry Bottomley ao superduperfactorial como o produto do primeiro $n$ superfatoriais, começando (a partir de $n = 0$ ) Como

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

e assim de forma recursiva para qualquer fatorial de níveis múltiplos onde o m ^th fatorial de -level $n$ é o produto do primeiro $n$ $(M - 1)$ fatoriais -LEVEL ^th, ou seja,

$\ Mathrm {mf} (n, m) = \ mathrm {mf} (n-1, m) \ mathrm {mf} (N, M-1) = \ Prod_ {k = 1} ^ nk ^ {n-k + m-1 \ escolher nk}$

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

Superfactoriais (definição alternativa)

Clifford Pickover em seus 1.995 livros Chaves para Infinito definiu o superfactorial de $n$ como

$n \ mathrm {S} \ \ \ \ \ \;!!! {!}! \, \ equiv \ begin {matrix} \ underbrace {{{n ^ n ^} {{\ cdot} ^ {{ \ cdot {} ^ {\ cdot {} ^ n!}}}}}} \\ n! \ End {matrix}, \,$

ou como,

$n \ mathrm {S} \ \ \ \ \ \;!!! \, = n ^ {(4)} {n!}! \,$

onde a ⁽⁴⁾ indica a notação hyper4 operador, ou usando Notação de seta para cima de Knuth,

$n \ mathrm {S} \ \ \ \ \ \;!!! {!} \, = (! n) \ uparrow \ uparrow (! n) \,$

Esta sequência de superfatoriais começa:

$1 \ mathrm {S} \ \ \ \ \ \;!!! {!} \, = 1 \,$

$2 \ mathrm {S} \ \ \ \ \ \;!!! {!} \, = 2 ^ 2 = 4 \,$

$3 \ mathrm {S} \ \ \ \ \ \;!!! {!} \, = 6 \ uparrow \ uparrow6 = {} ^ 6 6 = 6 ^ 6 ^ {{{6 ^ 6 ^ {6 ^ 6}}}}$

Hyperfactorials

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

$H (n) = \ Prod_ {k = 1} ^ nk ^ k = 1 ^ 1 \ ^ cdot2 2 \ cdot3 ^ 3 \ cdots (n-1) ^ {n-1} \ cdot n ^ n.$

Para n = 1, 2, 3, 4, ... os valores H (n) são 1, 4, 108, 27648, ... (seqüência A002109 em OEIS ).

A função hiperfactorial é semelhante ao fatorial, mas produz um número maior. A taxa de crescimento desta função, no entanto, não é muito maior do que um factorial regular. No entanto, H (14) = 1,85 x 10 ... ⁹⁹ já é quase igual a uma gugol, e H (15) = 8,09 x 10 ... ¹¹⁶ é quase da mesma magnitude como o Número de Shannon, o número teórico de possíveis jogos de xadrez.

A função hiperfactorial podem ser generalizados para os números complexos de uma forma semelhante como a função factorial. A função resultante é chamado a K-função.

Retirado de " http://en.wikipedia.org/w/index.php?title=Factorial&oldid=203072717 "

Amazon - Audible - Barnes and Noble - Everand - Kobo - Storytel

See also ebooksgratis.com: no banners, no cookies, totally FREE.