% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.67}{21(1)}{2014} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newcommand{\cs}{{\mathfrak{S}}} \newcommand{\lrf}[1]{\left\lfloor #1\right\rfloor} \newcommand{\lrc}[1]{\left\lceil #1\right\rceil} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf A group action on derangements\thanks{Supported by the National Natural Science Foundation of China (Nos. 11071030, 11371078) and the Specialized Research Fund for the Doctoral Program of Higher Education of China (No. 20110041110039).}} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Hua Sun\\ \small School of Mathematical Sciences\\[-0.8ex] \small Dalian University of Technology\\[-0.8ex] \small Dalian 116024, PR China\\ \small\tt hanch.sun@gmail.com\\ \and Yi Wang\\ \small School of Mathematical Sciences\\[-0.8ex] \small Dalian University of Technology\\[-0.8ex] \small Dalian 116024, PR China\\ \small\tt wangyi@dlut.edu.cn } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Sep 18, 2013}{Mar 14, 2014}{Mar 24, 2014}\\ \small Mathematics Subject Classifications: 05A15, 05A05, 05E18, 26C99} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} In this paper we define a cyclic analogue of the MFS-action on derangements, and give a combinatorial interpretation of the expansion of the $n$-th derangement polynomial on the basis $\{q^{k}(1+q)^{n-1-2k}\},k=0,1,\ldots,\lrf{(n-1)/2}$. % keywords are optional \bigskip\noindent \textbf{Keywords:} derangement polynomials; group action \end{abstract} \section{Introduction} Let $[n]$ denote the set $\{1,2,\ldots,n\}$ and let $\cs_{n}$ denote the set of all permutations of $[n]$. For $\pi=\pi_{1}\pi_{2}\cdots\pi_{n}\in\cs_{n}$ and $x\in [n]$, we write $\pi$ as the concatenation $\pi=w_{1}w_{2}xw_{3}w_{4}$, where $w_{2}$ is the maximal contiguous subword immediately to the left of $x$ whose letters are all smaller than $x$, and $w_{3}$ is the maximal contiguous subword immediately to the right of $x$ whose letters are all smaller than $x$. Following Foata and Strehl~\cite{FS74,FS76}, this concatenation is called the {\it $x$-factorization} of $\pi$. For example, let $\pi=714358296$ and $x=5$. Then $w_{1}=7$, $w_{2}=143$, $w_{3}=\emptyset$ and $w_{4}=8296$. Foata and Strehl~\cite{FS74,FS76} defined an involution acting on $\cs_{n}$ by $\varphi_{x}(\pi)=w_{1}w_{3}xw_{2}w_{4}$ for $x\in[n]$ and $\varphi_{S}(\pi)=\prod_{x\in S}\varphi_{x}(\pi)$ for $S\subseteq [n]$. The group $\mathbb{Z}_{2}^{n}$ acts on $\cs_{n}$ via the functions $\varphi_{S}$ for $S\subseteq [n]$. \begin{definition}\label{DEF1} Let $\pi=\pi_{1}\pi_{2}\cdots \pi_{n}\in\cs_{n}$ and denote $\pi_{0}=\pi_{n+1}=n+1$. The entry $\pi_{k}$ is called a {\it valley} if $\pi_{k-1}>\pi_{k}<\pi_{k+1}$; a {\it peak} if $\pi_{k-1}<\pi_{k}>\pi_{k+1}$; a {\it double ascent} if $\pi_{k-1}<\pi_{k}<\pi_{k+1}$; a {\it double descent} if $\pi_{k-1}>\pi_{k}>\pi_{k+1}$. \end{definition} Let $Val(\pi)$, $Peak(\pi)$, $Dasc(\pi)$, $Ddes(\pi)$ denote the set of all valley, peaks, double ascents and double descents of $\pi$, respectively. The corresponding cardinalities are $val(\pi)$, $peak(\pi)$, $dasc(\pi)$ and $ddes(\pi)$, respectively. Shapiro {\it et al}.~\cite{SWG83} modified the Foata-Strehl action in the following way. For $x\in[n]$, let \begin{equation} \varphi_{x}'(\pi)= \begin{cases} \varphi_{x}(\pi) & \text{if $x$ is a double ascent or a double descent,}\\ \pi & \text{if $x$ is a valley or a peak.} \end{cases} \end{equation} For any subset $S\subseteq[n]$, define $\varphi_{S}'(\pi)=\prod_{x\in S}\varphi_{x}'(\pi)$. From the definition, if $x$ is a double ascent (double descent, resp.) of $\pi$, then $x$ is a double descent (double ascent, resp.) of $\varphi_{x}'(\pi)$. The group $\mathbb{Z}_{2}^{n}$ acts on $\cs_{n}$ via the functions $\varphi_{S}',S\in [n]$ and call this action the {\it MFS-action}. By the theory of symmetric functions, Brenti~\cite{Bre90} showed that derangement polynomials are symmetric and unimodal polynomials. Using the method of continued fractions, Shin and Zeng~\cite{SZ12} gave a combinatorial interpretation for coefficients in the expansion of the $n$-th derangement polynomial on the basis $\{q^{k}(1+q)^{n-1-2k}\},k=0,1,\ldots,\lrf{(n-1)/2}$. In this note, we define a cyclic analogous of the MFS-action on derangements and give a new proof for the result of Shin and Zeng. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Main results} Let $\pi\in\cs_{n}$. We say that $\pi$ is a {\it derangement} of $[n]$ if $\pi_{i}\neq i$ for all $i\in[n]$. Denote by $D_{n}$ the set of all derangements of $[n]$. An element $i\in[n]$ is an {\it excedance} of $\pi$ if $\pi_{i}>i$. Denote by $Exc(\pi)$ the set of all excedances in $\pi$ and let $exc(\pi)=|Exc(\pi)|$. The {\it $n$-derangement polynomial} $D_{n}(q)$ is the generating function of statistic excedance over the set $D_{n}$, i.e., \begin{equation} D_{n}(q)=\sum_{\pi\in D_{n}}q^{exc(\pi)}=\sum_{j=1}^{n-1}d(n,j)q^j, \end{equation} where $d(n,j)=|\{\pi\in D_{n}: exc(\pi)=j\}|.$ Recall that a permutation $\pi\in \cs_{n}$ may be regarded as a disjoint union of its distinct cycles $C_{1},C_{2},\ldots,C_{k}$, written $\pi=C_{1}C_{2}\cdots C_{k}$. Let $c(\pi)$ denote the number of cycles of $\pi$. For a derangement $\pi$, each cycle contains at least two elements. The {\it standard cycle representation} of $\pi$ is defined by requiring that (\romannumeral1) each cycle is written with its largest element first, and (\romannumeral2) the cycles are written in increasing order of their largest elements~\cite{Sta97}. For example, the standard cycle representation of $\pi=456321\in D_{6}$ is $(52)(6143)$. Throughout the paper all permutations are written in standard cycle representation. \begin{definition}[\cite{SZ12}]\label{DEF2} Let $\pi\in\cs_{n}$. The entry $x=\pi_{i}(i\in[n])$ is called a {\it cyclic valley} if $i=\pi^{-1}(x)>x<\pi(x)$; a {\it cyclic peak} if $i=\pi^{-1}(x)\pi(x)$; a {\it cyclic double ascent} if $i=\pi^{-1}(x)x>\pi(x)$; a {\it fixed point} if $\pi(x)=x$. \end{definition} Let $Cval(\pi)$, $Cpeak(\pi)$, $Cdasc(\pi)$, $Cddes(\pi)$ and $Fix(\pi)$ denote the set of all cyclic valley, cyclic peaks, cyclic double ascents, cyclic double descents and fixed points of $\pi$, respectively. The corresponding cardinalities are $cval(\pi)$, $cpeak(\pi)$, $cdasc(\pi)$, $cddes(\pi)$ and $fix(\pi)$, respectively. It is easy to see that the union of sets $Cval(\pi)$, $Cpeak(\pi)$, $Cdasc(\pi)$, $Cddes(\pi)$ and $Fix(\pi)$ is $[n]$ for any $\pi\in\cs_{n}$. For a derangement $\pi$, the set $Fix(\pi)$ is empty. The following proposition is immediate by Definition~\ref{DEF2}. \begin{proposition}\label{Dn-exc} Let $\pi=C_{1}C_{2}\cdots C_{k}$ be a permutation of $[n]$. Then $$Exc(\pi)=Cval(\pi)\cup Cdasc(\pi)$$ and $$ exc(\pi)=cval(\pi)+cdasc(\pi).$$ \end{proposition} Let $\pi=C_{1}C_{2}\cdots C_{k}$. Following Stanley~\cite{Sta97}, let $o(\pi)$ be the permutation obtained from $\pi$ by erasing the parentheses of cycles. For example, if $\pi=(71435)(826)$, then $o(\pi)=71435862$. The map $o:\cs_{n}\rightarrow\cs_{n}$ defined above is a bijection. The following result is direct. \begin{proposition}\label{c-nonc} Let $\pi=C_{1}C_{2}\cdots C_{k}\in D_{n}$. Suppose that $o(\pi)(0)=0$ and $o(\pi)(n+1)=n+1$. Then $$Cpeak(\pi)=Peak(o(\pi)),\qquad Cval(\pi)=Val(o(\pi)),$$ $$Cdasc(\pi)=Dasc(o(\pi))\qquad \text{and}\qquad Cddes(\pi)=Ddes(o(\pi)),$$ where the sets $Peak(o(\pi)),Val(o(\pi)),Dasc(o(\pi))$ and $Ddes(o(\pi))$ are defined similar to Definition~\ref{DEF1} with the only difference $o(\pi)(0)=0$. \end{proposition} We define the cyclic analogous of the MFS-action on derangements in the following way. Let $\pi=C_{1}C_{2}\cdots C_{k}$. Suppose that $o(\pi)(0)=0$ and $o(\pi)(n+1)=n+1$. For $x\in[n]$, define the map $\theta_{x}:D_{n}\rightarrow D_{n}$ by $$\theta_{x}(\pi)=o^{-1}(\varphi_{x}'(o(\pi))).$$ The map is well-defined. To see this, let $\pi=C_{1}C_{2}\cdots C_{k}\in D_{n}$. If $x$ is a cyclic valley of $\pi$, then $x$ is a valley of $o(\pi)$, $\varphi_{x}'(o(\pi))=o(\pi)$ and $\theta_{x}(\pi)=\pi$. If $x$ is a cyclic peak of $\pi$, then $x$ is a peak of $o(\pi)$, $\varphi_{x}'(o(\pi))=o(\pi)$ and $\theta_{x}(\pi)=\pi$. If $x$ is a cyclic double ascent of $C_{i}$ in $\pi$, where $C_{i}=(w_{0}w_{1}xw_{2})$ and $w_{1}$ denotes the maximal contiguous subword immediately to the left of $x$ whose letters are all smaller than $x$. Then $x$ is a double ascent of $o(\pi)$, $\varphi_{x}'(o(\pi))=o(C_{1}C_{2}\cdots C_{i-1}\bar{C_{i}}C_{i+1}\cdots C_{k})$ and $\theta_{x}(\pi)=C_{1}C_{2}\cdots C_{i-1}\bar{C_{i}}C_{i+1}\cdots C_{k}\in D_{n}$, where $\bar{C_{i}}=(w_{0}xw_{1}w_{2})$. If $x$ is a cyclic double descent of $C_{i}$ in $\pi$, where $C_{i}=(w_{0}xw_{1}w_{2})$ and $w_{1}$ denotes the maximal contiguous subword immediately to the right of $x$ whose letters are all smaller than $x$. Then $x$ is a double descent of $o(\pi)$, $\varphi_{x}'(o(\pi))=o(C_{1}C_{2}\cdots C_{i-1}\bar{C_{i}}C_{i+1}\cdots C_{k})$ and $\theta_{x}(\pi)=C_{1}C_{2}\cdots C_{i-1}\bar{C_{i}}C_{i+1}\cdots C_{k}\in D_{n}$, where $\bar{C_{i}}=(w_{0}w_{1}xw_{2})$. Hence the map $\theta_{x}$ is well-defined for all $x\in [n]$. Table~1 gives an example of the maps $\theta_{x}$ on $\pi=(623)(87514)$ for all $x\in[8]$, where $o(\pi)=62387514$. \begin{center} \begin{tabular}{|c|c|c|c|c|} \hline $x$ & 1 & 2 & 3 & 4 \\ \hline $\varphi'_x(o(\pi))$ & 62387514 & 62387514 & 63287514 & 62387514 \\ \hline $\theta_x(\pi)$ & (623)(87514) & (623)(87514) & (632)(87514) & (623)(87514) \\ \hline \hline $x$ & 5 & 6 & 7 & 8 \\ \hline $\varphi'_x(o(\pi))$ & 62387145 & 62387514 & 62385147 & 62387514\\ \hline $\theta_x(\pi)$ & (623)(87145) & (623)(87514) & (623)(85147) & (623)(87514)\\ \hline \end{tabular} \medskip \end{center} \centerline{Table 1.} \bigskip %% CSG, 17.3.2014: reformatted table as above. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%% Fig 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\begin{center} %\setlength{\unitlength}{1cm} %\begin{picture}(11,4)(2,0) %%%%%% horizontal line %%%%%%%%%%%%%% edge %\put(0,0){\line(0,1){3}}\put(1.7,0){\line(0,1){3}}\put(3.4,0){\line(0,1){3}}\put(5.1,0){\line(0,1){3}} %\put(6.8,0){\line(0,1){3}}\put(8.5,0){\line(0,1){3}}\put(10.2,0){\line(0,1){3}}\put(11.9,0){\line(0,1){3}} %\put(13.6,0){\line(0,1){3}}\put(15.3,0){\line(0,1){3}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\put(0,0){\line(1,0){15.3}}\put(0,1){\line(1,0){15.3}}\put(0,2){\line(1,0){15.3}}\put(0,3){\line(1,0){15.3}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\put(0.7,2.3){$x$}\put(0.1,1.3){$\varphi_{x}'(o(\pi))$}\put(0.3,0.3){$\theta_{x}(\pi)$} %\put(2.4,2.3){$1$}\put(4.1,2.3){$2$}\put(5.8,2.3){$3$}\put(7.5,2.3){$4$}\put(9.2,2.3){$5$} %\put(10.9,2.3){$6$}\put(12.6,2.3){$7$}\put(14.3,2.3){$8$} %\put(1.7,1.3){$62387514$}\put(3.4,1.3){$62387514$}\put(5.1,1.3){$63287514$}\put(6.8,1.3){$62387514$} %\put(8.5,1.3){$62387145$}\put(10.2,1.3){$62387514$}\put(11.9,1.3){$62385147$}\put(13.6,1.3){$62387514$} %\put(1.9,0.2){$(87514)$}\put(2.1,0.6){$(623)$}\put(3.6,0.2){$(87514)$}\put(3.8,0.6){$(623)$} %\put(5.3,0.2){$(87514)$}\put(5.5,0.6){$(632)$}\put(7.,0.2){$(87514)$}\put(7.2,0.6){$(623)$} %\put(8.7,0.2){$(87145)$}\put(8.9,0.6){$(623)$}\put(10.4,0.2){$(87514)$}\put(10.6,0.6){$(623)$} %\put(12.1,0.2){$(81457)$}\put(12.3,0.6){$(623)$}\put(13.8,0.2){$(87514)$}\put(14,0.6){$(623)$} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\put(7,-0.8){Table~1. } %\end{picture} % %\end{center} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\hspace{4mm} % %~~~~~ The function $\theta_{x}$ is an involution and $\theta_{x}\theta_{y}=\theta_{y}\theta_{x}$ for all $x,y\in[n]$. For any subset $S\subseteq[n]$, define the function $\theta_{S}(\pi):D_{n}\rightarrow D_{n}$ by $$\theta_{S}(\pi)=\prod_{x\in S}\theta_{x}(\pi).$$ The group $\mathbb{Z}_{2}^{n}$ acts on $D_{n}$ via the functions $\theta_{S},S\in [n]$ and call this action the {\it CMFS-action}. For $\pi\in D_{n}$, let $Orb^{c}(\pi)$ denote the orbit including $\pi$ under the CMFS-action. There is a unique derangement in $Orb^{c}(\pi)$, denoted by $\tilde{\pi}$, such that $\tilde{\pi}$ has no cyclic double ascents. The next is the main results of this note. \begin{theorem}\label{Derangement-orbit} Let $\pi\in D_{n}$. Then $$\sum_{\sigma\in Orb^{c}(\pi)}q^{exc(\sigma)} =q^{exc(\tilde{\pi})}(1+q)^{n-2exc(\tilde{\pi})}=q^{cpeak(\pi)}(1+q)^{n-2cpeak(\pi)}.$$ \end{theorem} \begin{proof} If $x$ is a cyclic double descent of some cycle $C_{i}$ in $\pi$, then $x$ is a cyclic double ascent of cycle $C'_{i}$ in $\theta_{x}(\pi)$, where $\pi=C_{1}C_{2}\cdots C_{k}$ and $\theta_{x}(\pi)=C'_{1}C'_{2}\cdots C'_{k}$. We have $Cdasc(\theta_{x}(\pi))=Cdasc(\pi)\cup\{x\}$ and $Cval(\theta_{x}(\pi))=Cval(\pi)$. It follows that $Exc(\theta_{x}(\pi))=Exc(\pi)\cup\{x\}$ and $exc(\theta_{x}(\pi))=exc(\pi)+1$ from Proposition~\ref{Dn-exc}. Then $$\sum_{\sigma\in Orb^{c}(\pi)}q^{exc(\sigma)}=q^{exc(\tilde{\pi})}(1+q)^{cddes(\tilde{\pi})}.$$ For any $\pi=C_{1}C_{2}\cdots C_{k}\in D_{n}$, delete all double descents and double ascents of $o(\pi)$, then we get an alternating permutation $$0x_{2}\cdots>x_{n-cddes(\pi)-cdasc(\pi)}