%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[final]{FPSAC2022}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{mathrsfs,cases,
	latexsym,mathtools,mathdots,booktabs,colortbl,xparse,tikz,bm}

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\newtheorem{problem}[theorem]{Problem}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}


\newcommand{\oeis}[1]{\href{http://oeis.org/#1}{#1}}
\newcommand{\thsup}{\textnormal{th}}

\newcommand{\setN}{\mathbb{N}}

\newcommand{\xvec}{\mathbf{x}}
\newcommand{\yvec}{\mathbf{y}}
\newcommand{\wvec}{\mathbf{w}}
\newcommand{\vvec}{\mathbf{v}}


\newcommand{\symS}{\mathfrak{S}}
\newcommand{\dArr}{\mathfrak{D}}
\newcommand{\bdArr}{\mathfrak{BD}}

% Sets 
\newcommand{\SEF}{\mathcal{F}}  % Set of subexcedant functions
\newcommand{\DSEF}{\mathcal{DF}}%Elements in F, which are derangements


% The special involution on subexcedant functions
\newcommand{\frether}{\widehat{\Psi}}
%\newcommand{\fretherD}{\widehat{\Psi}}
\newcommand{\fretherD}{\Psi}

\newcommand{\fretherDConj}{\widehat{\Phi}}


\NewDocumentCommand\eqCond{o}{%
	\IfNoValueTF{#1}{%
		{${\circledast}$}%
	}{%
		{${\circledast_{#1}}$}%
}}


\NewDocumentCommand\caseOne{o}{%
	\IfNoValueTF{#1}{%
		{\ensuremath{\heartsuit}}%
	}{%
		{\ensuremath{\heartsuit_{#1}}}%
}}

\NewDocumentCommand\caseTwo{o}{%
	\IfNoValueTF{#1}{%
		{\ensuremath{\spadesuit}}%
	}{%
		{\ensuremath{\spadesuit_{#1}}}%
}}


\NewDocumentCommand\caseThree{o}{%
	\IfNoValueTF{#1}{%
		{\ensuremath{\diamondsuit}}%
	}{%
		{\ensuremath{\diamondsuit_{#1}}}%
}}


\NewDocumentCommand\caseFour{o}{%
	\IfNoValueTF{#1}{%
		{\ensuremath{\clubsuit}}%
	}{%
		{\ensuremath{\clubsuit_{#1}}}%
}}


\newcommand{\img}{\mathbf{m}}

%Math operators
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\type}{type}
\DeclareMathOperator{\length}{\ell}
\DeclareMathOperator{\cycle}{\mathfrak{c}}

\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\DES}{DES}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\FIX}{FIX}

\DeclareMathOperator{\exc}{exc}
\DeclareMathOperator{\EXCi}{EXCi}
\DeclareMathOperator{\EXCv}{EXCv}

\DeclareMathOperator{\rlm}{rlm}
\DeclareMathOperator{\RLMv}{RLMv}
\DeclareMathOperator{\RLMi}{RLMi}

\DeclareMathOperator{\zig}{zig}
\DeclareMathOperator{\ZIG}{ZIGx}
\DeclareMathOperator{\ZIGv}{ZIGv}
\DeclareMathOperator{\ZIGi}{ZIGi} %Same as peaks
\DeclareMathOperator{\peaks}{peaks}
\DeclareMathOperator{\PEAKS}{PEAKS}


\DeclareMathOperator{\aexc}{sae} % strict anti-excedance
\DeclareMathOperator{\supp}{IM}

\DeclareMathOperator{\fixMap}{\mathtt{fix}}
\DeclareMathOperator{\unfixMap}{\mathtt{unfix}}
\DeclareMathOperator{\sefToPerm}{\mathtt{sefToPerm}}
\DeclareMathOperator{\flipMap}{\mathtt{flip}}
\DeclareMathOperator{\zetaMap}{\zeta}




%\usepackage{lipsum}

%% define your title in the usual way
\title{An Involution on Derangements Preserving Excedances and Right-to-Left Minima}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[P.~Alexandersson and F.~Getachew]{Per Alexandersson\thanks{\href{mailto:per.w.alexandersson@gmail.com}{per.w.alexandersson@gmail.com}, \href{mailto:frigetach@gmail.com}{frigetach@gmail.com}}\addressmark{1} \and Frether Getachew\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Stockholm University, SE-106 91 Stockholm, Sweden \\ \addressmark{2}Department of Mathematics, Addis Ababa University, Ethiopia}

%% put the date of submission here
\received{2021-11-19}

%% leave this blank until submitting a revised version
\revised{2022-03-21}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We give a bijective proof of a result by R.~Mantaci and F.~Rakotondrajao from 2003
	regarding even and odd derangements with a fixed number of excedances.
	We refine their result by also considering the set of right-to-left minima.}

%% put your French abstract here, or comment this out if you don't have one
%%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{derangement, excedance, right-to-left minimum}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction and Notations}
A permutation $\pi$ is a bijection from the set $[n]=\{1, 2, \dotsc, n\}$ to itself and we will write it in standard representation as $\pi=\pi(1)\,\,\pi(2)\dotsb \pi(n)$, or as the product of disjoint cycles. We let $\symS_n$ be the the symmetric group, the set of all permutations, acting on $[n]$. A \textit{fixed point} of a permutation $\pi$ is an integer $i\in [n]$ such that $\pi(i)=i$. Let $\dArr_n\subseteq\symS_n$ denote the set of permutations with no fixed points, which are called \textit{derangements}. An \textit{inversion} of a permutation 
$\pi$ is a pair $(i,j)$ such that 
$\pi(i)>\pi(j)$, where 
$1\leq i < j \leq n$. The parity of a permutation $\pi$ is defined as the parity of the number of
inversions of $\pi$, $\inv(\pi)$. That is, $\pi$ is called an \textit{even} if $\inv(\pi)$ is even, and an \textit{odd} permutation otherwise. The set of even 
permutations in $\symS_n$ is denoted
$\symS^e_n$, and the set of odd 
permutations is $\symS^o_n$. Similarly,
$\dArr^e_n$ and $\dArr^o_n$ represent
the sets of even and odd 
derangements, respectively, in $\dArr_n$.  


In order to state our results, we need to 
recall some standard terminology and notations.
For any function $g \colon [n]\to [n]$, let 
the set of \textit{excedances}, the set of \textit{excedance values}, the set of 
\textit{right-to-left minima indices}, the set of \textit{right-to-left minima values}, and the fixed point set respectively, are defined as 
\begin{align*}
	\EXCi(g) &\coloneqq \{ j \in [n] : g(j)>j \}, \\
	\EXCv(g) &\coloneqq \{ g(j) : j \in \EXCi(g) \}, \\
	\RLMi(g) &\coloneqq  \{i\in [n]: g(i)<g(j) \text{ for all } j\in \{i+1,\dotsc,n\} \},\\
	\RLMv(g)  &\coloneqq  \{ g(i) : i \in \RLMi(g)\}, \\
   \FIX(g) &\coloneqq \{ i\in[n] : g(i)=i \}.
\end{align*}
Moreover, we denote $\exc(g) \coloneqq |\EXCi(g)|$ and $\rlm(g) \coloneqq |\RLMi(g)| = |\RLMv(g)|$. Note that,  $|\EXCv(\sigma)|=|\EXCi(\sigma)|=\exc(\sigma)$, for any $\sigma\in \symS_n$.

\begin{example}
	Consider the following three permutations in $\symS_7$.
	The first is not a derangement since it has $3$ and $6$ as 
	fixed-points, while the remaining two are derangements.
	\begin{center}
		\begin{tabular}{l c llll}
			Permutation, $\pi$ & $\inv(\pi)$ & $\EXCi(\pi)$ &  $\RLMi(\pi)$ & $\RLMv(\pi)$  \\
			\midrule 
			2135764 & 5 & \{1,4,5\} & \{2,3,7\} & \{1,3,4\}  \\
			2153746 & 5 & \{1,3,5\} & \{2,4,6,7\} & \{1,3,4,6\}  \\
			6713245 & 11 & \{1,2\} & \{3,5,6,7\} & \{1,2,4,5\} 
		\end{tabular}
	\end{center}
\end{example}
 Note that whenever $S = \{s_1,\dotsc,s_m\}$ is a finite set 
 of positive integers,
 we shall let $\xvec_S$ denote the product $x_{s_1}x_{s_2}\dotsm x_{s_m}$.
 By definition, $\xvec_\emptyset \coloneqq 1$.

\bigskip
R.~Mantaci and F.~Rakotondrajao~\cite{Mantaci2003}
have proven\footnote{Their proof uses a recursion rather than an explicit involution.} the identity
\begin{equation}\label{eq:mainEquation}
	|\{ \pi \in \dArr^e_n  : \exc(\pi) = k \}|
	-
	|\{ \pi \in \dArr^o_n  : \exc(\pi)=k \}|
	=(-1)^{n-1},
\end{equation}
for every $n\geq 1$ and $1 \leq k \leq n-1$.
This refines a result by Chapman, stating that
$|\dArr^e_n|-|\dArr^o_n|=(-1)^{n-1}(n-1)$, see \cite{Chapman2001}.

\medskip
We provide a proof for a refinement of \eqref{eq:mainEquation}, namely
\begin{equation*}\label{eq:mainResult}
	\sum_{\pi \in \dArr_n} (-1)^{\inv(\pi)} 
	\xvec_{\RLMv(\pi)} \yvec_{ \EXCv(\pi)} 
	= 
	(-1)^{n-1} \sum_{j=1}^{n-1} x_1 \!\dotsm \! x_j y_{j+1}  \!\dotsm  \! y_{n},
\end{equation*}
in \cref{sec:involution}, by exhibiting a bijection and by using generating functions. The bijection $\frether \colon \dArr_n \to \dArr_n$
with exactly $(n-1)$ fixed-elements, is a sign-reversing involution outside the set of fixed-elements. Moreover, it preserves
the excedance value and right-to-left minima permutation statistics,
which gives the desired result. We use the code obtained in \cite{Mantaci2001}, which defined as follows.
\begin{definition}\label{subex}
	A \textit{subexcedant function}  $f$ on $[n]$ is a map $f \colon [n] \to [n]$
	such that
	\begin{equation*}
		1\leq f(i)\leq i \text{ for all } 1\leq i\leq n.
	\end{equation*}
	We let $\SEF_n$ denote the set of all 
	subexcedant functions on $[n]$. 
	The \textit{image} of $f \in \SEF_n$ is defined as
	$\supp(f) \coloneqq \{ f(i) : i \in [n] \}$.
\end{definition}
We write subexcedant functions as words, $f(1)f(2)\dotsc f(n)$.
For example, the subexcedant function $f=112352$ has $\supp(f)=\{1,2,3,5\}$.

From each subexcedant function $f \in \SEF_{n-1}$,
one can obtain $n$ distinct subexcedant functions in $\SEF_{n}$ by appending
any integer $i\in [n]$ at the end of the word representing $f$.
Hence, the cardinality of $\mathcal{F}_n$ is $n!$.
The bijection $\sefToPerm \colon \SEF_n \to \symS_n$,
described in \cite{Mantaci2001}, is defined by the product:
\begin{equation*}\label{eq:sefToPerm}
	\sefToPerm(f) \coloneqq (n\,\,f(n))  \dotsm (2\,\,f(2)) (1\,\,f(1)).
\end{equation*}


For $\sigma \in \symS_n$ and $j \in [n]$, the $j^\thsup$ entry of $\sefToPerm^{-1}(\sigma)$
is express in the recursive formula:
\begin{equation}\label{eq:permToSefRecursion}
	\sefToPerm^{-1}(\sigma)_j \coloneqq 
	\begin{cases}
		\sigma(n) & \text{if $j=n$,} \\
		\sefToPerm^{-1}\big( \left(n\,\,\sigma(n)\right)\circ\sigma \big)_j & \text{otherwise}.
	\end{cases}
\end{equation}
Note that $\sigma' \coloneqq \left(n\,\,\sigma(n)\right)\circ\sigma$
is the result after interchanging $n$ and the image of $n$ in $\sigma$.
Therefore, $\sigma'(n)= n$ and, by a slight abuse of notation, $\sigma'$ can be considered as a permutation in $\symS_{n-1}$.
For simplicity, we use the shorthand $f_\sigma \coloneqq \sefToPerm^{-1}(\sigma)$.


\begin{example} The corresponding subexcedant function of the permutation $\sigma \! = \! 6\,1\,2\,9\,3\,5\,4\,8\,7$ is $f_\sigma = 112435487 \in \SEF_9$.
\end{example}

Since subexcedant functions are maps on $[n]$, we have the notion of excedance, right-to-left minima, fixed points, etc., as defined above.

\begin{proposition}[{See \cite[Proposition~3.5]{Mantaci2001}}]\label{prop:excAsIm}
	For $f_{\sigma} \in \SEF_n$ we have that
	$
	[n] \setminus \supp(f_{\sigma}) = \EXCv(\sigma).
	$
	In particular, $\exc(\sigma) = n - |\supp(f_{\sigma})|$.
\end{proposition}

We say that a subexcedant function $f$ has a \textit{strict anti-excedance} at $i$ if $f( i ) < i$.

\begin{proposition}[{See \cite[Proposition~4.1]{Mantaci2001}}]\label{prop:evenSEF}
	The permutation $\sigma$ is even (odd) if and only if the number of strict anti-excedances in $f_{\sigma}$ even (odd).
\end{proposition}

A fixed point of $f \in \SEF_n$ is an integer $i \in [n]$ such that $f(i)=i$.
Moreover, $i$ is a \textit{multiple fixed point} of $f$ if $f(i)=i$ and there is some $j>i$ such that $f(j)=i$.

\begin{proposition}[{See \cite[Proposition~3.8]{Mantaci2001}}]\label{prop:derangmentSEF}
	We have that $\sigma \in \dArr_n$ if and only if all
	fixed points of $f_{\sigma}$ are multiple.
\end{proposition}

\begin{proposition}\label{prop:rlmForSEF}
	Let $\pi\in\symS_n$ and $f_{\pi}$ be the corresponding subexcedant function. 
	Then
	\begin{enumerate}[label=(\alph*)]
		\item $i \in \RLMi(\pi)$ implies $\pi(i)=f_{\pi}(i)$,
		\item $\RLMv(\pi) = \RLMv(f_{\pi})$,
		\item $\RLMi(\pi) = \RLMi(f_{\pi})$.
	\end{enumerate}
\end{proposition}

\section{An involution and its consequences}\label{sec:involution}


A subexcedant function $f$ is \textit{matchless}
if it is of the form
\[
f\coloneqq 1\,1\,2\,3\,4\dotsc k{-}1\,\,k\,\,k\dotsc k \quad \text{  for $1\leq k \leq n{-}1$}.
\]
There are $n-1$ matchless subexcedant functions of length $n$. For example, for $n=10$, the following subexcedant functions are matchless:
\[
\begin{array}{c@{\qquad}c@{\qquad}c}
	1111111111, & 1122222222, & 1123333333, \\
	1123444444, & 1123455555, & 1123456666, \\
	1123456777, & 1123456788, & 1123456789. 
\end{array}
\]

Let $\DSEF_n$ be the set of subexcedant functions corresponding to derangements of $[n]$. Note that  every $f \in \DSEF_n$ must have at least two $1$'s
in its row representation. 

For any matchless $f_{\sigma}\in\DSEF_n$ 
\[
\sigma =\sefToPerm(f_\sigma)=(1\,\,k{+}1\,\,k{+}2 \; \dotsc\; n\,\,k\,\,k{-}1 \; \dotsc \; 2).
\] 
Since $\sigma$ has only one cycle, its sign is $(-1)^{n-1}$. Looking directly at the definition of $f_{\sigma}$, we have that
\[
\supp(f_{\sigma}) = [k] \; \text{ implies } \; \EXCv(\sigma) = [n]\setminus [k],
\]
by \cref{prop:excAsIm}. Similarly, from 
\cref{prop:rlmForSEF} we have $\RLMv(\sigma)=[k]$.

\begin{definition}
Define a mapping $\fretherD \colon \DSEF_n \to \DSEF_n$ below,  
where $f_{\tau}$ is short for $\fretherD(f_{\sigma})$.
First, if $f_\sigma$ is matchless, we set $f_\tau\coloneqq f_\sigma$.
%
Now we assume that $f_{\sigma}$ is non-matchless and  let 
\begin{equation*}\label{eq:supp}
	\supp(f_{\sigma})=\{ \img_1, \img_2, \img_3, \dotsc, \img_{\ell} \}.
\end{equation*}
Note that $\img_1=1$ and  since $f_\sigma$ is non-matchless,
we know that $\ell \geq 2$ in $\supp(f_{\sigma})$.
%
With these preparations, we define two auxiliary maps, 
$\fixMap_i$, $\unfixMap_i$ on subexcedant functions.
For $i \in \{2,\dotsc,\ell\}$,
\begin{equation*}
	\fixMap_i(f_\sigma)(\img_i) \coloneqq \img_i, \qquad 
	\unfixMap_i(f_\sigma)(\img_{i}) \coloneqq\img_{i-1}
\end{equation*}
while the remaining entries of $f_\sigma$ are untouched.
%
For  $i \in \{2,\dotsc,\ell\}$, we say that $f_\sigma$ satisfies \eqCond[i] if the three conditions
\begin{equation}\label{eq:case34Conditions}
	\begin{aligned}
		f_{\sigma}(\img_i) < \img_i < \img_\ell,\quad
		f^{-1}_\sigma(1) = \{1,2\}, \text{ and }
		\{\img_i + 1\}\subsetneq f^{-1}_\sigma(\img_i)
	\end{aligned} \tag{\text{\eqCond[i]}},
\end{equation}
hold. 
Note that 
\[
\{\img_i + 1\}\subsetneq f^{-1}_\sigma(\img_i) \text{ if and only if }
f_\sigma(\img_i + 1) = \img_i \text{ and } |f^{-1}_\sigma(\img_i)| \geq 2.
\]

\medskip 

Now let $i\in\{2,\dotsc,\ell\}$ be the \emph{smallest} element
satisfying one of the cases below,
and let $f_\tau$ be given as described in each case.
%
%
\begin{itemize}[leftmargin=2cm]
	\item[\textbf{Case \caseOne[i]:}] If $f_{\sigma}(\img_i) = \img_i$,
	then $f_\tau \coloneqq \unfixMap_i(f_\sigma)$.
	
	\item[\textbf{Case \caseTwo[i]:}] If $f_{\sigma}(\img_i) < \img_i$ and $|f^{-1}_\sigma(1)| \geq 3$,
	then $f_\tau \coloneqq \fixMap_i(f_\sigma)$.
	
	\item[\textbf{Case \caseThree[i]:}] \label{case3a} 
	If \eqCond[i] holds and $f_\sigma(\img_{i+1}) = \img_{i+1}$, then
	$
	f_\tau \coloneqq \unfixMap_{i+1}(f_\sigma).
	$
	
	\item[\textbf{Case \caseFour[i]:}] \label{case4} 
	If \eqCond[i] holds and $f_\sigma(\img_{i+1}) < \img_{i+1}$, then
	$
	f_\tau \coloneqq \fixMap_{i+1}(f_\sigma).
	$
\end{itemize}
Note that for the same $i$, the four cases are mutually exclusive.
We emphasize that by saying that a case with subscript $i$ holds,
this particular $i \geq 2$ is the smallest $i$ for which the conditions one of the four cases hold.
\end{definition}

\begin{remark}\label{rem:case2}
	Suppose \caseTwo[i] applies for $f_\sigma$.
	Then, for sure $f_\sigma(\img_2) < \img_2$, since otherwise, we would be in the case \caseOne[2]. 
	Hence, \caseTwo[i] may only apply when $i=2$.
\end{remark}
\begin{theorem}
	The map $\fretherD \colon \DSEF_n \to \DSEF_n$ is an involution with the following properties.
	\begin{enumerate}[label=(\roman*)]		
		\item The image is preserved, $\supp(f_{\sigma}) = \supp(\fretherD(f_\sigma))$.
		\item If $f_\tau=\fretherD(f_\sigma)$, then $\EXCv(\sigma) = \EXCv(\tau)$. 
		\item The set of right-to-left minima is preserved, $\RLMv(f_\sigma)=\RLMv(\fretherD(f_\sigma))$.
		\item $\fretherD$ changes the parity of a non-matchless subexcedant function.
	\end{enumerate}
\end{theorem}
The complete proof of this theorem can be found in \cite{alexandersson2021involution}.
\begin{example}\label{eg:main}
	Consider the following four subexcedant functions in $\DSEF_7$.
	\begin{enumerate}
		\item Let $f_\sigma=1133535$. Then 
		$\supp(f_\sigma)=\{1, 3, 5\}$ and 
		$2$ is the smallest index greater than 
		$1$ with
		$f_\sigma(\img_2)=f_\sigma(3)=3$. Hence, $f_\sigma$ is in case 
		\caseOne[2] and $f_\tau= 
		\unfixMap_2(f_\sigma)=1113535$.
		\item Now let $f_\sigma=1121355$. Then 
		$\supp(f_\sigma)=\{1, 2, 3, 5\}$. Since $f_\sigma(2)<2$ 
		and $|f_\sigma^{-1}(1)|=3$, then $f_\sigma$ is in case \caseTwo[2]. Thus, $f_\tau= 
		\fixMap_2(f_\sigma)=1221355$.
		\item Suppose that $f_\sigma=1123535$, then 
		$\supp(f_\sigma)=\{1, 2, 3, 5\}$. The index $2$ does not satisfy any of the four cases. So, we consider the next integer $i=3$. We note that \eqCond[3] holds and in 
		addition, 
		$f_\sigma(\img_{4})=f_\sigma(5)=5$. 
		Hence, $f_\sigma$ fulfills \caseThree[3]  and 
		$f_\tau= 
		\unfixMap_{i+1}(f_\sigma)=\unfixMap_{4}(f
		_\sigma)=1123335$.
		\item Now take $f_\sigma=1123445$. Then 
		$\supp(f_\sigma)=\{1, 2, 3, 4, 
		5\}$. None of the four cases for $f_\sigma$ are fulfilled 
		with $i\in\{2,3\}$. However, $f_\sigma$ 
		satisfies \eqCond[4] and 
		$f_\sigma(\img_{5})=f_\sigma(5)=4<\img_{5}$. 
		Thus, we are in \caseFour[4] and $f_\tau=\fixMap_{5}(f_\sigma)=1123545$.
	\end{enumerate}
\end{example}

We now have an involution on derangements $\frether:\dArr_n \to \dArr_n$
by setting
\[
\frether(\sigma) \coloneqq (\sefToPerm \circ \fretherD \circ \sefToPerm^{-1})(\sigma),
\text{ for $\sigma \in \dArr_n$}.
\]

\begin{corollary}\label{cor:frethermap}
	The involution $\frether$ satisfies the properties below:
	\begin{enumerate}[label=(\roman*)]
		\item The excedance value set is preserved:  $\EXCv(\frether(\sigma)) = \EXCv(\sigma).$
		\item 
		The set of right-to-left minima is preserved:
		$\RLMv( \frether(\sigma)) = \RLMv(\sigma )$.
		\item 
		Whenever $\sigma$ is a \textit{non-matchless derangement} (the corresponding $f_\sigma$ is non-matchless), 
		$\frether$ changes the parity of $\sigma$.
	\end{enumerate}
\end{corollary}
\begin{theorem}\label{thm:theMainTheorem}
	We have that 
	\begin{equation}\label{eq:mainResultInText}
		\sum_{\pi \in \dArr_n} (-1)^{\inv(\pi)} 
		\xvec_{\RLMv(\pi)} \yvec_{ \EXCv(\pi)} 
		=
		(-1)^{n-1} \sum_{j=1}^{n-1} x_1 \dotsm x_j \cdot y_{j+1}\dotsm y_{n}.
	\end{equation} 
	Moreover, 
	\begin{equation}\label{eq:mainResultInText2}
		\sum_{\pi \in \dArr_n} (-1)^{\inv(\pi)} 
		\xvec_{\RLMi(\pi)} 
		\yvec_{\EXCi(\pi)}
		=
		(-1)^{n-1} \sum_{j=1}^{n-1} y_1 \dotsm y_j \cdot x_{j+1}\dotsm x_{n}.
	\end{equation} 
\end{theorem}
\begin{proof}
	By applying the involution $\frether$ and 
	using all the properties listed in \cref{cor:frethermap},
	all terms in the left-hand side of \eqref{eq:mainResultInText} that are non-matchless derangements cancel. Thus, the left-hand side of \eqref{eq:mainResultInText} is equal to
	\begin{equation*}
		\sum_{k=1}^{n-1}
		(-1)^{n-1} \xvec_{[k]} \yvec_{[n] \setminus [k]},
	\end{equation*}
using properties of matchless derangements,
	which is the right-hand side of~\eqref{eq:mainResultInText}.
	\medskip
	
	Equation~\eqref{eq:mainResultInText2} follows by applying the change of variables $i\mapsto n+1-i$ on both sides
	of~\eqref{eq:mainResultInText} and then use the bijection  $\zeta:\dArr_n \to \dArr_n$, where
	\[
	\zeta(\sigma)(k) \coloneqq n+1-\sigma^{-1}(n+1-k), \quad \text{ for }\sigma\in\dArr_n\text{ and } k\in [n],
	\] 
	on the left-hand side.
\end{proof}

\begin{corollary}
	By letting $x_j \to 1$ and $y_j \to t$, we have that 
	\begin{equation*}
		\sum_{\pi \in \dArr_n} (-1)^{\inv(\pi)} t^{\exc(\pi)}
		=
		(-1)^{n-1}(t+t^2+\dotsb+t^{n-1}).
	\end{equation*}
	By comparing coefficients of $t^k$,
	we get \eqref{eq:mainEquation}.
	%
	In a similar manner,
	\begin{equation*}
		\sum_{\pi \in \dArr_n} (-1)^{\inv(\pi)} t^{\rlm(\pi)}
		=
		(-1)^{n-1}(t+t^2+\dotsb+t^{n-1}).
	\end{equation*}
\end{corollary}

\section{A proof using generating functions}\label{sec:genFunc}

Mantaci, in \cite{Mantaci1993}, proved \cref{lem:excEvenOdd} (albeit stated in a slightly different manner) by introducing a bijection on $\symS_n$ that preserves the set of excedances and changes the sign of non-fixed elements of the bijection. There is a unique fixed element for each excedance set and its parity is the same as the parity of the cardinality of its excedance set. 
\begin{proposition}\label{lem:excEvenOdd}
	Let $n \geq 1$, then
	\begin{equation}\label{eq:excEvenOdd}
		\sum_{\substack{\pi \in \symS_n}} (-1)^{\inv(\pi)} \xvec_{\EXCi(\pi)} = 
		\prod_{j \in [n-1]} (1-x_j) = \sum_{E \subseteq [n-1]} (-1)^{|E|}\xvec_{E}.
	\end{equation}
	In particular, by setting all $x_i$ equal to $t$, 
	we have
	\[
	\sum_{\substack{\pi \in \symS^e_n}} t^{\exc(\pi)} 
	-
	\sum_{\substack{\pi \in \symS^o_n }} t^{\exc(\pi)} = (1-t)^{n-1}.
	\]
\end{proposition}

\begin{proposition}\label{prop:main}
	Let $n\geq 1$ and let $T \subseteq [n]$. 
	Let $m \leq n$ be the largest integer not in $T$ and set
	$
	E = \{1,2,\dotsc,m-1\} \setminus T.
	$
	Then
	\begin{equation}\label{eq:main}
		\sum_{\substack{\pi \in \symS_n  \\ T \subseteq \FIX(\pi)  }} 
		(-1)^{\inv(\pi)} \xvec_{\EXCi(\pi)} =  
		\prod_{j \in E} (1-x_j),
	\end{equation}
	where the empty product has value $1$.
	
	Setting all $x_i$ to be $t$, we have
	\begin{equation*}
		\sum_{\substack{\pi \in \symS^e_n  \\ T \subseteq \FIX(\pi)  }} t^{\exc(\pi)}
		-
		\sum_{\substack{\pi \in \symS^o_n \\ T \subseteq \FIX(\pi)   }} t^{\exc(\pi)}
		= 
		\begin{cases}
			1 & \text{if $|T|=n$,} \\
			(1-t)^{n-1-|T|} & \text{otherwise.}
		\end{cases}
	\end{equation*}
\end{proposition}
\begin{proof}
	if $T=[n]$, then $E = \emptyset$  and \eqref{eq:main} follows. Now assume $|T| < n$. From formation of $E$, we can easily see that $|E| = n-1-|T|$.
	Now suppose $\pi \in \symS_n$ is a permutation such that $T \subseteq \FIX(\pi)$.
	We then construct $\pi' \in \symS_{n-|T|}$, by only considering the positions not in $T$,
	and the relative ordering of the entries at these positions.
	For example, for $\pi=127436589$ we have $T=\{2,4,6,8,9\}$,
	$[n] \setminus T = \{1,3,5,7\}$ and  $\pi' = 1423$.
	
	 Observe that $\exc(\pi) = \exc(\pi')$ and $(-1)^{\inv(\pi)} = (-1)^{\inv(\pi')}$. Hence, the sum in the left-hand side of \eqref{eq:main},
	can be taken as a sum over permutations $\pi' \in \symS_{n-|T|}$,
	but with a reindexing of the variables using values in $[n] \setminus T$.
	Now, this sum can be computed using \cref{lem:excEvenOdd}
	which finally gives \eqref{eq:main}.
\end{proof}
Using inclusion-Exclusion and \cref{prop:main}, the following theorem is obtained.
\begin{theorem}\label{thm:mainGenFunc}
	Let $n\geq 1$. Then
	\begin{equation}\label{eq:derangementSum}
		\sum_{\pi \in \dArr_n } (-1)^{\inv(\pi)} \xvec_{\EXCi(\pi)} = 
		(-1)^{n-1} \sum_{j=1}^{n-1} x_{1}x_{2}\dotsm x_{j}.
	\end{equation}
\end{theorem}
The following  follows directly by comparing coefficients of degree $k$ in \eqref{eq:derangementSum}.
\begin{corollary}
	For $n,k \geq 1$, we have that
	\[
	|\{ \pi \in \dArr^e_n : \exc(\pi) = k \}|-|\{ \pi \in \dArr^o_n : \exc(\pi) = k \}| = (-1)^{n-1}.
	\]
\end{corollary}

\subsection{A right-to-left minima analog}

\begin{definition}
	Let $\kappa : \symS_n \to \symS_n$ be defined as follows.
	Given $\pi \in \symS_n$, let $i \in [n]$ be the smallest \emph{odd} integer 
	such that $\pi (i \; i+1)$ and $\pi$ have the same sets of right-to-left minima,
	if such an $i$ exists. That is, we swap the entries at positions $i$ and $i+1$ in $\pi$.
	%
	We then set $\kappa(\pi) \coloneqq \pi (i \; i+1)$,
	and $\kappa(\pi) \coloneqq \pi$ otherwise.
	We say that $\pi$ is \textit{decisive}\footnote{As a nod to the word \emph{critical}.}
	if it is a fixed-element of $\kappa$.
\end{definition}

\begin{example}
	In $\symS_7$, there are $8$ decisive permutations:
	\[
	1234567,\;
	1234657,\;
	1243567,\;
	1243657,\;
	2134567,\;
	2134657,\;
	2143567,\;
	2143657.
	\]
	Note that $\{1,3,5,7\}$ are always right-to-left minima (but there might be more).
\end{example}

\begin{lemma}\label{lem:ltrMinEvenOdd}
	The map $\kappa : \symS_n \to \symS_n$ has the following properties:
	\begin{enumerate}[label=({\roman*})]
		\item \label{it:kappaprop1} $\kappa$ is an involution.
		\item \label{it:kappaprop2} $\kappa$ preserves the number of right-to-left minima.
		\item \label{it:kappaprop3} $\kappa$ changes sign of non-fixed elements.
		\item \label{it:kappaprop4} 
		For each subset $T \in [n] \cap \{2,4,6,\dotsc\}$,
		there is a unique decisive permutation with 
		$\{1,3,5,\dotsc\} \cup T$ as right-to-left minima set.
		
		\item \label{it:kappaprop5} 
		There are $\binom{ \lfloor n/2 \rfloor }{k - \lceil n/2 \rceil}$
		decisive permutations with exactly $k$ right-to-left minima,
		and they all have sign $(-1)^{n-k}$.
	\end{enumerate}
\end{lemma}

The following is a right-to-left minima analog of \cref{lem:excEvenOdd}.

\begin{corollary}\label{cor:rlminsum}
	We have that for any $n\geq 1$
	\begin{equation}\label{eq:rlminSymSum}
		\sum_{\substack{\pi \in \symS_n   }} (-1)^{\inv(\pi)} \xvec_{\RLMv(\pi)}
		= 
		\big(\prod_{\substack{i \in [n] \\ i \text{ odd}}} x_i\big)
		\big(\prod_{\substack{j \in [n] \\ j \text{ even}}} (x_j-1)\big).
	\end{equation}
	In particular, for any $k = 1,\dotsc,n$ we have that
	\[
	|\{ \pi \in \symS^e_n : \rlm(\pi)=k \}| - 
	|\{ \pi \in \symS^o_n : \rlm(\pi)=k \}| = (-1)^{n-k}
	\binom{ \lfloor n/2 \rfloor }{k - \lceil n/2 \rceil}.
	\]
\end{corollary}

We conclude with the following problem.
\begin{problem}
	Is it possible to state an analog of \cref{prop:main}?
	In particular, for $T \subseteq [n]$, is there a nice expression for the sum
	\[
	\sum_{\substack{\pi \in \symS_n  \\ T \subseteq \FIX(\pi) }}(-1)^{\inv(\pi)} t^{\rlm(\pi)}  ?
	\]
	Computer experiments suggest that this sum is either $0$ or of the form 
	$\pm t^a (t+1)^b (t-1)^c$, where $a$, $b$, and $c$ depend on $T$ in some manner.
\end{problem}



\acknowledgements{The authors have benefited greatly from the discussions
	with J\"orgen Backelin of Stockholm University.
	The Online Encyclopedia of Integer sequences~\cite{sloane2008line} 
	has been an invaluable resource in our project. The second author is grateful for the financial support extended
	by the cooperation agreement between International Science Program
	at Uppsala University and Addis Ababa University.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
