+ Selecció de membres de la seqüència factorial ; Els valors especificats en la notació científica s'arrodoneixen a la precisió mostrada n n! 0 1 1 1 2 2 3 6 4 24 5 120 6 720 7 8 9 10 11 12 13 14 15 16 17 18 19 20 25 50 70 100 450 10
En matemàtiques, el factorial d'un enter no negatiu , denotat per (en alguns llibres antics es pot trobar denotat per ), és el producte de tots els nombres enters positius inferiors o iguals a .
Per exemple,
El valor de és 1, d'acord amb la convenció d'un producte buit.Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1988) Concrete Mathematics, Addison-Wesley, Reading MA. , p. 111
L'operació factorial es troba en moltes àrees de les matemàtiques, principalment en combinatòria, àlgebra i anàlisi matemàtica. La seva aparició més bàsica és el fet que hi ha formes d'organitzar objectes diferents en una seqüència (és a dir, permutacions del conjunt d'objectes). Aquest fet ja era conegut pels erudits indis, almenys ja al .N. L. Biggs, The roots of combinatorics, Historia Math. 6 (1979) 109−136 En 1677, Fabian Stedman va descriure els factorials aplicats per canviar el timbre. The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for the Society of College Youths, to which society the "Dedicatory" is addressed. Després de descriure un enfocament recursiu, Stedman va donar una declaració de factorial (usant el llenguatge de l'original):
La notació va ser introduïda pel matemàtic francès Christian Kramp el 1808. says Krempe though.
La definició de la funció factorial també es pot ampliar a arguments no enters, tot conservant les seves propietats més importants; això implica matemàtiques més avançades, especialment tècniques d'anàlisi matemàtica.
Definició La funció factorial està definida formalment pel producte
inicialment per enters , i resultant en aquesta relació de recurrència fonamental: .
Per exemple:
0! Perquè aquesta relació de recurrència s'estengui a , cal definir
i que
Altres conseqüències que indiquen definir i la convenció que el resultat de multiplicar cap nombre sigui 1 és: Hi ha exactament una permutació de 0 objectes (sense res per permutar, «tot» es deixa en el seu lloc). Fa que moltes identitats en combinatòria siguin vàlides per a totes les mides aplicables. El nombre de maneres d'escollir 0 elements del conjunt buit és . Més generalment, la quantitat de formes de triar (tots) elements entre un conjunt de és . Permet l'expressió compacta de moltes fórmules, com la funció exponencial, com una sèrie de potències:
Factorial d'un no-enter La funció factorial també es pot definir per a valors no-enters a partir de matemàtiques més avançades (la funció gamma, ), detallat a la secció Ampliació de factorial a valors d'argument no-enter. Aquesta definició més generalitzada és utilitzada per calculadores avançades i programari matemàtic com Maple o Mathematica.
Aplicacions Encara que la funció factorial té els seus orígens en combinatòria, les fórmules que impliquen factorials es donen en moltes àrees de les matemàtiques. Hi ha diferents maneres d'ordenar objectes diferents en una seqüència, les permutacions d'aquests objectes. Sovint, els factorials apareixen al denominador d'una fórmula per explicar el fet que l'ordre s'ha d'ignorar. Un exemple clàssic és explicar k-combinacions (subconjunts de elements) d'un conjunt amb elements. Es pot obtenir aquesta combinació escollint una k-permutació: seleccionant i eliminant successivament un element del conjunt, vegades, per a un total de
possibilitats. Tanmateix, això produeix les k-combinacions en un ordre concret que un vol ignorar; ja que cada k-combinació s'obté en de manera diferent, el nombre correcte de combinacions és
Aquest nombre es coneix com el coeficient binomial , perquè també és el coeficient de en
De forma similar que el binomi de Newton, es pot trobar en la derivació per la regla del producte per derivades d'ordre superior:
on és la n-èsima derivada de la funció . Els factorials es produeixen en l'àlgebra per diversos motius, com per exemple a través dels coeficients esmentats de la fórmula binomial, o per mitjà de la mitjana de permutacions per simetrizació de determinades operacions. Els factorials també apareixen al càlcul infinitesimal; per exemple, es produeixen en els denominadors dels termes de la fórmula de Taylor, on s'utilitzen com a termes de compensació perquè la derivada de és equivalent a .
Els factorials també s'utilitzen molt sovint en la teoria de la probabilitat. Els factorials poden ser útils per facilitar la manipulació de l'expressió. Per exemple, es pot escriure el nombre de k-permutacions de com
mentre que això és ineficient com un mitjà per calcular aquest nombre, pot servir per provar una propietat de simetria dels coeficients binomials:
Es pot mostrar la funció factorial, utilitzant la regla de la potència, per ser
on és la notació d'Euler per la n-èsima derivada de
Taxa de creixement i aproximacions per a n grans upright=1.35|miniatura|Gràfica del logaritme natural del factorial A mesura que creix, el factorial augmenta més ràpidament que tots els polinomis i les funcions exponencials (però més lentes que les funcions exponencials dobles) de grau .
La majoria d'aproximacions per a es basen en aproximar el seu logaritme natural
La gràfica de la funció es mostra a la figura de la dreta. Es veu aproximadament lineal per a tots els valors raonables de n, però aquesta intuïció és falsa.
Obtenim una de les aproximacions més senzilles per a limitant la suma amb una integral per dalt i per sota:
que ens dona l'estimació
Per tant, (vegeu notació O gran). Aquest resultat té un paper clau en l'anàlisi de la complexitat computacional dels algorismes d'ordenació (vegeu ordenació per comparació). Des dels límits a ln n! deduït anteriorment tenim
De vegades és pràctic utilitzar estimacions més febles però més senzilles. Utilitzant la fórmula anterior, es mostra fàcilment que per a tots els tenim , i per a tots els tenim .
miniatura|upright=1.35|Comparació entre factorial (punts blaus), la funció gamma (línia blava) i la fórmula de Stirling (línia lila) Per a n grans podem obtenir una estimació millor per al número utilitzant l'aproximació de Stirling:
Això prové d'una sèrie asimptòtica del logaritme, i es troba entre aquesta i la següent aproximació:
Una altra aproximació per a va ser donada per Srinivasa Ramanujan
o
Tant aquest com el donar un error relatiu de l'ordre , però Ramanujan és quatre vegades més precís. No obstant això, si utilitzem dos termes de correcció (com en l'aproximació de Ramanujan) l'error relatiu serà de l'ordre :
Computació Si l'eficiència no és una preocupació, la computació de factorials és trivial des d'un punt de vista algorítmic: multiplicant successivament una variable inicialitzada a 1 pels nombres enters fins a (si n'hi ha cap) calcularà .
En llenguatges funcionals, sovint s'aplica directament la definició recursiva per il·lustrar funcions recursives.
Aquest algorisme es pot escriure en C++ utilitzant la funció recursiva: int factorial(int n) { if(n == 0) return 1; return n*factorial(n - 1); }
Amb el llenguatge de programació Python es pot calcular el factorial d'enters arbitràriament grans, limitat només per la memòria disponible. En un Intel Pentium 4, per exemple, el càlcul de 10.000! només triga uns pocs segons. El resultat té 35.660 dígits en notació decimal, amb els últims 2.499 dígits que són tots zeros. #!/usr/bin/env python3 # Syntax: Python 3.3.0 n = int(input('Factorial de n = ')) f = 1 for i in range(1, n + 1): f = f * i print(n,'! = ',f)
#!/usr/bin/env python # Syntax: Python 2.7 n = int(raw_input('Factorial de n = ')) f = 1 for i in range(1, n + 1): f = f * i print n,'! = ',f
La principal dificultat pràctica en la computació del factorial és la mida del resultat. Per assegurar que el resultat exacte s'adapti a tots els valors calculats, fins i tot el tipus d'enter més petit (enters amb signe de 8 bits) sovint requereix més de 700 bits, de manera que cap especificació raonable d'una funció factorial amb tipus de mida fixa pot evitar qüestions de desbordament. Els valors i són els factorials més grans que es poden emmagatzemar, respectivament, en els enters de 32 bits i 64 bits que s'utilitzen habitualment en ordinadors personals, tot i que molts llenguatges de programació admeten tipus d'enters de longitud variable capaços de calcular valors molt grans. https://github.com/wesselbosman/nFactorial La representació de punt flotant d'un resultat aproximat permet anar una mica més lluny, però això també es manté bastant limitat pel possible desbordament. La majoria de les calculadores utilitzen la notació científica amb exponents decimals de dos dígits, i el factor més gran que s'adapta és , perquè . Altres implementacions (com per exemple, programes informàtics com ara programes de full de càlcul) solen manejar valors més grans.
La majoria de les aplicacions per a ordinadors calcularan factorials petits mitjançant la multiplicació directa o la consulta de taules. Es poden aproximar valors factorials més grans mitjançant la fórmula de Stirling. Wolfram Alpha pot calcular resultats exactes per a la funció del sostre i la funció del sòl aplicada al logaritme binari, logaritme natural i logaritme decimal de per valors de fins a , i fins a per als enters.
Si es necessiten els valors exactes de grans factorials, es poden calcular utilitzant aritmètica de precisió arbitrària. En lloc de fer la seqüència de multiplicacions , un programa pot dividir la seqüència en dues parts, els productes tenen aproximadament la mateixa mida i multiplicar-les utilitzant un mètode de divideix i guanyaràs. Això sovint és més eficient.GNU MP software manual, "Factorial Algorithm" (retrieved 22 January 2013).
La millor eficiència asimptòtica s'obté mitjançant la computació de des de la seva factorització en nombres primers. Com va documentar Peter Borwein, la factorització en nombres primers permet a computar a temps , sempre que s'utilitzi un algoritme de multiplicació ràpid (per exemple, l'algoritme de Schönhage-Strassen).Peter Borwein. "On the Complexity of Calculating Factorials". Journal of Algorithms 6, 376–380 (1985) Peter Luschny presenta el codi font i punts de referència per a diversos algorismes factorials eficients, amb l'ús d'un sedàs de primers o no.Peter Luschny, Fast-Factorial-Functions: The Homepage of Factorial Algorithms.
Teoria de nombres
Els factorials tenen moltes aplicacions en la teoria de nombres. En particular, és necessàriament divisible per tots els nombres primers fins i incloent . Com a conseqüència, és un nombre compost si i només si
Un resultat més sòlid és el teorema de Wilson, que afirma que
si i només si és primer.
La fórmula de Legendre dona la multiplicitat del nombre primer que es produeix en la factorització principal de com
o de forma equivalent
on denota la suma dels dígits estàndard en base de .
Afegint 1 a es produeix un nombre divisible per un valor superior a . Aquest fet es pot utilitzar per demostrar en el teorema d'Euclides que el nombre de primers és infinit. Els nombres primers de la forma es diuen nombres primers factorials.
Sèries recíproques Els recíprocs de factorials produeixen una sèrie convergent, la suma del qual és el nombre d'Euler ():
Encara que la suma d'aquesta sèrie és un nombre irracional, és possible multiplicar els factorials per enters positius per produir una sèrie convergent amb una suma racional:
La convergència d'aquesta sèrie a 1 es pot veure del fet que les seves sumes parcials són menors d'un per un factor invers. Per tant, els factors no formen una seqüència d'irracionalitat.
Ampliació de factorial a valors d'argument no-enter La funció gamma i la funció Pi miniatura|La funció gamma interpola la funció factorial a valors no enters. La clau principal és la relació de recurrència generalitzada a un domini continu