Me encontré con la secuencia A000255 . $a(n)$ cuenta las permutaciones de $[1,...,n+1]$ que no tiene ninguna subcadena $[k,k+1]$
Me resulta difícil probarlo. ¿Pueden dar alguna pista sobre cómo resolver el problema?
Respuesta
¿Demasiados anuncios?
La recurrencia es $a(n)=na(n-1)+(n-1)a(n-2)$ El primer término es el número de formas de insertar $n+1$ en una permutación propia de $[1,\ldots,n]$ -puedes ponerlo en cualquier lugar excepto después de $n$ . El segundo cuenta las formas de tener una permutación de $[1,\ldots,n]$ con exactamente un par $[k,k+1]$ que luego se rompe poniendo $n+1$ entre ellos. Usted elige qué número será $k$ (para ser seguido por $k+1$ ), pero no puede ser $n$ . A continuación, enlace $k$ y $k+1$ como un par y hacer una permutación adecuada (de $n-1$ artículos).
