Combinatoria - 32. Particiones de números enteros

32.1 Introducción

En una partición de un conjunto agrupamos elementos. En una partición de un número entero descomponemos una cantidad en sumandos positivos, considerando iguales las expresiones que solo cambian el orden.

Por ejemplo, 5 = 3 + 2 y 5 = 2 + 3 representan la misma partición de 5.

32.2 Definición

Una partición de un entero positivo n es una secuencia de enteros positivos:

n = a₁ + a₂ + ... + a_k
a₁ ≥ a₂ ≥ ... ≥ a_k ≥ 1

La condición de orden decreciente es una forma de escribir cada partición una sola vez.

32.3 Ejemplo: particiones de 4

Las particiones de 4 son:

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

Por lo tanto, p(4) = 5.

32.4 Simulación de particiones enteras

Indica un número entre 1 y 12 para generar todas sus particiones en orden decreciente.

32.5 Primeros valores de p(n)

n	p(n)
0	1
1	1
2	2
3	3
4	5
5	7
6	11
7	15
8	22

La función p(n) crece más lentamente que n!, pero su crecimiento sigue siendo importante para algoritmos que generan todas las particiones.

32.6 Particiones por cantidad de sumandos

También podemos preguntar cuántas particiones de n utilizan exactamente k sumandos.

Particiones de 5 en 2 sumandos:
4 + 1, 3 + 2

Cantidad = 2

Esta clasificación conecta las particiones enteras con los problemas de distribución y con técnicas de recurrencia.

32.7 Un ejemplo en JavaScript

El siguiente algoritmo construye particiones eligiendo cada siguiente sumando sin superar el valor anterior.

function particionesEnteras(restante, maximo, actual = [], resultados = []) {
  if (restante === 0) {
    resultados.push([...actual]);
    return resultados;
  }

  for (let valor = Math.min(restante, maximo); valor >= 1; valor -= 1) {
    particionesEnteras(restante - valor, valor, [...actual, valor], resultados);
  }
  return resultados;
}

console.log(particionesEnteras(5, 5));

El parámetro maximo evita generar la misma partición con un orden diferente.

32.8 Recurrencia de particiones

Una forma de calcular p(n) consiste en decidir si se utiliza un valor máximo permitido. La cantidad de particiones puede expresarse mediante una función de dos parámetros:

P(n, m) = particiones de n usando valores no mayores que m

El problema se divide entre las particiones que utilizan m y las que no lo utilizan. Esta idea conduce a algoritmos de programación dinámica.

32.9 Algoritmo de programación dinámica

Otra estrategia utiliza una tabla donde cada valor acumula las formas de construir sumas con los valores disponibles.

function contarParticiones(n) {
  const formas = Array(n + 1).fill(0);
  formas[0] = 1;

  for (let valor = 1; valor <= n; valor += 1) {
    for (let suma = valor; suma <= n; suma += 1) {
      formas[suma] += formas[suma - valor];
    }
  }
  return formas[n];
}

console.log(contarParticiones(6));

El resultado es 11. El orden de los valores se controla recorriendo la tabla de izquierda a derecha.

32.10 Restricciones en particiones

Podemos estudiar particiones con condiciones adicionales:

Solo números pares.
Solo partes diferentes.
Un número fijo de sumandos.
Partes no mayores que un límite.
Una parte obligatoria.

Cada restricción cambia el conjunto de sumas válidas y puede requerir una recurrencia específica.

32.11 Particiones e informática

Distribuir una cantidad entre recursos.
Analizar formas de dividir tareas.
Generar configuraciones de tamaños de grupos.
Resolver problemas de optimización discreta.
Construir tablas de programación dinámica.
Estudiar algoritmos de suma y cambio de valores.

32.12 Errores frecuentes

Contar como diferentes las sumas que solo cambian de orden.
Permitir sumandos cero o negativos.
Generar una partición con partes crecientes y luego repetirla en orden decreciente.
Confundir particiones enteras con composiciones, donde el orden sí importa.
Olvidar la partición de 0 cuando se trabaja con recurrencias.

32.13 Qué debes recordar de este tema

Una partición de n es una suma de enteros positivos.
El orden de los sumandos no importa.
p(n) cuenta todas las particiones de n.
Escribir las partes en orden decreciente evita duplicados.
Las recurrencias y tablas permiten calcular p(n).
Las restricciones producen variantes del problema de partición.

32.14 Conclusión

Las particiones de números enteros describen formas de expresar una cantidad como suma de partes positivas sin considerar el orden. Su generación y conteo muestran cómo la combinatoria se conecta con recurrencias y programación dinámica.

En el próximo tema estudiaremos combinaciones con restricciones, aplicando condiciones a las selecciones de elementos.

Volver al índice

32. Particiones de números enteros