¿Cuántas permutaciones de $1,2,\cdots, n$ contienen exactamente $n-2$ dígitos que son más pequeños que el dígito de inmediato a su derecha?
Mi solución procedió con la recursividad. Tiene alguna posibilidad de estar equivocado.
Llamamos a todas esas permutaciones buena permutaciones. Llamamos a un dígito bueno si es que son más pequeños que el siguiente dígito. Deje $f(n)$ denotar el número de permutaciones de $1,2, \cdots ,n$. Tenga en cuenta que una buena permutación tiene exactamente $n-2$ dígitos.
Considere la posibilidad de cualquier buen permutación de $1,2,\cdots ,n+1$. Retire $1$ de la permutación. Tenga en cuenta que esto puede disminuir el número de dígitos a la mayoría de los $1$. Tenemos dos casos :
$1)$Buen número de dígitos que siguen siendo los mismos:
Desde la original de permutación fue buena, la nueva permutación tiene exactamente $(n+1)-2=n-1$ buena dígitos, pero sólo ha $n$ dígitos. Pero $n+1$ nunca puede ser un buen dígitos, ya que nunca puede ser menor que cualquier otro dígito. Por lo tanto, después de la eliminación de $1$, cada una de las $2,3,4, \cdots ,n$ es una buena cifra. Pero la única permutación es $2$ $3$ $\cdots$ $n+1$. Ahora nota que poner de nuevo las $1$ no aumentar o cambiar el número de dígitos (a menos que ponerlo en el inicio). Por lo tanto, no son exactamente $n$ lugares donde: $1$ puede ir.
$2)$Buen número de dígitos que se disminuye:
Dado que el número de dígitos puede disminuir en la mayoría de las $1$, en este caso, la nueva permutación tiene exactamente $n-2$ buena dígitos. Pero no son exactamente $f(n)$ de estas permutaciones. Cuando nos vuelve a poner $1$, se puede colocar en cualquiera de las siguientes posiciones, porque entonces el número de dígitos no aumenta:
A) Después de un buen dígitos en sí
B) al final
Hay dos lugares para poner $1$ entonces. Así que hay $2f(n)$ permutaciones en este caso.
La combinación de los, nos, $f(n+1)=2f(n)+n$
Esto es correcto?
Gracias de antemano
