Composiciones de un entero positivo

El problema 2 de la entrada Dos problemas pide encontrar el número de composiciones de un entero positivo (ver el artículo en inglés de Wikipedia), es decir, las formas en que el entero puede escribirse como suma de enteros positivos, siendo importante el orden de los sumandos. Por ejemplo $4$ se puede escribir como $1 + 1 + 1 + 1$, o como $1 + 2 + 1$, o como $2 + 1 + 1$, y todas ellas son composiciones distintas del entero $4$.

Cuando no se distingue el orden, se llaman particiones y es un problema mucho más difícil. Por ejemplo $1 + 2 + 1$ y $2 + 1 + 1$ son la misma partición de $4$.

Una forma de resolver el problema es empezar con ejemplos para números chicos. Llamando $c(n)$ a la cantidad de composiciones del entero $n$ y poniendo a la derecha todas las composciones omitiendo los signos de suma, tenemos:

• $c(1) = 1$: $1$.
• $c(2) = 2$: $11, 2$.
• $c(3) = 4$: $111, 21, 12, 3$.
• $c(4) = 8$: $1111, 112, 121, 211, 22, 13, 31, 4$.

$c$ parece seguir una ley exponencial, y conjeturamos que $c(n) = 2^{n-1}$.

Para demostrar nuestra conjetura podemos usar inducción, viendo que $c(n+1) = 2\, c(n)$ sabiendo que $c(1) = 1$. Efectivamente, cada forma de escribir $n - 1$ da lugar a dos formas de escribir $n$: una agregando un $1$ atrás y otra cambiando el último número en la expresión por uno más: por ejemplo, para pasar de $n = 3$ a $n + 1 = 4$ podemos poner:

• $111 \to 1111, 112$,
• $21 \to 211, 22$,
• $12 \to 121, 13$,
• $3 \to 31, 4$.

No es difícil ver que mediante este procedimiento dos composiciones distintas de $n$ no dan lugar a una misma composición de $n+1$, y que toda composición de $n+1$ se escribe (de única manera) como proveniente de una composición de $n$: si termina en $1$ se lo saca ($31\to 3$), y si termina en algo mayor que $1$ se le resta $1$ ($22\to 21$).

Aunque en general es útil para resolver rápidamente problemas, inducción es una técnica que a veces no deja ver claramente qué está pasando, y siempre vale la pena tratar de encontrar demostraciones alternativas.

Una demostración más visual es pensar en $n$ cajas alineadas, apretadas una contra otra, determinando $n-1$ bordes entre dos consecutivas. Eligiendo arbitrariamente $k$ de esas fronteras, $k = 0,\dots,n-1$, se determinan $k+1$ grupos de cajas, y la cantidad de cajas en cada grupo define un número para encontrar la composición.

Por ejemplo, tomemos $n = 10$ cajitas consecutivas,

elijamos arbitrariamente $k = 3$ divisiones remarcadas en azul,

y encontramos la composición $10 = 3 + 4 + 1 + 2$ con $k + 1 = 4$ sumandos.

Desde ya, podemos elegir cualquier subconjunto de los $n-1$ fronteras entre cajas para encontrar una única composición y recíprocamente, cada composición determina unívocamente un subconjunto de las $n-1$ fronteras, por lo que tenemos $2^{n-1}$ composiciones.

Por supuesto, esta segunda «demostración» es un tanto mentirosa, porque para demostrar que hay $2^n$ subconjuntos de un conjunto con $n$ elementos, muchas veces se usa inducción: fijando uno de los elementos, hay $2^{n-1}$ subconjuntos sin ese elemento y otros $2^{n-1}$ que sí lo tienen, lo que es una variante de la primera demostración para el número de composiciones.

Un ejercicio interesante es ahora pensar en cómo relacionar la cantidad de composiciones con las filas del triángulo de Pascal, en el que se suman dos entradas consecutivas en un nivel para obtener una entrada de la fila del nivel siguiente.