Una relación de recurrencia no es demasiado duro. Considere la posibilidad de un aceptable permutación $\pi$$[n+1]$. Si se quita la $n+1$, en general existen dos posibilidades para el resultado de permutación de $[n]$.
- Puede ser aceptable.
- Puede ser inaceptable, pero sólo porque el número que fue inmediatamente a la izquierda de $n+1$ $\pi$ es uno menos que el número que se fue inmediatamente a la derecha de $n+1$$\pi$.
Hay $f(n)$ aceptable permutaciones de $[n]$, e $n+1$ puede ser insertado en cualquier de ellos en cualquiera de las $n$ de los espacios que no están inmediatamente a la derecha de la $n$, por lo que estas cuentas para $nf(n)$ aceptable permutaciones de $[n+1]$. Sólo queda contar las permutaciones de $[n]$ que son inaceptables en exactamente la misma posición.
Supongamos que $\sigma$ es una permutación, y en ella $k$ $k+1$ son adyacentes en ese orden. Retire $k+1$ y la disminución de todos los restantes elementos de $\sigma$ que es mayor que $k$$1$; el resultado es aceptable permutación de $[n-1]$. Por el contrario, si usted comienza con un aceptable permutación de $[n-1]$, elija cualquiera de los $k$ en el aumento de $1$ cada elemento que es mayor que $k$, e inserte $k+1$ inmediatamente a la derecha de $k$, se obtiene una permutación de $[n]$ que es inaceptable en exactamente la misma posición. Hay $n-1$ opciones para $k$, por lo que hay $(n-1)f(n-1)$ permutaciones de $[n]$ que son inaceptables en exactamente la misma posición.
Juntando las piezas, podemos ver que $f(n+1)=nf(n)+(n-1)f(n-1)$. (Esto difiere de la recurrencia dada para OEIS A000255, se menciona en los comentarios, ya que la indexación es apagado por $1$.)
