Número de vías para llegar a la planta baja en $n$ pasos

Question

Dado un número entero $n$ que es el número de escalones que hay entre el primer piso y la planta baja de un edificio. Podemos $1$ renunciar, o $2$ renunciar, o $3$ Retírate. Sin embargo, podemos $3$ baja como máximo una vez. En otras palabras, a $3$ paso se puede hacer en cualquier momento, pero sólo una vez. Tenemos que encontrar el número de maneras de llegar a la planta baja.

Pensé que la solución es simple:

$f[n] = f[n-1]+f[n-2]+f[n-3]$

Sin embargo, no obtengo la respuesta correcta. ¿Qué puede estar mal?

Answer 1

Sea $f(n,k)$ denotan el número de formas de llegar a la planta baja desde el $n$ -ésimo paso, dando tres pasos a la vez exactamente $k$ veces.

Entonces la recurrencia que se obtiene es $$f(n,k) = f(n-1,k) + f(n-2,k) + f(n-3,k-1)$$

con valores iniciales adecuados, y la respuesta que buscas es $f(10,0) + f(10,1)$ .

Answer 2

El problema puede atacarse utilizando funciones generadoras (p. ej. aquí ).

---

Podemos tomar $3$ pasos se mueven después de la $k$ -ésima etapa. Es decir, dividir todo el recorrido en el primer $k$ pasos, uno $3$ pasos se mueven y $n-k-3$ pasos. Entonces, para la primera parte, el número de soluciones enteras de $$x_1+2x_2=k, x_1\geq0,x_2\geq0 \tag{1}$$ es el número de maneras de recorrer esos $k$ pasos con $1$ ou $2$ pasos se mueve. Para el último - el número de soluciones enteras de $$x_3+2x_4=n-k-3, x_3\geq0,x_4\geq0 \tag{2}$$ es el número de maneras de recorrer el último $n-k-3$ pasos con $1$ ou $2$ pasos se mueve.

Todos estos for $k=0$ a $n-3$ .

---

En general, el número de soluciones enteras para $$x_1+2x_2=k, x_1\geq0,x_2\geq0 \tag{3}$$ es el coeficiente de $x^k$ de la función generadora $$(1+x+x^2+...)(1+x^2+x^4+...+x^{2n}+...)=\frac{1}{1-x}\cdot \frac{1}{1-x^2}=\\ \frac{1}{2(1-x)^2} + \frac{1}{4(1-x)} + \frac{1}{4(1+x)}=...$$ que es $$...=\frac{1}{2}\left(\sum\limits_{n=0}(n+1)x^n\right)+ \frac{1}{4}\left(\sum\limits_{n=0}x^n\right)+ \frac{1}{4}\left(\sum\limits_{n=0}(-1)^nx^n\right)=\\ \sum\limits_{n=0}\left(\frac{n+1}{2}+\frac{1+(-1)^n}{4}\right)x^n$$ y el coeficiente es $$\frac{k+1}{2}+\frac{1+(-1)^k}{4} \tag{4}$$

---

Volver $(1)$ y $(2)$ tenemos $$\frac{k+1}{2}+\frac{1+(-1)^k}{4} \text{ and } \frac{n-k-3+1}{2}+\frac{1+(-1)^{n-k-3}}{4}$$ o $$\frac{k+1}{2}+\frac{1+(-1)^k}{4}+\frac{n-k-3+1}{2}+\frac{1+(-1)^{n-k-3}}{4}=\\ \frac{n-1}{2}+\frac{2+(-1)^k+(-1)^{n-k-3}}{4}=\\ \frac{n}{2}+\frac{(-1)^k+(-1)^{n-k-3}}{4}$$ y finalmente $$\sum\limits_{k=0}^{n-3}\left(\frac{n}{2}+\frac{(-1)^k+(-1)^{n-k-3}}{4}\right)=\\ \frac{n(n-2)}{2}+\sum\limits_{k=0}^{n-3}\left(\frac{(-1)^k+(-1)^{n-k-3}}{4}\right)=\\ \frac{n(n-2)}{2}+\frac{1}{2}\left(\sum\limits_{k=0}^{n-3}(-1)^k\right) \tag{5}$$ A ver si puedes simplificarlo más.

Answer 3

Empezaría por calcular el número de formas de bajar $n$ pasos, moviéndose sólo uno o dos pasos a la vez. Tenemos $$\begin{align} a_0,&=1\\ a_1,&=1\\ a_2,&=2\\ a_n&=a_{n-1}+a_{n-2},\,n\geq2 \end{align}$$ para que el $a_n$ son los números de Fibonacci, $F_n.$

Ahora dejemos que $b_n$ sea el número de maneras de bajar $n$ pasos, como se describe en el problema. Podemos no hacer ninguna $3$ -paso se mueve en absoluto, o podemos mover hacia abajo $k$ pasos, luego haga un $3$ -paso, luego mueve el resto $n-k-3$ pasos. Así,

$$b_n=F_n+\sum_{k=0}^{n-k-3}F_kF_{n-k-3}$$

No sé si se puede simplificar la suma.