¿De cuántas maneras distintas puede $133$ ser escrito como suma de $1s$ $2s$

Question

Desde la semana pasada he estado trabajando en una forma, cómo se suma $1$ $2$ a ha $133$.

Así, por ejemplo podemos tener $133$ $1s$ o $61$ $s$2 y uno y así sucesivamente. Mirando hacia atrás, en el ejemplo: si se suma: $1 + 1... + 1 = 133$ sólo hay una manera. Pero para el segundo no se $131$ formas posibles. Y tengo que hacer esto para cada combinación posible. Estoy pegado con ella y no tengo idea alguna sobre cómo empezar.

Todas las ideas o métodos que podría utilizar chicos?

Answer 1

Para $133$ hay $1$ resultado.

Para $131$ queridos y $1$ dos hay $132$ de los resultados.

Para $129$ queridos y $2$ dos hay ${131 \choose 2}$ resultado.

Por lo tanto, hay ${133 \choose 0}+{133-1 \choose 1}+{133-2 \choose 2}+...+{133-66 \choose 66}$ de los resultados, que es, como se señala por Jack D'Aurizio, la 134a número Fibonacci (consulte el número Fibonacci Uso en matemáticas - artículo de WikiPedia.)

Answer 2

Sugerencia: tenga en cuenta que el primer dígito de la suma es $1$ o $2$, por lo que el número de maneras de obtener una suma de $133$ es el número de maneras de obtener una suma de $132$ (añadir uno al principio) más el número de maneras de obtener una suma de $131$ (agregar dos al principio).

---

Vamos a hacerlo con el número de maneras de llegar a $5$.

Si el primer número en la suma es $2$, las posibilidades son $2+(2+1); 2+(1+2); 2+(1+1+1)$ que es el número de maneras de llegar a la total $3$ (ver los bits entre paréntesis) - que es de tres.

Si el primer dígito es un $1$, luego tenemos a $1+(2+2); 1+(2+1+1); 1+(1+2+1); 1+(1+1+2); 1+(1+1+1+1)$ - del total en cada soporte es $4$ y hay cinco maneras de conseguir.

Así llegamos a $5$ en tres y cinco = ocho maneras.

Se puede ver que íbamos a llegar a la total $6$ en cinco ( $2$ ) y ocho ($1$) = trece maneras?

Answer 3

Voy a demostrar que esto es en general, no sólo para 133

Deje $P_i$ ser la solución a este problema de número de $i$. Es decir, la respuesta a la pregunta exacta es $P_{133}$

Deje $F_i$ $ith$ número Fibonacci.

Prueba por inducción que $\forall i\geq1:P_i = F_{i+1}$

Base:
$i=1$ Puede hacer con un solo 1. Por lo $P_1 = 1 = F_2$

Hipótesis:
Suponga que se tiene para $i=k$ $i=k-1,k>1$

Paso: Mostrar que $P_k = F_{k+1} \rightarrow P_{k+1} = F_{k+2}$
De todas las soluciones a $P_k$, se puede agregar 1 y es una solución a $P_{k+1}$.
De todas las soluciones a $P_{k-1}$, podemos agregar 2 y es una solución a $P_{k+1}$
Esta es una lista exhaustiva de las formas de hacer de las soluciones a $P_{k+1}$, al pasar de cualquier número menor, addings 1 y 2 de la voluntad de pasar a través de cualquiera de las $P_k$ o $P_{k-1}$

Por lo tanto
$P_{k+1} = P_k + P_{k-1} = F_{k+1} + F_k = F_{k+2}$ Por hipótesis

(Esto es un poco de un crudo de la prueba. Principalmente porque me refiero a $P_i$ como un número y un conjunto de soluciones. Pero creo que se obtiene el punto a través de)

Answer 4

Esto es esencialmente una explicación de Jack D'Aurizio la respuesta.

Deje $k$ el número de dos en dos, luego tenemos a $n-2k$. Hay entonces $$ \sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}=\sum_{k=0}^\infty\binom{n-k}{n-2k} $$ formas de escribir $n$ como una suma de unos y doses. Una forma de calcular este número es mirar a la generación de función. $$ \begin{align} \sum_{n=0}^\infty\sum_{k=0}^\infty\binom{n-k}{n-2k}x^n &=\sum_{k=0}^\infty x^{2k}\sum_{n=0}^\infty\binom{-k-1}{n-2k}(-x)^{n-2k}\\ &=\sum_{k=0}^\infty\frac{x^{2k}}{(1-x)^{k+1}}\\ &=\frac1{1-x}\frac1{1-\frac{x^2}{1-x}}\\ &=\frac1{1-x-x^2} \end{align} $$ Que es la generación de la función de $F_{n+1}$, los números de Fibonacci compensado por $1$. Establecimiento $n=133$, obtenemos $$ F_{134}=4517090495650391871408712937 $$

Answer 5

Sugerencia: $$[x^{133}]\,\frac{1}{1-(x+x^2)}=F_{134}=4517090495650391871408712937.$$

Más información y el contexto se pueden encontrar en las preguntas aquí y aquí. Para ser claros, el número queremos calcular está dado por el coeficiente de $x^{133}$ en la suma: $$1+(x+x^2)+(x+x^2)^2+(x+x^2)^3+\ldots = \frac{1}{1-(x+x^2)}$$ y puesto que los coeficientes de Taylor $a_n$ de la función $$ f(x)=\frac{1}{1-x-x^2}=\sum_{n\geq 0}a_n\,x^n\tag{1}$$ obedecer la relación de recurrencia: $$ a_{n+2}=a_{n+1}+a_{n} $$ (para probarlo, basta con multiplicar ambos lados de $(1)$$1-x-x^2$), la solución está dada por un número Fibonacci, ya que $a_0=1=F_1$$a_1=1=F_2$.