Factorial

El factorial de${\displaystyle 0}$es${\displaystyle 1}$, o en símbolos,${\displaystyle 0!=1}$Existen varias motivaciones para esta definición :

• Para${\displaystyle n=0}$, la definición de${\displaystyle n!}$como un producto implica el producto de ningún número en absoluto, y por lo tanto es un ejemplo de la convención más amplia de que el producto vacío , un producto de ningún factor, es igual a la identidad multiplicativa. ^{[ 22 ]}
• Existe exactamente una permutación de cero objetos: al no haber nada que permutar, la única reorganización posible es no hacer nada. ^{[ 21 ]}
• Esta convención hace que muchas identidades en combinatoria sean válidas para todas las elecciones válidas de sus parámetros. Por ejemplo, el número de maneras de elegir todos${\displaystyle n}$elementos de un conjunto de${\displaystyle n}$es${\textstyle {\tbinom {n}{n}}={\tfrac {n!}{n!0!}}=1,}$una identidad de coeficiente binomial que solo sería válida con${\displaystyle 0!=1}$. ^{[ 23 ]}
• Con${\displaystyle 0!=1}$, la relación de recurrencia para el factorial sigue siendo válida en${\displaystyle n=1}$Por lo tanto , con esta convención, un cálculo recursivo del factorial solo necesita tener el valor de cero como caso base , lo que simplifica el cálculo y evita la necesidad de casos especiales adicionales. ^{[ 24 ]}
• Configuración${\displaystyle 0!=1}$permite la expresión compacta de muchas fórmulas, como la función exponencial , como una serie de potencias :${\textstyle e^{x}=\sum _{n=0}^{\infty }{\frac {x^{n}}{n!}}.}$^{[ 14 ]}
• Esta elección coincide con la función gamma.${\displaystyle 0!=\Gamma (0+1)=1}$y la función gamma se define como una función continua de números complejos que no implica una elección separada en este valor. ^{[ 25 ]}

Como función de${\displaystyle n}$, el factorial tiene un crecimiento más rápido que el exponencial , pero crece más lentamente que una función exponencial doble . ^{[ 48 ]} Su tasa de crecimiento es similar a${\displaystyle n^{n}}$pero más lento por un factor exponencial. Una forma de aproximarse a este resultado es tomando el logaritmo natural del factorial, lo que convierte su fórmula de producto en una suma, y ​​luego estimando la suma mediante una integral: $${\displaystyle \ln n!=\sum _{x=1}^{n}\ln x\approx \int _{1}^{n}\ln x\,dx=n\ln n-n+1.}$$ Exponenciando el resultado (e ignorando la insignificante${\displaystyle +1}$término) se aproxima${\displaystyle n!}$como${\displaystyle (n/e)^{n}}$. ^{[ 49 ]} Al acotar con mayor precisión la suma tanto superior como inferiormente mediante una integral, utilizando la regla del trapecio , se demuestra que esta estimación necesita un factor de corrección proporcional a${\displaystyle {\sqrt {n}}}$. La constante de proporcionalidad para esta corrección se puede encontrar a partir del producto de Wallis , que expresa${\displaystyle \pi }$como razón límite de factoriales y potencias de dos. El resultado de estas correcciones es la aproximación de Stirling : ^{[ 50 ]}$${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\,.}$$ Aquí, el${\displaystyle \sim }$El símbolo significa que, como${\displaystyle n}$tiende al infinito, la relación entre los lados izquierdo y derecho se aproxima${\displaystyle 1}$en el límite . La fórmula de Stirling proporciona el primer término de una serie asintótica que se vuelve aún más precisa cuando se toma a un mayor número de términos: ^{[ 51 ]}$${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\left(1+{\frac {1}{12n}}+{\frac {1}{288n^{2}}}-{\frac {139}{51840n^{3}}}-{\frac {571}{2488320n^{4}}}+\cdots \right).}$$ Una versión alternativa (la aproximación derivada directamente de la fórmula de Euler-Maclaurin ) converge más rápido porque solo requiere exponentes impares en los términos de corrección: ^{[ 51 ]}$${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\exp \left({\frac {1}{12n}}-{\frac {1}{360n^{3}}}+{\frac {1}{1260n^{5}}}-{\frac {1}{1680n^{7}}}+\cdots \right).}$$Srinivasa Ramanujan , Bill Gosper y otros también han desarrollado muchas otras variaciones de estas fórmulas . ^{[ 51 ]}

El logaritmo binario del factorial, utilizado para analizar la ordenación por comparación , puede estimarse con mucha precisión utilizando la aproximación de Stirling. En la fórmula siguiente,${\displaystyle O(1)}$El término invoca la notación ^de la gran O. ^{[ 45} ]$${\displaystyle \log _{2}n!=n\log _{2}n-n\log _{2}e+{\frac {1}{2}}\log _{2}n+O(1).}$$

La fórmula del producto para el factorial implica que${\displaystyle n!}$es divisible por todos los números primos que son como máximo${\displaystyle n}$y por ningún número primo mayor. ^{[ 52 ]} La fórmula de Legendre proporciona información más precisa sobre su divisibilidad , la cual da el exponente de cada número primo.${\displaystyle p}$en la factorización prima de${\displaystyle n!}$como ^{[ 53 ] [ 54 ]}$${\displaystyle \sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor ={\frac {n-s_{p}(n)}{p-1}}.}$$ Aquí${\displaystyle s_{p}(n)}$denota la suma de la base -${\displaystyle p}$dígitos de${\displaystyle n}$El exponente dado por esta fórmula puede denominarse más técnicamente valuación p -ádica del factorial. [ ^{54 ]} Aplicando la fórmula de Legendre a la fórmula del producto para coeficientes binomiales se obtiene ^el teorema de Kummer , un resultado similar sobre el exponente de cada primo en la factorización de un coeficiente binomial. ^{[ 55 ]} Agrupando los factores primos del factorial en potencias primas de diferentes maneras se obtienen las particiones multiplicativas de factoriales . ^{[ 56 ]}

El caso especial de la fórmula de Legendre para${\displaystyle p=5}$da el número de ceros finales en la representación decimal de los factoriales. ^{[ 57 ]} Según esta fórmula, el número de ceros se puede obtener restando los dígitos en base 5 de${\displaystyle n}$de${\displaystyle n}$y dividiendo el resultado por cuatro. ^{[ 58 ]} La fórmula de Legendre implica que el exponente del primo${\displaystyle p=2}$siempre es mayor que el exponente para${\displaystyle p=5}$, así que cada factor de cinco puede combinarse con un factor de dos para producir uno de estos ceros finales. ^{[ 57 ]} Los dígitos iniciales de los factoriales se distribuyen según la ley de Benford . ^{[ 59 ]} Toda secuencia de dígitos, en cualquier base, es la secuencia de dígitos iniciales de algún número factorial en esa base. ^{[ 60 ]}

Otro resultado sobre la divisibilidad de factoriales, el teorema de Wilson , establece que${\displaystyle (n-1)!+1}$es divisible por${\displaystyle n}$si y solo si${\displaystyle n}$es un número primo . ^{[ 52 ]} Para cualquier entero dado${\displaystyle x}$, la función de Kempner de${\displaystyle x}$viene dado por el más pequeño${\displaystyle n}$para qué${\displaystyle x}$divide${\displaystyle n!}$. ^{[ 61 ]} Para casi todos los números (todos excepto un subconjunto de excepciones con densidad asintótica cero), coincide con el mayor factor primo de${\displaystyle x}$. ^{[ 62 ]}

El producto de dos factoriales,${\displaystyle m!\cdot n!}$, siempre divide equitativamente${\displaystyle (m+n)!}$. ^{[ 63 ]} Hay infinitos factoriales que son iguales al producto de otros factoriales: si${\displaystyle n}$es en sí mismo cualquier producto de factoriales, entonces${\displaystyle n!}$es igual a ese mismo producto multiplicado por un factorial más,${\displaystyle (n-1)!}$Los únicos ejemplos conocidos de factoriales que son productos de otros factoriales pero que no son de esta forma "trivial" son :${\displaystyle 9!=7!\cdot 3!\cdot 3!\cdot 2!}$,${\displaystyle 10!=7!\cdot 6!=7!\cdot 5!\cdot 3!}$, y${\displaystyle 16!=14!\cdot 5!\cdot 2!}$. ^{[ 64 ]} De la conjetura abc se seguiría que solo hay un número finito de ejemplos no triviales. ^{[ 65 ]}

El máximo común divisor de los valores de un polinomio primitivo de grado${\displaystyle d}$sobre los enteros divide exactamente${\displaystyle d!}$. ^{[ 63 ]}

Hay infinitas maneras de extender los factoriales a una función continua . ^{[ 66 ]} La más utilizada de estas ^{[ 67 ]} utiliza la función gamma , que puede definirse para números reales positivos como la integral$${\displaystyle \Gamma (z)=\int _{0}^{\infty }x^{z-1}e^{-x}\,dx.}$$ La función resultante está relacionada con el factorial de un entero no negativo.${\displaystyle n}$por la ecuación $${\displaystyle n!=\Gamma (n+1),}$$ que puede utilizarse como definición del factorial para argumentos no enteros. En todos los valores${\displaystyle x}$para lo cual ambos${\displaystyle \Gamma (x)}$y${\displaystyle \Gamma (x-1)}$Se definen, la función gamma obedece la ecuación funcional$${\displaystyle \Gamma (n)=(n-1)\Gamma (n-1),}$$ generalizando la relación de recurrencia para los factoriales. ^{[ 66 ]}

La misma integral converge de forma más general para cualquier número complejo.${\displaystyle z}$cuya parte real es positiva. Se puede extender a los puntos no enteros en el resto del plano complejo resolviendo la fórmula de reflexión de Euler.$${\displaystyle \Gamma (z)\Gamma (1-z)={\frac {\pi }{\sin \pi z}}.}$$ Sin embargo, esta fórmula no se puede utilizar en números enteros porque, para ellos, la${\displaystyle \sin \pi z}$El término produciría una división por cero . El resultado de este proceso de extensión es una función analítica (más específicamente una función meromorfa ), la continuación analítica de la fórmula integral para la función gamma. Tiene un valor distinto de cero en todos los números complejos, excepto para los enteros no positivos donde tiene polos simples . Correspondientemente, esto proporciona una definición para el factorial en todos los números complejos distintos de los enteros negativos. ^{[ 67 ]} Una propiedad de la función gamma, que la distingue de otras interpolaciones continuas de los factoriales, viene dada por el teorema de Bohr-Mollerup , que establece que la función gamma (desplazada por uno) es la única función log-convexa en los números reales positivos que interpola los factoriales y obedece la misma ecuación funcional. Un teorema de unicidad relacionado de Helmut Wielandt establece que la función gamma compleja y sus múltiplos escalares son las únicas funciones holomorfas en el semiplano complejo positivo que obedecen la ecuación funcional y permanecen acotadas para números complejos con parte real entre 1 y 2. ^{[ 68 ]}

Otras funciones complejas que interpolan los valores factoriales incluyen la función gamma de Hadamard , que es una función completa sobre todos los números complejos, incluidos los enteros no positivos. ^{[ 69 ] [ 70 ]} En los números p -ádicos , no es posible interpolar continuamente la función factorial directamente, porque los factoriales de los enteros grandes (un subconjunto denso de los enteros p -ádicos) convergen a cero según la fórmula de Legendre, lo que obliga a que cualquier función continua que esté cerca de sus valores sea cero en todas partes. En cambio, la función gamma p -ádica proporciona una interpolación continua de una forma modificada del factorial, omitiendo los factores en el factorial que son divisibles por p . ^{[ 71 ]}

La función digamma es la derivada logarítmica de la función gamma. Así como la función gamma proporciona una interpolación continua de los factoriales, desplazada en uno, la función digamma proporciona una interpolación continua de los números armónicos , desplazada por la constante de Euler-Mascheroni . ^{[ 72 ]}

La función factorial es una característica común en las calculadoras científicas . ^{[ 73 ]} También está incluida en bibliotecas de programación científica como el módulo de funciones matemáticas de Python ^{[ 74 ]} y la biblioteca Boost C++ . ^{[ 75 ]}

Si la eficiencia no es una preocupación, calcular factoriales es trivial: simplemente multiplique sucesivamente una variable inicializada a${\displaystyle 1}$por los enteros hasta${\displaystyle n}$La simplicidad de este cálculo lo convierte en un ejemplo común en el uso de diferentes estilos y métodos de programación informática. [ ^{76 ] El} cálculo de${\displaystyle n!}$puede expresarse en pseudocódigo usando iteración ^{[ 77 ]} como

define factorial( n ): f := 1 para i := 1, 2, 3, ..., n : f := f * i retornar f

o utilizando recursión ^{[ 78 ]} basada en su relación de recurrencia como

define factorial( n ): if ( n = 0) return 1 return n * factorial( n − 1)

Otros métodos adecuados para su cálculo incluyen la memorización , ^{[ 79 ]} la programación dinámica , ^{[ 80 ]} y la programación funcional . ^{[ 81 ]} La complejidad computacional de estos algoritmos puede analizarse utilizando el modelo de computación de máquina de acceso aleatorio de costo unitario , en el que cada operación aritmética toma un tiempo constante y cada número utiliza una cantidad constante de espacio de almacenamiento. En este modelo, estos métodos pueden calcular${\displaystyle n!}$a tiempo${\displaystyle O(n)}$y la versión iterativa utiliza espacio${\displaystyle O(1)}$A menos que se optimice para la recursión de cola , la versión recursiva toma espacio lineal para almacenar su pila de llamadas . ^{[ 82 ]} Sin embargo, este modelo de computación solo es adecuado cuando${\displaystyle n}$es lo suficientemente pequeño como para permitir${\displaystyle n!}$para que quepa en una palabra de máquina . ^{[ 83 ]} Los valores 12! y 20! son los factoriales más grandes que se pueden almacenar, respectivamente, en los enteros de 32 bits ^{[ 84 ]} y 64 bits . ^{[ 85 ]} El punto flotante puede representar factoriales más grandes, pero aproximadamente en lugar de exactamente, y seguirá desbordándose para factoriales mayores que${\displaystyle 170!}$. ^{[ 84 ]}

El cálculo exacto de factoriales grandes implica aritmética de precisión arbitraria , debido al rápido crecimiento y al desbordamiento de enteros . El tiempo de cálculo se puede analizar como una función del número de dígitos o bits en el resultado. ^{[ 85 ]} Según la fórmula de Stirling,${\displaystyle n!}$tiene${\displaystyle b=O(n\log n)}$bits. ^{[ 86 ]} El algoritmo de Schönhage-Strassen puede producir una${\displaystyle b}$-producto de bits a tiempo${\displaystyle O(b\log b\log \log b)}$y algoritmos de multiplicación más rápidos que requieren tiempo${\displaystyle O(b\log b)}$son conocidos. ^{[ 87 ]} Sin embargo, el cálculo del factorial implica productos repetidos, en lugar de una sola multiplicación, por lo que estos límites de tiempo no se aplican directamente. En este contexto, el cálculo${\displaystyle n!}$multiplicando los números del 1 al${\displaystyle n}$en secuencia es ineficiente, porque implica${\displaystyle n}$multiplicaciones, una fracción constante de las cuales requieren tiempo${\displaystyle O(n\log ^{2}n)}$cada uno, dando tiempo total${\displaystyle O(n^{2}\log ^{2}n)}$. Un mejor enfoque es realizar las multiplicaciones como un algoritmo de divide y vencerás que multiplica una secuencia de${\displaystyle i}$números dividiéndolo en dos subsecuencias de${\displaystyle i/2}$números, multiplica cada subsecuencia y combina los resultados con una última multiplicación. Este enfoque para el factorial toma un tiempo total${\displaystyle O(n\log ^{3}n)}$: un logaritmo proviene del número de bits en el factorial, un segundo proviene del algoritmo de multiplicación y un tercero proviene de la estrategia de divide y vencerás. ^{[ 88 ]}

Se obtiene una eficiencia aún mejor calculando n ! a partir de su factorización prima, basándose en el principio de que la exponenciación por elevación al cuadrado es más rápida que expandir un exponente en un producto. ^{[ 86 ] [ 89 ]} Un algoritmo para esto de Arnold Schönhage comienza por encontrar la lista de los primos hasta${\displaystyle n}$Por ejemplo , utilizando la criba de Eratóstenes , y emplea la fórmula de Legendre para calcular el exponente de cada número primo. A continuación, calcula el producto de las potencias de los números primos con estos exponentes, mediante un algoritmo recursivo, de la siguiente manera:

• Utiliza la estrategia de divide y vencerás para calcular el producto de los números primos cuyos exponentes son impares.
• Divide todos los exponentes entre dos (redondeando hacia abajo al entero más cercano), calcula recursivamente el producto de las potencias de números primos con estos exponentes más pequeños y eleva al cuadrado el resultado.
• Multiplica los resultados de los dos pasos anteriores.

El producto de todos los números primos hasta${\displaystyle n}$es un${\displaystyle O(n)}$Número de bits, por el teorema de los números primos , por lo que el tiempo para el primer paso es${\displaystyle O(n\log ^{2}n)}$, con un logaritmo proveniente del algoritmo de divide y vencerás y otro proveniente del algoritmo de multiplicación. En las llamadas recursivas al algoritmo, se puede invocar nuevamente el teorema de los números primos para demostrar que la cantidad de bits en los productos correspondientes disminuye por un factor constante en cada nivel de recursión, por lo que el tiempo total para estos pasos en todos los niveles de recursión se suma en una serie geométrica a${\displaystyle O(n\log ^{2}n)}$. El tiempo para elevar al cuadrado en el segundo paso y la multiplicación en el tercer paso son nuevamente${\displaystyle O(n\log ^{2}n)}$, porque cada uno es una sola multiplicación de un número con${\displaystyle O(n\log n)}$bits. Nuevamente, en cada nivel de recursión, los números involucrados tienen una fracción constante de bits (porque de lo contrario, elevarlos al cuadrado repetidamente produciría un resultado final demasiado grande), por lo que nuevamente las cantidades de tiempo para estos pasos en las llamadas recursivas se suman en una serie geométrica a${\displaystyle O(n\log ^{2}n)}$En consecuencia , todo el algoritmo lleva tiempo.${\displaystyle O(n\log ^{2}n)}$, proporcional a una sola multiplicación con el mismo número de bits en su resultado. ^{[ 89 ]}