Permutations with no consecutive elements

Permutations with no consecutive elements

I was working on something this week that made me wonder how many permutations break up all consecutive elements. For example, if we’re looking at permutations of abcde then acebd counts, but acdbe does not. I’d like to count the number of such permutations, and estimate for large N the number of permutations of N elements with no consecutive terms. A brief search lead to OEIS sequence A000255 which gives a recursive formula for the answer. Befo…