¿Cuántas formas hay de sumar números enteros para $n$ tal que al menos uno de ellos sea igual a 1?

Question

Necesito encontrar cuántas formas hay de sumar enteros hasta un número dado, $n$ , tal que al menos uno de ellos sea igual a 1. Es decir $|$ { $(x_1,...,x_k) : 0\leq k \leq n, \sum _{i=1} ^k x_i=n,\exists i:x_i=1$ } $|$

Gracias.

nota: he podido encontrar una forma de calcular la respuesta con recursividad, pero no he podido encontrar una fórmula.

mi solución: Que $\sigma_n(k)=|$ { $(x_1,...,x_k):\sum x_i=n,\exists x_i=1$ } $| $

y $ \gamma _n(k)=|$ { $(x_1,...,x_k):\sum x_i=n,\forall x_i\ne1$ } $ $ .

ahora podemos ver que para todo k,n $ \sigma_n(k)+\gamma_n(k)=\binom{n+k-1}{n} $ .

Ahora definiremos $ \xi_n(k,\ell)$ para ser el número de todas las sumas de longitud $k$ que tienen exactamente $\ell$ de uno. Podemos ver que $ \sigma_n(k)=\sum_{\ell=1}^k \xi_n(k,\ell) $ .

podemos notar que podemos mapear todas las sumas que tienen $\ell$ y son de longitud $k$ a las sumas que tienen 0 unos y son de longitud $k-\ell$ . este mapeo envía $ \binom{n}{\ell}$ diferentes sumas que tienen unos a una sola suma que no los tiene.

por lo que vemos: $\xi_{n}(k,\ell)=\binom{n}{\ell}\gamma_{n}(k-\ell)$ .

Después de jugar con las fórmulas obtendremos que $ \sigma_{n}(k)=\sum_{\ell=1}^{k}\binom{n}{\ell}\cdot\gamma_{n}(k-\ell)=\sum_{\ell=1}^{k}\binom{n}{\ell}\cdot\left(\binom{n+k-\ell-1}{n}-\sigma_{n}(k-\ell)\right)$ y podemos evaluar $\sigma_n(k)$ de forma recusada.

Lo siento si mi inglés es malo, no es mi primer idioma :P

Answer 1

Nota: el post original dice "entero positivo" y esta solución está dedicada a esa pregunta, no a la actual.

Es igual al número de soluciones positivas menos el número de soluciones positivas todas al menos $2$ .

El primer número es $$n-1\choose k-1 $$

ya que es lo mismo que colocar $k-1$ palos en el $n-1$ espacios entre $n$ bolas

Para el segundo número,

nota que $a_1+a_2+...+a_k=n$ donde cada $a_i\geq 2$ es lo mismo que $b_1+b_2+...+b_k=n-k$ donde cada $b_i=a_i-1$ y $b_i\geq 1$ .

Así que el número total es

$${n-1\choose k-1} - {n-k-1\choose k-1}$$

Editado para incluir el cero: Si se permite el cero, entonces tenemos que sumar todos los casos para diferentes números de ceros y creo que no hay una fórmula limpia.

Con $0$ ceros: ${k \choose 0}({n-1\choose k-1} - {n-k-1\choose k-1})$

Con $1$ ceros: ${k \choose 1}({n-1\choose k-2} - {n-k-1\choose k-2})$

Con $3$ ceros: ${k \choose 2}({n-1\choose k-3} - {n-k-1\choose k-3})$

Y así sucesivamente. La suma será entonces

$$\sum_{i=0}^{k-1}{k \choose i}({n-1\choose k-1-i} - {n-k-1\choose k-1-i})$$

Answer 2

La respuesta es

$$2^{n-1}-F_{n-1}$$

donde $F_k$ es la secuencia de Fibonacci $F_0=0$ , $F_1=1$ y $F_{k+1}=F_k+F_{k-1}$ . La secuencia comienza $1,1,3,6,13,27,\ldots$ .

A probar esta es la fórmula correcta, tenga en cuenta que sin la restricción de tener al menos un $1$ la respuesta es simplemente $2^{n-1}$ : Es decir, para obtener una descomposición de $n$ , empezar con $(1+1+\cdots+1+1)$ donde usted tiene $n-1$ signos de adición, y luego colocar o no colocar un par de paréntesis hacia afuera alrededor de cada $+$ signo, es decir, convertir algunos $+$ 's en $)+($ y así agrupar los lotes de $1$ 's. Por lo tanto, tenemos que contar (y restar de $2^{n-1}$ ) el número de descomposiciones de $n$ que no tienen algún $1$ 's.

Ahora bien, si $n=x_1+x+x_2+\cdots+x_k$ no tiene $1$ y $x_k\ge3$ entonces $n-1=x_1+x_2+\cdots+(x_k-1)$ no tiene $1$ tampoco, mientras que si $x_k=2$ entonces $n-2=x_1+x_2+\cdots+x_{k-1}$ no tiene $1$ 's. En consecuencia, el número de descomposiciones de $n$ sin ninguna $1$ es la suma del número de descomposiciones de $n-1$ y $n-2$ sin ninguna $1$ es decir, satisface la recursión de Fibonacci $c_n=c_{n-1}+c_{n-2}$ . Y como $c_1=0$ y $c_2=1$ son fáciles de ver, obtenemos exactamente los números de Fibonacci $F_{n-1}$ .

Observación: Al principio encontré la fórmula general calculando los seis primeros casos de forma explícita, por ejemplo $3$ tiene $3$ composiciones con al menos una $1$ :

$$1+1+1\quad1+2\quad2+1$$

mientras que $6$ tiene $27$ :

$$ \underbrace{1+1+1+1+1+1}_1\quad\underbrace{1+1+1+1+2}_5\quad\underbrace{1+1+2+2}_6\quad\underbrace{1+2+3}_6\\\underbrace{1+1+1+3}_4\quad\underbrace{1+1+4}_3\quad\underbrace{1+5}_2\qquad1+5+6+6+4+3+2=27$$

(Los números bajo los paréntesis cuentan los distintos arreglos de los números sobre los paréntesis, por ejemplo el primero $6$ es ${4\choose2}$ mientras que el segundo $6$ es $3!$ .) La consulta de la OEIS dio la respuesta en A099036 . Es posible que hubiera podido encontrar la fórmula general sin consultar la OEIS si hubiera pensado en restar los seis primeros términos de las potencias correspondientes de $2$ correspondiente a la respuesta de descomposición relativamente simple "sin restricciones", $1,2,4,8,16,32,\ldots$ . Hacerlo deja $0,1,1,2,3,5,\ldots$ que un ojo experimentado detecta fácilmente como la secuencia de Fibonacci. Sin embargo, mi costumbre es ir directamente a la OEIS en cuanto tengo una secuencia en la mano.