OEIS A000255 recursion.

Question

I encountered the sequence A000255. $a(n)$ counts permutations of $[1,...,n+1]$ having no substring $[k,k+1]$

I am finding difficulty in proving it. Can you please give any clues or hints on how to attack the problem?

Answer 1

The recurrence is $a(n)=na(n-1)+(n-1)a(n-2)$ The first term is the number of ways to insert $n+1$ into a proper permutation of $[1,\ldots,n]$-you can put it anywhere except after $n$. The second counts the ways to have a permutation of $[1,\ldots,n]$ with exactly one pair $[k,k+1]$, which you then break up by putting $n+1$ between them. You choose which number will be $k$ (to be followed by $k+1$), but it can't be $n$. Then link $k$ and $k+1$ as a pair and make a proper permutation (of $n-1$ items).