Calculadora de particiones enteras

La función de partición entera p(n) responde a una pregunta clásica de conteo: ¿de cuántas maneras puede escribirse un entero no negativo n como suma de enteros positivos cuando el orden de los sumandos no importa? Por ejemplo, 4 es igual a 4, 3+1, 2+2, 2+1+1 y 1+1+1+1, de modo que p(4) vale cinco; 5 tiene siete particiones y 10 tiene cuarenta y dos. Las particiones aparecen en teoría de números, funciones generadoras, mecánica estadística y concursos de programación cuando se cuentan sumas de multiconjuntos en lugar de composiciones ordenadas o particiones de conjuntos etiquetados. Esta capacidad acepta un entero no negativo n y devuelve el p(n) exacto como cadena decimal calculada con programación dinámica en BigInt, de forma que valores muy por encima de los límites habituales de enteros seguros permanecen correctos dígito a dígito. Un n negativo se rechaza con un error de validación claro en lugar de un cero silencioso o una respuesta errónea.

Cómo se define la función de partición p(n)

Una partición entera no restringida de un entero no negativo n es una forma de escribir n como suma de enteros positivos en la que el orden de los sumandos es irrelevante. Por convención p(0) vale uno, contando la partición vacía de cero. Valores clásicos de manual son p(1)=1, p(2)=2 (a saber, 2 y 1+1), p(3)=3, p(4)=5, p(5)=7, p(6)=11 y p(10)=42.

La función generadora ordinaria de la secuencia es el producto infinito, sobre k mayor o igual que uno, de uno entre uno menos x elevado a k, que codifica que cada entero positivo puede aparecer cualquier número de veces como parte. Una recurrencia práctica usada en software es el programa dinámico clásico al estilo del cambio de monedas: se inicializa un arreglo con una forma de formar la suma cero y, para cada tamaño de parte de uno hasta n, se suman las formas de completar el resto.

Esa recurrencia rellena p(n) de forma exacta y nunca cuenta dos veces los ordenamientos porque las partes se introducen en orden no decreciente de tamaño una sola vez.

Objetos relacionados pero distintos incluyen las composiciones, donde el orden sí importa y hay dos elevado a n menos uno composiciones de n; las particiones de conjuntos contadas por números de Stirling de segunda especie o números de Bell, que particionan elementos etiquetados en lugar de sumar enteros positivos sin etiquetar; y las particiones restringidas que exigen partes distintas, solo partes impares o un número fijo de partes.

Esta implementación nunca usa aproximación en coma flotante, muestreo Monte Carlo ni tablas externas: rellena un arreglo unidimensional de BigInt para que cada dígito sea correcto. El camino es plenamente determinista —sin semillas aleatorias, sin relojes, sin red y sin deriva de modelo—, de modo que el mismo n siempre produce la misma cadena.

Dónde aparecen las particiones enteras en el trabajo real

Los cursos de teoría de números y los concursos de programación preguntan con frecuencia cuántas particiones no restringidas tiene un n dado, cómo crece p(n) o si una tabla de valores pequeños coincide con las congruencias de Ramanujan y otras identidades clásicas. Los diseñadores de algoritmos usan conteos de particiones al analizar espacios de estado al estilo de la mochila entera, al contar descomposiciones en multiconjuntos de un presupuesto de recursos o al dimensionar tablas de DP cuyas dimensiones siguen tamaños de parte.

En física y combinatoria, p(n) se conecta con funciones de partición bosónicas y coeficientes de funciones generadoras; los educadores suelen mostrar una lista breve de particiones de un n pequeño y luego pedir solo el conteo. La preparación de entrevistas y el entrenamiento olímpico necesitan a menudo un p(n) fiable sin mantener a mano tablas grandes ni arriesgar conteos de composiciones desfasados en uno.

Si más adelante necesita composiciones donde el orden importa, particiones de conjuntos vía números de Stirling de segunda especie, solo números de Bell, particiones restringidas con partes distintas o solo impares, o un listado explícito de cada partición en lugar del conteo, trátelos como intenciones de búsqueda distintas en lugar de sobrecargar esta página.

Mantenga n dentro del límite documentado para que la latencia del nivel gratuito sea previsible, y prefiera consumidores de cadena para el valor devuelto porque p(n) abandona el rango de enteros seguros mucho antes de cinco mil.