Bijection between “circularly nonconsecutive” permutations and permutations with one fixed point

combinatorial-proofscombinatoricsinclusion-exclusionpermutations

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]$.

Best Answer

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.

Related Question