Descent sets of cyclic permutations
We present a bijection between cyclic permutations of {1,2,...,n+1} and permutations of {1,2,...,n} that preserves the descent set of the first n entries and the set of weak excedances. This non-trivial bijection involves a Foata-like transformation on the cyclic notation of the permutation, followed by certain conjugations. We also give an alternate derivation of the consequent result about the equidistribution of descent sets using work of Gessel and Reutenauer. Finally, we prove a conjecture of the author in [SIAM J. Discrete Math. 23 (2009), 765-786] and a conjecture of Eriksen, Freij and Wästlund.
\section{Introduction}\label{sec:intro}

\subsection{Permutations, cycles, and descents}

Let $[n]=\{1,2,\dots,n\}$, and let $\S_n$ denote the set of permutations of $[n]$. We will use both the one-line notation of $\pi\in\S_n$
as $\pi=\pi(1)\pi(2)\dots\pi(n)$ and its decomposition as a  a product
of cycles of the form $(i,\pi(i),\pi^2(i),\dots,\pi^{k-1}(i))$ with $\pi^k(i)=i$.
For example, $\pi=2517364=(1,2,5,3)(4,7)(6)$. Sometimes it will be convenient to write
each cycle starting with its largest element and order cycles by increasing first element, e.g., $\pi=(5,3,1,2)(6)(7,4)$.

We denote by $\C_n$ the set of permutations in $\S_n$ that consist of one single cycle of length~$n$. We call these {\em cyclic permutations} or {\em $n$-cycles}.
For example, $$\C_3=\{(1,2,3),(1,3,2)\}=\{231,312\}.$$ It is clear that $|\C_n|=(n-1)!$.

Given $\pi\in\S_n$, let $D(\pi)$
denote the {\em descent set} of $\pi$, that is,
$$D(\pi)=\{i\,:\,1\le i\le n-1,\ \pi(i)>\pi(i+1)\}.$$
The descent set can be defined for any sequence of integers $a=a_1 a_2 \dots a_n$
by letting $D(a)=\{i\,:\,1\le i\le n-1,\ a_i>a_{i+1}\}$.

The main result of this paper, which we present in Section~\ref{sec:main}, is a bijection $\bij$
between $\C_{n+1}$ and $\S_n$ with the property that for every $(n+1)$-cycle $\pi$,
$$D(\pi(1)\pi(2)\dots\pi(n))=D(\bij(\pi)).$$
Despite the simplicity of the statement and the relatively natural description of $\bij$ that we will give, the proof that it is a bijection with the desired property is somewhat technical.

Let us introduce some notation. For $\pi\in\S_n$, let $\wt\pi$ be the permutation defined by $\wt\pi(i)=n+1-\pi(n+1-i)$ for $1\le i\le n$.
The cycle form of $\wt\pi$ can be obtained by replacing each entry $j$ with $n+1-j$ in the cycle form of $\pi$.
For $1\le i\le n-1$, we have that $i\in D(\wt\pi)$ if and only if $n+1-i\notin D(\pi)$.

We will write $I=\{i_1,i_2,\dots,i_k\}_<$ to indicate that the elements of $I$ are listed in increasing order.
Subsets $I\subseteq[n-1]$ are in bijective correspondence with compositions of $n$ via $=\{i_1,i_2,\dots,i_k\}\mapsto (i_1,i_2-i_1,\dots,i_k-i_{k-1},n-i_k)$. The partition of $n$ obtained by listing the parts of this composition
in non-increasing order is called the associated partition of $I$. For example, for $n=13$ and $I=\{3,5,8,12\}$, the associated partition is $(4,3,3,2,1)$.


\subsection{Related work}

Following the notation from~\cite{Eli}, let $\T^0_n$ be the set whose elements are $n$-cycles in one-line notation in which one entry has been replaced with $0$.
For example, $\T^0_3=\{031,201,230,012,302,310\}$. Since there are $n$ ways to choose what entry to replace, and the value of the replaced entry can be recovered by looking at the other entries,
it is clear that $|\T^0_n|=n!$. Note that if the $0$ in $\tau\in\T^0_n$ is in position $i$, then $i-1\in D(\tau)$ (if $i>1$) and $i\notin D(\tau)$.
It was conjectured in~\cite{Eli} that descent sets in $\T^0_n$ behave like descent sets in $\S_n$:

\begin{conj}[\cite{Eli}]\label{conj:Eli} For any $n$ and any $I\subseteq[n-1]$,
$$|\{\tau\in\T^0_n\,:\,D(\tau)=I\}|=|\{\sigma\in\S_n\,:\,D(\sigma)=I\}|.$$
\end{conj}

In Section~\ref{sec:consequences} we prove this conjecture as Corollary~\ref{cor:Elishift}, along with other consequences of our main bijection.

There is some work in the literature relating the cycle structure of a permutation with its descent set.
Gessel and Reutenauer~\cite{GR} showed that the number of permutations with given cycle structure and descent set can be expressed as a product of certain characters of the symmetric group.
They also gave a statistic-preserving bijection between words and multisets of necklaces. In Section~\ref{sec:related} we discuss how their work relates to ours, and how their methods can be used to prove some of our results non-bijectively.

More recently, Eriksen, Freij and W\"astlund~\cite{EFW} studied descent sets of derangements. Recall that derangements are permutations with no fixed points.
In~\cite[Problem~9.3]{EFW}, the authors pose the following question:

\begin{prob}[\cite{EFW}]\label{prob:EFW} For any two subsets $I,J\subseteq[n-1]$ with the same associated partition, give a bijection between derangements of $[n]$ whose descent
set is contained in $I$ and derangements of $[n]$ whose descent set is contained in $J$.
\end{prob}

At the end of Section~\ref{sec:related} we solve this problem by giving a bijection based on the work of Gessel and Reutenauer~\cite{GR}.

\section{The main result}\label{sec:main}

\begin{theorem}\label{thm:bij} For every $n$ there is a bijection $\bij:\C_{n+1}\rightarrow\S_n$ such that if $\pi\in\C_{n+1}$ and $\sigma=\bij(\pi)$, then
$$D(\pi)\cap[n-1]=D(\sigma).$$
\end{theorem}

We start this section defining the map $\bij:\C_{n+1}\rightarrow\S_n$ and giving some examples. Next we describe a map $\inv:\S_n\rightarrow\C_{n+1}$. Finally we
prove that $\inv=\bij^{-1}$ and that $\bij$ preserves the descent set of the first $n$ entries.

\subsection{The map $\bij$}

Given $\pi\in\C_{n+1}$, write it in cycle form with $n+1$ at the end, i.e., $\pi=(t_1,t_2,\dots,t_n,n+1)$. Let $t_1=t_{i_1}<t_{i_2}<\dots<t_{i_r}<t_{i_{r+1}}=n+1$ be the left-to-right maxima of the
sequence $t_1,t_2,\dots,t_n,n+1$. Let $$\sigm=(t_{1},t_2,\dots,t_{i_2-1})(t_{i_2},t_{i_2+1},\dots,t_{i_3-1})\cdots(t_{i_r},t_{i_r+1},\dots,t_n).$$ To simplify notation, let $a_j=t_{i_j}$ and $b_j=t_{i_{j+1}-1}$ for $1\le j\le r$,
so \beq\label{eq:sigm}\sigm=(a_1,\dots,b_1)(a_2,\dots,b_2)\cdots(a_r,\dots,b_r).\eeq
To obtain $\bij(\pi)$ we make some switches in the cycle form of $\sigm$, that we describe next.
At any stage of the algorithm we denote by $\Gamma_i$ the $i$-th cycle of $\sigm$, with the cycles written from left to right in the same order as in~(\ref{eq:sigm}).
The terms {\em left}, {\em right}, {\em first} (or {\em leftmost}) and {\em last} (or {\em rightmost}) will always assume that the entries within each cycle are also written in this order.
Whenever we have two adjacent elements $s$ and $t$ in a cycle, with $s$ immediately to the left of $t$,
we will say that $s$ {\em precedes} $t$.
For $1\le x,y\le n$, let $P(x,y)$ be the condition
$$\pi(x)>\pi(y) \ \textrm{ and }\  \sigm(x)<\sigm(y).$$
(For $x$ or $y$ outside of these bounds, $P(x,y)$ is defined to be false.)\ms

Repeat the following steps for $i=1,2,\dots,r-1$:
\bit
\item Let $z$ be the rightmost entry of $\Gamma_i$.
If $P(z,z+1)$ or $P(z,z-1)$ hold, let $\eps\in\{-1,1\}$ be such that $P(z,z+\eps)$ holds and $\sigm(z+\eps)$ is largest.
\item Repeat for as long as $P(z,z+\eps)$ holds:
\ben\renewcommand{\labelenumi}{\Roman{enumi}.}
\item\label{it:a} Switch $z$ and $z+\eps$ in the cycle form of $\sigm$.
\item\label{it:b} If the last switch did not involve the leftmost entry of $\Gamma_i$, let $x$ and $y$ be the elements preceding the switched entries.
If $|x-y|=1$, switch $x$ and $y$ in the cycle form of $\sigm$, and repeat step~II.
\item Let $z:=z+\eps$ (the new rightmost entry of $\Gamma_i$).
\een
\eit

Define $\bij(\pi)=\sigm$.

\begin{table}[htb]
$$\begin{array}{|c|c|c|c|c|c|c|}
\hline
\pi\in\C_5 & \sigma=\bij(\pi)\in\S_4 &  D(\pi)\cap[3]=D(\sigma) \\[2pt] \hline
(1,2,3,4,5) = 23451  & 1 2 3 4     & \emptyset \\ \hline
(2,1,3,4,5) = 31452  & 2 1 3 4     & \multirow{3}{*}{\{1\}}  \\
(3,2,1,4,5) = 41253  & 3 1 2 4     &   \\
(4,3,2,1,5) = 51234  & 4 1 2 3     &   \\ \hline
(1,3,2,4,5) = 34251  & 1 3 2 4     & \multirow{5}{*}{\{2\}}  \\
(1,4,3,2,5) = 45231  & 1 4 2 3     &  \\
(3,1,2,4,5) = 24153  & 2 3 1 4     &  \\
(3,1,4,2,5) = 45123  & 3 4 1 2     &  \\
(4,3,1,2,5) = 25134  & 2 4 1 3     &  \\ \hline
(1,2,4,3,5) = 24531  & 1 2 4 3     & \multirow{3}{*}{\{3\}}  \\
(2,4,1,3,5) = 34512  & 1 3 4 2     &  \\
(4,1,2,3,5) = 23514  & 2 3 4 1     &  \\ \hline
(2,3,1,4,5) = 43152  & 3 2 1 4     & \multirow{3}{*}{\{1,2\}}\\
(2,4,3,1,5) = 54132  & 4 2 1 3     & \\
(4,2,3,1,5) = 53124  & 4 3 1 2     & \\ \hline
(1,4,2,3,5) = 43521  & 3 2 4 1     & \multirow{5}{*}{\{1,3\}}\\
(2,1,4,3,5) = 41532  & 2 1 4 3     & \\
(2,3,4,1,5) = 53412  & 4 2 3 1     & \\
(3,4,2,1,5) = 51423  & 4 1 3 2     &  \\
(4,2,1,3,5) = 31524  & 3 1 4 2     &  \\ \hline
(1,3,4,2,5) = 35421  & 1 4 3 2     &  \multirow{3}{*}{\{2,3\}}\\
(3,4,1,2,5) = 25413  & 2 4 3 1     &   \\
(4,1,3,2,5) = 35214  & 3 4 2 1     &  \\ \hline
(3,2,4,1,5) = 54213  & 4 3 2 1     & \{1,2,3\}\\
\hline
\end{array}$$
\caption{\label{tab:n4} The images by $\bij$ of all elements in $\C_5$.}
\end{table}


\begin{example}
Let $$\pi=(11,4,10,1,7,16,9,3,5,12,20,2,6,14,18,8,13,19,15,17,21)\in\C_{21}.$$
Finding the left-to-right maxima of the sequence, we get $$\sigm=(11,4,10,1,7)(16,9,3,5,12)(20,2,6,14,18,8,13,19,15,17).$$

Now we look at the first cycle, so $z=b_1=7$. Both $P(7,6)$ and $P(7,8)$ hold, but $\sigm(6)=14>13=\sigm(8)$, so $\eps=-1$.
Switching $7$ and $6$ we get $$\sigm=(11,4,10,1,{\bf 6})(16,9,3,5,12)(20,2,{\bf 7},14,18,8,13,19,15,17).$$
The entries preceding the switched ones are $1$ and $2$ so we switch them too: $$\sigm=(11,4,10,{\bf 2},6)(16,9,3,5,12)(20,{\bf 1},7,14,18,8,13,19,15,17).$$
Now $z=6$, and since $P(6,5)$ holds, we switch $6$ and $5$:
$$\sigm=(11,4,10,2,{\bf 5})(16,9,3,{\bf 6},12)(20,1,7,14,18,8,13,19,15,17).$$
The entries to their left are $2$ and $3$, so they need to be switched, and then the entries preceding these are $10$ and $9$, so they need to be switched as well:
$$\sigm=(11,4,{\bf 9},{\bf 3},5)(16,{\bf 10},{\bf 2},6,12)(20,1,7,14,18,8,13,19,15,17).$$

Since $P(5,4)$ is false, we now look at $\Gamma_2$, so $z=b_2=12$. Only $P(12,13)$ holds, so $\eps=1$ and we switch $12$ and $13$:
$$\sigm=(11,4,9,3,5)(16,10,2,6,{\bf 13})(20,1,7,14,18,8,{\bf 12},19,15,17).$$
Now $z=13$ and $P(13,14)$ holds, so we switch $13$ and $14$, the preceding entries $6$ and $7$, and also $2$ and $1$:
$$\sigm=(11,4,9,3,5)(16,10,{\bf 1},{\bf 7},{\bf 14})(20,{\bf 2},{\bf 6},{\bf 13},18,8,12,19,15,17).$$
Finally, $z=14$ and $P(14,15)$ holds, so we switch $14$ and $15$, and we stop here because $P(15,16)$ is false:
$$\bij(\pi)=\sigm=(11,4,9,3,5)(16,10,1,7,{\bf 15})(20,2,6,13,18,8,12,19,{\bf 14},17)\in\S_{20}.$$
In one-line notation,
\renewcommand{\tabcolsep}{0pt}
$$\begin{array}{cc*{2}{c@{\,\cdot\,}}*{4}{c@{\ }}*{3}{c@{\,\cdot\,}}*{2}{c@{\ }}*{4}{c@{\,\cdot\,}}c@{\ }c@{\,\cdot\,}c@{\ }c@{\,\cdot\,}c@{\ }c}
\pi&=&7&6&5&10&12&14&16&13&3&1&4&20&19&18&16&9&21&8&15&2&11\\
\bij(\pi)&=&7&6&5&9&11&13&15&12&3&1&4&19&18&17&16&10&20&8&14&2&
\end{array}$$
where the descents have been marked with dots.
\end{example}


\begin{example}
Let $$\pi=(2,9,17,6,11,19,7,13,12,15,8,14,1,4,5,10,18,3,16,20)\in\C_{20}.$$
Inserting parentheses before the left-to-right maxima, we have
$$\sigm=(2)(9)(17,6,11)(19,7,13,12,15,8,14,1,4,5,10,18,3,16).$$
Now $z=b_1=2$, and only $P(2,1)$ holds, so we switch $2$ and $1$:
$$\sigm=({\bf 1})(9)(17,6,11)(19,7,13,12,15,8,14,{\bf 2},4,5,10,18,3,16).$$
In $\Gamma_2$ we have $z=b_2=9$ and $P(9,8)$ holds, so we switch $9$ and $8$.
Now $P(8,7)$ holds, so we switch $8$ and $7$. Similarly, we switch $7$ and $6$, then $6$ and $5$, and then $5$ and $4$, obtaining
$$\sigm=(1)({\bf 4})(17,{\bf 7},11)(19,{\bf 8},13,12,15,{\bf 9},14,2,{\bf 5},{\bf 6},10,18,3,16).$$
Finally, in $\Gamma_3$ we have $z=b_3=11$ and $P(11,10)$ holds, so we switch $11$ and $10$, and also the preceding entries $7$ and $6$:
$$\bij(\pi)=\sigm=(1)(4)(17,{\bf 6},{\bf 10})(19,8,13,12,15,9,14,2,5,{\bf 7},{\bf 11},18,3,16)\in\S_{19}.$$
In one-line notation,
\renewcommand{\tabcolsep}{0pt}
$$\begin{array}{cc*{2}{c@{\ }}c@{\,\cdot\,}*{7}{c@{\ }}*{3}{c@{\,\cdot\,}}*{2}{c@{\ }}*{2}{c@{\,\cdot\,}}c@{\ }c@{\,}c}
\pi&=&4&9&16&5&10&11&13&14&17&18&19&15&12&1&8&20&6&3&7&\cdot2\\
\bij(\pi)&=&1&5&16&4&7&10&11&13&14&17&18&15&12&2&9&19&6&3&8
\end{array}$$
where the descents have been marked with dots.
\end{example}

\subsection{The map $\inv$}

Given $\sigma\in\S_{n}$, write it in cycle form with the largest element of each cycle first, ordering the cycles by increasing first element,
say $$\sigma=(c_1,\dots,d_1)(c_2,\dots,d_2)\cdots(c_r,\dots,d_r).$$ Removing the internal parentheses and appending $n+1$, we obtain an $(n+1)$-cycle
$$\pim=(c_1,\dots,d_1;c_2,\dots,d_2;\dots;c_r\dots,d_r;n+1).$$ For convenience we write semicolons in order to keep track of the places from where parentheses were removed.
We call {\em blocks} the entries between consecutive semicolons.
Similarly to the description of $\bij$, we will obtain $\inv(\sigma)$ by making some switches to the cycle form of $\pim$.
At each stage of the algorithm, we denote by $\Delta_i$ the $i$-th block of $\pim$.
For $1\le x,y\le n$, let $Q(x,y)$ be the condition
$$\pim(x)>\pim(y) \ \textrm{ and }\ \sigma(x)<\sigma(y).$$

Repeat the following steps for  $i=r-1,r-2,\dots,1$:
\bit
\item Let $z$ be the rightmost entry of $\Delta_i$. If $Q(z,z+1)$ or $Q(z,z-1)$ hold, let $\eps\in\{-1,1\}$ be such that $Q(z,z+\eps)$ holds and $\pim(z+\eps)$ is smallest.
\item Repeat for as long as $Q(z,z+\eps)$ holds:
\ben\renewcommand{\labelenumi}{\Roman{enumi}'.}
\item Switch $z$ and $z+\eps$ in the cycle form of $\pim$.
\item If the last switch did not involve the leftmost entry of the $\Delta_i$, let $x$ and $y$ be the elements preceding the switched entries. If $|x-y|=1$, switch $x$ and $y$ in the cycle form of $\sigma$, and repeat step~II'.
\item Let $z:=z+\eps$ (the new rightmost entry of $\Delta_i$).
\een
\eit

Define $\inv(\sigma)=\pim$.

\ms

\begin{example}
Let $$\sigma=(11,4,9,3,5)(16,10,1,7,15)(20,2,6,13,18,8,12,19,14,17)\in\S_{20}.$$
Removing the parentheses and appending $n+1$ we get $$\pim=(11,4,9,3,5;16,10,1,7,15;20,2,6,13,18,8,12,19,14,17;21).$$

We start looking at $\Delta_2$, so $z=d_2=15$. Only $Q(15,14)$ holds, so we switch $15$ and $14$:
$$\pim=(11,4,9,3,5;16,10,1,7,{\bf 14};20,2,6,13,18,8,12,19,{\bf 15},17;21).$$
Now $z=14$ and $Q(14,13)$ holds, so we switch $14$ and $13$. The entries to their left are $7$ and $6$, and the entries preceding these are $1$ and $2$, so we make the corresponding switches:
$$\pim=(11,4,9,3,5;16,10,{\bf 2},{\bf 6},{\bf 13};20,{\bf 1},{\bf 7},{\bf 14},18,8,12,19,15,17;21).$$
Now $z=13$ and $Q(13,12)$ holds, so we switch $13$ and $12$:
$$\pim=(11,4,9,3,5;16,10,2,6,{\bf 12};20,1,7,14,18,8,{\bf 13},19,15,17;21).$$

Looking at $\Delta_1$, we have $z=d_1=5$. Only $Q(5,6)$ holds, so we switch $5$ and $6$, and also the preceding entries $3$ and $2$, and $9$ and $10$:
$$\pim=(11,4,{\bf 10},{\bf 2},{\bf 6};16,{\bf 9},{\bf 3},{\bf 5},12;20,1,7,14,18,8,13,19,15,17;21).$$
Now $z=6$ and $Q(6,7)$ holds, so we switch $6$ and $7$, and also the preceding entries $2$ and $1$:
$$\pim=(11,4,10,{\bf 1},{\bf 7};16,9,3,5,12;20,{\bf 2},{\bf 6},14,18,8,13,19,15,17;21).$$
Since $Q(7,8)$ is false, the algorithm ends here, so
$$\inv(\sigma)=(11,4,10,1,7,16,9,3,5,12,20,2,6,14,18,8,13,19,15,17,21)\in\C_{21}.$$
\end{example}


\begin{example}
Let $$\sigma=(1)(4)(17,6,10)(19,8,13,12,15,9,14,2,5,7,11,18,3,16)\in\S_{19}.$$
After removing the parentheses, $$\pim=(1;4;17,6,10;19,8,13,12,15,9,14,2,5,7,11,18,3,16;20).$$

In $\Delta_3$, $z=d_3=10$ and $Q(10,11)$ holds, so we switch $10$ and $11$, and also $6$ and $7$:
$$\pim=(1;4;17,{\bf 7},{\bf 11};19,8,13,12,15,9,14,2,5,{\bf 6},{\bf 10},18,3,16;20).$$
Since $Q(11,12)$ is false, we look at $\Delta_2$, so $z=d_2=4$. We see that both $Q(4,3)$ and $Q(4,5)$ hold, but $\pim(3)=16>6=\pim(5)$, so we switch $4$ and $5$.
Now $z=5$ and $Q(5,6)$ holds, so we switch $5$ and $6$. Similarly, we switch $6$ and $7$, next $7$ and $8$, and then $8$ and $9$:
$$\pim=(1;{\bf 9};17,{\bf 6},11;19,{\bf 7},13,12,15,{\bf 8},14,2,{\bf 4},{\bf 5},10,18,3,16;20).$$
Finally, in the first block we switch $1$ and $2$, ending with
$$\inv(\sigma)=\pim=(2,9,17,6,11,19,7,13,12,15,8,14,1,4,5,10,18,3,16,20)\in\C_{20}.$$
\end{example}


\subsection{Properties of $\bij$ and $\inv$}
The following five lemmas give more insight into the computation of $\bij(\pi)$. They are valid for each $1\le i\le r-1$.
The $i$-th iteration of the main loop of the algorithm will be sometimes referred to as {\em fixing $\Gamma_i$}.

\begin{lemma}\label{lem:decrpi}
Suppose that in the process of fixing $\Gamma_i$, the elements that occupy the last position of $\Gamma_i$ are $b,b+\eps,b+2\eps,\dots,b+k\eps$ in this order. Then
$$\pi(b)>\pi(b+\eps)>\pi(b+2\eps)>\dots>\pi(b+k\eps).$$
\end{lemma}

\begin{proof}
For each $1\le j\le k$, the switch between $b+(j-1)\eps$ and $b+j\eps$ only takes place if $P(b+(j-1)\eps,b+j\eps)$ holds, which implies that
$\pi(b+(j-1)\eps)>\pi(b+j\eps)$.
\end{proof}

\begin{lemma}\label{lem:relative} \ben \item\label{partt1} No switch ever takes place between two entries of the same $\Gamma_i$.
\item\label{partt2} The relative order of the entries within $\Gamma_i$ always stays the same. In particular, the first entry of $\Gamma_i$ is always the largest.
\een
\end{lemma}

\begin{proof} Since the switches always involve consecutive values, the relative order of the entries in $\Gamma_i$ never changes in a switch are between an entry of $\Gamma_i$ and an entry of another cycle.
Thus, part~(\ref{partt2}) follows from part~(\ref{partt1}).
To prove part~(\ref{partt1}), assume for contradiction that a switch takes place between two entries of $\Gamma_i$. Consider the first such switch, which must necessarily be
between the last element $z$ and another element $z+\eps$ in $\Gamma_i$.
For $P(z,z+\eps)$ to hold, we would need $\sigm(z)<\sigm(z+\eps)$. But this cannot happen because $\sigm(z)$ is the first entry of $\Gamma_i$, and hence the largest since by assumption this is the first switch between two entries of $\Gamma_i$.
\end{proof}


\begin{lemma}\label{lem:notmoved} While fixing $\Gamma_i$, \ben
\item\label{part1} neither the first nor the last entry of $\Gamma_j$ are moved for any $j>i$; in particular, before iteration $j$, $\Gamma_j=(a_j,\dots,b_j)$;
\item\label{part2} no entry $t$ with $t\ge a_{i+1}$ is moved;
\item\label{part3} no entry preceding an entry $t\ge a_{i+1}$ is moved.
\een
\end{lemma}

\begin{proof}
We use induction on $i$. Our induction hypothesis is that all three parts of the lemma hold for smaller values of $i$.
Assume we have fixed $\Gamma_1,\Gamma_2,\dots,\Gamma_{i-1}$, and neither $a_j$ nor $b_j$ for $j\ge i$ have moved.
In particular, $\sigm(b_i)=a_i$ at this point.

Suppose that during the process of fixing $\Gamma_i$ we move some $b_j$ with $j>i$. Consider the first time this happens,
and let $z$ be the rightmost entry of $\Gamma_i$ right before the switch. Since $b_i$ was the rightmost entry of $\Gamma_i$ before iteration $i$,
we have by Lemma~\ref{lem:decrpi} that $\pi(z)\le\pi(b_i)=a_{i+1}$.
For the switch between $z$ and $b_j$ to happen, we must have $b_j=z\pm1$ and $P(z,b_j)$ must hold,
which implies that $\pi(z)>\pi(b_j)$.  But $\pi(z)\le a_{i+1}$ as we just showed, $\pi(b_j)=a_{j+1}$, and $a_{i+1}<a_{j+1}$
because the left-to-right maxima of a sequence are increasing, so this is a contradiction.

Suppose now that during the process of fixing $\Gamma_i$ we move some $a_j$ with $j>i$.
Consider the first time this happens. Since switches only take
place between consecutive values and the sequence  $a_1,a_2,\dots$ is increasing, we must have $j=i+1$, and there must be some element in $x$ in $\Gamma_i$ with $|a_{i+1}-x|=1$.
Now, the facts that $a_{i+1}$ is larger than all the elements of $\Gamma_i$ and that $\Gamma_i$ starts with its largest element,
which we know from Lemma~\ref{lem:relative}(\ref{partt2}), imply that $x$ is the first entry of $\Gamma_i$ and $a_{i+1}=x+1$. However, we claim that in this case no switch
takes place. Indeed, for any switch to take place, $P(z,z+\eps)$ must hold for some $\eps\in\{-1,1\}$, where $z$ is the last entry of $\Gamma_i$. This means that
$\pi(z+\eps)<\pi(z)\le\pi(b_i)=a_{i+1}=x+1$ and $\sigm(z+\eps)>\sigm(z)=x$, so $\pi(z+\eps)<\sigm(z+\eps)$, which implies that
$z+\eps$ or $\sigm(z+\eps)$ have been moved in a previous steps of the algorithm. But the fact that $\sigm(z+\eps)\ge a_{i+1}$ makes this impossible, by the induction hypothesis on parts~(\ref{part2}) and~(\ref{part3}).

Now we prove part~(\ref{part2}). At the beginning of the computation of $\bij(\pi)$, when $\sigm$ is given by equation~(\ref{eq:sigm}), $a_{i+1}$ is larger than all the elements in $\Gamma_1,\dots,\Gamma_i$. Since all the switches involve
consecutive values, no $t\ge a_{i+1}$ can be involved in a switch with elements of $\Gamma_1,\dots,\Gamma_i$ without $a_{i+1}$ being involved in a switch first. But we just proved that this cannot happen.

To prove part~(\ref{part3}), assume without loss of generality that the entry $s$ preceding $t$ is moved for the first time while fixing $\Gamma_i$.
Since $t$ has not been moved, the switch must happen in step I of the $i$-th iteration, and it must involve $s$ and the last entry of $\Gamma_i$ at the time, say $z$. For this switch to take place,
we need $\pi(z)>\pi(s)$. But this can never happen, because by Lemma~\ref{lem:decrpi}, $\pi(z)\le\pi(b_i)=a_{i+1}$, and since neither $s$ nor $t$ have moved so far, $\pi(s)=t\ge a_{i+1}$.
\end{proof}


\begin{lemma}\label{lem:notback} While fixing $\Gamma_i$, no entries in cycles $\Gamma_j$ with $j<i$ are moved.
\end{lemma}

\begin{proof} Suppose this is false, and consider the first time that the last entry $z$ of $\Gamma_i$ is switched with an entry $z+\eps$ of $\Gamma_j$, where $j<i$.
Then we must have $\sigm(z)<\sigm(z+\eps)$. But $\sigm(z)$ is the first entry of $\Gamma_i$, which is larger than any element in $\Gamma_1,\Gamma_2,\dots,\Gamma_{i-1}$ by Lemma~\ref{lem:notmoved}(\ref{part1}),
in particular larger than $\sigm(z+\eps)$.
\end{proof}

\begin{lemma}\label{lem:bi}
In the process of fixing $\Gamma_i$, the elements that occupy the last position of $\Gamma_i$ are $b_i,b_i+\eps,b_i+2\eps,\dots,b_i+k\eps$ for some $k$, in this order. Additionally,
$$\pi(b_i)>\pi(b_i+\eps)>\pi(b_i+2\eps)>\dots>\pi(b_i+k\eps).$$
\end{lemma}

\begin{proof}
This follows easily from the description of $\bij$ and Lemmas~\ref{lem:decrpi} and~\ref{lem:notmoved}(\ref{part1}).
\end{proof}

Now we prove two properties of $\bij$, the main one being that it preserves the descent set if we forget $\pi(n+1)$.

\begin{prop}\label{prop:descents}
Let $\pi\in\C_{n+1}$ and $\sigma=\bij(\pi)$. Then \ben
\item\label{desc} $D(\pi)\cap[n-1]=D(\sigma)$,
\item\label{n} $\pi^{-1}(n+1)=\sigma^{-1}(n)$.
\een
\end{prop}

\begin{proof}
First observe that if $\sigm$ is the permutation in equation~(\ref{eq:sigm}), before any cycles are fixed, then $\sigm(x)=\pi(x)$ for all $x\notin\{b_1,\dots,b_r\}$, and $\sigm(b_i)<\pi(b_i)$ for $1\le i\le r$.
Note also that $\pi(b_r)=n+1$ and $\sigm(b_r)=a_r=n$. By Lemma~\ref{lem:notmoved}(\ref{part1}), $a_r$ and $b_r$ are never moved when fixing the cycles $\Gamma_1,\dots,\Gamma_{r-1}$, so $\sigma(b_r)=n$, which proves part~(\ref{n}) of the proposition.

To prove part~(\ref{desc}), let $W=(D(\pi)\cap[n-1])\bigtriangleup D(\sigm)$
be the set of indices where the descents of $\pi$ and $\sigm$ disagree ($\bigtriangleup$ denotes the symmetric difference). Before fixing any cycles, the only indices that may be in $W$
are $b_i-1$ and $b_i$ for $1\le i\le r-1$, by the previous observation.
We claim that fixing cycle $\Gamma_i$ removes $b_i-1$ and $b_i$ from $W$ (if they were in it) without adding any other elements to $W$.
Indeed, by Lemma~\ref{lem:bi}, the first step in iteration $i$ checks $P(b_i,b_i-1)$ and $P(b_i,b_i+1)$, which determine whether $b_i-1$ and $b_i$ are in $W$, respectively. If either of them is, the
switch between $b_i$ and $b_i+\eps$ (with $\eps$ chosen so that $\sigm(b_i+\eps)$ is largest) performed by $\bij$ in step I of the $i$-th iteration guarantees that $b_i-1,b_i\notin W$ after the switch.
However, two elements could now have been added to $W$:\bit
\item If $b_i$ was not the first entry of $\Gamma_i$ (note that by Lemma~\ref{lem:notmoved}(\ref{part1}) we know that $b_i+\eps$ was not the first entry of its cycle)
and the entries preceding $b_i$ and $b_i+\eps$ were consecutive, say $s$ and $s+1$,
then the switch between $b_i$ and $b_i+\eps$ adds $s$ to $W$. Step II of the $i$-th iteration switches $s$ and $s+1$ so that $s$ is no longer in $W$, and next
performs any necessary switches to prevent any other indices from being added to $W$.
\item It is possible that since $\sigm(b_i+\eps)$ has changed in step I, the relative order of $\sigm(b_i+\eps)$ and $\sigm(b_i+2\eps)$ is now different from the relative order of $\pi(b_i+\eps)$ and $\pi(b_i+2\eps)$.
The condition $P(b_i+\eps,b_i+2\eps)$ determines whether this is the case, and if so, the second repetition of step I
switches $b_i+\eps$ and $b_i+2\eps$ in the cycle form of $\sigm$ to fix the problem. Again, step II prevents other elements from being added to $W$.
\eit
These steps are repeated until for some $k$, $P(b_i+k\eps,b_i+(k+1)\eps)$ is false, which means that either $b_i+(k+1)\eps\in\{0,n+1\}$
or the relative order of $\sigm(b_i+k\eps)$ and $\sigm(b_i+(k+1)\eps)$ agrees with the relative order of $\pi(b_i+k\eps)$ and $\pi(b_i+(k+1)\eps)$.
Iteration $i$ ends here; at this time, the descent set of the sequence
$\sigm(b_i-\eps)\sigm(b_i)\sigm(b_i+\eps)\dots\sigm(b_i+k\eps)\sigm(b_i+(k+1)\eps)$ agrees with the descent set of
$\pi(b_i-\eps)\pi(b_i)\pi(b_i+\eps)\dots\pi(b_i+k\eps)\pi(b_i+(k+1)\eps)$, and the only elements that may remain in $W$ are $b_j-1$ and $b_j$ for $i< j\le r-1$.
After iteration $r-1$, we have $W=\emptyset$, so part~(\ref{desc}) is proved.
\end{proof}



\begin{prop}
The maps $\bij$ and $\inv$ are inverses of each other.
\end{prop}

\begin{proof}
Let $\pi\in\C_{n+1}$ and $\sigma=\bij(\pi)$. We will prove that $\inv(\sigma)=\pi$ by showing that the switches done by the $i$-th iteration of $\bij$ on $\pi$ are
the same as the switches done by the iteration of $\inv$ on $\sigma$ corresponding to the same $i$ (we will call this the $i$-th iteration of $\inv$, not being bothered by the fact that the iteration number decreases from $r-1$ to $1$).
By Lemma~\ref{lem:bi}, the elements that occupy the last position of $\Gamma_i$ during iteration $i$ are $b_i,b_i+\eps,b_i+2\eps,\dots,b_i+k\eps$ for some $k\ge0$.
Let $\sigm_0$ and $\sigm_k$ be the permutations obtained during the computation of $\bij(\pi)$ right before and right
after the $i$-th iteration, respectively. More generally, for each $1\le j\le k$, let $\sigm_j$ be the permutation obtained from $\sigm_{j-1}$ after the switch between $b_i+(j-1)\eps$ and $b_i+j\eps$
from step I and the subsequent switches of the preceding entries from step II take place.
For $0\le j\le k$, let $\pim_j\in\C_{n+1}$ be the permutation whose cycle notation is obtained by removing
all but the first and last parentheses in the cycle form of $\sigm_j$ and appending $n+1$.

We will show that if $\pim=\pim_k$ right before the $i$-th iteration of the computation of $\inv(\sigma)$, then $\pi=\pim_0$ right after the $i$-th iteration.
This being true for $i=r-1,r-2,\dots,1$ will prove that $\inv(\bij(\pi))=\pi$ for all $\pi\in\C_{n+1}$, and since $|\C_{n+1}|=|\S_n|=n!$, the proposition will follow.

We use the same notation as in the description of $\bij$, so $$\pi=(a_1,\dots,b_1,a_2,\dots,b_2,\dots,a_r,\dots,b_r,n+1).$$
The $i$-th cycle of $\sigm_0$ is $\Gamma_i=(a_i,\dots,b_i)$, since by Lemma~\ref{lem:notmoved}(\ref{part1}), $a_i$ and $b_i$ have not been moved before iteration $i$.
For $1\le j\le k$, let $s_j=\sigm_0(b_i+j\eps)$. If $b_i+(k+1)\eps\notin\{0,n+1\}$, let $s_{k+1}=\sigm_0(b_i+(k+1)\eps)$, and if $b_i-\eps\notin\{0,n+1\}$, let $s_0=\sigm_0(b_i-\eps)$.
Here are some useful remarks, where $1\le j\le k$:
\ben\renewcommand{\labelenumi}{(\alph{enumi})}
\item\setcounter{obsa}{\theenumi} For the switch between $b_i+(j-1)\eps$ and $b_i+j\eps$ to take place, $P(b_i+(j-1)\eps,b_i+j\eps)$ must hold, which is equivalent to
$$\pi(b_i+(j-1)\eps)>\pi(b_i+j\eps)\ \textrm{ and }\ \sigm_{j-1}(b_i+(j-1)\eps)<\sigm_{j-1}(b_i+j\eps).$$
\item\setcounter{obsd}{\theenumi}  In order for $s_j$ to be switched when fixing $\Gamma_i$, we must have $s_j=x-1$, where $x$ is the first element of $\Gamma_i$ right before the switch takes place, and the switch must be between $s_j$ and $x$.
To see this, assume without loss of generality that $s_j$ is the first entry among $s_1,s_2,\dots,s_k$ that is switched while going from $\sigm_{\ell-1}$ to $\sigm_\ell$ for some $\ell$, and that $x$ is the first entry of $\Gamma_i$ in
$\sigm_{\ell-1}$. After $s_j$ is switched, the element that takes its place must be larger than the first entry of $\sigm_\ell$, otherwise the condition $\sigm_{j-1}(b_i+(j-1)\eps)<\sigm_{j-1}(b_i+j\eps)$ from remark~(\alph{obsa})
would not hold.
However, if $s_j<x-1$ then, after $s_j$ is switched, the element that takes its place is $s_j\pm1<x$ and thus smaller than the first entry of $\sigm_\ell$.
If $s_j=x+1$ and it is switched with $x$, the same problem occurs. And if $s_j>x+1$, then there is no element in $\Gamma_i$ that $s_j$ can be switched with. So, the only possibility is that $s_j=x-1$ and it is switched with $x$.
\item\setcounter{obse}{\theenumi} From remark (\alph{obsa}) it follows that in iteration $i$, each $b_i+j\eps$ is only moved when going from $\sigm_{j-1}$ to $\sigm_j$.
Indeed, since $s_j$ can be only switched with the first entry of $\Gamma_i$, the preceding element $b_i+j\eps$ cannot be switched in step II of the algorithm.
\item\setcounter{obsb}{\theenumi} In $\sigm_0$, $b_i+j\eps$ is in a cycle $\Gamma_\ell$ with $\ell>i$, by Lemmas~\ref{lem:relative}(\ref{partt1}) and~\ref{lem:notback}, and remark~(\alph{obse}).
\item\setcounter{obsc}{\theenumi} In $\sigm_0$, $b_i+j\eps$ is not the rightmost entry of a cycle, because by Lemma~\ref{lem:notmoved}(\ref{part1}), none of the $b_\ell$ with $\ell>i$ moves while fixing $\Gamma_i$.
\item\setcounter{obsf}{\theenumi} Remarks (\alph{obse}) and (\alph{obsc}) imply that
$\pim_\ell(b_i+j\eps)=\sigm_\ell(b_i+j\eps)$ for $\ell\neq j$.
\een

For simplicity, assume first that $a_i$ is not moved while fixing $\Gamma_i$. By remark~(\alph{obsd}) above, none of the $s_j$ is moved while fixing $\Gamma_i$ in this case. Thus, using remark~(\alph{obse}) we
have $\sigm_\ell(b_i+j\eps)=s_j$ for $0\le\ell\le j-1$ and $\sigm_\ell(b_i+j\eps)=s_{j+1}$ for $j+1\le\ell\le k$. By remark~(\alph{obsa}),
$a_i=\sigm_{j-1}(b_i+(j-1)\eps)<\sigm_{j-1}(b_i+j\eps)=s_j$.
But then, by Lemma~\ref{lem:notmoved}(\ref{part2})(\ref{part3}), neither $b_i+j\eps$ nor $s_j$ for $1\le j\le k$ have been moved in the first $i-1$ iterations, so $\pi(b_i+j\eps)=s_j$, and by Lemma~\ref{lem:bi},
\beq\label{eq:orderai}a_{i+1}>s_1>s_2>\dots>s_k>a_i.\eeq
Additionally, it is not the case that $a_{i+1}>s_0>s_1$. Indeed, if it were (assuming that $s_0$ is defined), then we would have $a_i=\sigm_0(b_i)<\sigm_0(b_i-\eps)=s_0$ and $a_{i+1}=\pi(b_i)>\pi(b_i-\eps)=s_0$,
so $P(b_i,b_i-\eps)$ would hold, and since $s_0>s_1$, the algorithm would have switched $b_i$ with $b_i-\eps$ instead of with $b_i+\eps$.
Similarly, it is not the case that $s_k>s_{k+1}>a_i$. If it were (assuming that $s_{k+1}$ is defined), then we would have $a_i=\sigm_k(b_i+k\eps)<\sigm_k(b_i+(k+1)\eps)=s_{k+1}$ and $s_k=\pi(b_i+k\eps)>\pi(b_i+(k+1)\eps)=s_{k+1}$,
so $P(b_i+k\eps,b_i+(k+1)\eps)$ would hold, and the algorithm would switch $b_i+k\eps$ with $b_i+(k+1)\eps$.

We now show that, under the assumption that $a_i$ is not moved, iteration $i$ of $\inv$ undoes precisely the switches performed by iteration $i$ of $\bij$. Given $\pim_k$, whose $i$-th block is $c_i,\dots,d_i$,
where $c_i=a_i$ and $d_i=b_i+k\eps$,  $Q(b_i+k\eps,b_i+(k-1)\eps)$ is the condition $$\pim_k(b_i+k\eps)>\pim_k(b_i+(k-1)\eps)\ \textrm{ and }\ \sigma(b_i+k\eps)<\sigma(b_i+(k-1)\eps).$$
The first inequality can be restated as $a_{i+1}>\sigm_k(b_i+(k-1)\eps)=s_k$ by remark (\alph{obsf}), and it holds by equation~(\ref{eq:orderai}). The second inequality is equivalent to $\pi(b_i+k\eps)<\pi(b_i+(k-1)\eps)$ by Proposition~\ref{prop:descents},
and it holds by Lemma~\ref{lem:bi}. Additionally, since $s_k>s_{k+1}>a_i$ does not hold,
either $Q(b_i+k\eps,b_i+(k+1)\eps)$ does not hold or, if it does, then $s_k=\pim_k(b_i+(k-1)\eps)<\pim_k(b_i+(k+1)\eps)=s_{k+1}$, so $\inv$ starts
iteration $i$ by switching $b_i+k\eps$ and $b_i+(k-1)\eps$ (as opposed to $b_i+(k+1)\eps$) in step I'. Next, the switches in step II' of $\inv$ undo the switches from step II of $\bij$.

Afterwards, for each $j=k-1,k-2,\dots,1$, the computation of $\inv$ checks condition $Q(b_i+j\eps,b_i+(j-1)\eps)$, that is, whether $$\pim_j(b_i+j\eps)>\pim_j(b_i+(j-1)\eps)\ \textrm{ and }\ \sigma(b_i+j\eps)<\sigma(b_i+(j-1)\eps).$$
Again, the first inequality can be restated as $a_{i+1}>\sigm_j(b_i+(j-1)\eps)=s_j$ by remark (\alph{obsf}), and it holds by equation~(\ref{eq:orderai}). The second inequality is equivalent to $\pi(b_i+j\eps)<\pi(b_i+(j-1)\eps)$ by Proposition~\ref{prop:descents}, and it holds by Lemma~\ref{lem:bi}. Thus, $\inv$ performs the switch between $b_i+j\eps$ and $b_i+(j-1)\eps$ in step I', followed by the switches in step II' that undo the ones performed by $\bij$.

Finally, $\inv$ checks condition $Q(b_i,b_i-\eps)$, that is, whether $$\pim_0(b_i)>\pim_0(b_i-\eps)\ \textrm{ and }\ \sigma(b_i)<\sigma(b_i-\eps),$$ assuming that $b_i-\eps\notin\{0,n+1\}$.
The first inequality is $a_{i+1}>s_0$, and the second is equivalent to $s_i=\sigm_k(b_i)<\sigm_k(b_i-\eps)=s_0$.
If both inequalities held, then $a_{i+1}>s_0>s_1$, which we know is false. So iteration $i$ of $\inv$ stops here.

In general, it can happen that $a_i$ moves while fixing $\Gamma_i$, and if so it is possible that the $b_i+j\eps$ have moved in the first $i-1$ iterations of $\bij$.
In this case one can still show that $a_{i+1}>s_1>s_2>\dots>s_k$, but it is not necessarily true that $s_k>a_i$ anymore. At the beginning of iteration $i$ of $\bij$, we have
$a_i=\sigm_0(b_i)<\sigm_0(b_i+\eps)=s_1$. After switching $b_i$ and $b_i+\eps$ in step I and perhaps some preceding entries in step II, it is possible that $a_i$ has been switched with
$s_\ell$ for some $\ell$. In this case, $s_\ell=a_i-1$ by remark~(\alph{obsd}), and after the switch the first entry of $\Gamma_i$ is $s_\ell=a_i-1$ and $\sigm_1(b_i+\ell\eps)=s_\ell+1=a_i$. Now we have that
$\sigm_1(b_i)=s_1$, and for $j\notin\{0,1,\ell\}$,
$\sigm_1(b_i+j\eps)=s_j$. In general, after the switch between $b_i+(j-1)\eps$ and $b_i+j\eps$ takes place in step I, the last switch in step II may involve the first entry $x$ of $\Gamma_i$ and some $s_t$
with $s_t=x-1$, making the first entry of $\Gamma_i$ go down by one and $\sigm_j(b_i+t\eps)=\sigm_{j-1}(b_i+t\eps)+1=s_t+1$. At the end of iteration $i$,
$$\sigm_k(b_i)>\sigm_k(b_i+\eps)>\dots>\sigm_k(b_i+(k-1)\eps)>\sigm_k(b_i+k\eps)=a_i-m=c_i,$$ where $m$ is the number of times that the
first entry of $\Gamma_i$ has been switched, and $\sigm_k(b_i+j\eps)=s_{j+1}+1$ for exactly $m$ of the values of $j\in\{0,1,\dots,k-1\}$ and $\sigm_k(b_i+j\eps)=s_{j+1}$ for the remaining ones.
The above reasoning for the case where $a_i$ was not moved can be adapted to show that, also in this general case, iteration $i$ of $\inv$ reverses the switches done by iteration $i$ of $\bij$.
\end{proof}



\section{Consequences}\label{sec:consequences}

The following is an obvious consequence of Theorem~\ref{thm:bij}. We state it separately in order to refer to it later.

\begin{corollary}\label{cor:cycles} For every $n$ and every $I\subseteq[n-1]$,
$$|\{\pi\in\C_{n+1}\,:\,D(\pi)\cap[n-1]=I\}|=|\{\sigma\in\S_n\,:\,D(\sigma)=I\}|.$$
\end{corollary}

This result has the following probabilistic interpretation. Choose a permutation $\pi\in\S_{n+1}$ uniformly at random. Then, for any given $I\subseteq[n-1]$, the event that $D(\pi)\cap[n-1]=I$
and the event that $\pi$ is a cyclic permutation are independent. To see this, note that the relative order of $\pi(1)\pi(2)\dots\pi(n)$ is given by a uniformly random permutation in $\S_n$. Thus,
for any fixed $I\subseteq[n-1]$, the probability that $D(\pi)\cap[n-1]=I$ for a random $\pi\in\S_{n+1}$ is the same as the probability that $D(\sigma)=I$ for a random $\sigma\in\S_n$, which by Corollary~\ref{cor:cycles}
is the same as the probability that $D(\pi)\cap[n-1]=I$ for a random $\pi\in\C_{n+1}$.


Our next goal is to show that Conjecture~\ref{conj:Eli} follows from Theorem~\ref{thm:bij}.
First, instead of the set $\T^0_n$, it will be more convenient for the sake of notation to consider the set $\U_n$
consisting of $n$-cycles in one-line notation in which one entry has been replaced with $n+1$. For example, $\U_3=\{431,241,234,412,342,314\}$.

\begin{corollary}\label{cor:biju} For every $n$ there is a bijection $\biju$ between $\U_{n}$ and $\S_n$ such that if $\tau\in\U_n$ and $\sigma=\biju(\tau)$, then
$$D(\tau)=D(\sigma).$$
Additionally, if $n+1$ is in position $k$ of $\tau$, then $\sigma(k)=n$.
\end{corollary}

\begin{proof}
Let $\tau\in\U_n$ and suppose it has been obtained from an $n$-cycle $\pi$ by replacing $\pi(k)$ with $n+1$ in the one-line notation. Write $\pi$ in cycle form with $k$ at the end,
say $\pi=(t_1,t_2,\dots,t_{n-1},k)$, and let $\pi'=(t_1,t_2,\dots,t_{n-1},k,n+1)\in\C_{n+1}$. Clearly, $D(\tau)=D(\pi')\cap[n-1]$, and the map $\tau\mapsto\pi'$ is a bijection between $\U_n$ and $\C_{n+1}$.
Let $\sigma=\bij(\pi')$. By Theorem~\ref{thm:bij}, $D(\pi')\cap[n-1])=D(\sigma)$, and by Proposition~\ref{prop:descents}(\ref{n}), $\sigma(k)=n$.
\end{proof}

The following corollary proves Conjecture~\ref{conj:Eli}.
\begin{corollary}\label{cor:Elishift} For every $n$ there is a bijection $\biju'$ between $\T^0_{n}$ and $\S_n$ such that if $\tau\in\T^0_n$ and $\sigma=\biju'(\tau)$, then
$$D(\tau)=D(\sigma).$$
Additionally, if $0$ is in position $k$ of $\tau$, then $\sigma(k)=1$.
\end{corollary}

\begin{proof}
Given $\tau\in\T^0_n$ obtained from an $n$-cycle $\pi$ by replacing $\pi(k)$ with $0$ in its one-line notation, let $\wt\tau\in\U_n$ be obtained from $\wt\pi$ (see the definition in the introduction) by replacing $\wt\pi(n+1-k)$ with $n+1$.
It is clear that for $1\le i\le n-1$, $i\in D(\wt\tau)$ if and only if $n+1-i\notin D(\tau)$. Let $\sigma=\biju'(\tau)=\wt{\biju(\wt\tau)}$. Then, for $1\le i\le n-1$,
$$i\in D(\sigma) \ \Leftrightarrow\  n+1-i\notin D(\biju(\wt\tau))=D(\wt\tau) \ \Leftrightarrow\ i\in D(\tau).$$ Also $\wt\sigma(n+1-k)=n$, so $\sigma(k)=1$.
\end{proof}

The final result of this section can be seen as a generalization of Corollary~\ref{cor:cycles}. We give a bijective proof of it.

\begin{corollary}\label{cor:cyclesu} Fix $1\le m\le n$ and let $J=[n-1]\setminus\{m-1,m\}$. For any $I\subseteq J$,
$$|\{\pi\in\C_{n}\,:\,D(\pi)\cap J=I\}|=|\{\sigma\in\S_{n}\,:\,\sigma(m)=1,\,D(\sigma)\cap J=I\}|.$$
\end{corollary}

\begin{proof}
Let $\pi\in\C_n$ with $D(\pi)\cap J=I$. Let $\tau\in\T^0_n$ be obtained by replacing $\pi(m)$ with $0$ in the one-line notation of $\pi$, and let $\sigma=\biju'(\tau)$. By Corollary~\ref{cor:Elishift}, $\sigma(m)=1$
and $D(\sigma)\cap J=D(\tau)\cap J=D(\pi)\cap J=I$.
\end{proof}



\section{Related work and non-bijective proofs}\label{sec:related}

In this section we introduce some related work of Gessel and Reutenauer~\cite{GR}, which will allow us to give
non-bijective proofs of Corollaries~\ref{cor:cycles} and~\ref{cor:cyclesu}.
We start with some definitions. Let $X=\{x_1,x_2,\dots\}_<$ be a linearly ordered alphabet.
A {\em necklace} of length $\ell$ is a circular arrangement of $\ell$ beads which are labeled with elements of $X$. Two necklaces are considered the same if they are cyclic rotations of one another.
The cycle structure of a multiset of necklaces is the partition whose parts are the lengths of the necklaces in the multiset.
The {\em evaluation} of a multiset of necklaces is the monomial $x_1^{e_1}x_2^{e_2}\dots$ where $e_i$ is the number of beads with label $x_i$.

The following result is equivalent to Corollary~2.2 from~\cite{GR}.

\begin{theorem}[\cite{GR}]\label{thm:GR}
Let $I=\{i_1,i_2,\dots,i_k\}_<\subseteq[n-1]$ and let $\lambda$ be a partition of~$n$. Then the number of permutations with cycle structure $\lambda$ and descent set contained in $I$ equals the number of multisets of necklaces with cycle structure $\lambda$ and evaluation $x_1^{i_1}x_2^{i_2-i_1}\dots x_k^{i_k-i_{k-1}}x_{k+1}^{n-i_k}$ .
\end{theorem}

We can now give direct, non-bijective proofs of Corollaries~\ref{cor:cycles} and~\ref{cor:cyclesu}.

\begin{proof}[Alternate proof of Corollary~\ref{cor:cycles}]
Suppose that $I=\{i_1,i_2,\dots,i_k\}_<$, and let $I'=I\cup\{n\}$.
By Theorem~\ref{thm:GR}, the number of permutations $\pi\in\C_{n+1}$ with $D(\pi)\subseteq I'$ (equivalently, $D(\pi)\cap[n-1]\subseteq I$) equals the number of necklaces with evaluation 
$$x_1^{i_1}x_2^{i_2-i_1}\dots x_k^{i_k-i_{k-1}}x_{k+1}^{n-i_k}x_{k+2}.$$
By first choosing the bead labeled $x_{k+2}$, it is clear that the number of such necklaces is $$\binom{n}{i_1,i_2-i_1,\dots,i_k-i_{k-1},n-i_k}.$$
But this is precisely (see~\cite{EC1}) the number of permutations in $\S_n$ whose descent set is contained in $I$. Thus, we have shown that
$$|\{\pi\in\C_{n+1}\,:\,D(\pi)\cap[n-1]\subseteq I\}|=|\{\sigma\in\S_n\,:\,D(\sigma)\subseteq I\}|.$$
Since this holds for all $I\subseteq[n-1]$, the statement now follows by inclusion-exclusion:
\bmt |\{\pi\in\C_{n+1}\,:\,D(\pi)\cap[n-1]=I\}|=\sum_{J\subseteq I}(-1)^{|I|-|J|}|\{\pi\in\C_{n+1}\,:\,D(\pi)\cap[n-1]\subseteq J\}|\\
=\sum_{J\subseteq I}(-1)^{|I|-|J|}|\{\sigma\in\S_n\,:\,D(\sigma)\subseteq J\}|=|\{\sigma\in\S_n\,:\,D(\sigma)=I\}|.
\end{multline*}
\end{proof}

Note that even though a bijective proof of Theorem~\ref{thm:GR} is implicit in~\cite{GR}, the last inclusion-exclusion step in the above proof of Corollary~\ref{cor:cycles} makes it non-bijective.

\begin{proof}[Alternate proof of Corollary~\ref{cor:cyclesu}]
Let $I=\{i_1,i_2,\dots,i_k\}_<$. Assume first that $1<m<n$, and let $$I'=I\cup\{m-1,m\}=\{i_1,i_2,\dots,i_j,m-1,m,i_{j+1},\dots,i_k\}_<.$$
By Theorem~\ref{thm:GR}, the number of permutations $\pi\in\C_{n}$ with $D(\pi)\subseteq I'$ (equivalently, $D(\pi)\cap J\subseteq I$) equals the number of necklaces with evaluation
$$x_1^{i_1}x_2^{i_2-i_1}\dots x_j^{i_j-i_{j-1}}x_{j+1}^{m-1-i_j}x_{j+2}x_{j+3}^{i_{j+1}-m}\dots x_{k+2}^{i_k-i_{k-1}}x_{k+3}^{n-i_k}.$$
By first choosing the bead labeled $x_{j+2}$, it is clear that the number of such necklaces is
$$\binom{n-1}{i_1,i_2-i_1,\dots,i_j-i_{j-1},m-1-i_j,i_{j+1}-m,\dots,i_k-i_{k-1},n-i_k}.$$
But this is precisely the number of permutations $\sigma\in\S_n$ with $\sigma(m)=1$ whose descent set satisfies $D(\sigma)\cap J\subseteq I$.
Indeed, each partition of $\{2,3,\dots,n\}$ into blocks of sizes $$i_1,i_2-i_1,\dots,i_j-i_{j-1},m-1-i_j,i_{j+1}-m,\dots,i_k-i_{k-1},n-i_k$$
corresponds to the permutation whose first $i_1$ entries are the elements of the first block in increasing order, followed by the $i_2-i_1$ elements
of the second block in increasing order, until we get to the $m$-th entry, which is $1$, after which the $i_{j+1}-m$ elements of the $(j+1)$-st block follow in increasing order, and so on.
This proves that
$$|\{\pi\in\C_{n}\,:\,D(\pi)\cap J\subseteq I\}|=|\{\sigma\in\S_n\,:\,\sigma(m)=1,\,D(\sigma)\cap J\subseteq I\}|.$$
As before, since this equality holds for all $I\subseteq J$, the main statement now follows by inclusion-exclusion.

If $m=1$ or $m=n$, we let $I'=I\cup\{m\}=\{1,i_1,i_2,\dots,i_k\}$ or $I'=I\cup\{m-1\}=\{i_1,i_2,\dots,i_k,m-1\}$, respectively, and apply an analogous argument.
\end{proof}

\bs

We end this section with another application of the work of Gessel and Reutenauer. We show that \cite[Lemma 3.4]{GR} can be used to provide an explicit bijection
that solves a generalization of Problem~\ref{prob:EFW}. Indeed, since it preserves the cycle structure, the following bijection sends derangements to derangements

\begin{prop}\label{prop:subsets} For any two subsets $I,J\subseteq[n-1]$ with the same associated partition, there exists a bijection between
$\{\pi\in\S_n\,:\,D(\pi)\subseteq I\}$ and $\{\sigma\in\S_n\,:\,D(\sigma)\subseteq J\}$ preserving the cycle structure.
\end{prop}

\begin{proof}
Let $\pi\in\S_n$ with $D(\pi)\subseteq I$, where $I=\{i_1,i_2,\dots,i_k\}_<$, and let $\lambda$ be the cycle structure of $\pi$.
For convenience, define $i_0=0$ and $i_{k+1}=n$, and let $$(r_1,r_2,\dots,r_{k+1})=(i_1,i_2-i_1,\dots,i_k-i_{k-1},n-i_k)$$ be the corresponding composition on $n$.
Similarly, let $(s_1,s_2,\dots,s_{k+1})$ be the composition of $n$ corresponding to $J$. Since the associated partitions are the same, there is a permutation $\alpha$ of the indices such that
$r_j=s_{\alpha(j)}$ for $1\le j\le k+1$.

Write $\pi$ as a product of cycles and for each $1\le j\le k+1$, replace the entries $i_{j-1}+1,i_{j-1}+2,\dots,i_j$ with $x_{\alpha(j)}$,
thus obtaining a multiset of necklaces. For each bead, consider the periodic sequence obtained by reading the necklace starting at that bead. Now, order these sequences lexicographically (if there are repeated necklaces, first
choose an order among them), and label the vertices with $1,2,\dots,n$ according to this order. This yields the cycle form of a permutation $\sigma$, which clearly has cycle structure $\lambda$.
It follows from~\cite{GR} that $D(\sigma)\subseteq J$, and that the map $\pi\mapsto\sigma$ is a bijection. In fact, this map essentially amounts to applying the bijection $U$ from
\cite[Lemma 3.4]{GR} to a word whose standard permutation is $\pi^{-1}$, then replacing each $x_j$ with $x_{\alpha(j)}$ in the necklaces, and finally applying the inverse of $U$.
\end{proof}

\begin{example}
Let $n=12$, $I=\{2,8\}$ and $J=\{4,6\}$, so $(r_1,r_2,r_3)=(2,6,4)$ and $(s_1,s_2,s_3)=(4,2,6)$. Let $$\pi=3\:4\:1\:2\:5\:9\:11\:12\:6\:7\:8\:10=(1,3)(2,4)(5)(6,9)(7,11,8,12,10),$$
with $D(\pi)=\{2,8\}=I$.
After replacing $1,2$ with $x_{\alpha(1)}=x_2$, $3,4,5,6,7,8$ with $x_{\alpha(2)}=x_3$, and $9,10,11,12$ with $x_{\alpha(3)}=x_1$,
we obtain the multiset of necklaces $$(x_2,x_3)(x_2,x_3)(x_3)(x_3,x_1)(x_3,x_1,x_3,x_1,x_1).$$ The corresponding periodic sequences are
\bmt(x_2x_3x_2x_3\dots,x_3x_2x_3x_2\dots)(x_2x_3x_2x_3\dots,x_3x_2x_3x_2\dots)\\
(x_3x_3\dots)(x_3x_1x_3x_1\dots,x_1x_3x_1x_3\dots)\\
(x_3x_1x_3x_1x_1\dots,x_1x_3x_1x_1x_3\dots,x_3x_1x_1x_3x_1\dots,x_1x_1x_3x_1x_3\dots,x_1x_3x_1x_3x_1\dots),
\end{multline*}
and ordering them lexicographically we obtain the permutation $$\sigma=(5,10)(6,11)(12)(9,4)(8,2,7,1,3)=3\:7\:8\:9\:10\:11\:1\:2\:4\:5\:6\:12,$$ with $D(\sigma)=\{6\}\subseteq J$.

If instead we had had $J'=\{2,6\}$, with composition $(2,4,6)$, the permutation corresponding to $\pi$ would have been
$$\sigma'=(1,7)(2,8)(12)(11,6)(10,4,9,3,5)=7\:8\:5\:9\:10\:11\:1\:2\:3\:4\:6\:12,$$ with $D(\sigma')=\{2,6\}=J'$.
\end{example}

Note that for two arbitrary subsets $I,J\subseteq[n-1]$ with the same associated partition, there is in general no bijection between
$\{\pi\in\S_n:D(\pi)=I\}$ and $\{\sigma\in\S_n:D(\sigma)=J\}$ preserving the cycle structure. For example, in the case of $5$-cycles,
we see in Table~\ref{tab:n4} that, even though both $\{1,2\}$ and $\{1,4\}$ have the same associated partition $(3,1,1)$,
$$\{\pi\in\C_5:D(\pi)=\{1,2\}\}=\{53124\}$$ but $$\{\sigma\in\C_5:D(\sigma)=\{1,4\}\}=\{31452,41253\}.$$



2009-06-15T22:25:51.000
0906
0906.2795
en
https://arxiv.org/abs/0906.2795
We present a bijection between cyclic permutations of {1,2,...,n+1} and permutations of {1,2,...,n} that preserves the descent set of the first n entries and the set of weak excedances. This non-trivial bijection involves a Foata-like transformation on the cyclic notation of the permutation, followed by certain conjugations. We also give an alternate derivation of the consequent result about the equidistribution of descent sets using work of Gessel and Reutenauer. Finally, we prove a conjecture of the author in [SIAM J. Discrete Math. 23 (2009), 765-786] and a conjecture of Eriksen, Freij and Wästlund.
Combinatorics (math.CO)
Descent sets of cyclic permutations
Qwen/Qwen-72B
1. YES
2. YES