Distribución de objetos en recipientes

Dentro de la teoría combinatoria algunos problemas de recuento y un gran número de cuestiones combinatorias pueden ser resueltas y descritas en forma de distribuciones de objetos en recipientes («bolas en cajas»).

Existen numerosos casos dentro de este tipo de distribuciones, ya que se clasifican según si los objetos o las cajas son distinguibles o indistinguibles y también teniendo en cuenta el tipo de aplicación a la que están asociadas, es decir, las diferentes restricciones sobre las distribuciones.

Teniendo en cuenta lo anterior, nos encontramos con algunos de los siguientes casos, llamados modelos de ocupación:

Objetos y recipientes distinguibles (numerables)

Consideramos $n$ cajas distinguibles y $k$ bolas distinguibles.

Y también, teniendo en cuenta las aplicaciones de un conjunto de $k$ elementos en uno de $n$ elementos, dicho de otra manera, las posiciones que pueden tomar los objetos en las diferentes cajas. Algunos de los casos que nos encontramos son:

• Que puedan quedar cajas vacías (aplicación cualesquiera), para ello $n$ puede tomar cualquier valor y puede haber más de un objeto en una caja:
  • Variaciones con repetición: $V{R}_n^k$
• Ateniendo a la condición de que haya un único objeto por recipiente (aplicación inyectiva), posible solo si $n>=k$, mayor o igual número de cajas que de bolas:
  • Variación: $V_n^k$
• Con la condición anterior de que haya un único objeto por recipiente y que además no haya ningún recipiente vacío (aplicación biyectiva), tiene que ocurrir que $n=k$, mismo número de cajas que de bolas:
  • Permutación: $Pn$

Objetos indistinguibles y recipientes distinguibles

Consideramos $k$ bolas indistinguibles y $n$ cajas distinguibles. Ahora no se hace la pregunta de «qué bolas van en cada una de las cajas», ya que no las podemos numerar. Los casos destacados son:

• En el caso de que puedan quedar cajas vacías y en donde $n$ puede tomar cualquier valor, es decir, sin ninguna restricción (aplicación cualesquiera):
  • Combinaciones con repetición: $C{R}_{n,k}$
• Con la condición de que no se permitan cajas vacías (aplicación sobreyectiva), en donde $k>=n$, mayor número de objetos que de recipientes:
  • $C{R}_n^{k-n}=C_{k-1}^{n-1}$
• Con la condición de que haya un único objeto por recipiente (aplicación inyectiva), en donde tiene que ocurrir que $n>=k$ :
  • Combinaciones: $C_{n,k}$

Objetos y recipientes indistinguibles

Tenemos $k$ bolas y $n$ cajas. En este caso ambas son indistinguibles, no numerables. Estas distribuciones corresponden con las particiones del entero $k$:

• Suponiendo de que no haya cajas vacías, siendo $k>=n$. La solución es el número de particiones de $k$ con exactamente $n$ partes:
  • $p_n(k)$
• Si nos fijamos en el número de cajas, la solución es el número total de particiones de $k$:
  • $p(k)=\sum _{i=1}^k{p}_i(k)$

Obteniendo $p_n(k)$ y $p(k)$ a partir de Reglas de recurrencia.

Objetos distinguibles y recipientes indistinguibles

Consideramos $k$ bolas distinguibles y $n$ cajas indistinguibles. Las posibles situaciones que se pueden encontrar:

• La aplicación sea "cualesquiera":
  • Los posibles casos de distribuciones se calculan mediante $\sum _{k=1}^n(n,k)=\sum _{i=1}^{n}S(n,i)$
• La aplicación sea inyectiva, por lo que cada objeto solo puede estar en un recipiente:
  • El número de casos de distribuciones es de 1
• La aplicación sea sobreyectiva, cada recipiente tiene al menos un objeto:
  • Los casos de distribuciones vienen dados por Números de Stirling de segunda especie $S(n,k)$
• La aplicación sea biyectiva, por lo tanto a cada uno de los recipiente se le asigna un solo objeto:
  • El número de casos posibles es de 1

Véase también

• Combinatoria
• Relación de recurrencia

Enlaces externos

• Twelvefold way Plantilla:En idioma.
• Stars and bars (combinatorics) Plantilla:En idioma.
• Conceptos de combinatoria.