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  f r a c 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 :

 frac11, frac42, frac96, frac1624, frac25120, frac36720, frac495040, frac6440320, frac81362880, frac1003628800


Pero, 驴por qu茅 el resultado de la divisi贸n toma la forma?  fracn2n! ? De donde viene n2 ?

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  fracnn1 . Luego, dividiendo este valor por n2 tenemos

 cfrac fracnn1n2= fracn(n1)(n2)


Continuando de esta manera, terminamos con:

n mathbin/(n1) mathbin/(n2) mathbin/(n3) mathbin/ cdots mathbin/1= fracn(n1)(n2)(n3) cdots1= fracn(n1)!


Para obtener el resultado que se muestra en el tweet  fracn2n! , simplemente multiplicamos el numerador y el denominador por n . (Aunque para mi gusto, la expresi贸n  fracn(n1)! 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 ney mathbin/x y (x mathbin/y) mathbin/z nex mathbin/(y mathbin/z) .

En el tweet de Farm Library, los divisores est谩n en orden descendente: n,n1,n2, 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= frac12 times3 times4 ti m e s c d o t s t i m e s n   = f r a c 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  f r a c 1 n ! Es un mejor candidato que  f r a c 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:

 cfrack fracn!k, textquesepuedeconvertira frack2n!


Y as铆 resolvimos un peque帽o acertijo sobre c贸mo en este tweet  fracn(n1)! convertido en  fracn2n! .
Vale la pena se帽alar que todas estas funciones convergen a cero cuando n hasta el infinito Desde un punto de vista asint贸tico,  frac12n!, frac22n!, ldots, fracn2n! 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!(n1) 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 mathbbN .

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  frac1n! o  fracnn1 . 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  frac11 . Entonces i=2 y q= frac11 es decir, un nuevo significado q es igual  frac21 . En la tercera iteraci贸n i=3 y q= frac21 eso nos da  fraciq rightarrow frac32 . Si esto sigue siendo confuso, entonces imagina  fraciq como i times frac1q . Una observaci贸n importante aqu铆 es que con cada ciclo de bucle q obtiene el valor opuesto, convirti茅ndose  frac1q .

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

 frac11, quad frac21, quad frac1 cdot32, quad frac2 cdot41 cdot3, quad frac1 cdot3 cdot52 cdot4 quad frac2 cdot4 cdot61 cdot3 cdot5



En forma general:

 frac1 cdot3 cdot5 cdot cdots cdotn2 cdot4 cdot cdots cdot(n1) quad( textimparn) qquad frac2 cdot4 cdot6 cdot cdots cdotn1 cdot3 cdot5 cdot cdots cdot(n1) quad( textevenn)




Las funciones 1 cdot3 cdot5 cdot cdots cdotn por extra帽o n y 2 cdot4 cdot6 cdot cdots cdotn 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  fracn!!(n1)!! .

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 pi2= frac2 cdot2 cdot4 cdot4 cdot6 cdot6 cdots1 cdot3 cdot3 cdot5 cdot5 cdot7 cdots= limn rightarrow infty frac((2n)!!)2(2n+1)!!(2n1)!!


Una serie a煤n m谩s extra帽a que involucra un cubo de valores factoriales dobles se resume en  frac2 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:

 binomnk= fracn!k!(nk)!


La versi贸n dual se ve as铆:

 left( binomnk right)= fracn!!k!!(nk)!!


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( binomn1 right)= left( binomnn1 right)= fracn!!1!!(n1)!!


Frijol  binomn1 no muy interesante; el es igual n . Pero la doble versi贸n  left( binomn1 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 cdot4 cdot6=48 recibiendo de 6 multiplicador 3 . Pero el denominador es 1 cdot3 cdot5=$1 . Los trillizos arriba y abajo se encogen, dej谩ndonos  frac165 . 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 cdotm 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,  frac1n! - una respuesta m谩s intuitiva, pero  fracn!!(n1)!! 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  frac1n! . Y si cada segundo numerador se convierte, comenzando con n1 , entonces el resultado ser谩 un elemento de una secuencia en zigzag.

Estas son solo algunas de las muchas opciones disponibles; en total hay 2n 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  frac110 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  logq=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= frac53 , y los m铆nimos se acercan a un valor ligeramente inferior q= frac35 . (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 2n 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.

Source: https://habr.com/ru/post/440512/


All Articles