31. Conteo de particiones

31.1 Introducción

Una partición de un conjunto divide sus elementos en bloques no vacíos. Cada elemento pertenece a exactamente un bloque y los bloques, considerados en conjunto, contienen todos los elementos originales.

Las particiones aparecen al agrupar registros, clasificar objetos, construir equivalencias o separar recursos en grupos sin etiquetas.

31.2 Definición

Una colección de subconjuntos es una partición de A si cumple:

• Ningún bloque está vacío.
• Los bloques son disjuntos entre sí.
• La unión de todos los bloques es A.

31.3 El orden de los bloques no importa

Las particiones representan grupos sin etiquetas. Por eso:

Intercambiar el orden en que escribimos los bloques no crea una partición nueva. Esto diferencia las particiones de las asignaciones a grupos etiquetados.

31.4 Ejemplo con tres elementos

El conjunto {A, B, C} tiene 5 particiones:

El número 5 es el tercer número de Bell, que cuenta todas las particiones de un conjunto de 3 elementos.

31.5 Simulación de particiones

Escribe entre 2 y 5 elementos para generar todas las particiones. También puedes pedir solo las particiones con una cantidad determinada de bloques.

31.6 Números de Bell

El número de Bell B_n cuenta todas las particiones de un conjunto de n elementos.

El crecimiento de los números de Bell muestra que la cantidad de agrupaciones posibles aumenta rápidamente.

31.7 Particiones en exactamente k bloques

El número de Stirling de segunda especie, escrito S(n,k) o {n sobre k}, cuenta las particiones de n elementos en exactamente k bloques no vacíos.

La suma de S(n,k) para todos los valores posibles de k produce el número de Bell B_n.

31.8 Recurrencia de Stirling

Los números de Stirling de segunda especie cumplen:

Al agregar un nuevo elemento, puede formar un bloque nuevo o incorporarse a uno de los k bloques existentes.

31.9 Un ejemplo en JavaScript

La siguiente función construye particiones usando bloques existentes o creando uno nuevo.

function particiones(elementos) {
  if (elementos.length === 0) return [[]];
  const [primero, ...restantes] = elementos;
  const resultado = [];

  for (const particion of particiones(restantes)) {
    const nuevoBloque = [[primero], ...particion];
    resultado.push(nuevoBloque);

    for (let indice = 0; indice < particion.length; indice += 1) {
      const copia = particion.map(bloque => [...bloque]);
      copia[indice].push(primero);
      resultado.push(copia);
    }
  }
  return resultado;
}

console.log(particiones(["A", "B", "C"]));

El algoritmo inserta el primer elemento en un bloque nuevo o en cada bloque existente.

31.10 Particiones con bloques etiquetados

Si los grupos tienen etiquetas, el problema cambia. Por ejemplo, asignar elementos al grupo Rojo o Azul distingue:

En una partición sin etiquetas, ambos casos representan los mismos bloques. En una asignación etiquetada, son diferentes.

31.11 Aplicaciones en informática

• Agrupar registros por características comunes.
• Construir clases de equivalencia.
• Separar elementos en componentes o comunidades.
• Analizar agrupamientos posibles en datos.
• Diseñar algoritmos de clasificación y clustering.
• Contar formas de dividir recursos en grupos.

31.12 Errores frecuentes

• Permitir bloques vacíos.
• Repetir un elemento en dos bloques.
• Olvidar algún elemento del conjunto original.
• Contar dos veces una partición por cambiar el orden de sus bloques.
• Confundir particiones sin etiquetas con asignaciones a grupos identificados.

31.13 Qué debes recordar de este tema

• Una partición divide un conjunto en bloques no vacíos y disjuntos.
• Cada elemento pertenece exactamente a un bloque.
• El orden de los bloques no importa.
• Los números de Bell cuentan todas las particiones.
• Los números de Stirling de segunda especie cuentan particiones con k bloques.
• Las particiones se aplican a agrupamientos y clases de equivalencia.

31.14 Conclusión

Contar particiones significa estudiar todas las formas de dividir un conjunto en grupos no vacíos sin distinguir el orden de los grupos. Los números de Bell y de Stirling organizan estos conteos y conectan la combinatoria con los problemas de agrupamiento.

En el próximo tema estudiaremos las particiones de números enteros, donde el objeto que se divide es una cantidad numérica.