analco: Contar cantidad cupones que aparecen una unica vez

Lo que hace flajolet en el problema de los cupones es contar la cantidad de sobreyecciones en r elementos, y luego toma complemento y halla la esperanza para obtener la cantidad promedio de cupones que se necesitan para obtener cada cupón al menos una vez.

Pensé en hallar la cantidad de combinaciones diferentes en tener de sobreyecciones con al menos dos elementos y con exactamente uno (la cantidad de cupones que aparecen solo una vez, es la cantidad de cupones que le van a faltar a la hermana)

(e^ (2x) - e^ (x) -1)^k [ k Conjuntos con al menos dos elementos]

{r,k} : Combinaciones de r,k

(r-k)!{n,r-k} : sobreyecciones en r-k elementos

entonces la cantidad total de maneras de tener k cupones al menos dos veces y n-k cupones exactamente una vez es:

∑ (e^ (2x) - e^ (x) -1)^k * {r,k} * r!{n,r-k}

Luego tendria que dividir entre todas las formas posibles r^n.

La cosa es que no se como seguir, ahora tendría que hallar la esperanza de la sumatoria de eso?

Re: Contar cantidad cupones que aparecen una unica vez

de Alfredo Viola - martes, 20 de junio de 2017, 18:15

Disculpame por el retraso, pero he estado con mucho trabajo. Tengo que pensar bien la solución, pero ya te digo que lo tuyo es equivocado. exp(2*z) es la generatriz donde en cada urna podes poner urnas etiquetadas de dos colores. Si queres especificar que tenes k urnas con 1 sólo elemento tenes (r-k) urnas que tienen más de un elemento y k urnas con 1 sólo elemento.

Entonces tienens binomial(r,k) maneras de elegir las urnas cene on k elementos.

Además una urna con 1 elemento tiene generatriz (z/r) y una urna no vacía y sin un elemento tiene genratriz (exp(z/r)-1-z/r)

Te queda binomial(r,k)*(exp(z/r)-1-z/r)^(r-k)*(z/r)^k = F_k(z)

Entonces n! [z^n]F_k(z) es la probabilidad de que llegues a tener sobreyecciones en menor o igual a r pasos y con k urnas con 1 sóla pelota.

Si haces el valor esperado sum(k*F_k(z),k=0..r) = F(z) tenes el valor esperado de la cantidad de urnas en 1.

Te queda una suma del tipo sum(k*binomial(r,k)*A^(k)*B^(r-k),k=0..r) = r*A*(A+B)^(r-1)

Si luego a esto le haces exp(z/r)-F(z) y seguis los mismos pasos que eq (30) y (31) de la página 117, deberías llegar al resultado.

Puede estar mal, y estoy muy cansado, pero creo que la mano puede venir por ahí.

Saludos,

Tuba.

Re: Contar cantidad cupones que aparecen una unica vez

de Gaston Daniel Barreto Sugliani - lunes, 26 de junio de 2017, 13:41

Hola Tuba,

Gracias por la respuesta.

La estuve revisando varias veces pero me quedan algunas dudas:

"Si luego a esto le haces exp(z/r)-F(z) " Por qué haría eso? Si estoy queriendo tomar el complemento de la probabilidad no tendría que hacer exp(z) - F(Z)?

Además, por qué F(Z)? F(Z) es la esperanza de la cantidad de urnas con un elemento. Si quiero tomar el complemento de la probabilidad tendría que hacer 1 - P( k urnas con 1 elemento en r tiradas) = n! [z^n]F_k(z)

"Si luego a esto le haces exp(z/r)-F(z) y seguis los mismos pasos que eq (30) y (31) de la página 117" el problema que tengo aca es que el truco de la integral me pide un n!

Re: Contar cantidad cupones que aparecen una unica vez

de Alfredo Viola - martes, 27 de junio de 2017, 10:22

Hola Gastón:

La estadía aquí está siendo muy productiva, y ayer creo que ayudé mucho a encontrar una manera de resolver un problema interesante que la gente aquí de Francia hacía varios años que quería resolver y no sabía como hacerlo. Me basé en sus ideas, pero entontré una manera más elegante de presentarla y usarla, y algoritmo (que lo estaban buscando) polinomial para resolver el problema (pensaban que podía ser exponencial). Así que en estos días, me he matado (casi literalmente! :-) ) laburando incluso los fines de semana.

Por otro lado, hace días también que me viene dando vueltas a la cabeza que lo que te dije tiene algo de incorrecto, pero en los tiempos libres que tengo, no pude ponerme tranquilamente a ver el error. Te pido disculpas.

Apenas pueda, pienso bien tu consulta y te contesto de una manera mucho más apropiada a la que te di la otra vez. Te pido disculpas. De todas formas, la mano viene por usar bivariadas (cosa que si haces las cuentas bien sería equivalente) o de la manera que te dije: especificar el número de k urnas con 1 elemento usando la expresión con los números combinatorios. Esto es claro! El tema es luego integrarlo bien con el resto del problema para dar el resultado correcto! Esta es la parte interesante!

Dame unos días, y disculpame.

Abrazo,

Tuba.