Combinatoria de sumas

Question

Supongamos que tenemos un número S que representa una suma. Esta suma se puede descomponer en una suma de términos. Quiero calcular cuántas expresiones puedo escribir que representen esa suma donde los términos estén en el rango de $ 1 $ a $ S $ .

Por ejemplo:
$$\begin{align} 4 &= 1 + 1 + 1 + 1\\ 4 &= 2 + 1 + 1\\ 4 &= 1 + 2 + 1\\ 4 &= 1 + 1 + 2\\ 4 &= 2 + 2\\ 4 &= 3 + 1\\ 4 &= 1 + 3\\ 4 &= 4 \end{align} $$ Para $S=4$ tenemos $N=8$ .
Para $S=3$ tenemos $N=4$

Aunque he descubierto que puedo calcularlo con esta fórmula:

$N = 2^{S-1}$

No sé muy bien por qué. Puedo contarlos para algunas sumas y ver la regla, pero ¿hay una mejor manera de explicar esto?

Answer 1

Pista: Imagina $S$ bolas alineadas en fila. Entre cada par de bolas adyacentes, puedes elegir si colocar un "divisor" entre ellas o no. Después de considerar todos los pares posibles, puede agrupar las bolas en función de los divisores. Por ejemplo, $4=1+1+2$ puede representarse como *|*|** donde | denota un divisor, y * denota una bola.

Answer 2

Véase el triángulo de Pascal. Observa cómo cada línea posterior se crea sumando sus líneas anteriores. Por ejemplo, veamos el ejemplo 4. Observa la cuarta línea, que dice 1 3 3 1. Esto significa que hay 1 forma de sumar 4 con 4 enteros, 3 formas de sumar 4 con 3 enteros, 3 formas de sumar 4 con 2 enteros y 1 forma de sumar 4 en 1 entero. Y la suma de cada fila del triángulo de Pascal es $2^{S-1}$ .