una relación de recurrencia para la permutación de la montaña

Question

No sé por dónde empezar. ¿Puede dar algunas pistas?

Answer 1

Para $M(n)$ es evidente que el número $1$ debe estar situado en uno de los dos extremos de la permutación. Entonces queda $\{2,3,\ldots,n\}$ que también hay que colocar en una disposición de montaña. Esto equivale a colocar $\{1,2,\ldots,n-1\}$ en un arreglo de montaña, por lo que el número de formas de hacerlo es $M(n-1)$ . A partir de este análisis tenemos

$$M(n)=2M(n-1),\qquad n\ge 2 \tag{1}$$

Además, como sólo hay una disposición de un solo número, tenemos la condición inicial

$$M(1)=1$$

La solución a esta recurrencia es

$$M(n)=2^{n-1}$$

ya que la ecuación (1) define básicamente una secuencia geométrica con $r=2$ .