No sé como aplicar esta ecuación de concurrencia sin calcular todos los valores a mano para n=100. El problema que tiene es que los coeficientes no son constantes.
Permutaciones de objetos con largo menor o igual a r
Número de respuestas: 6
En respuesta a Gaston Daniel Barreto Sugliani
Re: Permutaciones de objetos con largo menor o igual a r
de Alfredo Viola -
Disculpá la demora en responder. He estado con mucho trabajo aquí, pero muy productivo al menos.
La idea es que uses un sistema somputacional como SAGE (que está libre en internet) para hacer una función que te compute la recurrencia. Tenés que usar luego el comando evalf para sacar el valor en punto flotante en vez de tener una fracción. Por ejemplo, en Maple tenés la función que computa la recurrencia escrita de la manera que puse al final. Si luego haces ala (100, 50) tenés el valor que tú querés. El "option remember" es para evitar un algoritmo exponencial, porque sino tiene que repetir recursivamente los cáculos varias veces. Lo que hace, es almacenar los resultados intermedios (como programación dinámica) y cuando se llama con un valor que ya tiene, en vez de volver a calcularlo, va a la tabla y saca el resultado. Para asimptóticos hay que usar los métodos que si quieren verlo lo haremos en un seminario en el segundo semesre.
En respuesta a Alfredo Viola
Re: Permutaciones de objetos con largo menor o igual a r
de Alfredo Viola -
Algunos detalles a mi respuesta anterior.
Me equivoqué en los casos de borde de la función que te di. Las condiciones son si n<= 0 (es con = y NO estricto) entonces 0 si n=1 entonces 1 sino ..
O sea que el caso de borde 1 es con n=1 y NO con n=0.
Por otro lado, tenés aquí un caso especial que te permite simplificar la recurrencia.
Aquí tienes n par y r = n/2. En nuestro caso n = 100 y r = n/2 = 50.
Entonces precisas: ciclos(2*n,n) con n = 50.
Ahora, creo que es importante que hagas el siguiente ejercicio. Tu sabes que ciclos(n,r) = 1 si n <= r. O sea que si tienes, por ejemplo n = 30, entonces la probabilidad de que todos los ciclos tengan largo <= 30 es 1 (un ciclo no puede tener largo mayor que n).
Ahora, tú querés calcular ciclos(2*n,n). Si divides entre 2n por ambos lados vas a tener que
ciclos(2n,n) - ciclos(2n,n-1) = -ciclos(2n-n-1,n)/2n
Ahora, ciclos(2n-n-1,n) = ciclos(n-1,n) = 1 (por lo que te dije antes).
Entonces te queda una recurrencia telescópica:
ciclos(2n,n) - ciclos(2n,n-1) = -1/2n
Al final tenés podés probar que ciclos(2n,n) = 1+H_{n}-H_{2n} donde H_{i} son los números armónicos.
Más aún, usando la expansión traidicional de los números armónicos usando logaritmos, vas a poder probar que cuando n tiende a infinito:
ciclos(2n,n) es asimptóticamente igual a 1 - log(2) aproximadamente 0.3068528194, o sea que si n es grande, con esta estrategia tenés mas o menos un 30% de éxito.
Creo que es muy bueno que puedas desarrollar todos estos cáculos, y comararlos empíricamente con el programa que hagas. Más aún, si usas la fórmula exacta usando los números armónicos, vas a poder comprobar empíricamente usando el programa que los valores van a ser iguales para cualquier valor ciclos(2n,n) que tú hagas.
Este tipo de ejercicios está pensado para que pienses estas cosas y trates de avanzar más de lo que dice la letra. Es parte de la idea de estos ejercicios, para aprovechar bien los conceptos del curso.
Tuba.
En respuesta a Alfredo Viola
Re: Permutaciones de objetos con largo menor o igual a r
de Alfredo Viola -
Gastón:
Otro detalle. Si te fijas, tenes la expresión con la exponencial, y luego Flajolet da una recurrencia para los coeficientes. Una vez que sabes la recurrencia, no es Smuy difícil de probarla (por ejemplo, por inducción o inspección de coeficientes).
Pero hay un camino más directo.
Los coeficientes b_n^(r) de la foto que me sacaste del libro (página 122 justo antes del ejemplo II.14) son probabilidades.
Dado que la generatriz es exponencial, y que la cantidad de permutaciones es n!, el coeficiente es un número que ya está dividido por n! (fijate que NO pone n! enfrente del [z^n]). Entonces son probabilidades. Entonces si multiplico los coeficientes b_i^(r) por i! me da la cantidad de permutaciones de "i" elementos tal que todos los ciclos que tiene son de largo menor o igual que r.
Si llamamos N_i^(r) = b_i^(r)*i!, ahí tengo número de permutaciones. Si multiplicas a ambos lados por n! y luego haces el cambio de variable que te dije te queda
N_{n+1}^(r) = (n+1)*N_{n}^(r) - n*(n-1)*...*(n-r+1)*N_{n-r}^(r).
Se interpreta así. Todas las permutaciones de n+1 elementos con ciclos de largo menor o igual a r se constuyen a partir de todas las permutaciones de largo n con ciclos de largo menor o igual a r agregando el elemento (n+1). Todo funciona bien, salvo en el caso de que justo este elemento me genere un ciclo de tamaño r+1 (es lo único malo que puede ocurrir: que justo entre en un ciclo de tamaño r y lo agrande a uno de tamaño r+1 y entonces está mal). Así que tengo que quitar este caso.
Este caso pasa cuando tengo un ciclo de tamaño r (tengo n elementos para el primer lugar, (n-1) para el segundo, y así sigo hasta llegar a (n-r+1)). Lo que me queda es una permutación de (n-r) elementos y además todos con ciclos de largo menor o igual a r (pues ya saqué el que me daba problemas).
Y esta es la ecuación. En el mail anterior, te di cómo resolver la recurrencia de manera exacta cuando n=2*r (y en este caso r=50 y n = 100).
Espero que haya ayudado con esto. Avisame si tenés más dudas.
Tuba.
En respuesta a Alfredo Viola
Re: Permutaciones de objetos con largo menor o igual a r
Ahora, tú querés calcular ciclos(2*n,n). Si divides entre 2n por ambos lados
Que ecuacion divido? la de la foto? (n+1)b_(n+1) = (n+1)...?
ciclos(2n,n) - ciclos(2n,n-1) = -ciclos(2n-n-1,n)/2n
Por que queda negativo? Como se llega a esa ecuación? a partir de dividir que cosa?
Entonces te queda una recurrencia telescópica:
ciclos(2n,n) - ciclos(2n,n-1) = -1/2n
Intente desarrollarla como telescopica pero me da terminos que no puedo escribir
ejemplo
n=2
ciclos(2*n, 2) = ciclos(2*n, n-1) - 1/(2n) -> ciclos(4,2) = ciclos(4,1) - 1/4
pero ciclos (4,1) no puedo calcularlo usando la recurrencia, no es de la forma ciclos(2n,n)
En respuesta a Gaston Daniel Barreto Sugliani
Re: Permutaciones de objetos con largo menor o igual a r
Tuba, revise los calculos pero me da otra cosa distinta
(n+1) b(n+1,r) = (n+1) b(n,r) - b(n-r,r)
hago el cv: n = n+1. r= n
(n) b(n,r) = (n) b(n-1,r) - b(n-1-r,r)
cv: r=n, n=2n
(2n) b(2n,n) = (2n) b(2n-1,n) - b(2n-1-n,n)
* 1/2n
b(2n,n) = b(2n-1,n) - b(2n-1-n,n)/2n
por los casos base:
b(2n,n) = b(2n-1,n) - 1/2n
que es distinto a lo vos llegaste
ciclos(2n,n) - ciclos(2n,n-1) = -1/2n
ciclos(2n,n) = ciclos(2n,n-1) -1/2n
de todas maneras no logro desarrollar la recurrencia, no sé si estoy mareado con algo
En respuesta a Gaston Daniel Barreto Sugliani
Re: Permutaciones de objetos con largo menor o igual a r
de Alfredo Viola -
La clave es que cuando n <= r entonces b_n^(r) = 1 dado que siempre si tenes menos elementos que el tamaño máximo de ciclos vas a tener ciclos de largo menor o igual a r.
Si hacés el cambio de variable n+1=2*r te queda:
b_{2r}^(r) = b_{2r-1}^(r) - b_r^(r)/2r.
Pero b_r^(r) = 1 por lo que comenté al principio del mail con lo cual te queda
b_{2r}^(r) = b_{2r-1}^(r) - 1/2r.
Si hacés lo mismo para b_{2r-1}^(r) te queda
b_{2r-1}^(r) = b_{2r-2}^(r) - 1/(2r-1).
y así podemos seguir.
Al final, si desarrollas todo te queda:
b_{2r}^(r) = b_{r}^(r)-(1/2r+1/(2r-1)+1/(2r-2)+...+1/(r+1)).
Ahora bien, si sabés que b_{r}^(r) = 1 y el resto es H_{2r}-H_r ya tenes el resultado.
No se si te aclaré la duda.
Tuba.