Bijection between "circularly nonconsecutive" permutations and permutations with one fixed point

Question

A permutation $\pi$ of $[n]:=\{1,2,\dots,n\}$ is called circularly nonconsecutive (CNC) if $\pi_{i+1}-\pi_i\neq 1$ for all $i=1,2,\dots,n-1$, and furthermore $\pi_1-\pi_n\ne 1$. In other words, $i+1$ does not occur immediately after $i$, for any $i\in \{1,2,\dots,n-1\}$, where we consider the first entry of the permutation as occurring immediately after the last in a circular fashion.

There are $3$ CNC permutations of $[3]$: $(1,3,2)$, and its two rotations, $(3,2,1)$ and $(2,1,3)$. In general, all $n$ rotations of a CNC permutation are also CNC.

It can be shown that the number of CNC permutations is equal to the number of permutations with exactly one fixed point. You can count both of these quantities with an inclusion exclusion argument and find the the resulting expressions are coincidentally the same, both equal to $$n!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}$$

Can you give a bijection between CNC permutations of $[n]$ and permutations of $[n]$ with one fixed point?

Equivalently, permutations with one fixed point can be partitioned into $n$ equal classes based on which point is fixed, just like CNC permutations can be partitioned into circular rotation classes. So it would be equivalent to find a bijection between CNC permutations for which $\pi_n=n$ and permutations where the only fixed point is $\pi_n=n$. The latter is obviously in bijection with derangements of $[n-1]$.

Answer 1

OK, I found the answer in a wonderful blog post by Mike Spivey. It is implied by the following discussion, which is a better way of viewing the problem.

From now on, a succession in a permutation is an index $i\in \{1,\dots,n-1\}$ for which $\pi({i+1})=\pi(i)+1$. Furthermore, an extended succession is defined as follows; given a permutation $\pi:\{1,\dots,n\}\to \{1,\dots,n\}$, extend this to a function $\pi':\{0,\dots,n\}\to\{0,\dots,n\}$ by setting $\pi'(0)=0$ and $\pi'(i)=\pi(i)$ for $i\in \{1,\dots,n\}$. Then an extended succession of $\pi$ is defined to be a succession of $\pi'$. The only difference between the two concepts is that $\pi(1)=1$ counts as an extended succession, but not a succession.

The reason for this funny definition is that extended successions behave just like fixed points, in that for any $k\in \{0,\dots,n\}$, the number of permutations with $k$ fixed points equals the number of permutations with $k$ extended succesions. This is proven with the following bijection. In the rightmost column, $i$ represents a generic fixed point greater than $1$. Note how the fixed points, $3$ and $6$, become successions in the result. You also need to show that if $1$ is a fixed point, that it ends up at the beginning of the result (so it is an extended succession).

Bijection Step	Example	Effect on fixed points
Write $\pi$ in one line notation.	$[2,5,\def\r{\color{red}}\r3,1,4,\r 6]$	$\pi(i)=i$
Move each entry of $\pi$ one step to the left, and the first entry to the end, to get a new permutation in one-line notation.	$[5,\def\r{\color{red}}\r3,1,4,\r 6,2]$	$\pi(i-1)=i$
Write the result from the last step in cycle notation, so that each cycle has its largest element written last, and the cycles decrease in order of largest element.	$(2,3,1,5,6)(4)$	$i$ follows $i-1$ in a cycle.
Erase the parentheses, and interpret the result in one-line notation.	$[2,\r 3,1,5,\r 6,4]$	$i$ succeeds $i-1$.

Answer 2

Here's a potentially-unsatisfying answer, which I'd post in a comment if I had enough reputation to comment.

One way to see that the number of CNC permutations of $[n]$ with $\pi_n=n$ is equal to the number of derangements of $[n-1]$ is to note that both counting functions satisfy the same recurrence relation $f(n)=(n-2)f(n-1)+(n-2)f(n-2)$.

For CNC permutations, these two terms correspond to the two cases for whether our permutation of $[n]$ remains CNC after deleting the $n$ from the end. If it does, the resulting permutation of $[n-1]$ is one of the $n-2$ nontrivial rotations of an arbitrary CNC permutation of $[n-1]$ that ends with $n-1$. Otherwise, our permutation of $[n]$ is of the form $(a+1,\dots,a,n)$, where the $(\dots,a)$ part is an arbitrary CNC permutation of $[n-2]$ (after subtracting one from each value larger than $a$).

Similarly for derangements of $[n-1]$, the two terms correspond to the two cases for whether the $n-1$ is in a 2-cycle. If it's not, our derangement is obtained by splicing the $n-1$ into a cycle in an arbitrary derangement of $[n-2]$ (after any of its $n-2$ elements). Otherwise, our derangement of $[n-1]$ is obtained by pairing the $n-1$ with an arbitrary element of $[n-2]$ and choosing an arbitrary derangement of the remaining $n-3$ elements.

Based on these observations, we could recursively define the desired bijection (basically identifying each permutation with a path through the decision tree used to build it), but I'm not sure this would reveal any more interesting structure.