De cuántas maneras puede un número natural n se expresa como una suma de uno o más números enteros positivos, con el fin de tomar en cuenta?

Question

P: El número 4 puede ser expresada como una suma de uno o más números enteros positivos, con el fin de tomar en cuenta, de 8 maneras: \begin{array}{l} 4&=1+3&=3+1&=2+2&=1+1+2\\ &=1+2+1&=2+1+1&=1+1+1+1. \end{array} En general, dada $\mathbb n$ $\in$ $\mathbb N$, ¿de cuántas maneras distintas puede $\mathbf n$ ser de forma expresa?

Consulta: me las arreglé para resolver a través de un combinatoric prueba, pero la solución siempre es así: \begin{align} &~~Idea: n= x_1 + x_2 +...+x_k, k \in \mathbb N, x_k \gt 0.\\ &\implies x_1 - 1 + x_2 - 1 +...+ x_k -1 = n - k\\ &\implies x_1* + x_2* + ... + x_k* = n-k \qquad-(*) \end{align} Desde $H^n_r$ = \begin{pmatrix} r+n-1 \\ r \end{pmatrix}, tenemos $H^k_{n-k}$ = \begin{pmatrix} n-k+k-1 \\ n-k \end{pmatrix} Y la respuesta es, como tal,: $$\sum_{k=1}^n H^k_{n-k} =$$ $$\sum_{k=1}^n \begin{pmatrix} n-1 \\ n-k \end{pmatrix} = 2^{n-1}$$. No tengo idea de por qué $H^n_r$ se aplica y por qué $$\sum_{k=1}^n H^k_{n-k}$$ is used to derive the desired result $$2^{n-1}$$. Alguna explicación sobre esto será muy apreciado.

Answer 1

Una forma de ver por qué la respuesta es $2^{n-1}$ directamente es escribir $n$ como una suma de $1$s:

$$ n = \underbrace{1 + 1 + 1 + ... + 1}_{n \textrm{ times}}. $$

Por supuesto, esto expresa $n$ como una suma de $1$s, pero queremos que todas las expresiones de la $n$ como una suma de (ordenada) los números positivos. Para ello, para cada '$+$' en la expresión anterior, podemos elegir si desea o no para dividir la suma allí para formar un nuevo sumando. Por ejemplo, supongamos $n = 8$. A continuación, comenzamos con

$$ 8 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1. $$

Ahora supongamos que la decisión de dividir la suma en la 2ª, 3ª y 5ª signos más, se destacan a continuación.

$$ 8 = 1 + 1 \color{red}{+} 1 \color{red}{+} 1 + 1 \color{red}{+} 1 + 1 + 1. $$

Ahora añadimos la $1$'s entre el elegido importantes para formar los sumandos,

$$ 8 = (1+1) \color{red}{+} 1 \color{red}{+} (1+1) \color{red}{+} (1+1+1) = 2 \color{red}{+} 1 \color{red}{+} 2 \color{red}{+} 3,$$

dando una expresión de $8$ como suma de enteros positivos.

En general, esta claramente bijects a todas las expresiones de la $n$ como un ordenado suma de enteros positivos. Desde allí se $n-1$ signos más entre la $n$ $1$s, hay $2^{n-1}$ maneras de elegir dónde dividir la suma, y por lo tanto, $2^{n-1}$ sumas posibles.

Answer 2

Lo que se busca es la composiciones de $n$

Tome una cadena de $1's,\;$ por ejemplo$\; \large 1{\boxed.} 1\boxed. 1\boxed. 1$

En el $\;(n-1)\;$ cajas, poner un $+\;$ o una coma.

$1,\;\;1+1+1$ por ejemplo, representaría $1+3$

Puesto que usted ha $2$ opciones para cada cuadro, # de composiciones = $2^{n-1}$

Answer 3

Desde su título distingue cuidadosamente entre números naturales (que incluyen a $0$) y los enteros positivos (que no, al menos no por el inglés sentido de "positivo"), creo que una fórmula que da el valor correcto (es decir,$0$, dado que al menos uno sumando era necesario) por $n=0$, e $2^{n-1}$ no lo hace. La fórmula correcta sería $\lfloor2^{n-1}\rfloor$, o usted podría dar el valor como $$ \begin{cases}0&\text{if %#%#%,}\\2^{n-1}&\text{if %#%#%.}\end{casos} $$ La prueba puede ser simplemente por inducción, donde tenemos $n=0$ e $n>0$ a partir de los casos para capturar el comportamiento excepcional en $n=0$ (ambos a partir de los casos son evidentes). Si asumimos para $n=1$ demostrado que no $n=0$ composiciones de $n>0$, luego de cada uno de ellos podemos obtener dos composiciones diferentes de $2^{n-1}$: uno por el aumento de la final de plazo por uno, y otro por la adición de un nuevo plazo $n$ y el final. Está claro que el primer método, aplicado a todas las composiciones de $n+1$ da todas las composiciones de $1$ que no tienen $n$ como término final, y el otro método da todas las composiciones de $n+1$ que no cuentan $1$ como término final. Juntos, que le da todas las composiciones de $n+1$, y cada uno de ellos en uno solo; su número es, a continuación,$1$, como iba a ser probado.

Tenga en cuenta que el paso inductivo no puede aplicarse al caso de $n+1$, ya que no hay término final a modificar; esto explica la excepción al principio de la secuencia.