\documentclass[12pt]{article}
\def\refname{References}
\textheight=22.8 cm \textwidth=15.6cm \hoffset-2truecm
\voffset-.5cm \def\P{{\cal P}}
%binomial coefficients:\bi{#1}{#2}
\newcommand\bi[2]{{{#1}\atopwithdelims(){#2}}}
\newcommand{\pv}{\noindent{\bf Proof : \/}}
\def\qed{\quad\raise -2pt\hbox{\vrule\vbox
to 10pt{\hrule width 4pt \vfill\hrule}\vrule}\medskip}
\newenvironment{ex}{\smallskip\noindent{\bf Example.
}}{\smallskip}
\newenvironment{rmq}{\smallskip\noindent{\bf Remark.
}}{\smallskip}
\newcounter{num}
\newcommand{\defi}{\addtocounter{num}{1}
\noindent\textbf{Definition~\thenum~. }\kern 5pt}
\newtheorem{prop}{Proposition}
\newtheorem{propr}{Proprety}
\newtheorem{lem}{Lemma}
\newtheorem{thm}{Theorem}
%\def\refname{R\'ef\'erences}
\newtheorem{coro}{Corollary}
\def\cyc{\mathrm{cyc\,}}
\def\exc{\mathrm{exc\,}}
\def\fix{\mathrm{fix\,}}
\def\lrm{\mathrm{lrm\,}}
\def\des{\mathrm{des\,}}
\def\suc{\mathrm{suc\,}}
\def\C{\mathcal C}
\def\S{\mathcal S}
\def\D{\mathcal D}
\title{TWO INVOLUTIONS FOR SIGNED EXCEDANCE NUMBERS}

\author{G\'erald Ksavrelof and Jiang Zeng\\
\small Institut Girard Desargues\\
\small Universit\'e Claude Bernard (Lyon 1)\\
\small 69622 Villeurbanne Cedex, France\\
\small \texttt{E-mail:\{ksavrelo, zeng\}@igd.univ-lyon1.fr}}
\date{}

\begin{document}

\maketitle
\begin{abstract}

Two involutions on permutations and derangements are constructed.
They lead to a direct evaluation of some signed Eulerian
polynomials on permutations and derangements. The latter formulas,
combined with the exponential formula, give a new derivation of
the corresponding generating functions.

\end{abstract}

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 49 \rms (2003), Article~B49e\hfill}
\def\thepage{}
%
%

\section{Introduction}
Let $n$ be a positive integer. A permutation $\sigma$ of the set
$[n]:=\{1,\ldots,n\}$ has an \emph{excedance} at $i$ if $\sigma
(i)>i$, for $1\leq i\leq n$. As usual, we denote the numbers of
excedances, cycles and fixed points of $\sigma$ by $\exc\sigma$,
$\cyc\sigma$ and $\fix \sigma$, respectively. A fixed-point-free
permutation is called a \emph{derangement}. Let $\S_n$ (resp.
$\D_n$) be the set of \emph{permutations} (resp.
\emph{derangements}) of $[n]$. For example, the permutation
$\sigma=\sigma(1)\ldots\sigma(5)\sigma(6)=3\,2\,6\,5\,4\,1 \in
\S_6$ has the cycle decomposition $(1,3,6)(2)(4,5)$, so $2$ is the
only fixed point and $\sigma$ has an excedance at 1, 3 and 4;
finally $\cyc\sigma=3$, $\exc\sigma=3$ and $\fix\sigma=1$.
Consider the following enumerative polynomial of $\S_n$~:
$$
P_n(x,y, \beta)=\sum_{\sigma \in \S_n}x^{\exc\sigma}y^{\fix
\sigma}\beta^{\cyc\sigma}.
$$
Then $P_n(x, 1, 1)$ is the classical \emph{Eulerian polynomial}
(cf. \cite[Chap. 1]{Sta}), and $P_n(x,0, 1)$ the counterpart for
the derangements.  For a combinatorial treatment of Eulerian
polynomials the reader is referred to the seminal book of Foata
and Sch\"utzenberger~\cite{FS}.


It is remarkable that when $\beta=-1$, these two polynomials have
simple closed formulas~:

\begin{eqnarray}
P_n(x,1, -1)&=&-(x-1)^{n-1}, \label{eq1}\\
P_n(x,0, -1)&=&-x-x^2-\cdots-x^{n-1}. \label{eq2}
\end{eqnarray}

Although $P_n(x,0, -1)$ is a special case of $P_n(x,y, \beta)$,
its evaluation  does imply
 the exponential generating
function of $P_n(x,y, \beta)$. Actually, weighting  each
permutation $\sigma$ by the monomial
$x^{\exc\sigma}y^{\fix\sigma}(-1)^{\cyc\sigma}$, the counting
polynomial for permutations in $\S_n$ with $k$  chosen fixed
points for $0\leq k\leq n$ is $(-y)^kP_{n-k}(x,0, -1)$, hence we
deduce from  (\ref{eq2}) that
\begin{equation}\label{eq4}
P_n(x,y, -1)=\sum_{k=0}^n\bi{n}{k}(-y)^kP_{n-k}(x,0, -1)=
{(x-y)^n-x(1-y)^n\over 1-x}.
\end{equation}
Now, according to  the \emph{exponential formula}~(cf. \cite{FS},
\cite[Chap.~5]{Sta}) and the evident identity $e^x=(e^{-x})^{-1}$,
we have
\begin{equation}\label{eq:lem}
1+\sum_{n\geq 1} P_n(x,y,
\beta)\frac{t^n}{n!}=\left[\exp\left(-\sum_{n\geq 1}\sum_{\sigma\in \C_n}
x^{\exc \sigma} y^{\fix \sigma}\frac{t^n}{n!}\right)\right]^{-\beta},
\end{equation}
where $\C_n$ denotes the set of cyclic permutations in $\S_n$.
Setting $\beta=-1$ in (\ref{eq:lem}) we see that the expression
under brackets in (\ref{eq:lem}) is equal to $1+\sum_{n\geq 1}
P_n(x,y, -1)t^n/n!$, hence
\begin{equation}
1+\sum_{n\geq 1} P_n(x,y, \beta)\frac{t^n}{n!} =\left(\sum_{n\geq
0} {(x-y)^n-x(1-y)^n\over 1-x}{t^n\over n!}\right)^{-\beta}.
\label{eq5}
\end{equation}
Conversely, it is a simple matter to derive (\ref{eq2}) from
(\ref{eq5}) with $\beta=1$ and $y=0$, so  (\ref{eq2}) is actually
equivalent to  (\ref{eq5}), of which the $\beta=1$ case was
already given by Foata and Sch\"utzenberger~\cite{FS}.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
%\markboth{\SMALL STEEN RYOM--HANSEN}{\SMALL LITTELMANN'S REFINED DEMAZURE 
%CHARACTER FORMULA}

Note that the polynomial $P_n(x,y,\beta)$ can also be interpreted
through some {\em linear statistics} on permutations. Identify
each permutation $\sigma\in \S_n$ with the word
$\sigma(1)\sigma(2)\ldots \sigma(n)$. An integer $i$, $1\leq i\leq
n-1$, is a {\em descent} (resp. {\em succession}) of $\sigma$ if
$\sigma(i)>\sigma(i+1)$ (resp. $\sigma(i+1)=\sigma(i)+1$), and an
integer  $j=\sigma(i)$ for some $i\in [n]$ is a {\em left-to-right
maximum} of $\sigma$ if $\sigma(k)<j$ for all $k<i$. Let
$\des\sigma$, $\suc\sigma$ and $\lrm\sigma$ be the numbers of
descents, successions and left-to-right maxima of $\sigma$,
respectively. Then, thanks to the {\em fundamental transformation}
of Foata and Sch\"utzenberger~\cite{FS}, we have also
$$
P_n(x,y,\beta)=\sum_{\sigma\in
\S_n}x^{\des\sigma}y^{\suc\sigma}\beta^{\lrm\sigma}.
$$
For some latest developments of the above fundamental
transformation on words we refer the reader to a recent paper by
Foata and Han~\cite{FH}.

Our purpose is to provide bijective proofs to
 the identities
(\ref{eq1}) and (\ref{eq2}). In particular, this bijective
approach leads  to the following refinement of (\ref{eq2}), which
seems to be new.
\begin{thm} Let
$D_{n,j}=\{\sigma\in \D_n \mid \sigma(n)=j\}$ for $j\in [n-1]$.
Then
\begin{equation}\label{eq6}
\sum_{\sigma\in D_{n,j}}(-1)^{\cyc\sigma}x^{\exc\sigma}=-x^{n-j}.
\end{equation}
\end{thm}


This paper was motivated by several recent papers: after deriving
(\ref{eq1}) from its generating function, which is equivalent to
formula~(\ref{eq5}) with $y=1$, Brenti~\cite[p.163]{Bre} asked for
a bijective proof, Chapman~\cite{Cha} gave a bijective proof of
(\ref{eq2}) when $x=1$, Gessel~\cite{Ges} gave a combinatorial
proof of (\ref{eq5}) when $\beta=x=1$ and $y=0$,  and  Kim and
Zeng~\cite{Kim} have given a direct combinatorial proof of
(\ref{eq5}) when $\beta=1$ and $y=1$ or 0, see also
\cite{Des2,Wac} for some related problems.


In Section~2 we first give a bijective proof of the following
recurrences:
\begin{eqnarray}
P_n(x,1, -1)&=&(x-1)P_{n-1}(x,1, -1), \qquad n\geq 3,\label{eq7}\\
P_n(x,0, -1)&=&P_{n-1}(x,0, -1)-x^{n-1},\qquad n\geq 3.\label{eq8}
\end{eqnarray}
Since $P_2(x,1, -1)=1-x$ and $P_2(x,0, -1)=-x$, (\ref{eq7})
implies (\ref{eq1}) and (\ref{eq8}) implies (\ref{eq2}). The
reason for including such recursive proofs of (\ref{eq1}) and
(\ref{eq2}) is that they use simpler involutions than the
bijective ones. In Section~3 we then give  a second proof of
(\ref{eq1}) and  (\ref{eq2}) (in fact (\ref{eq6}))  based on a
direct interpretation of their right-sides.


All our four involutions are constructed by composing (\emph{from
right to left}) a permutation $\sigma$ with a \emph{transposition}
$(i,j)$. It is easy to see that the number of the cycles of the
resulting permutation will be increased  by \emph{one} if $i$ and
$j$ are in the same cycle of $\sigma$, and decreased by one
otherwise.

The \emph{weight} of a permutation $\sigma\in \S_n$ is
$w(\sigma)=(-1)^{\cyc\sigma}x^{\exc\sigma}$, and that of a subset
$E\subseteq \S_n$ is the sum of the weights of its elements, i.e.,
$w(E)=\sum_{\sigma\in E}w(\sigma)$. Therefore, the basic idea of
proving an identity  is then to construct a subset $E$ of $\S_n$
whose weight is the right-side of the identity; and a
\emph{killing involution} on $\S_n\setminus E$, i.e. an involution
which preserves the number of excedances but changes the sign of
the weight of each element.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%
\section{Involutions for recursive proofs}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%
\subsection{Permutations}

Define the involution $\phi_1$ on $\S_n$ by
$$
\sigma\mapsto
\sigma'=(\sigma(n-1),\sigma(n))\circ\sigma.
$$
Clearly $\sigma'(j)= \sigma(j)$ if $j \neq n-1, n$, $\sigma'(n-1)=
\sigma(n)$, and $\sigma'(n)= \sigma(n-1)$. Let's partition $\S_n$
into three subsets:
\begin{eqnarray*}
\S_n^1&=&\{\sigma\in \S_n\mid \sigma(n-1)\ne n, \, \sigma(n)\ne
n\},\\
 \S_n^2&=&\{\sigma\in \S_n\mid \sigma(n)=n\},\\
\S_n^3&=&\{\sigma\in \S_n\mid \sigma(n-1)=n\}.
\end{eqnarray*}
It is easy to check that the restriction of $\phi_1$ to $\S_n^1$
is a killing involution, and the mapping
$\sigma\mapsto\sigma''=\sigma (1) \sigma(2)\cdots \sigma (n-1)$ is
a bijection from $\S_n^2$ to $\S_{n-1}$ such that
$w(\sigma)=-w(\sigma'')$, so the weight of $\S_n^2$ is
$-P_{n-1}(x,1,-1)$. Finally the restriction of $\phi_1$ to
$\S_n^3$ is a bijection from $\S_n^3$ to $\S_n^2$ such that
$w(\sigma)=-x\, w(\sigma')$. So the weight of $\S_n^3$ is
$xP_{n-1}(x,1,-1)$. Summarizing the above three cases yields
(\ref{eq7}).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%
\subsection{Derangements}
Let $U_n=\{\sigma \in \D_n\mid \sigma(2)= 1 \mbox{ and } \sigma(1)
\neq 2\}$. Clearly the mapping $\sigma\mapsto \sigma''=\bar \sigma
(1)\bar \sigma(3)\cdots \bar \sigma (n)$, where $\bar
\sigma(i)=\sigma(i)-1$, is a weight preserving bijection from
$U_n$ to $D_{n-1}$, so $w(U_n)=P_{n-1}(x,0,-1)$. Note also that
the weight of the cyclic permutation $\sigma_0=(1,\,2,\, \ldots,
\, n)$ is $-x^{n-1}$. Hence, to prove (\ref{eq8}) it remains to
construct a killing involution on $\overline{\D}_n=\D_n\setminus
(U_n\cup \{\sigma_0\})$. We claim that $\varphi_1 : \sigma\mapsto
(\sigma(i_\sigma),\sigma(i_\sigma+1)) \circ\sigma $ is such an
involution on $\overline{D}_n$, where $i_\sigma$ is the smallest
integer $i\in [n-1]$ such that $\sigma(i)\neq i+1$.

We first show that $\varphi_1$ is an involution on
$\overline{D}_n$. Let $\sigma\in \overline{D}_n$.

\begin{itemize}
\item $\varphi_1(\sigma)\in \D_n$ : if $i_\sigma=1$,
then $\sigma(1)\neq 2$ and by definition of $\sigma$, $\sigma
(2)\neq 1$; if $i_\sigma\neq 1$, then $\sigma (i_\sigma)\neq
i_\sigma+1$ and $\sigma (i_\sigma+1)\neq i_\sigma$ since $
i_\sigma$ is the image of $i_\sigma-1$ by definition of
$i_\sigma$.
\item $\varphi_1(\sigma)\notin U_n\cup \{\sigma_0\}$ :
If $i_\sigma=1$, $\varphi_1(\sigma)(2)=\sigma (1)\neq 1$ since
$\sigma\in \D_n$; otherwise $\varphi_1(\sigma)(1)=\sigma(1)= 2$.
So $\varphi_1(\sigma)\notin U_n$, moreover $\varphi_1(\sigma)\neq
\sigma_0$ because
\begin{equation}\label{*}
\varphi_1 (\sigma)(i_\sigma)=\sigma(i_\sigma+1)\neq i_\sigma+1,
\end{equation}

\item $\varphi_1$ is an involution :
for all $j<i_\sigma$, $\varphi_1(\sigma)(j)=\sigma(j)=j+1$, so
$\varphi_1(\sigma)=i_\sigma$ in view of (\ref{*}).
\end{itemize}
Next, we check that $\exc \varphi_1(\sigma)=\exc \sigma$: if
$\sigma(i_\sigma)>i_\sigma$ (resp. $<i_\sigma$), then
$\varphi_1(\sigma)(i_\sigma+1)=\sigma(i_\sigma)>i_\sigma+1$ (resp.
$<i_\sigma+1$); if $\sigma(i_\sigma+1)<i_\sigma+1$ (resp.
$>i_\sigma+1$), then
$\varphi_1(\sigma)(i_\sigma)=\sigma(i_\sigma+1)<i_\sigma$ (resp.
$>i_\sigma$) since $i_\sigma$ is the image of $i_\sigma-1$. Note
that the number of cycles changes by one, and so our involution reverses
 sign,  and hence is a killing involution on
$\overline{D}_n$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Involutions for bijective proofs }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Permutations}

Let $\Omega_n$ denote the set of permutations $\sigma$ in $\S_n$,
whose cycle decomposition consists of a $k$-cycle, $k\geq 1$, such
that
\begin{equation}\label{incr}
\sigma(1)<\sigma^2(1)<\cdots<\sigma^{k-1}(1),
\end{equation}
and $n-k$ singletons. Set $C_\sigma(1)=\{1,\sigma(1),\ldots,
\sigma^{k-1}(1)\}$, the orbit of $\sigma$ containing 1. It is not
hard to see that the weight of $\Omega_n$ is $-(x-1)^{n-1}$.
Therefore, to prove (2), it remains to construct a killing
involution on $\overline{\Omega}_n=\S_n\setminus \Omega_n$. Each
permutation $\sigma$ in $\overline\Omega_n$ can be characterized
by the condition that either the $k$-cycle containing 1 does not
satisfy the condition~(\ref{incr}) or there exists an $m$-cycle
($m>1$) disjoint with $C_\sigma(1)$; in other words, there exists
$i\in [n]$ such that
\begin{equation}\label{cond}
i\in C_{\sigma}(1)\quad \mbox{and }\quad\sigma^{-1}(i)>i>1,
\quad\mbox{ or}\quad i\notin C_{\sigma}(1)\quad
\mbox{and}\quad\sigma(i)\neq i.
\end{equation}
Let $i_\sigma$ denote the \emph{smallest} integer satisfying
(\ref{cond}) and $j_\sigma$ the \emph{largest} integer $<i_\sigma$
in $C_{\sigma}(1)$. Then we claim that the mapping $\phi_2 :
\sigma\mapsto\sigma \circ(i_{\sigma},j_{\sigma})$ is a killing
involution on $\overline\Omega_n$.

\begin{itemize}
\item Assume that $i_\sigma\in C_\sigma(1)$, then
there exist integers $p,q\geq 0$ such that $q<p$,
$i_\sigma=\sigma^p(1)$, $j_\sigma=\sigma^q(1)$ and the only
elements $<i_\sigma$ in $C_\sigma(1)$ are $1, \sigma(1),\ldots,
\sigma^q(1)=j_\sigma$. It follows that
$i_{\phi_2(\sigma)}=i_\sigma$ and $\phi_2$ is an involution. It
remains to check the corresponding values of $\sigma$ and
$\phi_2(\sigma)$ at $i_\sigma$ and $j_\sigma$. Clearly
$\sigma(j_\sigma)>i_\sigma$ and $\sigma(i_\sigma)<i_\sigma$ (resp.
$>i_\sigma$) if $\sigma(i_\sigma)=1$ (resp. otherwise). On the
other hand, $\phi_2(\sigma)(i_\sigma)=\sigma(j_\sigma)>i_\sigma$
and $$ \phi_2(\sigma)(j_\sigma)=\left\lbrace\begin{array}{ll}
\sigma(i_\sigma)=1\leq j_\sigma& \quad \hbox{if} \quad
\sigma(i_\sigma)=1;\\ \sigma(i_\sigma)>i_\sigma>j_\sigma& \quad
\hbox{otherwise}.
\end{array}
\right. $$ So $\exc \phi_2(\sigma)=\exc \sigma$.
\item The case where $i_\sigma\notin
C_\sigma(1)$ can be proved similarly. Note that if $i_\sigma\notin
C_\sigma(1)$, then $i_\sigma$ is the smallest element in
$C_\sigma(i_\sigma)$, and the only elements $<i_\sigma$ in
$C_\sigma(1)$ are $1,\sigma(1),\ldots, j_\sigma$, arranged in
increasing order. The rest of the verification is left to the
reader. \end{itemize}
\begin{rmq} 1. Since $n\notin \{i_\sigma,j_\sigma\}$ for
$\sigma\in \overline\Omega_n$, we see that $\phi_2$ is actually a
killing involution on $\overline\Omega_{n, j}:=\{\sigma\in
\overline\Omega_n\mid \sigma(n)=j\}$ for $j\in [n]$.\\ 2. It is
also easy to see that $\phi_2$ is a bijection between permutations
$\sigma\in \overline\Omega_n$ such that $i_\sigma\in C_\sigma(1)$
and those $\sigma\in \overline\Omega_n$ such that $i_\sigma\notin
C_{\sigma}(1)$.
\end{rmq}

We end with an example of $\phi_2$ for $n=4$ in Table~1. As
observed above, we need only to apply $\phi_2$ to permutations
$\sigma\in \overline\Omega_n$ with $i_\sigma\in C_\sigma(1)$.

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline $\sigma$ with $i_\sigma\in C_\sigma(1)$ & $i_\sigma$
&$j_\sigma$&$(\sigma(j_\sigma),\sigma(i_\sigma))$ &
$\phi_2(\sigma)$\\ \hline \hline 3\,4\,2\,1=(1,3,2,4) & 2&1 &
(3,4) & 4\,3\,2\,1=(1,4)(2,3)
\\
\hline 3\,1\,4\,2=(1,3,4,2) & 2&1 & (3,1) & 1\,3\,4\,2=(1)(2,3,4)
\\ \hline 4\,3\,1\,2=(1,4,2,3) & 2 &1 & (4,3) &
3\,4\,1\,2=(1,3)(2,4)
\\ \hline 4\,1\,2\,3=(1,4,3,2) & 2&1 & (4,1) &
1\,4\,2\,3=(1)(2,4,3)
\\ \hline 2\,4\,1\,3=(1,2,4,3) & 3&2 & (4,1) &
2\,1\,4\,3=(1,2)(3,4)
\\ \hline 3\,1\,2\,4=(1,3,2)(4) & 2&1 & (3,1) &
1\,3\,2\,4=(1)(2,3)(4) \\ \hline 4\,1\,3\,2=(1,4,2)(3) & 2&1 &
(4,1) & 1\,4\,3\,2=(1)(2,4)(3) \\ \hline 4\,2\,1\,3=(1,4,3)(2) &
3&1 & (4,1) & 1\,2\,4\,3=(1)(2)(3,4) \\ \hline
\end{tabular}
\medskip
\caption{ Involution $\phi_2$ for  $n=4$}
\end{center}
\end{table}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%
\subsection{Derangements}
Fix $j\in [n-1]$ and set  $D_{n,j}=\{\sigma\in \D_n \mid
\sigma(n)=j\}$. By definition, the weight of each $\sigma\in
D_{n,j}$ is $(-1)^{\cyc\sigma}x^{\exc\sigma}$, hence
the weight of
the cyclic permutation
$$ \sigma_{j}=\left( n, j, j+1, \ldots,
n-1, j-1, j-2, \ldots, 2, 1 \right)\in D_{n,j}
$$
is $-x^{n-j}$, to prove (\ref{eq6}) it remains to
construct a killing involution on
$\overline{D}_{n,j}=D_{n,j}\setminus\{\sigma_j\}$.

For $a,\,b\in [n]$, we say that $a$ is \emph{smaller} than $b$,
denoted $a\prec b$, if $a$ is to the left of $b$ in the word:
$$
w_j=n\, 1\, 2\, \ldots \, (j-2)\, (j-1)\, (n-1)\, \ldots \,
(j+1)\, j.
$$
For $\sigma\in
\overline{D}_{n,j}=D_{n,j}\setminus\{\sigma_j\}$ denote by
$i_\sigma$ the \emph{smallest} integer $i$ in the above word such
that $\sigma(i)\ne \sigma_j(i)$. We notice that $i_\sigma\neq n$
because $\sigma$ and $\sigma_j$ have the same value $j$ at $n$,
and also $i_\sigma\neq j$ because, otherwise, $\sigma$ and
$\sigma_j$ differ only at $j$ and coincide at all the other $
k\neq j$.

We claim that $\varphi_2:\sigma \longrightarrow (i_\sigma,
\sigma_j(i_\sigma))\circ \sigma$ is a killing involution on
$\overline{D}_{n,j}$. It suffices to check the following points :
\begin{itemize}
\item $\varphi_2(\sigma)\in \D_n$: First, by definition
of $i_\sigma$, $\sigma(i_\sigma)\ne \sigma_j(i_\sigma)$. Secondly,
if $i_\sigma=1$ then $\sigma(\sigma_j(i_\sigma))=j\neq i_\sigma$;
otherwise $\sigma(\sigma_j(i_\sigma))=\sigma_j^2(i_\sigma) \prec
i_\sigma$ since $\sigma_j$ maps each $ k\neq n$ to his left in
$w_j$. Thus $\sigma(\sigma_j(i_\sigma))\ne i_\sigma$.
\item $\varphi_2(\sigma)\in D_{n,j}$ : Since $i_\sigma\neq
j$ and $i_\sigma\neq n$ then $j\notin
\{i_\sigma,\sigma_j(i_\sigma)\}$. It follows that
$\varphi_2(\sigma)(n)=j$.
\item $\varphi_2(\sigma)\neq \sigma_j$ and
$i_{\varphi_2(\sigma)}=i_\sigma$ : For $k\prec i_\sigma$ and
$k\neq n$, since $\sigma(k)=\sigma_j(k)\neq \sigma_j(i_\sigma)$
and $\sigma(k)=\sigma_j(k)\prec k\prec i_\sigma$, then
$\sigma(k)\notin \{i_\sigma, \sigma_j(i_\sigma)\}$, which implies
that $\varphi_2(\sigma)(k)=\sigma_j(k)$. Since
$\varphi_2(\sigma)(i_\sigma)=\sigma(i_\sigma)\neq
\sigma_j(i_\sigma)$, then $\varphi_2(\sigma)\neq \sigma_j$ and
$i_{\varphi_2(\sigma)}=i_\sigma$.
\item $\exc \varphi_2(\sigma)=\exc\sigma$ : It suffices to
check the values of $\varphi_2(\sigma)$ and $\sigma$ at $k\in
[n-1]$ such that $\sigma(k)=i_\sigma$ or
$\sigma(k)=\sigma_j(i_\sigma)$. If $i_\sigma\leq j-1$ then
$\sigma$ maps $1,\, 2,\, \ldots, \, i_\sigma-1$ respectively to
$n,\,1,\,\ldots, i_\sigma-2$, so $\sigma^{-1}(i_\sigma)>i_\sigma$
and $\sigma^{-1}(i_\sigma-1)>i_\sigma$; if $i_\sigma=n-1$ then
$\sigma$ maps $1,\, 2,\, \ldots, \, j-1$ respectively to
$n,\,1,\,\ldots, j-2$, moreover $\sigma^{-1}(j)=n$, so
$j-1<\sigma^{-1}(n-1)<n-1$ and $j-1<\sigma^{-1}(j-1)<n-1$; if
$i_\sigma\in \{n-2,\ldots, j+1\}$ then $\sigma$ maps $1,2, \ldots,
j-~2, j-1, n-1, \ldots, i_\sigma+1$ respectively to $n, 1, \ldots,
j-1, n-1, \ldots, i_\sigma+2$, so $\sigma^{-1}(i_\sigma)<i_\sigma$
and $\sigma^{-1}(i_\sigma+1) <i_\sigma$. Summarizing
$\phi_2(\sigma)$ and $\sigma$ have the same number of excedances
at $\sigma^{-1}(i_\sigma)$ and $\sigma^{-1}(\sigma_j(i_\sigma))$.
\end{itemize}

As an example, we illustrate $\varphi_2$ for $n=5$. There are four
subsets $\overline{D}_{5,j}$ ($1\leq j\leq 4$) :

\begin{itemize}
\item subset $\overline{D}_{5,4}$ :
$\sigma_4=5\,1\,2\,3\,4$, $w_4=5\,1\,2\,3\,4$,
\begin{center}

\begin{tabular}{|c|c|c|c|}
\hline $\sigma$ & $i_\sigma$ & $\sigma_4(i_\sigma)$ & $(i_\sigma,
\sigma_4(i_\sigma))\circ \sigma$ \\ \hline \hline
2\,1\,5\,3\,4=(1,2)(3,5,4) & 1& 5 & 2\,5\,1\,3\,4=(1,2,5,4,3) \\
\hline 2\,3\,1\,5\,4=(1,2,3)(4,5) & 1 & 5 &
2\,3\,5\,1\,4=(1,2,3,5,4) \\ \hline 3\,1\,2\,5\,4=(1,3,2)(4,5) & 1
& 5 & 3\,5\,2\,1\,4=(1,3,2,5,4) \\ \hline
3\,5\,1\,2\,4=(1,3)(2,5,4) & 1 & 5& 3\,1\,5\,2\,4=(1,3,5,4,2) \\
\hline 5\,3\,2\,1\,4=(1,5,4)(2,3) &2 & 1 &
5\,3\,1\,2\,4=(1,5,4,2,3) \\ \hline
\end{tabular}

\end{center}

\item subset $\overline{D}_{5,3}$ :
$\sigma_3=5\,1\,4\,2\,3$, $w_3=5\,1\,2\,4\,3$,
\begin{center}

\begin{tabular}{|c|c|c|c|}
\hline $\sigma$ & $i_\sigma$ &$\sigma_3(i_\sigma)$ & $(i_\sigma,
\sigma_3(i_\sigma))\circ \sigma$ \\ \hline \hline
2\,1\,4\,5\,3=(1,2)(3,4,5) & 1 & 5& 2\,5\,4\,1\,3=(1,2,5,3,4) \\
\hline 2\,4\,5\,1\,3=(1,2,4)(3,5) &1 & 5 &
2\,4\,1\,5\,3=(1,2,4,5,3) \\ \hline 4\,1\,5\,2\,3=(1,4,2)(3,5) &1
& 5 & 4\,5\,1\,2\,3=(1,4,2,5,3) \\ \hline
4\,5\,2\,1\,3=(1,4)(2,5,3) &1 & 5 & 4\,1\,2\,5\,3=(1,4,5,3,2) \\
\hline 5\,4\,1\,2\,3=(1,5,3)(2,4) &2 & 1&
5\,4\,2\,1\,3=(1,5,3,2,4) \\ \hline
\end{tabular}

\end{center}

\item subset $\overline{D}_{5,2}$ :
$\sigma_2=5\,3\,4\,1\,2$, $w_2=5\,1\,4\,3\,2$,
\begin{center}

\begin{tabular}{|c|c|c|c|}
\hline $\sigma$ &$i_\sigma$ &$\sigma_2(i_\sigma)$ & $(i_\sigma,
\sigma_2(i_\sigma))\circ \sigma$ \\ \hline \hline
3\,4\,1\,5\,2=(1,3)(2,4,5) & 1 & 5 & 3\,4\,5\,1\,2=(1,3,5,2,4) \\
\hline 3\,5\,4\,1\,2=(1,3,4)(2,5) & 1&5& 3\,1\,4\,5\,2=(1,3,4,5,2)
\\ \hline 4\,3\,5\,1\,2=(1,4)(2,3,5) & 1& 5&
4\,3\,1\,5\,2=(1,4,5,2,3) \\ \hline 4\,5\,1\,3\,2=(1,4,3)(2,5) &
1& 5 & 4\,1\,5\,3\,2=(1,4,3,5,2) \\ \hline
5\,1\,4\,3\,2=(1,5,2)(3,4) & 4 & 1& 5\,4\,1\,3\,2=(1,5,2,4,3) \\
\hline
\end{tabular}

\end{center}

\item subset $\overline{D}_{5,1}$ :
$\sigma_1=2\,3\,4\,5\,1$, $w_1=5\,4\,3\,2\,1$,
\begin{center}

\begin{tabular}{|c|c|c|c|}

\hline $\sigma$ & $i_\sigma$ &$\sigma_1(i_\sigma)$ & $(i_\sigma,
\sigma_1(i_\sigma))\circ \sigma$\\ \hline \hline
2\,5\,4\,3\,1=(1,2,5)(3,4) & 4& 5 & 2\,4\,5\,3\,1=(1,2,4,3,5) \\
\hline 3\,4\,5\,2\,1=(1,3,5)(2,4)& 4& 5& 3\,5\,4\,2\,1=(1,3,4,2,5)
\\ \hline 5\,3\,4\,2\,1=(1,5)(2,3,4)& 4& 5 &
4\,3\,5\,2\,1=(1,4,2,3,5) \\ \hline 5\,4\,2\,3\,1=(1,5)(2,4,3)& 4
& 5& 4\,5\,2\,3\,1=(1,4,3,2,5) \\ \hline
4\,3\,2\,5\,1=(1,4,5)(2,3)& 3& 4& 3\,4\,2\,5\,1=(1,3,2,4,5)
\\
\hline
\end{tabular}

\end{center}

\end{itemize}

\begin{rmq}
 Chapman~\cite{Cha} has given
   a bijective proof of (\ref{eq6}) with  $x=1$, but
his involution does  not work for our purpose.
\end{rmq}
\small
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{99}
\bibitem{Bre} F. Brenti: \emph{ A Class of $q$-Symmetric
Function Arising from Plethysm}, J. Combin. Theory Ser. A, {\bf
91} (2000), 137-170.

\bibitem{Cha} R. Chapman: \emph{ An involution on
derangements}, Discrete Math., {\bf 231} (2001), 121--122.

\bibitem{Des2} J. D\'esarm\'enien: \emph{Une autre
interpr\'etation du nombre des d\'erangements}, Actes $8^e$
S\'eminaire Lotharingien, B08b, ed. D. Foata, publ. IRMA
Strasbourg (1984), 11--16. (Available electronically
at {\tt http://igd.univ-lyon1.fr/\~{}slc}.)

\bibitem{FH} D. Foata and G. N. Han:
\emph{Further properties of the second fundamental transformation
on words}, preprint, october 2003.


\bibitem{FS} D. Foata and M. P. Sch\"utzenberger: \emph{Th\'eorie
g\'eom\'etrique des polyn\^omes eul\'eriens}, Lecture Notes in
Mathematics,   Springer-Verlag, vol. 138, 1970.

\bibitem{Ges} I. M. Gessel: \emph{A coloring problem},
Amer. Math. Monthly, {\bf 98} (1991), 530--533.

\bibitem{Kim} D. Kim and J. Zeng: \emph{A new
decomposition of derangements},  J. Combin. Theory Ser. A,
{\bf 96} (2001), no. 1, 192--198.

\bibitem{Sta} R. P. Stanley: \emph{Enumerative
Combinatorics}, vol.~1 and 2, Cambridge University Press, 1997.

\bibitem{Wac} M. L. Wachs: \emph{An involution for signed
Eulerian numbers}, Discrete Math., {\bf 99}, (1992), 59--62.

\end{thebibliography}

\end{document}