Factorial

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Producto de números de 1 a n

Factoriales seleccionados; valores en notación científica son redondeados
$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×10²⁵
50	3.041409320×10⁶⁴
70	1.197857167×10¹⁰⁰
100	9.332621544×10¹⁵⁷
450	1.733368733×10¹⁰⁰⁰
1000	4.023872601×10²⁵⁶⁷
3249	6.412337688×10¹⁰⁰⁰⁰
10000	2.846259681×10³⁵⁶⁵⁹
25206	1.205703438×10¹⁰⁰⁰⁰⁰
100000	2.824229408×10⁴⁵⁶⁵⁷³
205023	2.503898932×10^1000004
1000000	8.263931688×10^5565708
10100	10^{10^{101.9981097754820}}

En matemáticas, la factorial no negativo entero $n$ , denotado por $n!$ , es el producto de todos los enteros positivos menos o igual a $n$ . El factorial de $n$ también es igual al producto de $n$ con la siguiente factorial más pequeña:

{displaystyle {begin{aligned}n!&=ntimes (n-1)times (n-2)times (n-3)times cdots times 3times 2times 1\&=ntimes (n-1)!\end{aligned}}}

{displaystyle 5!=5times 4!=5times 4times 3times 2times 1=120.}

Los factores han sido descubiertos en varias culturas antiguas, especialmente en matemáticas indias en las obras canónicas de la literatura Jain, y por místicos judíos en el libro Talmúdico Sefer Yetzirah. La operación factorial se encuentra en muchas áreas de matemáticas, especialmente en combinatoria, donde su uso más básico cuenta las posibles secuencias distintas – las permutaciones – de $n$ objetos distintos: allí son $n!$ . En el análisis matemático, los factoriales se utilizan en la serie de poder para la función exponencial y otras funciones, y también tienen aplicaciones en álgebra, teoría de números, teoría de probabilidad y ciencia informática.

Gran parte de las matemáticas de la función factorial se desarrolló a finales del siglo XVIII y principios del XIX. La aproximación de Stirling proporciona una aproximación precisa al factorial de números grandes, mostrando que crece más rápidamente que el crecimiento exponencial. La fórmula de Legendre describe los exponentes de los números primos en una descomposición en factores primos de los factoriales y se puede utilizar para contar los ceros finales de los factoriales. Daniel Bernoulli y Leonhard Euler interpolaron la función factorial a una función continua de números complejos, excepto en los enteros negativos, la función gamma (compensada).

Muchas otras funciones notables y secuencias numéricas están estrechamente relacionadas con los factoriales, incluidos los coeficientes binomiales, los factoriales dobles, los factoriales descendentes, los primoriales y los subfactoriales. Las implementaciones de la función factorial se usan comúnmente como un ejemplo de diferentes estilos de programación de computadoras y se incluyen en calculadoras científicas y bibliotecas de software de computación científica. Aunque calcular directamente factoriales grandes utilizando la fórmula del producto o la recurrencia no es eficiente, se conocen algoritmos más rápidos que igualan dentro de un factor constante el tiempo para algoritmos de multiplicación rápida para números con el mismo número de dígitos.

Historia

El concepto de factoriales ha surgido de forma independiente en muchas culturas:

En las matemáticas indias, una de las primeras descripciones conocidas de los factores proviene del Anuyogadvāra-sūtra, una de las obras canónicas de la literatura Jain, que se ha asignado fechas que varían de 300 a 400 CE. Se separa el orden ordenado e inverso de un conjunto de artículos de las otras órdenes ("mixed"), evaluando el número de órdenes mixtas restando dos de la fórmula de producto habitual para el factorial. La regla del producto para las permutaciones también fue descrita por el monje Jinabhadra del siglo VI. Los eruditos hindúes han estado usando fórmulas factoriales desde al menos 1150, cuando Bhāskara II mencionó factoriales en su trabajo Līlāvatī, en relación con un problema de cuántas maneras Vishnu podría contener sus cuatro objetos característicos (una concha de concha, discus, mace y lotus flor) en sus cuatro manos, y un problema similar para un dios de diez manos.
En las matemáticas del Medio Oriente, el libro místico hebreo de la creación Sefer Yetzirah, del período Talmúdico (200 a 500 CE), enumera los factoriales hasta 7! como parte de una investigación sobre el número de palabras que se pueden formar del alfabeto hebreo. Los factores también fueron estudiados por razones similares por Al-Khalil ibn Ahmad al-Farahidi, del siglo VIII. El matemático árabe Ibn al-Haytham (también conocido como Alhazen, c. 965 – c. 1040) fue el primero en formular el teorema de Wilson que conecta los factores con los números principales.
En Europa, aunque las matemáticas griegas incluyeron algunas combinatorias, y Platón utilizó famosamente 5040 (un factorial) como la población de una comunidad ideal, en parte debido a sus propiedades divisibilidad, no hay evidencia directa del estudio griego antiguo de factores. En cambio, la primera obra sobre factoriales en Europa fue por eruditos judíos como Shabbethai Donnolo, explicando el pasaje de Sefer Yetzirah. En 1677, el autor británico Fabian Stedman describió la aplicación de factores para cambiar el anillo, un arte musical que implica el anillo de varias campanas sintonizadas.

Desde finales del siglo XV, los factores se convirtieron en tema de estudio de los matemáticos occidentales. En un tratado de 1494, el matemático italiano Luca Pacioli calculó factoriales hasta 11!, en relación con un problema de los arreglos de mesa de comedor. Christopher Clavius discutió factoriales en un comentario de 1603 sobre la obra de Johannes de Sacrobosco, y en los años 1640, el polimatismo francés Marin Mersenne publicó tablas grandes (pero no totalmente correctas) de factoriales, hasta 64!, basados en la obra de Clavius. La serie de potencia para la función exponencial, con las reciprocas de factoriales para sus coeficientes, fue formulada por primera vez en 1676 por Isaac Newton en una carta a Gottfried Wilhelm Leibniz. Otras importantes obras de matemáticas europeas tempranas sobre factoriales incluyen una amplia cobertura en un tratado de 1685 por John Wallis, un estudio de sus valores aproximados para grandes valores de $n$ por Abraham de Moivre en 1721, una carta de 1729 de James Stirling a de Moivre indicando lo que se conoce como aproximación de Stirling, y trabajar al mismo tiempo por Daniel Bernoulli y Leonhard Euler formulando la extensión continua de la función factorial a la función gamma. Adrien-Marie Legendre incluyó la fórmula de Legendre, describiendo a los exponentes en la factorización de los factoriales en los poderes primarios, en un texto de 1808 sobre la teoría del número.

La notación $n!$ para factoriales fue introducido por el Kramp cristiano matemático francés en 1808. También se han utilizado muchas otras notaciones. Otra notación posterior, en la que el argumento del factorial estaba medio cerrado por los lados izquierdo y inferior de una caja, fue popular durante algún tiempo en Gran Bretaña y América, pero cayó fuera de uso, tal vez porque es difícil de escribir. La palabra "factorial" (originalmente francés: factorielle) fue utilizado por primera vez en 1800 por Louis François Antoine Arbogast, en la primera obra sobre la fórmula de Faà di Bruno, pero refiriéndose a un concepto más general de productos de progresiones aritméticas. Los "factores" a los que se refiere este nombre son los términos de la fórmula del producto para el factorial.

Definición

La función factorial de un entero positivo $n$ se define por el producto de todos los enteros positivos no mayor que $n$

{displaystyle n!=1cdot 2cdot 3cdots (n-2)cdot (n-1)cdot n.}

{displaystyle n!=prod _{i=1}^{n}i.}

Si esta fórmula de producto se cambia para mantener todo menos el último término, definiría un producto de la misma forma, para un factorial más pequeño. Esto conduce a una relación de recurrencia, según la cual se puede obtener cada valor de la función factorial multiplicando el valor anterior por $n$ :

{displaystyle n!=ncdot (n-1)!.}

{displaystyle 5!=5cdot 4!=5cdot 24=120}

Factoriales de cero

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

Para $n=0$ , la definición de $n!$ como un producto implica el producto de ningún número en absoluto, y así es un ejemplo de la convención más amplia que el producto vacío, un producto de ningún factor, es igual a la identidad multiplicativa.
Hay exactamente una permutación de cero objetos: sin nada a permutar, la única reorganización es no hacer nada.
Esta convención hace que muchas identidades en combinatoria sean válidas para todas las opciones válidas de sus parámetros. Por ejemplo, el número de maneras de elegir todos $n$ elementos de un conjunto de $n$ es ${textstyle {tbinom {n}{n}}={tfrac {n!}{n!0!}}=1,}$ una identidad de coeficiente binomio que sólo sería válida con ${displaystyle 0!=1}$ .
Con ${displaystyle 0!=1}$ , la relación de recurrencia para el factorial sigue siendo válida a $n=1$ . Por lo tanto, con esta convención, una computación recurrente de las necesidades factoriales debe tener sólo el valor para cero como un caso base, simplificando la computación y evitando la necesidad de casos especiales adicionales.
Ajuste ${displaystyle 0!=1}$ permite la expresión compacta de muchas fórmulas, como la función exponencial, como una serie de potencia: ${textstyle e^{x}=sum _{n=0}^{infty }{frac {x^{n}}{n!}}.}$
Esta elección coincide con la función gamma ${displaystyle 0!=Gamma (0+1)=1}$ , y la función gamma debe tener este valor para ser una función continua.

Aplicaciones

Los primeros usos de la función factorial implican contar permutaciones: hay $n!$ diferentes formas de organizar $n$ objetos distintos en una secuencia. Los factores aparecen más ampliamente en muchas fórmulas en combinatoria, para contabilizar diferentes pedidos de objetos. Por ejemplo, los coeficientes binomiales ${tbinom {n}{k}}$ Contamos con $k$ - Elemento combinaciones (subconjuntos de $k$ elementos) de un conjunto con $n$ elementos, y se puede calcular de factoriales utilizando la fórmula

{displaystyle {binom {n}{k}}={frac {n!}{k!(n-k)!}}.}

n

n

n!/e

En álgebra, los factoriales surgen a través del teorema del binomio, que usa coeficientes binomiales para expandir las potencias de las sumas. También ocurren en los coeficientes usados para relacionar ciertas familias de polinomios entre sí, por ejemplo, en las identidades de Newton para polinomios simétricos. Su uso para contar permutaciones también se puede reformular algebraicamente: los factoriales son los órdenes de grupos simétricos finitos. En cálculo, los factoriales aparecen en la fórmula de Faà di Bruno para encadenar derivadas superiores. En el análisis matemático, los factoriales aparecen con frecuencia en los denominadores de las series de potencias, sobre todo en las series de la función exponencial,

{displaystyle e^{x}=1+{frac {x}{1}}+{frac {x^{2}}{2}}+{frac {x^{3}}{6}}+cdots =sum _{i=0}^{infty }{frac {x^{i}}{i!}},}

n!

n

th derivativede

x^{n}

n_{i}

tamaño

i

{displaystyle sum _{i=0}^{infty }{frac {x^{i}n_{i}}{i!}}.}

En la teoría de números, la propiedad más saliente de los factores es la divisibilidad de $n!$ por todos los enteros positivos arriba a $n$ , descrito más precisamente para los factores principales por la fórmula de Legendre. Sigue que los números primitivos arbitrariamente grandes se pueden encontrar como los principales factores de los números ${displaystyle n!pm 1}$ , llevando a una prueba del teorema de Euclides que el número de primos es infinito. Cuando ${displaystyle n!pm 1}$ es en sí mismo un principio factorial; relacionado, el problema de Brocard, también planteado por Srinivasa Ramanujan, se refiere a la existencia de números cuadrados de la forma ${displaystyle n!+1}$ . En contraste, los números ${displaystyle n!+2,n!+3,dots n!+n}$ debe ser todo compuesto, demostrando la existencia de grandes brechas arbitrariamente. Una prueba elemental del postulado de Bertrand sobre la existencia de una prima en cualquier intervalo del forma ${displaystyle [n,2n]}$ , uno de los primeros resultados de Paul Erdős, se basó en las propiedades divisibilidad de los factoriales. El sistema de número factorial es una notación de radio mixta para números en los que los valores de lugar de cada dígito son factoriales.

Los factores se utilizan ampliamente en la teoría de la probabilidad, por ejemplo en la distribución Poisson y en las probabilidades de permutaciones aleatorias. En la informática, más allá de aparecer en el análisis de búsquedas de fuerza bruta sobre permutaciones, los factores surgen en el límite inferior de ${displaystyle log _{2}n!=nlog _{2}n-O(n)}$ sobre el número de comparaciones necesarias para ordenar un conjunto de $n$ ítems, y en el análisis de tablas de hash encadenadas, donde la distribución de llaves por celda puede ser precisamente aproximada por una distribución Poisson. Además, los factores aparecen naturalmente en fórmulas de la física cuántica y estadística, donde a menudo se consideran todas las permutaciones posibles de un conjunto de partículas. En la mecánica estadística, los cálculos de la entropía como la fórmula de entropía de Boltzmann o la ecuación de Sackur-Tetrode deben corregir el conteo de microstates dividiendo por los factores de los números de cada tipo de partículas indistinguibles para evitar la paradoja de Gibbs. La física cuántica proporciona la razón subyacente para por qué estas correcciones son necesarias.

Propiedades

Crecimiento y aproximación

Comparación de la aproximación factorial, de Stirling, y la aproximación más simple

{displaystyle (n/e)^{n}}

, en una escala doblemente logarítmica

Error relativo en una serie de Stirling truncada vs. número de términos

Como función de $n$ , el factorial tiene un crecimiento más rápido que exponencial, pero crece más lentamente que una doble función exponencial. Su tasa de crecimiento es similar a $n^n$ , pero más lento por un factor exponencial. Una manera de acercarse a este resultado es tomando el logaritmo natural del factorial, que convierte su fórmula de producto en una suma, y luego estimando la suma por una integral:

{displaystyle ln n!=sum _{x=1}^{n}ln xapprox int _{1}^{n}ln x,dx=nln n-n+1.}

+1

n!

{displaystyle (n/e)^{n}}

{sqrt {n}}

pi

{displaystyle n!sim {sqrt {2pi n}}left({frac {n}{e}}right)^{n},.}

sim

n

{displaystyle n!sim {sqrt {2pi 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).}

{displaystyle n!sim {sqrt {2pi 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).}

El logaritmo binario del factorial, utilizado para analizar la clasificación de comparación, se puede calcular con precisión utilizando la aproximación de Stirling. En la fórmula siguiente, la $O(1)$ término invoca gran O notación.

{displaystyle log _{2}n!=nlog _{2}n-(log _{2}e)n+{frac {1}{2}}log _{2}n+O(1).}

Divisibilidad y dígitos

La fórmula de producto para el factorial implica que $n!$ es divisible por todos los números primos que están en más $n$ , y sin números primos mayores. Más información precisa sobre su divisibilidad es dada por la fórmula de Legendre, que da el exponente de cada primo $p$ en la factorización principal $n!$ como

{displaystyle sum _{i=1}^{infty }leftlfloor {frac {n}{p^{i}}}rightrfloor ={frac {n-s_{p}(n)}{p-1}}.}

s_{p}(n)

Base.

p

n

El caso especial de la fórmula de Legendre para $p=5$ da el número de ceros rastreadores en la representación decimal de los factoriales. Según esta fórmula, el número de ceros se puede obtener restando los 5 dígitos base de $n$ desde $n$ , y dividir el resultado por cuatro. La fórmula de Legendre implica que el exponente de la primera $p=2$ es siempre más grande que el exponente para $p=5$ , por lo que cada factor de cinco puede ser emparejado con un factor de dos para producir uno de estos ceros que siguen. Los principales dígitos de los factores se distribuyen según la ley de Benford. Cada secuencia de dígitos, en cualquier base, es la secuencia de dígitos iniciales de algún número factorial en esa base.

Otro resultado sobre la divisibilidad de los factores, el teorema de Wilson, afirma que ${displaystyle (n-1)!+1}$ es divisible por $n$ si $n$ es un número primo. Para cualquier entero $x$ , la función Kempner de $x$ es dado por el más pequeño $n$ para la cual $x$ divideciones $n!$ . Para casi todos los números (todos pero un subconjunto de excepciones con densidad asintotica cero), coincide con el factor principal más grande de $x$ .

El producto de dos factores, ${displaystyle m!cdot n!}$ , siempre divide ${displaystyle (m+n)!}$ . Hay infinitamente muchos factores que equivalen al producto de otros factores: si $n$ es en sí mismo cualquier producto de factoriales, entonces $n!$ igual que el mismo producto multiplicado por un factorial más, $(n-1)!$ . Los únicos ejemplos conocidos de factores que son productos de otros factores, pero 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!}$ . Seguiría de la conjetura abc que sólo hay muchos ejemplos finitos y no triviales.

El mayor divisor común de los valores de un polinomio primitivo de grado $d$ sobre los enteros divide uniformemente ${displaystyle d!}$ .

Interpolación continua y generalización no entera

La función gamma (hijado una unidad izquierda para coincidir con los factoriales) interpola continuamente los valores factoriales a los no enteros

Valores absolutos de la función gamma compleja, mostrando postes en enteros no positivos

Hay infinitas formas de extender los factoriales a una función continua. El más utilizado de estos utiliza la función gamma, que se puede definir para números reales positivos como la integral

{displaystyle Gamma (z)=int _{0}^{infty }x^{z-1}e^{-x},dx.}

n

{displaystyle n!=Gamma (n+1),}

x

Gamma(x)

{displaystyle Gamma (x-1)}

{displaystyle Gamma (n)=(n-1)Gamma (n-1),}

La misma integral converge más generalmente para cualquier número complejo $z$ cuya parte real es positiva. Puede extenderse 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}}.}

{displaystyle sin pi z}

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 números enteros no positivos. En los números p-ádicos, no es posible interpolar continuamente la función factorial directamente, porque los factoriales de números enteros grandes (un subconjunto denso del $p$ -adics) convergen a cero de acuerdo con la fórmula de Legendre, obligando a cualquier función continua que esté cerca de sus valores a ser 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$ .

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 compensados por uno, la función digamma proporciona una interpolación continua de los números armónicos compensados por la constante de Euler-Mascheroni.

Cálculo

TI SR-50A, una calculadora de 1975 con una clave factorial (tercera fila, centro derecho)

La función factorial es una característica común en las calculadoras científicas. También se incluye en bibliotecas de programación científica como el módulo de funciones matemáticas Python y la biblioteca Boost C++. Si la eficiencia no es una preocupación, los factoriales de computación es trivial: simplemente multiplicar sucesivamente una variable inicializada a $1$ por los enteros arriba a $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.

La computación de $n!$ se puede expresar en pseudocódigo usando iteración como

definir factorial(n):
 f:= 1
para i:= 1, 2, 3,..., n:
 f:= f × iretorno f

o usar la recursión basada en su relación de recurrencia como

definir factorial(n):
si n = 0 retorno 1
retorno n × factorial(n −1)

Otros métodos adecuados para su cálculo son la memoización, la programación dinámica y la programación funcional. La complejidad computacional de estos algoritmos se puede analizar utilizando el modelo de máquina de acceso aleatorio de costo unitario de computación, en el que cada operación aritmética toma tiempo constante y cada número utiliza una cantidad constante de espacio de almacenamiento. En este modelo, estos métodos pueden calcular $n!$ en el tiempo $O(n)$ , y la versión iterativa utiliza el espacio $O(1)$ . A menos que se optimice para la repetición de cola, la versión recursiva toma espacio lineal para almacenar su pila de llamadas. Sin embargo, este modelo de computación sólo es adecuado cuando $n$ es lo suficientemente pequeño para permitir $n!$ para encajar en una palabra de máquina. ¡Los valores 12 y 20! son los factoriales más grandes que se pueden almacenar en, respectivamente, los enteros de 32 bits y 64 bits. El punto de inundación puede representar factoriales más grandes, pero aproximadamente en lugar de exactamente, y seguirá desbordando los factores más grandes que los factores ${displaystyle 170!}$ .

La computación exacta de factores más grandes implica aritmética de precisión arbitraria, debido al rápido crecimiento y el flujo entero. El tiempo de cálculo se puede analizar como función del número de dígitos o bits en el resultado. Por la fórmula de Stirling, $n!$ tiene ${displaystyle b=O(nlog n)}$ bits. El algoritmo Schönhage-Strassen puede producir un $b$ -bit producto en el tiempo ${displaystyle O(blog blog log b)}$ , y algoritmos de multiplicación más rápido tomando tiempo ${displaystyle O(blog b)}$ son conocidos. Sin embargo, computar el factorial implica productos repetidos, en lugar de una sola multiplicación, por lo que estos plazos no se aplican directamente. En este entorno, computación $n!$ multiplicando los números de 1 a $n$ en secuencia es ineficiente, porque implica $n$ multiplicaciones, una fracción constante de las cuales toma tiempo ${displaystyle O(nlog ^{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 división y conquista que multiplica una secuencia de $i$ números dividiéndolo en dos subsecuencias $i/2$ números, multiplica cada subsequencia, y combina los resultados con una última multiplicación. Este enfoque del factorial lleva tiempo total ${displaystyle O(nlog ^{3}n)}$ : un logaritmo viene del número de bits en el factorial, un segundo viene del algoritmo de multiplicación, y un tercio viene de la división y conquista.

Aún mejor eficiencia se obtiene por computación $n!$ de su factorización principal, basado en el principio de que la exponencia por el escuadrón es más rápida que la expansión de un exponente en un producto. Un algoritmo para esto por Arnold Schönhage comienza por encontrar la lista de los primos arriba a $n$ , por ejemplo usando el tamiz de Eratosthenes, y utiliza la fórmula de Legendre para calcular el exponente para cada primo. Luego computa el producto de los primeros poderes con estos exponentes, utilizando un algoritmo recurrente, como sigue:

Usar la división y conquistar para calcular el producto de los primos cuyos exponentes son extraños
Divide a todos los exponentes por dos (redondeando a un entero), computa recursivamente el producto de los primeros poderes con estos exponentes más pequeños, y cuadrado el resultado
Multiply together the results of the two previous steps

El producto de todos los primos hasta $n$ es un $O(n)$ -bit número, por el número principal teorema, así que el tiempo para el primer paso es ${displaystyle O(nlog ^{2}n)}$ , con un logaritmo proveniente de la división y conquista y otro proveniente del algoritmo de multiplicación. En las llamadas recursivas al algoritmo, el teorema de números primos puede ser nuevamente invocado para demostrar que los números de bits en los productos correspondientes disminuyen 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 agrega en una serie geométrica a ${displaystyle O(nlog ^{2}n)}$ . El tiempo para el balanceo en el segundo paso y la multiplicación en el tercer paso son otra vez ${displaystyle O(nlog ^{2}n)}$ , porque cada uno es una sola multiplicación de un número con $O(nlog n)$ bits. De nuevo, en cada nivel de recursión los números involucrados tienen una fracción constante como muchos bits (porque de lo contrario repetidamente squaring ellos produciría un resultado final demasiado grande) así que de nuevo las cantidades de tiempo para estos pasos en las llamadas recursivas añadir en una serie geométrica a ${displaystyle O(nlog ^{2}n)}$ . Por consiguiente, todo el algoritmo toma tiempo ${displaystyle O(nlog ^{2}n)}$ , proporcional a una sola multiplicación con el mismo número de bits en su resultado.

Secuencias y funciones relacionadas

Varias otras secuencias de enteros son similares o están relacionadas con los factoriales:

Factores alternativos: El factorial alternante es el valor absoluto de la suma alternada de la primera $n$ factoriales, ${textstyle sum _{i=1}^{n}(-1)^{n-i}i!}$ . Estos han sido estudiados principalmente en relación con su primalidad; sólo finitamente muchos de ellos pueden ser primos, pero no se conoce una lista completa de primos de esta forma.
Factorial de Bhargava: Los factoriales Bhargava son una familia de secuencias enteros definidas por Manjul Bhargava con propiedades numera-teoréticas similares a los factoriales, incluyendo los propios factoriales como un caso especial.
Doble factorial: El producto de todos los números extraños hasta algunos positivos extraños entero $n$ se llama doble factorial de $n$ , y denotado por $n!!$ . Eso es, ${displaystyle (2k-1)!!=prod _{i=1}^{k}(2i-1)={frac {(2k)!}{2^{k}k!}}.}$ Por ejemplo, 9! = 1 × 3 × 7 × 9 = 945. Los factoriales dobles se utilizan en integrales trigonométricos, en expresiones para la función gamma a medio-integers y los volúmenes de hiperesféricas, y en contar árboles binarios y combinaciones perfectas.
Factorial exponencial: Así como los números triangulares resumen los números de $1$ a $n$ , y los factores toman su producto, los exponenciados factoriales exponenciales. El factorial exponencial se define recursivamente como ${displaystyle a_{0}=1, a_{n}=n^{a_{n-1}}}$ . Por ejemplo, el factorial exponencial de 4 es ${displaystyle 4^{3^{2^{1}}}=262144.}$ Estos números crecen mucho más rápido que los factoriales regulares.
Falling factorial: Las notaciones $(x)_{n}$ o $x^{{underline n}}$ a veces se utilizan para representar el producto del $n$ enteros contando hasta y incluido $x$ , iguales ${displaystyle x!/(x-n)!}$ . Esto también se conoce como factorial de caída o factorial atrasado, y el $(x)_{n}$ notación es un símbolo Pochhammer. Los factores de caída cuentan el número de secuencias diferentes de $n$ elementos distintos que pueden extraerse de un universo $x$ artículos. Se presentan como coeficientes en los derivados superiores de los polinomios, y en los momentos factoriales de variables aleatorias.
Hiperfactoriales: El hiperfactorial de $n$ es el producto ${displaystyle 1^{1}cdot 2^{2}cdots n^{n}}$ . Estos números forman los discriminantes de los polinomios hermitas. Pueden ser interpolados continuamente por la función K, y obedecer análogos a la fórmula de Stirling y el teorema de Wilson.
Jordania–Pólya números: Los números Jordan-Pólya son los productos de factoriales, permitiendo repeticiones. Cada árbol tiene un grupo de simetría cuyo número de simetrías es un número Jordan–Pólya, y cada número Jordan–Pólya cuenta las simetrías de algún árbol.
Primorial: El primorial ${displaystyle n#}$ es el producto de números primos menos o igual a $n$ ; esta construcción les da algunas propiedades de divisibilidad similares a los factoriales, pero a diferencia de los factores son libres de cuadrados. Como con los principios factoriales ${displaystyle n!pm 1}$ , investigadores han estudiado primos de primera calidad ${displaystyle n#pm 1}$ .
Subfactorial: El subfactorial produce el número de despidos de un conjunto de $n$ objetos. A veces se denota. $!n$ , e igual al entero más cercano a $n!/e$ .
Superfactorial: El superfactorial de $n$ es el producto de la primera $n$ factoriales. Los superfactoriales son continuamente interpolados por la función Barnes G.

Contenido relacionado

Más resultados...