Combinatorial proof of an identity between restricted counts of permutations and derangements

Question

In an answer to Counting permutations with given condition, I showed that the number of permutations of $k$ elements that satisfy $\sigma(i+1)\ne\sigma(i)+1$ is $\frac{!(k+1)}k$, which is the number of derangements of $k+1$ elements with one value fixed, e.g. $\tau(k+1)=1$. I did this by showing that these numbers satisfy the same recurrence relation with the same initial values, but it seems one should be able to exhibit an explicit bijection between the sets. Do you see one?

Answer 1

We will sketch one way to define a bijection between these sets, relying heavily on the bijection given in http://arxiv.org/abs/1308.5459:

Let $T_n=\{\sigma\in S_n: \sigma(i+1)\ne \sigma(i)+1$ for $1\le i\le n-1\}$,

let $U_n=\{\sigma\in S_n: \sigma(i)\ne i$ for $1\le i\le n-1\}$, and

let $V_n=\{\tau\in S_{n+1}: \tau(i)\ne i$ for $1\le i\le n$ and $\tau(n+1)=1\}$.

$\textbf{1)}$ Define a bijection $h:V_n\rightarrow U_n$ as follows:

If $\tau\in V_n$ with $\tau(1)\ne n+1$, let $h(\tau)=\sigma$ where $\sigma(i)=\begin{cases}\tau(i)&\mbox{, if }\tau(i)\ne n+1\\1&\mbox{, if }\tau(i)=n+1\end{cases}$

If $\tau\in V_n$ with $\tau(1)= n+1$, let $h(\tau)=\sigma$ where $\sigma(i)=\begin{cases}\tau(i+1)-1&\mbox{, if }1\le i\le n-1\\n&\mbox{, if }i=n\end{cases}$

$\textbf{2)}$ Now we can use the bijection $g:U_n\rightarrow T_n$ defined by Diaconis, Evans, and Graham:

Define $\rho\in S_n$ by $\rho(i)=i+1 \pmod{n}$ for $1\le i\le n$.

For $\pi\in S_n$, write $\pi$ in its cycle decomposition as $\pi=(a_1,\cdots, a_r)(b_1,\cdots, b_s)\cdots(c_1,\cdots,c_t)$

$\hspace{.78 in}$where each cycle starts with its least element and $a_1>b_1>\cdots>c_1$, and

define $F(\pi)$ to be the permutation $a_1\cdots a_rb_1\cdots b_s\cdots c_1\cdots c_t$ in $S_n$.

For any $\sigma\in U_n$, define $g:U_n\rightarrow T_n$ by $g(\sigma)=\left(F(\rho\sigma)\right)^{-1}$.

Then $g\circ h: V_n\rightarrow T_n$ is a bijection.

---

Here are two examples:

$\textbf{a)}$ Let $\tau\in V_9$ be given by $\tau=\begin{pmatrix}1&2&3&4&5&6&7&8&9&10\\5&7&9&8&6&10&4&3&2&1\end{pmatrix}$

Then $\sigma=h(\tau)=\begin{pmatrix}1&2&3&4&5&6&7&8&9\\5&7&9&8&6&1&4&3&2\end{pmatrix}$,

so $\rho\sigma=\begin{pmatrix}1&2&3&4&5&6&7&8&9\\6&8&1&9&7&2&5&4&3\end{pmatrix}=(5,7)\;(1,6,2,8,4,9,3)$.

Then $F(\rho\sigma)=\begin{pmatrix}1&2&3&4&5&6&7&8&9\\5&7&1&6&2&8&4&9&3\end{pmatrix}$,

so $g(\sigma)=\left(F(\rho\sigma)\right)^{-1}=\begin{pmatrix}1&2&3&4&5&6&7&8&9\\3&5&9&7&1&4&2&6&8\end{pmatrix}\in T_9$

$\textbf{b)}$ Let $\tau\in V_9$ be given by $\tau=\begin{pmatrix}1&2&3&4&5&6&7&8&9&10\\10&4&7&9&3&5&6&2&8&1\end{pmatrix}$

Then $\sigma=h(\tau)=\begin{pmatrix}1&2&3&4&5&6&7&8&9\\3&6&8&2&4&5&1&7&9\end{pmatrix}$,

so $\rho\sigma=\begin{pmatrix}1&2&3&4&5&6&7&8&9\\4&7&9&3&5&6&2&8&1\end{pmatrix}=(8)\;(6)\;(5)\;(2,7)\;(1,4,3,9)$.

Then $F(\rho\sigma)=\begin{pmatrix}1&2&3&4&5&6&7&8&9\\8&6&5&2&7&1&4&3&9\end{pmatrix}$,

so $g(\sigma)=\left(F(\rho\sigma)\right)^{-1}=\begin{pmatrix}1&2&3&4&5&6&7&8&9\\6&4&8&7&3&2&5&1&9\end{pmatrix}\in T_9$