Recuento de composiciones enteras

Una composición ordenada de un entero positivo n es una tupla de enteros positivos que suman n, en la que el orden de las partes forma parte de la identidad: 1+3 y 3+1 son dos composiciones distintas de cuatro. La combinatoria clásica demuestra que el número de tales sumas ordenadas es siempre dos elevado a n menos uno. Esta capacidad acepta un único entero positivo n y devuelve ese recuento exacto, junto con la fórmula cerrada 2^(n-1), de modo que usted no tenga que enumerar cada tupla, recorrer un árbol binario de separadores ni arriesgarse a un error por uno al revisar tareas, casos de concurso o identidades de funciones generadoras.

Por qué el número de composiciones ordenadas es dos elevado a n menos uno

Escriba n unos en una fila. Entre esos unos hay exactamente n menos uno huecos. En cada hueco usted puede insertar una barra que parte la secuencia en una nueva parte, o dejar el hueco vacío para que los unos adyacentes queden pegados como una parte mayor.

Cada patrón de barras y huecos vacíos produce una composición ordenada de n, y toda composición surge de exactamente un patrón de ese tipo. Como cada uno de los n menos uno huecos tiene dos elecciones independientes, el número total de patrones es dos elevado a n menos uno. Esa identidad es todo el algoritmo que evalúa esta capacidad: no recorre ramas de primera parte, no reserva un arreglo de tuplas y no muestrea.

Una comprobación de una línea para n igual a cuatro da ocho, coincidiendo con las ocho composiciones (4), (1,3), (3,1), (2,2), (1,1,2), (1,2,1), (2,1,1) y (1,1,1,1). Para n igual a uno hay un único patrón sin barras y el recuento es uno, la composición (1) misma. La forma cerrada es exacta para todo entero positivo, de modo que un trabajo que afirme nueve composiciones de cuatro está simplemente equivocado, y un generador que necesite el tamaño de la familia de composiciones puede dimensionar buffers con este recuento sin listarlas nunca.

El orden es esencial: si identifica 1+3 con 3+1 ha abandonado las composiciones y ha entrado en el mundo de las particiones, cuyo recuento p(n) no tiene esa fórmula de potencia de dos y es una intención de búsqueda distinta.

Qué envía, qué recibe y cuándo falla la solicitud

La regla de producto es estricta: n menor que uno es inválido, incluido el cero y todo negativo, porque la definición habitual de composición exige un entero positivo que componer. Si tiene éxito, la respuesta repite el n normalizado, devuelve count como cadena decimal del valor exacto 2^(n-1) e incluye formula como la cadena de identidad 2^(n-1) para que los clientes muestren el teorema sin codificarlo a mano.

El recuento es una cadena a propósito: dos elevado a cincuenta y tres ya abandona el rango de enteros seguros de JavaScript, y esta página es útil precisamente cuando n es tan grande que listar cada composición resulta imposible. La validación fallida no se cobra.

Dónde encaja un recuento de composiciones y cómo se tarifa

Use este recuento cuando la pregunta sea cuántas sumas ordenadas existen, no cuáles son las tuplas. Los programadores de concursos confrontan soluciones candidatas de problemas de conteo de composiciones con un oráculo determinista en lugar de reimplementar una potencia BigInt en cada arnés de lenguaje. El profesorado asigna la demostración de huecos y barras y necesita una comprobación automática de que 2^(n-1) es de verdad el tamaño de la familia antes de que el alumnado intente listarla.

Los sandboxes de entrevistas y las demostraciones de funciones generadoras necesitan el mismo número cada vez que preguntan. El trabajo de datos y de compiladores a veces dimensiona un espacio de búsqueda de divisiones por etapas ordenadas de un presupuesto n y debe conocer la cardinalidad antes de reservar memoria.

Si de verdad necesita cada tupla, deténgase aquí y use una herramienta de listado con un n pequeño; si necesita composiciones en exactamente k partes, eso es el binomial C(n-1, k-1) y otra página; si el orden no importa, usted quiere la función de partición p(n). Mantenga n dentro de los límites documentados, trate la cadena count como el entero exacto y obtendrá un recuento de composiciones reproducible sin instalar un sistema de álgebra computacional.