buenas,
como era que se resolvia este tipo de problema?
Cuando tenes n pelotitas identicas, m recipientes identicos y queres saber la cantidad de formas de repartir sin que sobren pelotitas o que sobren
o que no queden cajas vacias
pelotitas identicas recipientes identicos
Número de respuestas: 3
En respuesta a Francisco Quagliotti Taullard
Re: pelotitas identicas recipientes identicos
de Claudio Qureshi -
Podés considerar primero el problema de repartir n pelotitas idénticas en m recipientes numerados, esto es un problema de composiciones (o permutaciones con repetición, lo que prefieran), o sea de contar cuantas soluciones naturales tiene la ecuación:
x1+x2+..+xm=n donde xi sería la cantidad de pelotitas que van al recipiente i (para esto hay C(n+m-1,m-1) posibilidades).
como no nos importa la numeración de los recipientes, podriamos llamar de "equivalentes" dos composiciones si se corresponden por una permutación, por ejemplo 2+4+3=9 sería equivalente a 4+2+3=9 que sería equivalente a 3+2+4=9 (en este caso la clase de equivalencia correspondiente tendría 3!=6 elementos). Sin embargo no sería tan simple como dividir todo entre m! porque algunas clases de equivalencias contienen menos elementos (por ejemplo 3+3+3=9 solamente sería equivalente a si misma).
Entonces otra estrategia para contar cuantas clases de equivalencia tenemos sería encontrar un representante "distinguido" de cada clase y contar cuantos representantes de ese tipo hay aquí. En este caso cada composición es equivalente a exactamente una composición ordenada (es decir tal que x1 <= x2 <= x3 <= ... <= xm, donde <= significa menor o igual) el cual sería el representante "distinguido" de cada clase de equivalencia.
Por todo lo de arriba resulta que el problema de repartir n pelotitas idénticas en m recipientes idénticos sería equivalente al de hallar las soluciones naturales de x1+x2+..+xm=n con la restricción x1 <= x2 <= x3 <= ... <= xm. Estas se conocen como particiones de n en a lo sumo m partes (las "partes" son los sumandos positivos).No hay una fórmula "fácil" para obtener el número de particiones como lo hay para composiciones. Hay una fórmula cerrada descubierta por Ramanujan (hay una peli que les recomiendo que habla un poco sobre esto) pero es un poco complicada (y no, no se pretende que se sepa en el curso).
Espero haber ayudado con la pregunta.
PD. Cuando me refiero a naturales estoy considerando también el 0 como natural.
En respuesta a Claudio Qureshi
Re: pelotitas identicas recipientes identicos
pero es posible encontrar la solucion a la ecuacion con esas restricciones o no?
este tipo de problema forma parte del curso? Porque me parecia que si pero ahora me entrevere...
En respuesta a Francisco Quagliotti Taullard
Re: pelotitas identicas recipientes identicos
de Claudio Qureshi -
En el curso si aparece algo asi siempre va a ser con valores pequeños y la forma de hacerlo es a mano.
Por ejemplo supongamos que querés ver cuantas formas hay de repartir 5 pelotitas idénticas en 3 recipientes idénticos, entonces por todo lo dicho antes cada repartición corresponde a una solución en los naturales de x1+x2+x3=5 con la restricción x1<=x2<=x3. Las posibilidades para x1, x2, x3 son:
0 0 5
0 1 4
0 2 3
1 1 3
1 2 2
Entonces hay 5 formas (sería un ejercicio interesante escribir explícitamente como serían las clases de equivalencias correspondientes en cada caso con respecto a la relación mencionada en el post anterior).