Particiones en partes distintas

La función de partición en partes distintas q(n) responde a una pregunta clásica de teoría de números: ¿de cuántas formas puede usted escribir un entero no negativo n como suma de enteros positivos cuando cada sumando aparece a lo sumo una vez y el orden no importa? Por ejemplo, 5 es igual a 5, 4+1 y 3+2, de modo que q(5) vale tres; 6 tiene cuatro particiones en partes distintas y 10 tiene diez. Este recuento difiere de la función de partición sin restricciones p(n), que permite partes repetidas como 2+2 o 1+1+1. Las particiones en partes distintas aparecen en identidades de funciones generadoras, en el teorema de Euler que las equipara con las de partes impares, en olimpiadas y en ejercicios de programación dinámica. Esta capacidad acepta un entero no negativo n y devuelve el q(n) exacto como cadena decimal calculada con programación dinámica 0-1 en BigInt, de modo que los valores más allá de los enteros seguros se mantienen 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 incorrecta.

Cómo se definen y cuentan las particiones en partes distintas

Una partición de un entero no negativo n en partes distintas es una forma de escribir n como suma de enteros positivos en la que ninguna parte se repite y el orden de los sumandos es irrelevante. Por convención q(0) vale uno, contando la partición vacía del cero. Valores clásicos de libro son q(1)=1 (a saber, 1), q(2)=1 (a saber, 2), q(3)=2 (3 y 2+1), q(4)=2 (4 y 3+1), q(5)=3 (5, 4+1, 3+2), q(6)=4 y q(10)=10.

La función generadora ordinaria de la sucesión es el producto infinito sobre k mayor o igual que uno de uno más x elevado a k, lo que codifica que cada entero positivo puede aparecer cero veces o exactamente una vez como parte.

Un algoritmo práctico en software es el programa dinámico clásico estilo mochila 0-1: inicialice un arreglo con una forma de formar la suma cero y, para cada tamaño de parte de uno hasta n, recorra el arreglo de sumas restantes de n hacia abajo hasta ese tamaño y sume las formas que excluyen la parte a las que la incluyen. El orden descendente garantiza que cada parte se usa a lo sumo una vez, de modo que el uso múltiple sin restricción nunca ocurre.

Objetos relacionados pero distintos incluyen las particiones sin restricción p(n), donde las partes pueden repetirse; las composiciones, donde el orden importa; las particiones de conjuntos contadas por números de Stirling de segunda especie; y las particiones solo en partes impares, que Euler demostró equinumerables con las de partes distintas para todo n. Esta implementación no usa aproximación en coma flotante, muestreo Monte Carlo ni tablas externas: rellena un arreglo unidimensional BigInt para que cada dígito sea correcto.

El camino es totalmente determinista —sin semillas aleatorias, relojes, red ni deriva de modelo—, de modo que el mismo n siempre produce la misma cadena.

Dónde aparecen las particiones en partes distintas en el trabajo real

Los cursos de teoría de números y los concursos de programación preguntan a menudo cuántas particiones de n usan sumandos dos a dos distintos, cómo se compara ese conteo con p(n) sin restricción, o si una tabla de valores pequeños coincide con la identidad de Euler con particiones en partes impares.

Los diseñadores de algoritmos usan conteos en partes distintas al analizar espacios de estados tipo suma de subconjuntos 0-1, al contar combinaciones de tamaños de recurso únicos que totalizan un presupuesto, o al dimensionar tablas de DP cuyas dimensiones siguen tamaños de parte usados a lo sumo una vez.

Las lecciones de combinatoria y funciones generadoras conectan q(n) con el producto de uno más x elevado a k y con identidades restringidas tipo Rogers–Ramanujan; los educadores suelen listar las particiones distintas de un n pequeño y luego pedir solo el conteo. La preparación de entrevistas y olimpiadas necesita con frecuencia un q(n) fiable sin mantener tablas a mano ni contar por error composiciones o particiones sin restricción.

Si más adelante necesita p(n) sin restricción, composiciones donde el orden importa, particiones de conjuntos vía Stirling de segunda especie, o un listado explícito de cada partición en partes distintas en lugar del conteo, trátelos como intenciones de búsqueda separadas en lugar de sobrecargar esta página. Mantenga n dentro del límite documentado para que la latencia del nivel gratuito sea predecible, y prefiera consumidores de cadena para el valor devuelto porque q(n) acaba saliendo del rango de enteros seguros para argumentos grandes.