Factoriales divisibles

Recientemente, estaba completamente desconcertado por este tweet de Farm Library:


"Eso es lo que sucede si no multiplicas sino que divides en factorial".

Cuando lo vi, tuve que renunciar a mi negocio, tomar un cuaderno y verificar la fórmula. El resultado preliminar parecía lógico. Desde la versión multiplicativa $$$n!$ con el aumento $$$n$ tiende al infinito, entonces la versión "divisoria" debería tender a cero. Y $$$\ frac {n ^ 2} {n!}$ se comporta de esa manera; función polinómica $$$n ^ 2$ crece más lento que una función de potencia $$$n!$ para lo suficientemente grande $$$n$ :

$$

$$\ frac {1} {1}, \ frac {4} {2}, \ frac {9} {6}, \ frac {16} {24}, \ frac {25} {120}, \ frac {36 } {720}, \ frac {49} {5040}, \ frac {64} {40320}, \ frac {81} {362880}, \ frac {100} {3628800}$$

Pero, ¿por qué el resultado de la división toma la forma? $$$\ frac {n ^ 2} {n!}$ ? De donde viene $$$n ^ 2$ ?

Para responder a esta pregunta, tuve que desmantelar el viejo trauma asociado con el estudio de la división fraccional, pero hice frente al dolor. Pasando de la fórmula del tweet de izquierda a derecha, primero obtenemos $$$\ frac {n} {n-1}$ . Luego, dividiendo este valor por $$$n-2$ tenemos

$$

$$\ cfrac {\ frac {n} {n-1}} {n-2} = \ frac {n} {(n-1) (n-2)}$$

Continuando de esta manera, terminamos con:

$$

$$n \ mathbin {/} (n-1) \ mathbin {/} (n-2) \ mathbin {/} (n-3) \ mathbin {/} \ cdots \ mathbin {/} 1 = \ frac {n } {(n-1) (n-2) (n-3) \ cdots 1} = \ frac {n} {(n-1)!}$$

Para obtener el resultado que se muestra en el tweet $$$\ frac {n ^ 2} {n!}$ , simplemente multiplicamos el numerador y el denominador por $$$n$ . (Aunque para mi gusto, la expresión $$$\ frac {n} {(n-1)!}$ más claro)

---

Soy un fanático factorial oficialmente reconocido. Mantenga sus secuencias de Fibonacci con usted; Aquí está mi característica favorita. Cada vez que aprendo un nuevo lenguaje de programación, mi primer ejercicio es escribir varios procedimientos para calcular factoriales. Con los años, he encontrado varias variaciones de este tema, por ejemplo, un reemplazo en la definición $$$\ veces$ en $$$+$ (que nos da números triangulares). Pero parece que nunca pensé en reemplazar antes $$$\ veces$ en $$$\ mathbin {/}$ . Resulta extraño Como la multiplicación es conmutativa y asociativa, podemos definir $$$n!$ tal como el producto de todos los enteros de $$$1$ antes $$$n$ sin preocuparse por el orden de las operaciones. Pero al dividir, el orden no puede ser ignorado. En el caso general $$$x \ mathbin {/} y \ ne y \ mathbin {/} x$ y $$$(x \ mathbin {/} y) \ mathbin {/} z \ ne x \ mathbin {/} (y \ mathbin {/} z)$ .

En el tweet de Farm Library, los divisores están en orden descendente: $$$n, n-1, n-2, \ ldots, 1$ . Obviamente, esto será reemplazado por un orden ascendente: $$$1, 2, 3, \ ldots, n$ . ¿Qué sucede si definimos el factorial de división como $$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n$ ? Otro retorno al algoritmo de división fraccional de la escuela nos da una respuesta simple:

$$

$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n = \ frac {1} {2 \ times 3 \ times 4 \ times \ cdots \ times n} = \ frac {1} {n!}$$

En otras palabras, cuando hacemos divisiones muchas veces, contamos $$$1$ antes $$$n$ , el resultado final será igual al recíproco $$$n!$ . (Me gustaría poner un signo de exclamación al final de esta oración, pero ¡ay!) Si está buscando una respuesta canónica a la pregunta "¿Qué obtenemos al dividir en lugar de multiplicar en $$$n!$ ? ", Entonces yo diría que $$$\ frac {1} {n!}$ Es un mejor candidato que $$$\ frac {n} {(n - 1)!}$ . ¿Por qué no aceptamos la simetría entre $$$n!$ y su valor inverso?

Por supuesto, hay muchas otras formas de colocar n valores enteros en el conjunto $$$\ {1 \ ldots n \}$ . ¿Pero cuánto exactamente? Al final resultó que, exactamente $$$n!$ ! Por lo tanto, puede parecer que hay $$$n!$ formas únicas de definir una función de división $$$n!$ . Sin embargo, estudiar las respuestas de las dos permutaciones mostradas arriba nos hace comprender que aquí funciona un patrón más simple. Cualquier elemento de la secuencia aparece primero, aparece en el numerador de una fracción grande, y el producto de todos los demás elementos es el denominador. Por lo tanto, al final, solo hay $$$n$ resultados diferentes (suponiendo que siempre realicemos operaciones de división estrictamente de izquierda a derecha). Para cualquier entero $$$k$ en el rango de $$$1$ antes $$$n$ estableciendo $$$k$ al comienzo de la línea, creamos una división $$$n!$ igual a $$$k$ dividido por todos los demás factores. Puede escribir esto de la siguiente manera:

$$

$$\ cfrac {k} {\ frac {n!} {k}}, \ text {que se puede convertir a} \ frac {k ^ 2} {n!}$$

Y así resolvimos un pequeño acertijo sobre cómo en este tweet $$$\ frac {n} {(n-1)!}$ convertido en $$$\ frac {n ^ 2} {n!}$ .
Vale la pena señalar que todas estas funciones convergen a cero cuando $$$n$ hasta el infinito Desde un punto de vista asintótico, $$$\ frac {1 ^ 2} {n!}, \ frac {2 ^ 2} {n!}, \ ldots, \ frac {n ^ 2} {n!}$ idéntico

---

Si! Misión cumplida El problema está resuelto. El trabajo esta hecho. Ahora sabemos todo lo que necesitamos para dividir factoriales, ¿verdad?

Bueno, tal vez hay una pregunta más. ¿Qué dirá la computadora? Si tomamos nuestro algoritmo factorial favorito y hacemos lo que se propone en un tweet, reemplazamos todas las ocurrencias del operador $$$\ veces$ (o * ) en / , ¿qué pasará? Cual de $$$n$ opciones de división $$$n!$ nos dará el programa?

Aquí está mi algoritmo favorito para calcular factoriales como programa en Julia :

 function mul!(n) if n == 1 return 1 else return n * mul!(n - 1) end end 

Este algoritmo introdujo generaciones enteras de nerds al concepto de recursión. En forma de texto, se lee: si $$$n$ es igual $$$1$ entonces $$$mul! (n)$ es igual $$$1$ . De lo contrario, debe calcular la función $$$mul! (n-1)$ y luego multiplica el resultado por $$$n$ .

_{Puede preguntar qué sucede si} $$_{$n$ será cero o negativo Puedes preguntar, pero es mejor no hacerlo. Para nuestros objetivos actuales} $$_{$n \ in \ mathbb {N}$ .}

Comenzando con cualquier positivo $$$n$ , la secuencia de llamadas recursivas tarde o temprano caerá a $$$n = 1$ .

Una función se puede escribir de manera más sucinta utilizando el estilo de definición de Julia de una sola línea:

 mul!(n) = n == 1 ? 1 : n * mul!(n - 1) 

¿Es la parte derecha del operador de asignación una expresión condicional o un operador ternario de la forma a ? b : c a ? b : c . Aquí a es la condición booleana de la prueba, que debería devolver true o false . Si a es true , entonces b evalúa la expresión b , y el resultado se convierte en el valor de toda la expresión. De lo contrario, c calcula c .

Solo para asegurarme de que hice todo bien, aquí están los primeros 10 factores calculados por este programa:

 [mul!(n) for n in 1:10] 10-element Array{Int64,1}: 1 2 6 24 120 720 5040 40320 362880 3628800 

Ahora, cambiemos esta definición y transformemos la única aparición * en / , dejando todo lo demás sin cambios (excepto el nombre de la función).

 div!(n) = n == 1 ? 1 : n / div!(n - 1) 

Y esto es lo que devolverá el programa si lo ejecutamos para los valores $$$n$ de $$$1$ antes $$$20$ :

 [div!(n) for n in 1:20] 20-element Array{Real,1}: 1 2.0 1.5 2.6666666666666665 1.875 3.2 2.1875 3.657142857142857 2.4609375 4.063492063492063 2.70703125 4.432900432900433 2.9326171875 4.773892773892774 3.14208984375 5.092152292152292 3.338470458984375 5.391690662278897 3.523941040039063 5.675463855030418 

Que? Definitivamente no es como converger a cero, como $$$\ frac {1} {n!}$ o $$$\ frac {n} {n - 1}$ . De hecho, los valores no se ven así, porque no van a converger. A juzgar por el siguiente gráfico, la secuencia consta de dos componentes intermitentes, cada uno de los cuales parece crecer lentamente hacia el infinito, y también se desvía del otro.


¡Entendiendo lo que estamos observando aquí, será útil cambiar el tipo de salida de la función div! . En lugar de usar el operador de división / , que devuelve el valor como un número de coma flotante, podemos reemplazarlo con el operador // , que devuelve el valor racional exacto, redondeado al término más bajo.

 div!(n) = n == 1 ? 1 : n // div!(n - 1) 

Aquí hay una secuencia de valores para n 1:20 :

 20-element Array{Real,1}: 1 2//1 3//2 8//3 15//8 16//5 35//16 128//35 315//128 256//63 693//256 1024//231 3003//1024 2048//429 6435//2048 32768//6435 109395//32768 65536//12155 230945//65536 262144//46189 

La lista está llena de patrones interesantes. Esta es una doble hélice en la que los números pares e impares en zigzags se mueven en hilos complementarios. Los números pares no son solo pares, son todos grados $$$2$ . Además, aparecen en pares, primero en el numerador, luego en el denominador, y su secuencia no es decreciente. Pero hay lagunas; no todos los grados están presentes $$$2$ . El hilo extraño se ve aún más complejo, diferentes coeficientes simples pequeños aparecen y desaparecen en los números. (Los números primos deben ser pequeños, al menos menos $$$n$ .)

Este resultado me sorprendió. Esperaba ver una secuencia mucho más suave, como las que calculé en papel. Todos estos saltos rotos no tenían sentido. La tendencia general hacia un crecimiento ilimitado en la relación tampoco tenía sentido. ¿Cómo podemos dividir constantemente, mientras recibimos todos los números cada vez más grandes?

En este punto, puede pausar la lectura e intentar desarrollar su propia teoría sobre el origen de estos números en zigzag. Si necesita una pista, entonces la tiene, y una muy fuerte, casi un spoiler: busque una secuencia de numeradores o una secuencia de denominadores en la Enciclopedia en línea de secuencias enteras .

---

Aquí hay otra pista. Un pequeño cambio en el programa div! Convierte completamente la salida. Simplemente cambie la última expresión reemplazando n // div!(n - 1) con div!(n - 1) // n .

 div!(n) = n == 1 ? 1 : div!(n - 1) // n 

Ahora los resultados se ven así:

 10-element Array{Real,1}: 1 1//2 1//6 1//24 1//120 1//720 1//5040 1//40320 1//362880 1//3628800 

Esta es la función inversa del factorial que ya hemos visto, una serie de valores generados al ir de izquierda a derecha en una secuencia creciente de divisores $$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n$ .

No es sorprendente que cambiar la última expresión en un procedimiento cambie el resultado. Al final, sabemos que la división no es conmutativa ni asociativa. Pero es difícil entender por qué la secuencia de valores generados por el programa original da una forma de zigzag tan extraña. ¿Qué mecanismo da lugar a tales potencias pares de dos y valores pares e impares alternos?

Descubrí que explicar lo que está sucediendo en una secuencia en zigzag es más fácil en una versión iterativa del procedimiento, en lugar de una recursiva. (Esta afirmación puede parecer molesta para aquellos que encuentran las definiciones recursivas más simples, pero simplemente sucedió). Así es como se ve el programa:

 function div!_iter(n) q = 1 for i in 1:n q = i // q end return q end 

Declaro que este procedimiento con un ciclo funcional es idéntico a una función recursiva, en el sentido de que si div!(n) y div!_iter(n) devuelven un resultado para algún entero positivo n , entonces siempre será el mismo. Aquí está mi prueba:

 [div!(n) for n in 1:20] [div!_iter(n) for n in 1:20] 1 1//1 2//1 2//1 3//2 3//2 8//3 8//3 15//8 15//8 16//5 16//5 35//16 35//16 128//35 128//35 315//128 315//128 256//63 256//63 693//256 693//256 1024//231 1024//231 3003//1024 3003//1024 2048//429 2048//429 6435//2048 6435//2048 32768//6435 32768//6435 109395//32768 109395//32768 65536//12155 65536//12155 230945//65536 230945//65536 262144//46189 262144//46189 

Para comprender el proceso que genera estos números, considere los valores secuenciales de las variables. $$$i$ y $$$q$ cada vez que corres un bucle. Originalmente $$$i$ y $$$q$ son iguales $$$1$ ; por lo tanto, después del primer paso del ciclo, la expresión q = i // q da $$$q$ valor $$$\ frac {1} {1}$ . Entonces $$$i = 2$ y $$$q = \ frac {1} {1}$ es decir, un nuevo significado $$$q$ es igual $$$\ frac {2} {1}$ . En la tercera iteración $$$i = 3$ y $$$q = \ frac {2} {1}$ eso nos da $$$\ frac {i} {q} \ rightarrow \ frac {3} {2}$ . Si esto sigue siendo confuso, entonces imagina $$$\ frac {i} {q}$ como $$$i \ times \ frac {1} {q}$ . Una observación importante aquí es que con cada ciclo de bucle $$$q$ obtiene el valor opuesto, convirtiéndose $$$\ frac {1} {q}$ .

Si expande estas operaciones y observa las multiplicaciones y divisiones incluidas en cada elemento de la serie, entonces surge un patrón:

$$

$$\ frac {1} {1}, \ quad \ frac {2} {1}, \ quad \ frac {1 \ cdot 3} {2}, \ quad \ frac {2 \ cdot 4} {1 \ cdot 3 }, \ quad \ frac {1 \ cdot 3 \ cdot 5} {2 \ cdot 4} \ quad \ frac {2 \ cdot 4 \ cdot 6} {1 \ cdot 3 \ cdot 5}$$

En forma general:

$$

$$\ frac {1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot n} {2 \ cdot 4 \ cdot \ cdots \ cdot (n-1)} \ quad (\ text {impar} n) \ qquad \ frac {2 \ cdot 4 \ cdot 6 \ cdot \ cdots \ cdot n} {1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot (n-1)} \ quad (\ text {even} n)$$

---

Las funciones $$$1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot n$ por extraño $$$n$ y $$$2 \ cdot 4 \ cdot 6 \ cdot \ cdots \ cdot n$ para incluso $$$n$ tienen su propio nombre! Se llaman factoriales dobles y se escriben como $$$n !!$ .

_{Terminología horrible, ¿verdad? Sería mejor si se llamaran "semifactoriales". Y si no lo supiera, leería} $$_{$n !!$ como factorial factorial.}

El factorial doble n se define como el producto de ny todos los enteros positivos más pequeños de la misma paridad. Entonces nuestra curiosa secuencia de valores en zigzag es solo $$$\ frac {n !!} {(n-1) !!}$ .

Un artículo de 2012 de Henry W. Gould y Jocelyn Quentens (por desgracia, detrás de paywall) explora el uso de factoriales dobles. Son mucho más comunes de lo que piensas. A mediados del siglo XVII, John Wallis obtuvo la siguiente identidad:

$$

$$\ frac {\ pi} {2} = \ frac {2 \ cdot 2 \ cdot 4 \ cdot 4 \ cdot 6 \ cdot 6 \ cdots} {1 \ cdot 3 \ cdot 3 \ cdot 5 \ cdot 5 \ cdot 7 \ cdots} = \ lim_ {n \ rightarrow \ infty} \ frac {((2n) !!) ^ 2} {(2n + 1) !! (2n - 1) !!}$$

Una serie aún más extraña que involucra un cubo de valores factoriales dobles se resume en $$$\ frac {2} {\ pi}$ . Fue descubierto por nada menos que Srinivasa Ramanujan.

Gould y Kientens también consideraron el doble factorial equivalente para los coeficientes binomiales. El coeficiente binomial estándar se define como:

$$

$$\ binom {n} {k} = \ frac {n!} {k! (n-k)!}$$

La versión dual se ve así:

$$

$$\ left (\! \ binom {n} {k} \! \ right) = \ frac {n !!} {k !! (n-k) !!}$$

Tenga en cuenta que nuestros números en zigzag corresponden a esta descripción y, por lo tanto, pueden considerarse coeficientes binomiales de factoriales dobles. Más específicamente, son tales números:

$$

$$\ left (\! \ binom {n} {1} \! \ right) = \ left (\! \ binom {n} {n - 1} \! \ right) = \ frac {n !!} {1 !! (n-1) !!}$$

Frijol $$$\ binom {n} {1}$ no muy interesante; el es igual $$$n$ . Pero la doble versión $$$\ left (\! \ binom {n} {1} \! \ right)$ como vimos, un baile más animado es el baile. Y a diferencia del binomio habitual, no siempre es entero. (Los únicos valores enteros son $$$1$ y $$$2$ .)

Una mirada a los números en zigzag como cociente de factoriales dobles explica algunas de sus propiedades, comenzando con valores alternos pares e impares. También podemos ver por qué todos los números pares en la secuencia son potencias de 2. Considere el ejemplo con $$$n = 6$ . El numerador de esta fracción es $$$2 \ cdot 4 \ cdot 6 = 48$ recibiendo de $$$6$ multiplicador $$$3$ . Pero el denominador es $$$1 \ cdot 3 \ cdot 5 = $ 1$ . Los trillizos arriba y abajo se encogen, dejándonos $$$\ frac {16} {5}$ . Dichas reducciones ocurren en cada caso. Cada vez que aparece un factor impar en la secuencia de números pares $$$m$ necesariamente tiene la forma $$$2 \ cdot m$ pero en este momento $$$m$ ya debería aparecer en una secuencia de números impares.

---

Es una secuencia de números en zigzag una respuesta razonable a la pregunta: "¿Qué sucede si dividimos, en lugar de multiplicar en $$$n!$ ? " ¿O el programa de computadora que los generó resultó ser un algoritmo erróneo? En mi opinión personal, $$$\ frac {1} {n!}$ - una respuesta más intuitiva, pero $$$\ frac {n !!} {(n - 1) !!}$ Más interesante.

Además, la existencia misma de una secuencia en zigzag amplía nuestros horizontes. Como se indicó anteriormente, si insiste en que el algoritmo de división siempre debe ir en orden a través de la lista de numeradores $$$n$ , en cada paso dividiendo el número de la izquierda por el número de la derecha, hay un total $$$n$ posibles resultados, y todos se ven muy similares. Pero la solución en zigzag ofrece posibilidades mucho más amplias. Podemos formular el problema de la siguiente manera: tomar el conjunto de numeradores $$$\ {1 \ puntos n \}$ , elija su subconjunto e invierta todos los elementos de este subconjunto; Ahora multiplicamos todos los numeradores, tanto inversos como directos. Si el subconjunto invertido está vacío, el resultado será un factorial regular $$$n!$ . Si todos los numeradores se han vuelto inversos a sus valores, entonces obtenemos lo contrario $$$\ frac {1} {n!}$ . Y si cada segundo numerador se convierte, comenzando con $$$n - 1$ , entonces el resultado será un elemento de una secuencia en zigzag.

Estas son solo algunas de las muchas opciones disponibles; en total hay $$$2 ^ n$ subconjuntos de $$$n$ elementos Por ejemplo, puede tomar el inverso de cada número que es primo o una potencia prima $$$(2, 3, 4, 5, 7, 8, 9, 11, \ puntos)$ . En pequeño $$$n$ los resultados están saltando, pero permanecen constantemente por debajo de $$$1$ :


Sin embargo, si continué este cuadro por más $$$n$ despegaría hacia la estratosfera. Los grados de primos se vuelven muy escasos en la recta numérica.

---

Ahora haré una pregunta. Vimos variaciones factoriales cercanas a cero como $$$n$ hasta el infinito por ejemplo $$$1 / n!$ . Hemos visto crecer otras variaciones con el aumento $$$n$ ilimitado, incluyéndome a mí $$$n!$ y números en zigzag. ¿Hay alguna variedad del proceso factorial que converja en algún límite finito que no sea cero?

En primer lugar, se me ocurrió el siguiente algoritmo:

 function greedy_balance(n) q = 1 while n > 0 q = q > 1 ? q /= n : q *= n n -= 1 end return q end 

Recorremos los valores enteros de $$$n$ abajo a $$$1$ calcular el producto / cociente actual en el proceso $$$q$ . En cada paso, si el valor actual $$$q$ mas $$$1$ , lo dividimos por el siguiente numerador, de lo contrario, realizamos la multiplicación. Este esquema implementa algún tipo de gestión de retroalimentación o comportamiento de búsqueda de destino. Si $$$q$ creciendo demasiado, lo reducimos; si es demasiado pequeño, lo aumentamos. Sugerí que mientras luchaba $$$n$ hasta el infinito $$$q$ convergerá a un rango de valores constantemente estrecho al lado de $$$1$ .

Pero el experimento me arrojó otra sorpresa:


Tal onda de diente de sierra no es exactamente lo que esperaba. Curiosamente, la curva no es simétrica $$$1$ ; Las desviaciones de arriba tienen una amplitud mayor que las de abajo. Pero esta distorsión es más visual que matemática. Desde $$$q$ es privado, distancia de $$$1$ antes $$$10$ igual que la distancia desde $$$1$ antes $$$\ frac {1} {10}$ pero en una escala lineal no se ve así. Puede solucionar esto compilando un gráfico logarítmico del cociente:


Ahora el gráfico es simétrico, o al menos aproximadamente el mismo, y está centrado en relación con el valor. $$$0$ cual es el logaritmo $$$1$ . Pero queda un secreto más serio. La onda de diente de sierra es muy regular y tiene un período $$$4$ , sin mostrar signos de compresión en la dirección del valor límite esperado $$$\ log q = 0$ . Los valores numéricos sugieren que cuando $$$n$ hasta el infinito, los picos de la curva convergen a un valor ligeramente más alto $$$q = \ frac {5} {3}$ , y los mínimos se acercan a un valor ligeramente inferior $$$q = \ frac {3} {5}$ . (Logaritmos de base correspondientes $$$10$ son aproximadamente iguales $$$\ pm0.222$ ) No pude entender por qué sucede esto. Quizás alguien pueda explicarlo.

El fracaso con este algoritmo codicioso no significa que no podamos dividir la convergencia factorial a $$$q = 1$ .

_{Si trabajamos con los logaritmos de numeradores, entonces este procedimiento se convierte en el caso de un problema computacional bien conocido llamado "problema de dividir un conjunto de números". Se nos dan muchos números reales, y debemos dividirlos en dos conjuntos, cuya suma es igual o lo más cercana posible a la igualdad. Esta es una tarea probadamente difícil, pero también se llama ( PDF ) "la tarea compleja más simple".}

Para cualquier $$$n$ podemos encontrar que al usar los valores inversos de algún otro subconjunto de numeradores nos da una mejor aproximación a $$$n! = 1$ . Para pequeños $$$n$ podemos resolver este problema por la fuerza bruta: solo considera todo $$$2 ^ n$ subconjuntos y elegir el mejor.

Calculé las particiones óptimas hasta $$$n = 30$ cuando necesita elegir entre mil millones de opciones.


Obviamente, el gráfico se está volviendo más plano. Puede usar el mismo método para forzar la convergencia a cualquier otro valor en el rango de $$$0$ antes $$$n!$ .

Y así, recibimos otra respuesta a la pregunta planteada por un tweet y comenzamos nuestro viaje. ¿Qué sucede si dividimos y no multiplicamos en $$$n!$ ? Cualquier cosa que queramos.