\documentclass[12pt]{amsart} \usepackage{mathbbol} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage{amssymb,latexsym} %\usepackage{pstcol,pstricks,color} \setlength{\unitlength}{1mm} \textwidth15.6cm \textheight22.8cm \hoffset-2truecm \voffset-.5truecm \newcommand{\light}[1]{{#1}} \newcommand{\bulletcolor}[1]{{#1}} \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{definition}[theorem]{Definition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{remark}[theorem]{Remark} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{fact}[theorem]{Fact} \newtheorem{example}[theorem]{Example} \newtheorem{axiom}[theorem]{Axiom} \newtheorem{property}[theorem]{Property} \newtheorem{problem}[theorem]{Problem} \newtheorem{notation}[theorem]{Notation} \newcommand{\csum}{{\rm csum}} \newcommand{\sumlim}{\sum\limits} \newcommand{\prodlim}{\prod\limits} \newcommand{\grn}{G_{r,n}} \def\pf{\noindent {\it Proof.} } \begin{document} \pagenumbering{arabic} \pagestyle{headings} \newbox\Adr \setbox\Adr\vbox{ \centerline{Toufik Mansour} \vskip5pt \centerline{Department of Mathematics,} \centerline{University of Haifa, 31905 Haifa, Israel} \centerline{E-mail: {\footnotesize toufik@math.haifa.ac.il}} \vskip4mm \centerline{Yidong Sun$^*$} \vskip2mm \centerline{Department of Mathematics,} \centerline{ Dalian Maritime University, 116026 Dalian, P.R. China} \centerline{E-mail: {\footnotesize sydmath@yahoo.com.cn}} } \title{ Excedance numbers for permutations in complex reflection groups} \author[ Toufik Mansour and Yidong Sun]{\box\Adr} \subjclass[2000]{Primary 05A05, 05A15.} \keywords{ Complex reflection group, excedance, colored permutations} \thanks{$^*$Corresponding author: Yidong Sun. } \thanks{$^*$The author is supported by The National Science Foundation of China (10726021).} \begin{abstract} {Recently, Bagno, Garber and Mansour [S\'em. Lotharingien Combin.\ {\bf 56} (2007), Art.~B56d] studied a kind of excedance number on the complex reflection groups and computed its multidistribution with the number of fixed points on the set of involutions in these groups. In this note, we consider the similar problems in more general cases and make a correction of one result obtained by them.} \end{abstract} \maketitle %=================================================================================== %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 58 \rms (2008), Article~B58b\hfill} \def\thepage{} % % \section{Introduction} It is well known that there is a single infinite family of groups $G_{r,s,n}$ and exactly $34$ other ``exceptional" complex reflection groups \cite{ST}. The infinite family $G_{r,s,n}$, where $r,s,n$ are positive integers with $s\mid r$, consists of the groups of $n\times n$ matrices such that \begin{itemize} \item the entries are either 0 or $r^{\rm th}$ roots of unity; \item there is exactly one nonzero entry in each row and each column; \item the $(r/s)^{{\rm th}}$ power of the product of the nonzero entries is 1. \end{itemize} The classical Weyl groups appear as special cases: for $r=s=1$ we have the symmetric group $G_{1,1,n}=S_n$, for $r=2, s=1$ we have the hyperoctahedral group $G_{2,1,n}=B_n$, and for $r=s=2$ we have the group of even-signed permutations $G_{2,2,n}=D_n$. We say that a permutation $\pi \in G_{r,s,n}$ is {\it an involution} if $\pi^2=1$. More generally, we define $\mathcal{G}_{r,s,n}^{m}=\{\sigma\in G_{r,s,n}\mid \sigma^m=1\}$. Recently, Bagno, Garber and Mansour \cite{BGM} studied an excedance number on the complex reflection groups (see~\cite{SS}) and computed the number of involutions having specific numbers of fixed points and excedances. In this note, we consider the similar problems on the set $\mathcal{G}_{r,s,n}^{m}$. This paper is organized as follows. In Section~\ref{pre}, we recall some properties of $G_{r,s,n}$ and define some parameters on $\grn=G_{r,1,n}$ and hence also on $G_{r,s,n}$. In Section~\ref{mainresults}, we present our main results and compute the corresponding recurrences together with explicit formulas. %=================================================================================== \section{Preliminaries}\label{pre} Let $r$ and $n$ be any two positive integers. {\it The group of colored permutations of $n$ digits with $r$ colors} is the wreath product $\grn=\mathbb{Z}_r \wr S_n=\mathbb{Z}_r^n \rtimes S_n$ consisting of all the pairs $(z,\tau)$ where $z\in\mathbb{Z}_r^n$ and $\tau \in S_n$. Let $\tau,\tau'\in S_n$, $z=(z_1,...,z_n)\in\mathbb{Z}_r^n$ and $z'=(z'_1,...,z'_n)\in\mathbb{Z}_r^n$, the multiplication in $\grn$ is defined by $(z,\tau) \cdot (z',\tau')=((z_1+z'_{\tau^{-1}(1)},...,z_n+z'_{\tau^{-1}(n)}),\tau \circ \tau') $, where $+$ is taken modulo $r$. %First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire %--restoring the headers and pagenumbering \pagenumbering{arabic} \addtocounter{page}{1} \markboth{\SMALL TOUFIK MANSOUR AND YIDONG SUN}{\SMALL EXCEDANCE NUMBERS FOR PERMUTATIONS IN COMPLEX REFLECTION GROUPS} % % We use some conventions along this paper. For an element $\sigma=(z,\tau) \in \grn$ with $z=(z_1,...,z_n)$ we write $z_i(\sigma)=z_i$. For $\sigma=(z,\tau)$, we denote $|\sigma|=(0,\tau), (0 \in \mathbb{Z}_r^n)$. A much more natural way to present $\grn$ is the following: consider the alphabet $\Sigma=\{1^{[0]},\dots,n^{[0]},1^{[1]},\dots,n^{[1]},\dots, 1^{[r-1]},\dots,n^{[r-1]} \}$ as the set $\Lbrack n\Rbrack=\{1,\dots,n\}$ colored by the colors $0,\dots,r-1$. Then, an element of $\grn$ is called a {\it colored permutation}, i.e., a bijection $\sigma: \Sigma \rightarrow \Sigma$ such that if $\sigma(i)=k^{[t]}$ then $\sigma(i^{[j]})=k^{[t+j]}$ where $0\leq j \leq r-1$ and the addition is taken modulo $r$. Occasionally, we write $j$ bars over a digit $i$ instead of $i^{[j]}$. For example, an element $(z,\tau)=((1,2,1,2),(3,1,2,4)) \in G_{3,4}$ will be written as $(\bar{3} \bar{\bar{1}} \bar{2} \bar{\bar{4}})$. For each $s\mid r$, the {\it complex reflection group} can also be defined as: $$G_{r,s,n}:=\{\sigma \in G_{r,n} \mid \csum(\sigma)\equiv 0 \; {\rm mod} \; s\},$$ where ${\rm csum}(\sigma) = \sumlim_{i=1}^n z_i(\sigma)$. One can define the following well-known statistics on $S_n$. For any permutation $\sigma \in S_n$, $i \in \Lbrack n\Rbrack$ is {\it an excedance of $\sigma$} if and only if $\sigma(i)>i$. We denote the number of excedances by ${\rm exc}(\sigma)$. Another natural statistic on $S_n$ is the number of fixed points, denoted by ${\rm fix}(\sigma)$. We can similarly define some statistics on $\grn$. The complex reflection group $G_{r,s,n}$ inherits all of them. Given any ordered alphabet $\Sigma'$, we recall the definition of the {\it excedance set} of a permutation $\sigma$ on $\Sigma'$: $${\rm Exc}(\sigma)=\{i \in \Sigma' \mid \sigma(i)>i\},$$ and the {\it excedance number} is defined to be ${\rm exc}(\sigma)=|{ \rm Exc}(\sigma)|$. We define the color order on the set $\Sigma=\{1,\dots,n,\bar{1},\dots,\bar{n},\dots, 1^{[r-1]},\dots,n^{[r-1]} \}$ for $0\leq j i \}$, where the comparison is with respect to the color order, and denote ${\rm exc}_A(\sigma) = |{\rm Exc}_A(\sigma)|$. For instance, if $\sigma=(\bar{1}\bar{\bar{3}}2\bar{\bar{4}}) \in G_{3,4}$, then ${\rm csum}(\sigma)=5$, ${\rm Exc_A}(\sigma)=\{3\}$ and hence ${\rm exc}_A(\sigma)=1$. Now we can define the colored excedance number for $\grn$ by $${\rm exc}^{{\rm Clr}}(\sigma)=r \cdot {\rm exc}_A(\sigma)+{\rm csum}(\sigma).$$ Let $\Sigma$ be ordered by the color order, and let ${\rm exc}(\sigma)$ denote the number of excedances of $\sigma$ with respect to the color order. Then it is not difficult to see that ${\rm exc}(\sigma)={\rm exc}^{{\rm Clr}}(\sigma)$ for any $\sigma \in \grn$ (cf.\ \cite{BG}). For $\sigma=(z,\tau)\in \grn$, $|\sigma|$ is the permutation of $\Lbrack n\Rbrack$ satisfying $|\sigma|(i)=\tau(i)$. We say that $i \in \Lbrack n\Rbrack$ is an {\it absolute fixed point} of $\sigma \in \grn$ if $|\sigma|(i)=i$. We denote the number of absolute fixed points of $\sigma \in \grn$ by ${\rm fix(\sigma)}$. \section{Main results and proofs}\label{mainresults} Recall that $\mathcal{G}_{r,s,n}^{m}=\{\sigma\in G_{r,s,n}\mid \sigma^m=1\}$. Define \begin{align*} H_{r,s,n}^{(m)}(u,v,w)&=\sum_{\sigma\in \mathcal{G}_{r,s,n}^{m}}u^{{\rm fix}(\sigma)}v^{{\rm exc}_{A}(\sigma)}w^{{\rm csum}(\sigma)}, \\ \mathcal{H}_{r,s}^{(m)}(x;u,v,w)&=\sum_{n \geq 0}{H_{r,s,n}^{(m)}(u,v,w)\frac{x^n}{n!}}. %=\sum_{n\geq0}\sum_{\sigma\in %\mathcal{G}_{r,s,n}^{m}}\left( u^{{\rm fix}(\sigma)}v^{{\rm %exc}_A(\sigma)}w^{{\rm csum}(\sigma)}\right)\frac{x^n}{n!}. \end{align*} It is well known that the Eulerian number, $A_{d-1,k}$, is the number of permutations on $\Lbrack d-1\Rbrack$ with $k-1$ excedances for $k\in \Lbrack d-1\Rbrack$, which is also the number of cyclic permutations in $S_d$ with $k$ excedances. A bijective proof of this fact is given in \cite[Theorem~1.19]{FS}. Our main result can be formulated as follows. \begin{theorem}\label{maintheo} For any integers $r,m\geq 1$, the generating function $\mathcal{H}_{r,1}^{(m)}(x;u,v,w)$ is \begin{eqnarray*} \exp\left\{\sum_{\{t\mid 0\leq tj\}$$ such that ${\rm exc}(C)=k$, we can color the symbols in $C$ with the color set $\{[0],[1],\ldots,[r-1]\}$ and obtain the colored cyclic permutation $C'$. Suppose that ${\rm exc}_A(C')=k-i$. We know that ${\rm Exc}_A(C')\subseteq{\rm Exc}(C)$, which means that ${\rm exc}(C)-{\rm exc}_A(C)=i$. In other words, there are $i$ symbols in ${\rm Exc}(C)$ with color numbers ranging from $[1]$ to $[r-1]$. Clearly, there are $\binom{k}{i}$ ways to do this. Let $t=\csum(C')$ and $t_{\ell}$ be the color number of $\ell\in \Lbrack d\Rbrack$. Then we have the equation $t=t_1+t_2+\cdots+t_d$ with $0\leq t_1,t_2,\cdots,t_d\leq r-1$ such that \begin{itemize} \item $t_j=0$ for $j\in {\rm Exc}(C)$ and $j$ has color number $[0]$, and \item $1\leq t_j\leq r-1$ for all $j\in {\rm Exc}(C)-{\rm Exc}_A(C')$; there are $i$ such $j$'s. \end{itemize} Therefore there are $U_{d-k,t}^{(i)}$ solutions of the above equation. In total, there are $\binom{k}{i}U_{d-k,t}^{(i)}$ ways to color the symbols in $C$ such that $\csum(C')=t$ and ${\rm exc}_A(C')=k-i$, where $U_{d-k,t}^{(i)}$ is the coefficient of $x^t$ in $(x+x^2+\cdots+x^{r-1})^i(1+x+\cdots+x^{r-1})^{d-k}$, which can be expressed as \begin{align*} U_{d-k,t}^{(i)}&=[x^t](x+x^2+\cdots+x^{r-1})^i(1+x+\cdots+x^{r-1})^{d-k}\\ &=[x^t]\left(\frac{1-x^r}{1-x}-1\right)^i\left(\frac{1-x^r}{1-x}\right)^{d-k}\\ &=[x^t]\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}\Big(\frac{1-x^r}{1-x}\Big)^{d+j-k}\\ &=\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}\sum_{{\ell}\geq 0}(-1)^{{\ell}}\binom{d+j-k}{{\ell}}\binom{d+j+t-k-{\ell}r-1}{t-{\ell}r}. \end{align*} Let $C'=(i_1^{[t_1]},i_2^{[t_2]},\dots,i_d^{[t_d]})$. Then $C'^d=(i_1^{[t]},i_2^{[t]},\dots,i_d^{[t]})$ with $t=t_1+t_2+\cdots+t_d$. Hence, $C'^{m}=(i_1^{[\frac{tm}{d}]},i_2^{[\frac{tm}{d}]},\dots,i_d^{[\frac{tm}{d}]})=1$ implies that $r\mid \frac{tm}{d}$. For any $\pi \in \mathcal{G}_{r,1,n}^{m}$ such that the symbol $n$ lies in a cycle $C'$ of length $d\geq 2$ with $d\mid m$ (note that there are $\binom{n-1}{d-1}$ ways to choose the digits of such a cycle), define $\pi'' \in \mathcal{G}_{r,1,n-d}^{m}$ in the following way: write $\pi$ in its complete notation, i.e., as a matrix of two rows, see $(\star)$. The first row of $\pi''$ is $(1,2,\ldots,n-d)$ while the second row is obtained from the second row of $\pi$ by ignoring the digits in $C'$, and ``standardizing" the remaining digits, that is, by replacing the $i$-th largest of the remaining digits by $i$ (keeping the colors). For example, if $\pi=(\bar{3} 4 \bar{1} {\bar{2}})\in \mathcal{G}_{2,1,4}^{4}$ and $C'=(1,\bar{3})$, then $\pi''=(2\bar{1})$. The parameters satisfy \begin{align*} {\rm fix}(\pi)&={\rm fix}(\pi''),\\ {\rm exc}_A(\pi)&={\rm exc}_A(\pi'')+{\rm exc}_A(C'),\\ \csum(\pi)&=\csum(\pi'')+\csum(C'). \end{align*} The above considerations lead to the following recurrence: %%\begin{small} \begin{align*} H_{r,1,n}^{(m)}(u,v,w)&=H_{r,1,n-1}^{(m)}(u,v,w)\sum_{\{t\mid 0\leq t