36. Distribución de objetos idénticos y diferentes

36.1 Introducción

En el tema anterior presentamos los problemas de distribución. Ahora compararemos dos modelos fundamentales: objetos diferentes, que pueden identificarse individualmente, y objetos idénticos, que solo se distinguen por su cantidad.

La misma cantidad de objetos y recipientes puede producir resultados muy distintos según el modelo elegido.

36.2 Objetos diferentes

Si los objetos tienen identidad, cada uno elige de manera independiente uno de los m recipientes etiquetados.

Con 3 objetos A, B y C y 2 cajas identificadas:

La distribución A en la caja 1 y B en la caja 2 es diferente de B en la caja 1 y A en la caja 2.

36.3 Objetos idénticos

Si los objetos son iguales, solo importa cuántos recibe cada recipiente. Distribuir n objetos idénticos en m recipientes etiquetados equivale a resolver:

La cantidad de soluciones no negativas es:

36.4 Ejemplo comparativo

Distribuyamos 3 objetos entre 2 recipientes:

Las distribuciones de objetos idénticos se representan por las cantidades:

36.5 Simulación de ambos modelos

Indica la cantidad de objetos y recipientes. Selecciona si los objetos son idénticos o diferentes para observar la diferencia.

36.6 Método de estrellas y barras

Para objetos idénticos y recipientes etiquetados usamos estrellas para representar objetos y barras para separar recipientes.

Hay n estrellas y m-1 barras, por lo que se eligen las posiciones de las barras entre n+m-1 lugares.

36.7 Un ejemplo en JavaScript: objetos diferentes

La función genera asignaciones cuando cada objeto conserva su identidad.

function distribuirDiferentes(cantidadObjetos, cantidadRecipientes, actual = [], resultados = []) {
  if (actual.length === cantidadObjetos) {
    resultados.push([...actual]);
    return resultados;
  }
  for (let recipiente = 1; recipiente <= cantidadRecipientes; recipiente += 1) {
    distribuirDiferentes(cantidadObjetos, cantidadRecipientes, [...actual, recipiente], resultados);
  }
  return resultados;
}

console.log(distribuirDiferentes(3, 2));

36.8 Un ejemplo en JavaScript: objetos idénticos

Para objetos idénticos generamos las cantidades que recibe cada recipiente, sin distinguir qué objeto concreto fue colocado.

function distribuirIdenticos(restantes, recipientes, actual = [], resultados = []) {
  if (recipientes === 1) {
    resultados.push([...actual, restantes]);
    return resultados;
  }
  for (let cantidad = 0; cantidad <= restantes; cantidad += 1) {
    distribuirIdenticos(restantes - cantidad, recipientes - 1, [...actual, cantidad], resultados);
  }
  return resultados;
}

console.log(distribuirIdenticos(3, 2));

36.9 Recipientes no vacíos

Si los objetos son idénticos y cada uno de los m recipientes debe recibir al menos uno, reservamos un objeto para cada recipiente y distribuimos los restantes:

Esta fórmula solo tiene sentido cuando n ≥ m.

36.10 Recipientes indistinguibles

Si además los recipientes no tienen etiquetas, cambiar sus cantidades de lugar no produce una distribución nueva. El problema se convierte en una partición del número n.

Por ejemplo, distribuir 4 objetos idénticos en recipientes indistinguibles corresponde a las particiones de 4.

36.11 Aplicaciones en informática

• Distribuir unidades de recursos entre servidores.
• Asignar objetos identificables a categorías.
• Representar cargas por cantidades acumuladas.
• Comparar configuraciones de datos con o sin identidad.
• Resolver problemas de capacidad y almacenamiento.
• Modelar particiones y distribuciones en algoritmos.

36.12 Errores frecuentes

• Usar mⁿ para objetos idénticos.
• Usar estrellas y barras cuando los objetos son distinguibles.
• Confundir recipientes etiquetados con indistinguibles.
• Olvidar si los recipientes pueden quedar vacíos.
• Contar como diferentes distribuciones que solo intercambian recipientes iguales.

36.13 Qué debes recordar de este tema

• Los objetos diferentes conservan identidad individual.
• Los objetos idénticos se distinguen solo por cantidades.
• Objetos diferentes en recipientes etiquetados: mⁿ.
• Objetos idénticos en recipientes etiquetados: C(n+m-1,m-1).
• Recipientes no vacíos requieren ajustar el modelo.
• Recipientes indistinguibles conducen a particiones enteras.

36.14 Conclusión

La distinción entre objetos idénticos y diferentes cambia completamente el conteo. Cuando cada objeto puede identificarse, contamos asignaciones; cuando solo importan las cantidades, usamos distribuciones y estrellas y barras.

En el próximo tema estudiaremos la distribución con restricciones de capacidad, ocupación y compatibilidad.