Me preguntaba si alguno de vosotros podría ayudarme con este problema de combinatoria. Necesito mostrar el número exacto de composiciones (c1, c2 , c3, ...) que tienen una suma de N es $2^{N-1}$ . Por ejemplo, para $n=4$ tenemos $C_N = \{(4) , (3,1), (2,2), (1,3), (2,1,1), (1,2,1), (1,1,2), (1,1,1,1)\}$ con $|C_N| = 2^{4-1} = 8$
Respuestas
¿Demasiados anuncios?
Justin
Puntos
121
Para una suma determinada $N$ Considere una colección de $N$ objetos colocados en fila. El problema de determinar el número de composiciones equivale a determinar el número de formas en que podemos agrupar los objetos de esta fila. Por ejemplo, la composición $(2,1,1)$ para $N=4$ correspondería a la agrupación $$**|*|*$$ Para cada objeto, además del primero, hay dos posibilidades: $1)$ El objeto está en el mismo grupo que el objeto anterior $2)$ El objeto está en un grupo diferente al del objeto anterior. Las composiciones están determinadas de forma única por estos $N-1$ opciones. Por lo tanto, hay $2^{N-1}$ composiciones.
Alternativamente, se puede formular este problema como un problema de estrellas y barras . En este caso, el número total de combinaciones se convierte en $$\sum_{k=1}^N \binom{N-1}{k-1}=2^{N-1}$$
Te invito a que reescribas tu ejemplo de una manera que pueda ser un poco más útil para ver la combinatoria involucrada. Por ejemplo, escribe (1+1+1,1) en lugar de (3,1). Ten en cuenta que como $c_1,c_2,\cdots\in \mathbb{N}$ entonces observamos que al escribir un elemento de $C_N$ en el asunto indicado anteriormente, aparece el número 1 $n$ tiempos. Esto es similar a observar que cada elemento de $\mathbb{N}$ se puede escribir como: $$n=\underbrace{1+1+\cdots +1}_{\text{$ n $ times}}$$
A partir de aquí, observamos que cada elemento de $C_N$ es simplemente una forma diferente de sustituir los símbolos de adición por comas. En el ejemplo que has dado, $4=1+1+1+1$ , por lo que hay 3 símbolos de adición que podrían ser sustituidos por comas de alguna manera. El número de formas en que se puede hacer esto es $2^3$ . ¿Ves por qué?
Una vez que entiendas esto, deberías ser capaz de usar el mismo argumento para cualquier $N\in\mathbb{N}$ .
