Factorial

De Viquipèdia
Salta a: navegació, cerca
Selecció de membres de la seqüència factorial (successió A000142 a l'OEIS); 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 5040
8 40320
9 362880
10 3628800
11 39916800
12 479001600
13 6227020800
14 87178291200
15 1307674368000
16 20922789888000
17 355687428096000
18 6402373705728000
19 121645100408832000
20 2432902008176640000
25 1,551121004×1025
50 3,041409320×1064
70 1,197857167×10100
100 9,332621544×10157
450 1,733368733×101.000
1000 4,023872601×102.567
3249 6,412337688×1010.000
10000 2,846259681×1035.659
25206 1,205703438×10100.000
100000 2,824229408×10456.573
205023 2,503898932×101.000.004
1000000 8,263931688×105.565.708
10100
109,956570552×10101

En matemàtiques, el factorial d'un enter no negatiu , 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.[1]

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 segle xii.[2] En 1677, Fabian Stedman va descriure els factorials aplicats per canviar el timbre.[3] Després de descriure un enfocament recursiu, Stedman va donar una declaració de factorial (usant el llenguatge de l'original):

« Ara, la naturalesa d'aquests mètodes és tal, que els canvis d'un número comprenen [inclosos] els canvis en tots els nombres inferiors, ... de manera que el canvi d'un nombre en un repicament complet sembla que es forma mitjançant la unió dels repicaments complets de tots els nombres inferiors en un cos sencer;[4] »

La notació va ser introduïda pel matemàtic francès Christian Kramp el 1808.[5][6]

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ó[modifica]

La funció factorial està definida formalment pel producte

inicialment per enters , i resultant en aquesta relació de recurrència fonamental:

.

Per exemple:

0![modifica]

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 tots els tamanys 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
.

Factorial d'un no-enter[modifica]

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[modifica]

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.[7][8]
  • 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 ,[9] perquè també és el coeficient de en
on és la n-èsima derivada de la funció .
  • Els factorials també s'utilitzen molt sovint en la teoria de la probabilitat.[11]
  • 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:[8][9]
on és la notació d'Euler per la n-èsima derivada de [12]

Taxa de creixement i aproximacions per a n grans[modifica]

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 dóna 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 .

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 (Ramanujan 1988)

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ó[modifica]

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.[13] 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.[14]

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).[15] Peter Luschny presenta el codi font i punts de referència per a diversos algorismes factorials eficients, amb o sense l'ús d'un sedàs de primers.[16]

Teoria de nombres[modifica]

Vegeu també: Operació mòdul

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.[17][18]

La fórmula de Legendre dóna 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.[19] Els nombres primers de la forma es diuen nombres primers factorials.

Sèries recíproques[modifica]

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.[20]

Ampliació de factorial a valors d'argument no-enter[modifica]

La funció gamma i la funció Pi[modifica]

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
Article principal: Funció gamma

A més d'enters no negatius, la funció factorial també es pot definir per a valors no enters, però això requereix eines més avançades per a l'anàlisi matemàtica. Una funció que «omple» els valors del factorial (però amb un desplaçament de 1 en l'argument) s'anomena funció gamma, denotada , definida per a tots els nombres complexos , excepte els enters no positius, i donada quan la part real de és positiva per

La seva relació amb els factorials és que per a qualsevol nombre natural

La fórmula original d'Euler per a la funció gamma era

A vegades s'utilitza una notació alternativa, originalment introduïda per Gauss. La funció Pi, denotada per als nombres reals no inferior a 0, està definida per

En termes de la funció gamma és

La funció factorial, generalitzada a tots els nombres reals, excepte els nombres enters negatius. Per exemple: *

Realment el factorial s'estén en això

A més d'això, la funció Pi satisfà la mateixa recurrència que fan els factors, però a cada valor complex on es defineix

De fet, això ja no és una relació de recurrència, sinó una equació funcional.

Expressat en termes de la funció gamma, aquesta equació funcional pren la forma

Atès que el factorial s'amplia per la funció Pi, per a cada valor complex on es defineix, podem escriure:

Els valors d'aquestes funcions en valors de mig enters es determinen, doncs, per un d'ells; s'obté

del qual segueix per  ∈ N,

Per exeple,

També es desprèn que per a  ∈ N,

Per exemple,

La funció de Pi no és, sens dubte, l'única manera d'estendre factorials a una funció definida en gairebé tots els valors complexos, ni tan sols l'única que és analítica allà on es defineixi. No obstant això, se sol considerar com la forma més natural d'ampliar els valors dels factors a una funció complexa. Per exemple, el teorema de Bohr-Mollerup estableix que la funció gamma és l'única funció que pren el valor 1 a 1, satisfà l'equació funcional , és meromorfa en els nombres complexos i és logarítmica convexa en l'eix real positiu. També hi ha una afirmació similar per a la funció Pi, usant l'equació funcional .

No obstant això, existeixen funcions complexes que probablement són més simples en el sentit de la teoria analítica de funcions i que interpolen els valors factorials. Per exemple, la funció gamma de Hadamard (Hadamard 1894) que, a diferència de la funció Gamma, és una funció entera.[21]

Euler també va desenvolupar una aproximació de producte convergent per als factorials no enters, que es pot considerar equivalent a la fórmula de la funció gamma anterior:

Tanmateix, aquesta fórmula no proporciona un mitjà pràctic de computar la funció Pi o gamma, ja que la seva taxa de convergència és lenta.

El factorial al pla complex[modifica]

Amplitud i fase de factorial d'argument complex

La representació a través de la funció gamma permet avaluar el factor d'argument complex. En la imatge de la dreta es mostren les equilínies d'amplitud i fase de factorial. Fem . Es mostren diversos nivells de mòdul constant (amplitud) i fase constant . L'interval abasta el rang, amb el pas de la unitat. La línia ratllada mostra el nivell .

Les línies primes mostren nivells intermedis de mòdul constant i fase constant. En els pols, la fase i l'amplitud no estan definides. Les equilínies són denses a prop de les singularitats al llarg de valors enters negatius de l'argument.

Per a , es poden utilitzar els desenvolupament de Taylor:

Els primers coeficients d'aquest desenvolupament són

aproximació
0
1
2
3

on és la constant d'Euler-Mascheroni i és la funció zeta de Riemann. Els sistemes d'àlgebra computacional, com SageMath, poden generar molts termes d'aquest desenvolupament.

Aproximacions de factorial[modifica]

Per als grans valors de l'argument, es pot calcular aproximadament el valor del factorial a través de la integral de la funció digamma, utilitzant la representació de la fracció contínua. Aquest enfocament es deu a Thomas Joannes Stieltjes (1894). Escrivint , llavors és

Stieltjes va donar una fracció contínua per a

Els primers coeficients d' són[22]

n an
0 1 / 12
1 1 / 30
2 53 / 210
3 195 / 371
4 22999 / 22737
5 29944523 / 19733142
6 109535241009 / 48264275462

Hi ha una idea errònia que o per a qualsevol complex . De fet, la relació a través del logaritme és vàlida només per a un rang de valors específic de en la proximitat de l'eix real, mentre que . Com més gran sigui la part real de l'argument, més petit ha de ser la part imaginària. No obstant això, la relació inversa, , és vàlida per a tot el pla complex a part de zero. La convergència és pobra a prop de la part negativa de l'eix real; és difícil tenir una bona convergència de qualsevol aproximació a prop de les singularitats. Mentre o , els 6 coeficients anteriors són suficients per a l'avaluació del factorial amb la complexa «doble» precisió. Per obtenir una major precisió, es poden calcular més coeficients per un esquema QD racional (algoritme QD de H. Rutishauser).[23]

La no-extensibilitat als nombres enters negatius[modifica]

La relació permet computar el factorial d'un enter a partir del factorial d'un enter «més petit». La relació es pot invertir de manera que es pot calcular el factorial d'un enter donat el factorial d'un nombre enter «més gran»:

Tingueu en compte, però, que aquesta recursió no permet computar el factor d'un enter negatiu; ús de la fórmula per calcular requeriria una divisió per zero i, per tant, ens impedeix computar un valor factorial per a cada enter negatiu; de la mateixa manera, la funció gamma no està definida per a nombres enters negatius, encara que es defineix per a tots els altres nombres complexos).

Productes i funcions de tipus factorial[modifica]

Hi ha diverses seqüències d'enters similars als factorials que s'utilitzen en matemàtiques:

Doble factorial[modifica]

Article principal: Doble factorial

El producte de tots els nombres sencers senars fins a un nombre senar es diu el doble factorial de , denotat per .[24] Això és,

Per exemple, .

La seqüència de factorials dobles per a ,és (successió A001147 a l'OEIS)

Es pot utilitzar la notació de doble factorial per simplificar l'expressió de determinades integrals trigonomètriques,[25] per proporcionar una expressió dels valors de la funció gamma en arguments mig-enters i el volum d'hiperesferes,[26] i per resoldre molts problemes de comptadors en combinatórics, incloent comptar arbres binaris amb fulles etiquetades i coincidències perfectes en grafs complets.[24][27]

Multifactorials[modifica]

Vegeu també: Nombre de Catalan

Una notació comuna relacionada és utilitzar múltiples punts d'exclamació per denotar un multifactorial, el producte dels enters en dos (), tres (), o més passos. El doble factorial és la variant més utilitzada, però també es pot definir el triple factorial i així successivament.

Es pot definir el k-èsim factorial, denotat per , recursivament per enters positius com

encara que vegeu la definició alternativa a continuació. A més, de manera similar a , es pot definir:

Per a prou gran, la funció factorial única ordinària s'amplia a través de funcions multifactorials de la següent manera:

Alguns matemàtics han suggerit una notació alternativa de per al doble factorial i de manera similar per a altres multifactorials, però això no s'ha fet un ús general. Una altra notació comuna és col·locar el paràmetre com a subíndex com per denotar els multifactorials definits anteriorment.

De la mateixa manera que no està definit per a nombres enters negatius, i no està definit per a nombres parells enters negatius, no està definit per a enters negatius divisibles per .

Primorial[modifica]

Article principal: Primorial

El primorial (successió A002110 a l'OEIS) és similar al factorial, però es realitza els productes només amb nombres primers.

Per al n-èsim nombre primer , el primorial es defineix com el producte dels primers nombres primes:[28][29]

,

on és el k-èsim nombre primer. Per exemple, significa el producte dels cinc primers nombres primers:

Superfactorial[modifica]

Vegeu també: Nombres grans

Neil Sloane i Simon Plouffe van definir un superfactorial en The Encyclopedia of Integer Sequences (Acadèmic Press, 1995) com el producte dels primers factorials de . Així que el superfactorial de 4 és

En general

De forma equivalent, un superfactorial es calcula amb la fórmula

que és el determinant d'una matriu Vandermonde.

La seqüència dels superfactorials (successió A000178 a l'OEIS) comença:

Definició alternativa[modifica]

Vegeu també: Tetració

Clifford Pickover en el seu llibre de 1995 Keys to Infinity va utilitzar una nova notació, , per definir el superfactorial

o com,

on la notació [4] denota l'hiperoperador 4, o usant la notació de Knuth,

La seqüència d'aquests superfactorials comença

Aquí, com és habitual per a l'exponenciació composta, l'agrupació s'entén que de dreta a esquerra:

Hiperfactorial[modifica]

En ocasions es considera l'hiperfactorial de . S'escriu com i es defineix per

Els primers valors de l'hiperfactorial (successió A002109 a l'OEIS) són

L'índex de creixement asimptòtic és

on és la constant de Glaisher–Kinkelin.[30] és gairebé igual a un googol, i <math>H(15) = 8,0896 \times10^{116} és gairebé igual que el nombre de Shannon, el nombre teòric de possibles jocs d'escacs. En comparació amb la definició Pickover del superfactor, l'hiperfactorial creix relativament lentament.

La funció hiperfactorial es pot generalitzar a nombres complexos d'una manera similar a la funció factorial. La funció resultant es diu funció K.

Referències[modifica]

  1. Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1988) Concrete Mathematics, Addison-Wesley, Reading MA. ISBN 0-201-14236-8, p. 111
  2. N. L. Biggs, The roots of combinatorics, Historia Math. 6 (1979) 109−136
  3. Stedman, Fabian. Campanalogia, 1677, p. 6–9.  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.
  4. Stedman, 1677, p. 8.
  5. Higgins, Peter. Number Story: From Counting to Cryptography. New York: Copernicus, 2008, p. 12. ISBN 978-1-84800-000-1.  says Krempe though.
  6. Hayes, Brian. «Fat Tails.». American Scientist, abstracte a la Britannica Online Encyclopedia, 05 2007. [Consulta: 9 desembre 2009].
  7. Cheng, Eugenia. Beyond Infinity: An expedition to the outer limits of the mathematical universe (en en). Profile Books, 2017-03-09. ISBN 9781782830818. 
  8. 8,0 8,1 Conway, John H.; Guy, Richard. The Book of Numbers (en en). Springer Science & Business Media, 1998-03-16. ISBN 9780387979939. 
  9. 9,0 9,1 Knuth, Donald E. The Art of Computer Programming: Volume 1: Fundamental Algorithms (en en). Addison-Wesley Professional, 1997-07-04. ISBN 9780321635747. 
  10. «18.01 Single Variable Calculus, Lecture 37: Taylor Series», Fall 2006.
  11. Kardar, Mehran. «Chapter 2: Probability». A: Statistical Physics of Particles (en anglès). Cambridge University Press, 2007-06-25. ISBN 9780521873420. 
  12. «18.01 Single Variable Calculus, Lecture 4: Chain rule, higher derivatives», Fall 2006.
  13. https://github.com/wesselbosman/nFactorial
  14. GNU MP software manual, "Factorial Algorithm" (retrieved 22 January 2013).
  15. Peter Borwein. "On the Complexity of Calculating Factorials". Journal of Algorithms 6, 376–380 (1985)
  16. Peter Luschny, Fast-Factorial-Functions: The Homepage of Factorial Algorithms.
  17. O'Connor, John J.; Robertson, Edmund F. «Abu Ali al-Hasan ibn al-Haytham» (en anglès). MacTutor History of Mathematics archive.
  18. W., Weisstein, Eric. «Wilson's Theorem» (en en).
  19. Bostock, Linda; Chandler, Suzanne; Rourke, C. Further Pure Mathematics (en en). Nelson Thornes, 2014-11-01, p. 168. ISBN 9780859501033. 
  20. Guy, Richard K. Unsolved problems in number theory. 3rd. Springer-Verlag, 2004, p. 346. ISBN 0-387-20860-7. «E24 Irrationality sequences» 
  21. Peter Luschny, Hadamard versus Euler – Who found the better Gamma function?.
  22. Digital Library of Mathematical Functions, http://dlmf.nist.gov/5.10
  23. Peter Luschny, On Stieltjes' Continued Fraction for the Gamma Function..
  24. 24,0 24,1 Callan, David. A combinatorial survey of identities for the double factorial, 2009. 
  25. Meserve, B. E. «Classroom Notes: Double Factorials». The American Mathematical Monthly, 55, 7, 1948, p. 425–426. DOI: 10.2307/2306136.
  26. Mezey, Paul G. «Some dimension problems in molecular databases». Journal of Mathematical Chemistry, 45, 1, 2009, p. 1–6. DOI: 10.1007/s10910-008-9365-8.
  27. Dale, M. R. T.; Moon, J. W. «The permuted analogues of three Catalan sets». Journal of Statistical Planning and Inference, 34, 1, 1993, p. 75–87. DOI: 10.1016/0378-3758(93)90035-5.
  28. Weisstein, Eric W., «Primorial» a MathWorld (en anglès).
  29. (successió A002110 a l'OEIS)
  30. Weisstein, Eric W., «Glaisher–Kinkelin Constant» a MathWorld (en anglès).

Bibliografia[modifica]

Vegeu també[modifica]

Enllaços externs[modifica]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Factorial Modifica l'enllaç a Wikidata