\documentclass[12pt]{amsart}

%\usepackage{amsmath,amssymb}
\usepackage{epsf,amsmath,amssymb,latexsym,amsthm}

\numberwithin{equation}{section}

\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{Obs}[theorem]{Observation}
\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{\grn}{G_{r,n}}
\newcommand{\sumlim}{\sum\limits}
\newcommand{\prodlim}{\prod\limits}

\begin{document}

%\pagenumbering{arabic}
%\pagestyle{headings}
\def\sof{\hfill\rule{2mm}{2mm}}
\def\ls{\leq}
\def\gs{\geq}
\def\SS{\mathcal S}
\def\qq{{\bold q}}
\def\txx{{\frac1{2\sqrt{x}}}}

\title[Colored descents in $\grn$]{Counting descent pairs with prescribed colors in the colored permutation groups}

\author{Eli Bagno}
\address{Eli Bagno, The Jerusalem College of Technology, Jerusalem, Israel}
\email{bagnoe@jct.ac.il}

\author{David Garber}
\address{David Garber, Department of Applied Mathematics, Faculty of Sciences, Holon Institute of Technology, PO Box 305,
58102 Holon, Israel} \email{garber@hit.ac.il}

\author{Toufik Mansour}
\address{Toufik Mansour, Department of Mathematics, University of Haifa, 31905 Haifa,
Israel.}
\email{toufik@math.haifa.ac.il}

\begin{abstract} We define new statistics,
{\it $(c,d)$-descents}, on the colored permutation groups
$\mathbb{Z}_r \wr S_n$ and compute the distribution of these
statistics on the elements in these groups. We use some
combinatorial approaches, recurrences, and generating functions
manipulations to obtain our results.
\end{abstract}

\date{}

\maketitle

%First page headline in 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 60 \rms (2009), Article~B60e\hfill}
\def\thepage{}


%===========================================================================
%===========================================================================
\section{Introduction}
A permutation statistic on the symmetric group $S_n$, or more generally over a group,
is a function from the group to the set of nonnegative integers.
The study of permutation statistics started with Euler, who
considered the number of descents of a permutation. Netto, at the beginning of the
last century, considered the number of inversions, and Major Percy
MacMahon \cite[Vol. I, pp. 135, 186; Vol. II, p. viii]{MM1},
\cite{MM2} considered the parameter called today major index and the
excedance number.

 On the symmetric group $S_n$, a {\it descent pair} of a permutation $\pi \in S_n$ is a pair
 $(i,i+1)$ such that $\pi_i>\pi_{i+1}$. The {\it descent set} of a permutation
 $\pi=\pi_1\pi_2\cdots\pi_n\in S_n$, denoted by ${\rm Des}(\pi)$, is the set
of indices $i$ such that $(i,i+1)$ is a descent pair. The {\it
number of descents} in a permutation $\pi$, denoted by ${\rm
des}(\pi)=|{\rm Des}(\pi)|$, is a classical permutation statistic.
This statistic was first studied by MacMahon \cite{MM1} almost a
century ago, and it still plays an important role in the study of
permutation statistics.

Kitaev and Remmel \cite{KR} counted descents in $S_n$ according to
the parity of the first or second element of the descent pair. In
\cite{KR0},  they generalize it to the case where the first or the
second element in the descent pair is divisible by $k$ for some $k
\geq 2$. Some more research was done in the direction of studying
the corresponding distribution for words (see \cite{HLR,HR,KMR}).

Let $r, n$ be positive integers. A {\it colored permutation} on of $n$ objects with $r$ colors is a bijection $\pi$ on the set
$$\Sigma_{r,n}=\{1,\dots,n,1^{[1]},\dots,n^{[1]},\dots,1^{[r-1]},\dots,n^{[r-1]}\}$$
satisfying the following condition: if $\pi(i^{[\alpha]})=j^{[\beta]}$, then $\pi(i^{[\alpha+1]})=j^{[\beta+1]}$, where the exponents
are taken modulo $r$.
If $\pi_k=i^{[j]}$, we define $|\pi_k|=i$, where $\pi_k=\pi(k^{[0]})$ for each $k$. Moreover, the {\it color} of the position $k$, denoted by $c_k(\pi)$, is $j$.
The set of all such colored permutations form a group, $G_{r,n}$, which is isomorphic to the wreath product $\mathbb{Z}_r \wr S_n=\mathbb{Z}_r^n \rtimes S_n$.
 The classical
Weyl groups appear as special cases:
 the symmetric group $G_{1,n}=S_n$ and the
hyperoctahedral group $G_{2,n}=B_n$.



\medskip

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL ELI BAGNO, DAVID GARBER AND TOUFIK MANSOUR}{\SMALL 
COLORED DESCENTS IN $\grn$}
%
%

We fix two different orders on the set $\Sigma_{r,n}$:

\begin{itemize}
\item The color order:
{\small
$$1^{[r-1]} < 2^{[r-1]} < \cdots < n^{[r-1]} < \cdots < 1^{[1]}< \cdots < n^{[1]} < 1^{[0]} < \cdots < n^{[0]}.$$}
\item The absolute order:
{\small
$$1^{[r-1]} < 1^{[r-2]} < \cdots < 1^{[0]} <   2^{[r-1]}< \cdots < 2^{[0]} < \cdots <n^{[r-1]} <\cdots < n^{[0]}.$$}
\end{itemize}

Let $\prec$ be one of the orders defined above. Let $\pi \in \grn$
and let $c,d$ be two nonnegative integers such that $c\leq d$. A {\em $(c,d)$-descent
in position $i$} is a descent (with
respect to $\prec$) in position $i$ such that $c_i(\pi)=c$ and $c_{i+1}(\pi)=d$. For example, if
$\pi=6^{[1]}2^{[2]}4^{[0]}3^{[1]}5^{[2]}1^{[2]}$, then $\pi$ has two
$(1,2)$-descents with respect to the color order: $i=1$ and $i=4$,
but only one $(1,2)$-descent with respect to the absolute order:
$i=1$. The number of $(c,d)$-descents in $\pi$ with respect to the
color order (respectively absolute order) is denoted by ${\rm des}^{\rm Clr}_{c,d}(\pi)$ (respectively ${\rm des}^{\rm Abs}_{c,d}(\pi)$).


It should be noted that actually, in the case of $(c,d)$-descents
where $c<d$ with respect to the color order, one can forget about the
colored permutations and deal with the underlying color words. For
example, the underlying color word of
$\pi=6^{[1]}2^{[2]}4^{[0]}3^{[1]}5^{[2]}1^{[2]}$ is $120122$,    so our
problem reduces to finding the number of words over $\{0,\dots ,
r-1\}$ having a fixed number of places where the color $d$ is subsequent to $c$.
Hence, the enumeration of $(c,d)$-descents in the case of the color order can be done as a special case of the work of Hall and
Remmel \cite{HR} where they compute the generating function of $(X,Y)$-descents (where $X$ and $Y$ are subsets of the alphabet).
Nevertheless, since our enumeration covers both orders at once,  we present here a simple and direct combinatorial proof for these enumerations.



In Section~\ref{enumerate_grn}, we study the generating function for
the number of colored permutations in $G_{r,n}$ having exactly $m$
$(c,d)$-descents where $c<d$.


We get the following results.

\begin{proposition}\label{cddes}
The number of colored permutations in $G_{r,n}$ with exactly $0$
$(c,d)$-descents ($0\leq c<d\leq r-1$), with respect to both orders is
$$n!\sumlim_{k=0}^n (r-1)^k+n!\sumlim_{k=1}^{n-1} \sumlim_{b=1}^{k}
{\binom k  b}{\binom {n-k}
b} (r-2)^{b} (r-1)^{n-k-b}.$$

The number of colored permutations in $G_{r,n}$ with exactly $m>0$
$(c,d)$-descents ($0\leq c<d\leq r-1$) with respect to the color order, is given by
$$n!\sumlim_{k=1}^{n-1} \sumlim_{b=1}^{k} {\binom k  b}{\binom {n-k}
b} {\binom b  m} (r-2)^{b-m} (r-1)^{n-k-b}.$$

The number of colored permutations in $G_{r,n}$ with exactly $m>0$
$(c,d)$-descents ($0\leq c<d\leq r-1$) with respect to the absolute order, is given by
$$\frac{n!}{2^m}\sumlim_{k=1}^{n-1} \sumlim_{b=1}^{k} {\binom k
b}{\binom {n-k}
b} {\binom b  m} (r-2)^{b-m} (r-1)^{n-k-b}.$$
\end{proposition}


Note that when $n=2$, there will be no dependency on the value of $r$, as a simple verification shows.

The following is a special case for the hyperoctahedral group
$B_n=G_{2,n}$.

\begin{proposition}\label{thm1}
The number of signed permutations in $B_n$ with exactly $m$
$(0,1)$-descents is given by $n!\binom{n+1}{n-2m}$.
\end{proposition}


In Section~\ref{cc-des}, we study the generating function for
the number of colored permutations in $G_{r,n}$ having exactly $m$
$(c,c)$-descents. Here, we obtain our results by using recurrences and
manipulations with exponential generating functions.

\begin{proposition}\label{ccdes}
The number of colored permutations in $G_{r,n}$ with exactly $m$
$(c,c)$-descents, $0\leq c \leq r-1$, with respect to both
orders is given by
$$n!\sum\limits_{j=0}^{n}\sum\limits_{i=0}^m(-1)^i(r-1)^j\binom{j+m-i}{j}\binom{n+1}{i}\frac{(m-i+j+1)^{n-j}}{(n-j)!}.$$
\end{proposition}



\section{Counting $(c,d)$-descents with $c<d$ by a direct combinatorial approach}\label{enumerate_grn}

Our approach for enumerating $(c,d)$-descents is based on a counting
argument. We enumerate for both orders simultaneously.

\medskip

Let $\pi =\pi_1^{[c_1]} \pi_2^{[c_2]} \cdots \pi_n^{[c_n]} \in
\grn$. Define a $c$-block (respectively $\bar{c}$-block) in $\pi$ to be a maximal subsequence $\pi_i^{[c_i]}
\pi_{i+1}^{[c_{i+1}]} \cdots \pi_j^{[c_j]}$ of $\pi$ such that for
all $k \in [i,j]$, $c_k=c$  (respectively $c_k\neq c$). The cardinalities of the blocks form a composition of $n$.
For example, in $G_{6,6}$, with $c=2, d=3$, if $\pi = 2^{[2]}
4^{[2]} 5^{[3]} 1^{[4]} 6^{[2]} 3^{[1]}$, then the corresponding
blocks of $\pi$ are $$\{2^{[2]},4^{[2]}\}, \{5^{[3]}, 1^{[4]}\},
\{6^{[2]} \}, \{ 3^{[1]}\},$$ while the corresponding composition is
$(2,2,1,1)$.

Note that $(c,d)$-descents can appear in the transitions from a
$c$-block to a $\bar{c}$-block, but not necessarily in all of these
transitions.

Let ${\rm Comp}(n)$ be the set of compositions of $n$, and let
${\rm Comp^{clr}}(n)={\rm Comp}(n) \times \{c,\bar{c}\}$. For each
$\varphi \in {\rm Comp}(n)$ and $x \in \{c, \bar{c}\}$, the element
$(\varphi,x) \in {\rm Comp^{clr}}(n)$ represents the composition
$\varphi$ where the first part is colored by $x$.

Now, let $\mu = (\varphi,x) \in {\rm Comp^{clr}}(n)$. We define the
following parameters:

\begin{itemize}
\item $e_\varphi$ is the sum of parts in the even places of $\varphi$.
For example, if $\varphi=(2,3,4,5)$ then $e_\varphi=3+5=8$.

\item $k=k_\mu=\begin{cases} n-e_\varphi &\text{if } x=c,\\
                                         e_\varphi &\text{if }
                                         x=\bar{c}.\end{cases}$
\item $b=b_\mu$ is the number of $c$-blocks and $\bar{b}_{\mu}$ is
the number of $\bar{c}$-blocks. Explicitly,
 $$b_\mu=\begin{cases} \frac{|\varphi|}{2} & \text{if } |\varphi|\ {\rm
 even,} \\
                                         \frac{|\varphi|+1}{2} & 
\text{if }|\varphi|\ {\rm odd},  x=c,
                                         \\ 
                                         \frac{|\varphi|-1}{2} & 
\text{if }|\varphi|\ {\rm odd},
                                         x=\bar{c},
                                         \end{cases}$$
where $|\varphi|$ is the number of parts of $\varphi$, and
$\bar{b}_{\mu}=|\varphi|-b_{\mu}$.
\item $t_\mu$ is the number of transitions between a $c$-block
to a $\bar{c}$-block.

\end{itemize}

\medskip

Define
$$A^{\rm Ord}_{r,n}(q) = \sumlim_{\pi \in G_{r,n}} q^{{\rm des}^{\rm Ord}_{c,d}(\pi)},$$ 
where $\rm Ord$ stands for the orders {\rm Clr} or
{\rm Abs}.
For calculating $A^{\rm Ord}_{r,n}(q)$, we run over the elements of ${\rm Comp^{clr}}(n)$, instead of running over the elements
of $\grn$.


\begin{lemma}\label{comp formula}
For all $n\geq0$,



\begin{equation}\label{comp formula Clr}
A^{\rm Clr}_{r,n}(q)=n! \sumlim_{\mu \in {\rm Comp^{clr}}(n)}
(q+r-2)^{t_\mu}(r-1)^{n-k_\mu-t_\mu}.
\end{equation}



\begin{equation}\label{comp formula Abs}
A^{\rm Abs}_{r,n}(q)=n! \sumlim_{\mu \in {\rm Comp^{clr}}(n)}
\left(\frac{q}{2}+r-2\right)^{t_\mu}(r-1)^{n-k_\mu-t_\mu}.
\end{equation}


\end{lemma}
\begin{proof}
Each $\mu \in {\rm Comp^{clr}}(n)$ gives rise to $n!
(r-1)^{n-k_{\mu}}$ elements of $\grn$. $\pi\in \grn$ contributes a
$(c,d)$-descent with respect to the color order in each transition from a $c$-block to a
$\bar{c}$-block such that the first digit of the $\bar{c}$-block is
colored by $d$. This proves Equation~\eqref{comp formula Clr}.

Only half of the $(c,d)$-descents with respect to the color order are also $(c,d)$-descents with
respect to the absolute order (see an example in the introduction), so we have Equation~\eqref{comp formula Abs} too.
\end{proof}


In order to get an explicit expression for the formulas appearing in Lemma~\ref{comp formula},
we treat separately ${\rm Comp}(n) \times \{c\}$ and
${\rm Comp}(n) \times \{\bar{c}\}$. We do this only for the color order. The other computation is similar.

\medskip

Let $\mu=(\varphi,c) \in {\rm Comp}(n) \times \{c\}$.

We split the contribution into three cases according to $|\varphi|$.
\begin{enumerate}
\item $|\varphi|=1$:
in this case we have $k_{\mu}=n$ and $t_{\mu}=0$, thus its
 contribution is
$$n!\underset{|\varphi|=1}{\sum_{\mu=(\varphi,c) \in {\rm Comp^{clr}}(n)}}
(q+r-2)^{t_\mu}(r-1)^{n-k_\mu-t_\mu} = n!.$$
\item $|\varphi|$ is even: in this case, $k_{\mu}$ can vary in
$\{1,\dots,n-1\}$ and hence  $b_{\mu} \in \{1,\dots ,k_{\mu}\}$.
Moreover, $\bar{b}_{\mu}=t_{\mu}=b_{\mu}$. Then the
contribution is
\begin{multline*}
n!\underset{|\varphi| \text{ even}}{\sum_{\mu=(\varphi,c) \in {\rm Comp^{clr}}(n) }}
(q+r-2)^{t_\mu}(r-1)^{n-k_\mu-t_\mu} \\
=n! \sumlim_{k=1}^{n-1}
\sumlim_{b=1}^{k} {\binom {k-1}  {k-b}}{\binom {n-k-1} {n-k-b}} (q+r-2)^b
(r-1)^{n-k-b}.
\end{multline*}

Note that the first binomial coefficient corresponds to the choice
of dividing the $k$ digits colored by $c$ into $b$ non-empty
blocks, while the second binomial coefficient corresponds to the
choice of dividing the remaining $n-k$ digits (which are not
colored by $c$) into $\bar{b}$ non-empty blocks.

\item $|\varphi|>1$ odd: In this case, $k_{\mu}$ can vary in
$\{2,\dots,n-1\}$ and hence $b_{\mu} \in \{2,\dots ,k_{\mu}\}$.
Moreover, $\bar{b}_{\mu}=b-1,t_{\mu}=b_{\mu}-1$. Then the
contribution is
\begin{multline*}
n!\underset{|\varphi| \text{ odd}}{\sum_{\mu=(\varphi,c) \in {\rm Comp^{clr}}(n) }}
(q+r-2)^{t_\mu}(r-1)^{n-k_\mu-t_\mu}\\
=n!
\sumlim_{k=2}^{n-1} \sumlim_{b=1}^{k} {\binom {k-1} {k-b}}{\binom {n-k-1}
{n-k-b+1}} (q+r-2)^{b-1} (r-1)^{n-k-b+1}.
\end{multline*}
\end{enumerate}

\medskip

Now, let us treat the set ${\rm Comp}(n) \times \{\bar{c}\}$. Let
$\mu=(\varphi,\bar{c}) \in {\rm Comp}(n) \times \{\bar{c}\}$.

As in the case of ${\rm Comp}(n) \times \{c\}$, we split the
computation into three cases according to $|\varphi|$.
\begin{enumerate}
\item $|\varphi|=1$:
$$n!\underset{|\varphi|=1}{\sum_{ \mu=(\varphi,\bar{c}) \in {\rm Comp^{clr}}(n) }}
(q+r-2)^{t_\mu}(r-1)^{n-k_\mu-t_\mu} = n!(r-1)^n.$$

\item $|\varphi|$ is even: in this case, $k_{\mu}\in \{1,\dots,n-1\}$ and hence\break $b_{\mu} \in \{1,\dots
,k_{\mu}\}$. Moreover, $\bar{b}_{\mu}=t_{\mu}=b_{\mu}-1$. Then we
have
\begin{multline*}
n!\underset{|\varphi| \text{ even}}{\sum_{ \mu=(\varphi,\bar{c}) \in {\rm Comp^{clr}}(n) }}
(q+r-2)^{t_\mu}(r-1)^{n-k_\mu-t_\mu} \\
=n!
\sumlim_{k=1}^{n-1} \sumlim_{b=1}^{k} {\binom {k-1} {k-b}}{\binom {n-k-1}
{n-k-b}} (q+r-2)^{b-1} (r-1)^{n-k-b+1}.
\end{multline*}
\item $|\varphi|>1$ odd: in this case, $k_{\mu}$ can vary in
$\{1,\dots,n-2\}$ and hence $b_{\mu} \in \{2,\dots ,k_{\mu}\}$.
Moreover, $\bar{b}_{\mu}=b_{\mu}+1,t_{\mu}=b_{\mu}$. Then we have
\begin{multline*}
n!\underset{|\varphi| \text{ odd}}{\sum_{ \mu=(\varphi,{\bar{c}}) \in {\rm Comp^{clr}}(n) }}
(q+r-2)^{t_\mu}(r-1)^{n-k_\mu-t_\mu}\\
=n!
\sumlim_{k=1}^{n-2} \sumlim_{b=1}^{k} {\binom {k-1}{ k-b}}
{\binom {n-k-1}{ n-k-b-1}} (q+r-2)^{b} (r-1)^{n-k-b}.
\end{multline*}
\end{enumerate}



Summing up all the parts, we get
\begin{align*}
 A^{\rm Clr}_{r,n}(q)& =n!(1+(r-1)^n) \\
 & \quad \quad +n!\sumlim_{k=1}^{n-1} \sumlim_{b=1}^{k} {\binom {k-1}{
k-b}}{\binom {n-k}{ n-k-b}} (q+r-2)^{b}
(r-1)^{n-k-b}\\
& \quad \quad +n!\sumlim_{k=1}^{n-1} \sumlim_{b=1}^{k} {\binom {k-1}{
k-b}}{\binom {n-k}{ n-k-b+1}} \\
&\kern5cm \cdot (q+r-2)^{b-1} (r-1)^{n-k-b+1} \\
&= n!\sumlim_{k=0}^n{(r-1)^k} \\
& \quad  \quad +n!\sumlim_{k=1}^{n-1} \sumlim_{b=1}^{k} {\binom {k}{
b}}{\binom {n-k}{ b}} (q+r-2)^{b} (r-1)^{n-k-b}.
\end{align*}

Here is the analogous result for the absolute order.

\begin{corollary}
\begin{multline*}
 A^{\rm Abs}_{r,n}(q) = n!\sumlim_{k=0}^n{(r-1)^k} \\
 +n!\sumlim_{k=1}^{n-1} \sumlim_{b=1}^{k} {\binom {k}{
b}}{\binom {n-k}{ b}} \left(\frac{q}{2}+r-2\right)^{b} (r-1)^{n-k-b}.
\end{multline*}
\end{corollary}



Hence, we get the following result.
\begin{proposition}
The number of colored permutations in $G_{r,n}$ with exactly $0$
$(c,d)$-descents, $0\leq c<d\leq r-1$, is
$$n!\sumlim_{k=0}^n{(r-1)^k}+n!\sumlim_{k=1}^{n-1} \sumlim_{b=1}^{k}
{\binom {k}{ b}}{\binom {n-k}{ b}} (r-2)^{b} (r-1)^{n-k-b}.$$

The number of colored permutations in $G_{r,n}$ with exactly $m>0$
$(c,d)$-descents ($0\leq c<d\leq r-1$) with respect to the color order, is given by
$$n!\sumlim_{k=1}^{n-1} \sumlim_{b=1}^{k} {\binom {k}{ b}}{\binom {n-k}{
b}} {\binom {b}{ m}} (r-2)^{b-m} (r-1)^{n-k-b}.$$

The number of colored permutations in $G_{r,n}$ with exactly $m>0$
$(c,d)$-descents ($0\leq c<d\leq r-1$) with respect to the absolute order, is given by
$$\frac{n!}{2^m}\sumlim_{k=1}^{n-1} \sumlim_{b=1}^{k} {\binom {k}{
b}}{\binom {n-k}{
b}} {\binom {b}{ m}} (r-2)^{b-m} (r-1)^{n-k-b}.$$
\end{proposition}

This proves Proposition~\ref{cddes}.


\section{$(c,c)$-descents}\label{cc-des}

In this section, we calculate the number of permutations of $\grn$ having a fixed number of $(c,c)$-descents.
Note that in this case, the enumeration is identical in the color order and the absolute order, since both orders satisfy
$$1^{[c]} < 2^{[c]} < \cdots <n^{[c]}.$$
Hence, we denote: ${\rm des}_{c}(\pi)={\rm des}_{c,c}^{\rm Clr}(\pi)={\rm des}_{c,c}^{\rm Abs}(\pi)$.

We use here a recursive approach.
Let $\pi=i_1^{[j_1]}\cdots i_n^{[ j_n]} \in \grn$. Using a map $f:
\grn \rightarrow \grn$ which takes each colored digit $i^{[j]}$ to
$i^{[(j+1) \pmod r]}$, we are led to the following.

\begin{Obs}\label{gl2}
For each color $c \in \{0,\dots,r-1\}$, the number of colored
permutations with exactly $m$ $(c,c)$-descents is equal to the
number of colored permutations with exactly $m$ $(0,0)$-descents.
\end{Obs}

By the above observation, it suffices to find the generating
function for the number of colored permutations in $G_{r,n}$ having
$(0,0)$-descents.

\medskip

Let
$$g_{r,n}(q)= \sum_{\pi\in G_{r,n}}q^{{\rm des}_{0}(\pi)}.$$
In order to find a recurrence  for $g_{r,n}(q)$, we will use the
following notations. Define
$$g_{r,n}^+(q)=\sum\limits_{\pi\in G_{r,n}, \ c_1(\pi)=0}q^{{\rm des}_{0}(\pi)},$$
$$ g_{r,n}^-(q)=\sum\limits_{\pi\in G_{r,n}, \ c_1(\pi) \neq 0}q^{{\rm des}_{0}(\pi)}.$$
Note that $g_{r,n}(q)=g_{r,n}^+(q)+g_{r,n}^-(q)$.

\medskip

Let $\pi \in G_{r,n}$. If $|\pi_n|=n$, denote $\pi=\pi'\pi_n$ and we
have $${\rm des}_{0}(\pi)={\rm des}_{0}(\pi').$$

Otherwise, let $j<n$ be such that $|\pi_j|=n$. Denote: $\pi=\pi'
\pi_j \pi'' \in G_{r,n}$. If $\pi_j=n^{[c]}$ for $c \neq 0$, then ${\rm des}_{0}(\pi)={\rm
des}_{0}(\pi')+{\rm des}_{0}(\pi'')$. If $\pi_j=n$, we have two cases
depending on the color of $\pi''_1$ (the first element of $\pi''$):
$${\rm des}_{0}(\pi)=\begin{cases}
{\rm des}_{0}(\pi')+{\rm des}_{0}(\pi'') &\text{if } c_1(\pi'') \neq 0, \\
1+{\rm des}_{0}(\pi')+{\rm des}_{0}(\pi'') & \mbox{otherwise.}
\end{cases}$$
Since there are no restrictions on the positions of the digits\break
$1,2,\dots,n-1$, we have the following recurrences.

\begin{lemma}\label{lem1}
For all $n\geq1$, we have
\begin{multline*}
g_{r,n}(q)=rg_{r,n-1}(q)+(r-1)\sum\limits_{j=1}^{n-1}\binom{n-1}{j-1}g_{r,j-1}(q)g_{r,n-j}(q)\\
+\sum\limits_{j=1}^{n-1}\binom{n-1}{j-1}g_{r,j-1}(q)(g_{r,n-j}^-(q)+qg_{r,n-j}^+(q)),
\end{multline*}
and for $n \geq2$, we have
\begin{multline*}
g_{r,n}^+(q)=rg_{r,n-1}^+(q)+(r-1)\sum\limits_{j=2}^{n-1}\binom{n-1}{j-1}g_{r,j-1}^+(q)g_{r,n-j}(q)\\
+\sum\limits_{j=1}^{n-1}\binom{n-1}{j-1}g_{r,j-1}^+(q)(g_{r,n-j}^-(q)+qg_{r,n-j}^+(q)).
\end{multline*}
\end{lemma}

\begin{proof}
In both expressions, the first summand corresponds to the case
$|\pi_n|=n$, the second corresponds to the case $\pi_j=n^{[c]}$ ($c\neq 0$) for
some $j$, $1 \leq j \leq n-1$, and the third corresponds to the case
$\pi_j=n$ for some $j$, $1 \leq j \leq n-1$.
\end{proof}

In order to find an explicit formula for $g_{r,n}(q)$, we rewrite
the above recurrences in terms of exponential generating functions.
Define
$$G_r(x,q)=\sum_{n\geq0}g_{r,n}(q)\frac{x^n}{n!},\quad
G^+_r(x,q)=\sum_{n\geq0}g_{r,n}^+(q)\frac{x^n}{n!},$$
and
$$G^-_r(x,q)=\sum_{n\geq0}g_{r,n}^-(q)\frac{x^n}{n!}.$$
Since $g_{r,n}(q)=g_{r,n}^+(q)+g_{r,n}^-(q)$, we have 
$$G_r(x,q)=G_r^+(x,q)+G_r^-(x,q).$$
Moreover, for all $n \geq 1$, Lemma~\ref{lem1} yields
\begin{align*}
\frac{d}{dx} \left(\frac{g_{r,n}(q)}{n!}x^n\right)&=
\frac{rg_{r,n-1}(q)}{(n-1)!}x^{n-1}\\
&\quad \quad +(r-1)x^{n-1}\sum_{j=0}^{n-2}\frac{g_{r,j}(q)}{j!}\cdot\frac{g_{r,n-1-j}(q)}{(n-1-j)!}\\
&\quad \quad
+x^{n-1}\sum_{j=0}^{n-2}\frac{g_{r,j}(q)}{j!}\cdot\frac{g_{r,n-1-j}^-(q)+qg_{r,n-1-j}^+(q)}{(n-1-j)!},
\end{align*}
and
\begin{align*}
\frac{d}{dx} \left(\frac{g_{r,n}^+(q)}{n!}x^n\right)&=
r\frac{g_{r,n-1}^+(q)}{(n-1)!}x^{n-1}\\
&\quad \quad +(r-1)x^{n-1}\sum_{j=1}^{n-2}\frac{g_{r,j}^+(q)}{j!}\cdot\frac{g_{r,n-1-j}(q)}{(n-1-j)!}\\
&\quad \quad  +x^{n-1}\sum_{j=0}^{n-2}\frac{g_{r,j}^+(q)}{j!}\cdot\frac{g_{r,n-1-j}^-(q)+qg_{r,n-1-j}^+(q)}{(n-1-j)!}.
\end{align*}
Summing over all $n\geq1$ and using the initial conditions
$g_{r,0}(q)=g_{r,0}^+(q)=g_{r,1}^+(q)=1$, $g_{r,0}^-(q)=0$ and
$g_{r,1}^-(q)=r-1$, we get 
\begin{align*}
G_r(x,q)&=G_r^+(x,q)+G_r^-(x,q),\\
\frac{d}{dx}\left(G_r(x,q)\right)&=(1-q)G_r(x,q)+(r-1)(G_r(x,q))^2\\
&\quad \quad +G_r(x,q)G_r^-(x,q)  +qG_r(x,q)G_r^+(x,q),\\
\frac{d}{dx}\left(G_r^+(x,q)\right)&=(1-q)G_r^+(x,q)+(r-1)G_r^+(x,q)G_r(x,q)\\
&\quad \quad   +G_r^+(x,q)G_r^-(x,q)+q(G_r^+(x,q))^2.
\end{align*}
Using any computer algebra package, such as {\sl Maple} or
{\sl Mathematica}, we obtain the following result.

\begin{theorem}
The generating functions $G_r(x,q)$, $G_r^+(x,q)$ and\break $G_r^-(x,q)$
are given by
$$G_r(x,q)=\frac{1-q}{(r-1)x(q-1)-q+e^{(q-1)x}},$$
$$G_r^+(x,q)=\frac{(1-q)(1-(r-1)x)}{(r-1)x(q-1)-q+e^{(q-1)x}},$$
$$G_r^-(x,q)=\frac{x(r-1)(1-q)}{(r-1)x(q-1)-q+e^{(q-1)x}},$$
respectively.
\end{theorem}

In order to obtain an explicit formula for the number of colored
permutations in $G_{r,n}$ with exactly $m$ $(0,0)$-descents, we find
the coefficient of $x^nq^m$ in $G_r(x,q)$:
\begin{align*}
G_r(x,q)&=\frac{1-q}{e^{(q-1)x}-q}\cdot\frac{1}{1-\frac{(r-1)x(1-q)}{e^{(q-1)x}-q}}\\
&=\sum\limits_{j\geq0}\frac{(r-1)^jx^j(1-q)^{j+1}}{(e^{(q-1)x}-q)^{j+1}}\\
&=\sum\limits_{j,i,k\geq0}(r-1)^jx^j(1-q)^{j+1}\binom{j+i}{j}q^i\frac{(1-q)^kx^k(i+j+1)^k}{k!}\\
&=\sum\limits_{j,i,k\geq0}\sumlim_{\ell=0}^{j+k+1}(-1)^\ell(r-1)^j\binom{j+i}{j}\binom{j+k+1}{\ell}\\
&\kern6cm\cdot q^{\ell+i}x^{j+k}\frac{(i+j+1)^k}{k!}.
\end{align*} 
Thus the coefficient of $x^nq^m$ in $G_r(x,q)$ is
given by
$$\sum\limits_{j=0}^{n}\sum\limits_{i=0}^m(-1)^i(r-1)^j\binom{j+m-i}{j}\binom{n+1}{i}\frac{(m-i+j+1)^{n-j}}{(n-j)!}.$$
This implies that the number of colored permutations in $G_{r,n}$
with exactly $m$ $(0,0)$-descents (or $(c,c)$-descents for any $0 \leq c \leq r-1$) is
$$n!\sum\limits_{j=0}^{n}\sum\limits_{i=0}^m(-1)^i(r-1)^j\binom{j+m-i}{j}\binom{n+1}{i}\frac{(m-i+j+1)^{n-j}}{(n-j)!},$$
as stated in Proposition~\ref{ccdes}.


\section*{Acknowledgements}
The authors would like to thank Ron Adin for some helpful advice.

%----------------------------------------------------------------------------
\begin{thebibliography}{99}

\bibitem{HLR} J. Hall, J. Liese and J. Remmel, {\it q-Analogues of
formulas counting descent pairs with prescribed tops and bottoms}, preprint.


\bibitem{HR}  J. Hall and J. Remmel, {\it Counting descent pairs with prescribed
tops and bottoms}, J. Combin. Theory Ser.~A {\bf 115}(5) (2008), 693--725.

\bibitem{KMR} S. Kitaev, T. Mansour and J. Remmel, {\it Counting descents, rises, and levels, with prescribed first
element, in words}, Discrete Math. Theoret. Comp. Sci. {\bf 10}(3) (2008), 1--22.

\bibitem{KR0} S. Kitaev and J. Remmel, {\it Classifying descents according to equivalence mod $k$},
Electronic J. Combin. {\bf 13}(1) (2006), Article~\#R64.

\bibitem{KR} S. Kitaev and J. Remmel, {\it Classifying descents according to
parity}, Ann. Combin. {\bf 11} (2007), 173--193.

%\bibitem{Mac}
%P. A. MacMahon, Combinatory Analysis, Vol. 1 and 2, Cambridge Univ.
%Press, Cambridge, 1915 (reprinted by Chelsea, New York, 1955).



\bibitem{MM1}
P. A. MacMahon, {\em Combinatory Analysis, Vol. 1 and 2}, Cambridge Univ.
Press, Cambridge, 1915 (reprinted by Chelsea, New York, 1955).



\bibitem{MM2}
P.\ A.\ MacMahon, {\it The indices of permutations and the
derivation therefrom of functions of a single variable associated
with the permutations of any assemblage of objects}, Amer. J. Math.
{\bf 35} (1913), 281--322.




\end{thebibliography}

\end{document}