<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}   

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage[dvips]{epsfig}
\usepackage{latexsym}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{indentfirst}
\usepackage{array}

\def\Des{{\rm Des}}
\def\Ris{{\rm Ris}}
\def\Rise{{\rm Rise}}
\def\WDes{{\rm WDes}}
\def\WRis{{\rm WRis}}
\def\NonDes{{\rm NonDes}}
\def\nondes{{\rm nondes}}
\def\coinv{{\rm coinv}}
\def\inv{{\rm inv}}
\def\sgn{{\rm sgn}}
\def\SUP{{\it SUP}}
\def\SDU{{\it SDU}}
\def\WUD{{\it WUD}}
\def\WDU{{\it WDU}}
\def\WU{{\it WU}}
\def\SUD{{\it SUD}}


\newcommand{\coi}[1][\sigma]{\mathrm{coinv}(#1)}
\DeclareMathOperator{\des}{\mathrm{des}}
\DeclareMathOperator{\maj}{\mathrm{maj}}
%\newcommand{\inv}[1][\sigma]{\mathrm{inv}(#1)}
\newcommand{\la}{\lambda}
\newcommand{\La}{\Lambda}
\newcommand{\wdes}[1][\gamma]{\mathrm{wdes}(#1)}
\newcommand{\ov}{\overline}
\newcommand{\pos}[1][\sigma]{\mathrm{pos}(#1)}
\newcommand{\qbinom}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{q}}
\newcommand{\pqbinom}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{p,q}}
\newcommand{\rbinom}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{r}}
\newcommand{\ris}[1][\sigma]{\mathrm{ris}(#1)}
\newcommand{\sg}{\sigma}
\newcommand{\ep}{\epsilon}
\newcommand{\ga}{\gamma}
\newcommand{\Ta}{\Theta}
\newcommand{\N}{\mathbf{N}}
\newcommand{\Pos}{\mathbf{P}}
\newcommand{\Ev}{\mathbf{E}}
\newcommand{\Odd}{\mathbf{O}}
\newcommand{\sP}{s\mathbf{P}}
\newcommand{\C}{\mathbf{C}}
\newcommand{\UD}{U\mbox{-}D}
\newcommand{\NDD}{ND\mbox{-}D}
\newcommand{\UNU}{U\mbox{-}NU}
\newcommand{\ud}{u\mbox{-}d}
\newcommand{\ndd}{nd\mbox{-}d}
\newcommand{\unu}{u\mbox{-}nu}
\def\dd{{\textrm d}}
\def\qexp{{\mathbf{e}}_q}
\def\pqexp{{\mathbf{e}}_{p,q}}
\newcommand{\fig}[2]{\begin{figure}[ht]
\centerline{\scalebox{.66}{\epsfig{file=#1.eps}}}
\caption{#2}
\label{figure:#1}
\end{figure}}




\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Analogues of Up-down Permutations for   \\
\vskip .05in
Colored Permutations
}
\vskip 1cm
\large
Andrew Niedermaier and Jeffrey Remmel\footnote{Partially supported by NSF grant DMS 0654060.}\\
Department of Mathematics\\
University of California, San Diego\\
La Jolla, CA 92093-0112\\
USA\\
\href{mailto:jremmel@ucsd.edu}{\tt jremmel@ucsd.edu}\\
\end{center}

\vskip .2 in

\begin{abstract}
Andr\'e proved that $\sec x$ is the generating 
function of all up-down permutations of even length and 
$\tan x$ is the generating function of all up-down permutation 
of odd length. There are three equivalent ways to define 
up-down permutations in the symmetric group $S_n$. That is, a permutation 
$\sg$ in the symmetric group $S_n$ is an 
up-down permutation if either (i) the rise set of $\sg$ consists 
of all the odd numbers less than $n$, (ii) the descent set of $\sg$ 
consists of all even number less than $n$, or (iii) both (i) and (ii). 
We consider analogues of Andr\'e's results 
for colored permutations of the form $(\sg,w)$ where 
$\sg \in S_n$ and $w \in \{0,\ldots, k-1\}^n$ under the product order. 
That is, we define $(\sg_i,w_i) &lt; (\sg_{i+1},w_{i+1})$ if and only if 
$\sg_i &lt; \sg_{i+1}$ and $w_i \leq w_{i+1}$. 
We then say a colored permutation $(\sg,w)$ is 
(I) an {\em up-not up} permutation 
if the rise set of $(\sg,w)$ consists 
of all the odd numbers less than $n$, (II) a {\em not down-down} permutation 
if the descent set of $(\sg,w)$ consists 
of all the even numbers less than $n$, (III) an {\em up-down} permutation 
if both (I) and (II) hold. For $k \geq 2$, 
conditions (I), (II), and (III) are pairwise distinct. We 
find $p,q$-analogues of the generating functions 
for up-not up, not down-down, and up-down colored permutations. 
\end{abstract}


\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}






\section{Introduction}

Let $\Pos = \{1,2,3, \ldots \}$ denote the set of
positive integers, $\Ev = \{2,4,6, \ldots \}$ denote
the set of even integers in $\Pos$, and $\Odd =\{1,3,5,\ldots \}$ denote
the set of odd integers in $\Pos$. 
Let $\Pos_n = \{1,\ldots,n\}$,
$\Ev_n = \Ev \cap \Pos_n$, and $\Odd_n = \Odd \cap \Pos_n$. 
Let $S_n$ denote the symmetric group, i.e., 
the set of all permutations of $\Pos_n$. Then
if $\sg = \sg_1 \sg_2 \ldots \sg_n \in S_n$, we define
$\Des(\sg) =\{i: \sg_i &gt; \sg_{i+1}\}$ and $\Ris(\sg) =\{i: \sg_i &lt; \sg_{i+1}\}$.
We say that $\sg$ is an {\em up-down permutation} if
$$\sg_1 &lt; \sg_2 &gt; \sg_3 &lt; \sg_4 &gt; \sg_5 \cdots ,$$
or, equivalently, if $\Des(\sg) = \Ev_{n-1}$ or $\Ris(\sg) = \Odd_{n-1}$.
Similarly, we say that $\sg$ is an {\em down-up permutation} if
$$\sg_1 &gt; \sg_2 &lt; \sg_3 &gt; \sg_4 &lt; \sg_5 \cdots ,$$
or, equivalently, if $\Ris(\sg) = \Ev_{n-1}$ or  $\Des(\sg) = \Odd_{n-1}$.
Clearly if $\sg = \sg_1 \sg_2 \cdots \sg_n \in S_n$ is an up-down
permutation, then the complement of $\sg$,
$$\sg^c= (n+1 - \sg_1)  (n+1 - \sg_2) \cdots (n+1 - \sg_n)$$
is a down-up permutation. Thus the number of up-down
permutations in  $S_n$ is equal to the number of down-up permutations
in $S_n$. Let  $UD_n$ denote the number of up-down permutations in $S_n$.
Then Andr\'e \cite{Andre1,Andre2} proved the following.
\begin{eqnarray}
\sec t &amp;=&amp; 1+ \sum_{n \in \Ev} UD_n \frac{t^n}{n!}  \ \mbox{and} \\
\tan t &amp;=&amp; \sum_{n \in \Odd} UD_n \frac{t^n}{n!}.
\end{eqnarray}


The goal of this paper is to find  analogues of Andr\'e's results
for colored permutations.  That is, we shall consider pairs of 
the form $(\sg,w)$ where $\sg \in S_n$ and $w \in \{0,1, \ldots, k-1\}^n$. 
Thus if $w =w_1 \cdots w_n$ and $\sg = \sg_1 \cdots \sg_n \in S_n$, 
then we will say that $\sg_i$ is colored with $w_i$ in $(\sg,w)$. 
Alternatively, we can think of $(\sg,w)$ as an element of 
the wreath product $C_k \wr S_n$ of the cyclic group $C_k$ and the
symmetric group $S_n$.
$C_k \wr S_n$ is the group of $k^nn!$ signed permutations
where there are $k$ signs, $1=\ep^0$, $\ep$, $\ep^2$,
$\ldots$, $\ep^{k-1}$ where $\ep$ is a primitive $k$-th root of
unity. Hence we can think of $\Gamma \in C_k \wr S_n$ as a pair
$(\sg,w)$ where $\sg  = \sg_1 \ldots \sg_n \in S_n$ and 
the sign of $\sg_i$ is $\ep^{w_i}$ for $i=1,\ldots, n$. Throughout 
the paper, we shall abbreviate $S_n \times \{0,\ldots, k-1\}^n$ by 
$C_k \wr S_n$ even though our results do not use the group structure 
of $C_k \wr S_n$. . 


To define the analogues of up-down permutations in $C_k \wr S_n$, we need
to define the analogues of the descent set and the rise set
of a colored permutation.  That is, suppose $\prec$ is a partial order on the set of
pairs $(i,j) \in \{1,\ldots,n\} \times
\{0,\ldots, k-1\}$. Then if $\sg = \sg_1 \ldots \sg_n \in S_n$ and 
$w = w_1 \ldots w_n \in \{0, \ldots, k-1\}^n$, we define  
\begin{eqnarray*}
\Des_{\prec}((\sg,w)) &amp;=&amp; \{i: (\sg_i,w_i) \succ (\sg_{i+1},w_{i+1})\} \ \mbox{and} \\
\Ris_{\prec}((\sg,w)) &amp;=&amp;\{i: (\sg_i,w_i) \prec (\sg_{i+1},w_{i+1})\}.
\end{eqnarray*}
 We then say that  $(\sg,w)$ is  an up-down permutation if
\begin{equation}\label{basic}
(\sg_1,w_1) \prec (\sg_2,w_2) \succ (\sg_3,w_3) \prec (\sg_4,w_4)
\succ (\sg_5,w_5) \cdots .
\end{equation}
Now if $\prec$ is a total order, then counting the number of
up-down permutations is uninteresting.
For example,
Adin and Roichman \cite{AR} used the following total order to define their
notion of flag major index on $C_k \wr S_n$:
$$(1,{k-1}) \prec \cdots \prec (n,{k-1}) \prec
(1,{k-2}) \prec \cdots \prec (n,{k-2}) \prec \cdots \prec
(1,0) \prec \cdots \prec (n,0).$$
If we use such a total  order $\prec$ and
we pick an assignment of colors,  $(1,w_1), \ldots (n,w_n)$, to 
$1,2, \ldots,n$, then
$\prec$ induces a total order on the pairs $(1,w_1), \ldots ,(n,w_n)$. Hence for this assignment of colors, there are clearly just
$UD_n$ pairs $(\sg,w)$ which satisfy (\ref{basic}).  Hence relative
to a total order $\prec$, there are  $k^n UD_n$ colored permutations
$(\sg,w) \in C_k\wr S_n$ that satisfy (\ref{basic}).

However
if we use the product order on $\{1,\ldots,n\} \times
\{0, \ldots, k-1\}$, then we
have a completely different situation. That is,  
we define the product order  $\leq$ on
$\{1,\ldots,n\} \times \{0,,\ldots, {k-1}\}$
by declaring that $(i_1,j_1) \leq (i_2,j_2)$ if and only
if $i_1 \leq i_2$ and $j_1 \leq j_2$. Again
we can define the analogue of the descent set and rise set of a colored permutation in $C_k \wr S_n$ as
\begin{eqnarray}
\Des((\sg,w)) &amp;=&amp; \{i: (\sg_i,w_i) &gt; (\sg_{i+1},w_{i+1})\} \ \mbox{and}\\
\Ris((\sg,w)) &amp;=&amp; \{i: (\sg_i,w_i) &lt; (\sg_{i+1},w_{i+1})\}.
\end{eqnarray}
We can then define three different natural analogues
of up-down permutations. That is, we define the following
three sets of permutations in $C_k \wr S_n$:
\begin{enumerate}
\item $\displaystyle U\mbox{-}D_{n,k} =
\{(\sg,w) \in C_k \wr S_n: \Ris((\sg,w)) = \Odd_{n-1} \ \mbox{and} \
\Des((\sg,w)) = \Ev_{n-1}\}$,
\item $\displaystyle U\mbox{-}NU_{n,k} =
\{(\sg,w) \in C_k \wr S_n: \Ris((\sg,w)) = \Odd_{n-1}\}$, and
\item $\displaystyle ND\mbox{-}D_{n,k} =
\{(\sg,w) \in C_k \wr S_n:
\Des((\sg,w)) = \Ev_{n-1}\}$.
\end{enumerate}
Here $U\mbox{-}NU$ stands for ``up-not up'' and $ND\mbox{-}D$ stands for 
``not down-down.'' Clearly  $U\mbox{-}D_{n,k}$ is contained
in both $U\mbox{-}NU_{n,k}$ and $ND\mbox{-}D_{n,k}$. However,
both of these containments are strict and
$U\mbox{-}NU_{n,k} \neq ND\mbox{-}D_{n,k}$. For example, if
$k=2$ and $n=3$, then
\begin{eqnarray*}
(1~2~3,1~1~0) &amp;\in&amp; U\mbox{-}NU_{3,2} -
(U\mbox{-}D_{3,2} \cup \NDD_{3,2})\ \mbox{and} \\
(1~3~2,1~0~0) &amp;\in&amp; ND\mbox{-}D_{3,2} - (U\mbox{-}D_{3,2}
\cup \UNU_{3,2}).
\end{eqnarray*}


Let
$\ud_{n,k} = |\UD_{n,k}|$, $\ndd_{n,k} = |\NDD_{n,k}|$, and
$\unu_{n,k} = |\UNU_{n,k}|$. Then the main goal of this paper is to find expressions for the following
generating functions:
\begin{eqnarray*}
A(t) &amp;=&amp; \sum_{n \geq 0} \frac{\ud_{2n,k}t^{2n}}{(2n)!}, \ \ \ \ \ \ \ \ \ 
B(t) = \sum_{n \geq 0} \frac{\ud_{2n+1,k}t^{2n+1}}{(2n+1)!},\\
C(t) &amp;=&amp; \sum_{n \geq 0} \frac{\unu_{2n,k}t^{2n}}{(2n)!}, \ \ \ \ \ \ \ 
D(t) = \sum_{n \geq 0} \frac{\unu_{2n+1,k}t^{2n+1}}{(2n+1)!},\\
E(t) &amp;=&amp; \sum_{n \geq 0} \frac{\ndd_{2n,k}t^{2n}}{(2n)!}, \ \mbox{and} \ 
F(t) = \sum_{n \geq 0} \frac{\ndd_{2n+1,k}t^{2n+1}}{(2n+1)!}.
\end{eqnarray*}


The generating functions $A(t)$ and $B(t)$ are simply
Hadamard products of the generating functions for up-down permutations
of $S_n$ and the generating functions for sequences of
words $w = w_1 \ldots w_n \in \{0,\ldots, k-1\}^*$ such that
$$w_1 \leq w_2 \geq w_3 \leq w_4 \geq w_5 \leq w_6 \cdots .$$
The generating function for such words was found by Rawlings
\cite{Raw}. The generating functions for $C(t)$, $D(t)$, $E(t)$ and $F(t)$
are more interesting. For example, we shall show that
\begin{eqnarray}
C(t) &amp;=&amp;
\frac{(k-1)!}{\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1}\cos t} \ \mbox{and} \\
D(t) &amp;=&amp;  \frac{\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1}\sin t}{\frac{\dd^{k-1}}{\dd t^{k-1}}t^{k-1}\cos t}
\end{eqnarray}
For $k\leq 4$, the generating functions and their initial terms are listed below:\[
\begin{array}{c@{\qquad}c@{\qquad}c@{\qquad}l}
k &amp; \textrm{egf for } \unu_{2n,k} &amp; \textrm{egf for } \unu_{2n+1,k} &amp; \{\unu_{n,k}\}_{n\geq 1} \\ \hline 1 &amp; \sec t &amp; \tan t &amp; 1, 1, 2, 5, 16, 61, \ldots\\
2 &amp; \frac{1}{\cos t-t\sin t}&amp; \frac{\sin t+t\cos t}{\cos t-t\sin t}&amp; 2, 3, 14, 49, 376, 1987,\ldots\\
3 &amp; \frac{2}{(2-t^2)\cos t-4t\sin t}&amp; \frac{4t\cos t+(2-t^2)\sin t}{(2-t^2)\cos t-4t\sin t} &amp; 3, 6, 44, 201, 2436, 16768, \ldots\\
4 &amp; \frac{6}{(6-9t^2)\cos t -(18t-t^3)\sin t}&amp; \frac{(18t-t^3)\cos
t+(6-9t^2)\sin t}{(6-9t^2)\cos t -(18t-t^3)\sin t}&amp; 4, 10, 100, 565, 9356,
79584,\ldots
\end{array}
\]

It is easy to see that if $(\sg,w) = (\sg_1 \ldots \sg_{2n+1},
w_1\ldots  w_{2n+1})$ is in $\UNU_{2n+1,k}$, then the reverse of $(\sg,w)$,
$$(\sg,w)^r = (\sg_{2n+1} \ldots \sg_1,w_{2n+1} \ldots  w_1),$$
will be in $\NDD_{2n+1,k}$ so that
\begin{align}
\sum_{n\geq 0}\frac{\ndd_{2n+1,k}\cdot t^{2n+1}}{(2n+1)!} &amp;=
\frac{\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1}\sin t}{\frac{\dd^{k-1}}{\dd
t^{k-1}} t^{k-1}\cos t}.
\end{align}
Thus $D(t) = F(t)$.  However the generating function for $E(t)$ is not
the same as for $C(t)$. We shall prove that
\begin{align*}
E(t) = \sum_{n\geq 0}\frac{\ndd_{2n,k}\cdot t^{2n}}{(2n)!} &amp;=
\left(\frac{(k-1)!}{2\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1}e^{it}} +
\frac{(k-1)!}{2\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1}e^{-it}}\right)^{-1} \\
&amp;= \frac{\left(\frac{\dd^{k-1}}{\dd t^{k-1}}
t^{k-1}e^{it}\right)\left(\frac{\dd^{k-1}}{\dd t^{k-1}}
t^{k-1}e^{-it}\right)}{(k-1)!\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1}\cos t} \\
&amp;= \frac{P_{k-1}(it)P_{k-1}(-it)}{(k-1)!\frac{\dd^{k-1}}{\dd t^{k-1}}
t^{k-1}\cos t},
\end{align*}
where $P_d(z) = \sum_{m=0}^d z^d \binom{d}{m}^2 ((d-m)!)$. In fact,
we shall prove that 
\begin{eqnarray}
P_{d}(it)P_{d}(-it) &amp;=&amp;
\sum_{s=0}^{d} t^{2s} \sum_{r=0}^{2s} (-1)^{s-r}
\binom{d}{r}^2 (d-r)!
\binom{d}{2s-r}^2 (d-(2s-r))! \nonumber \\
&amp;=&amp; \sum_{s=0}^{d} \frac{(d!)^2}{(2s)!} \binom{d}{s} \binom{d+s}{s}t^{2s}.
\end{eqnarray}
Thus $P_{d}(it)P_{d}(-it)$  is a polynomial with integer coefficients
of degree $2d$ where only
even-degree terms are non-zero. 
For $k\leq 4$, we get the following results:
\[
\begin{array}{c@{\qquad}c@{\qquad}c@{\qquad}l}
k &amp; \textrm{egf for } \ndd_{2n,k} &amp; P_{k-1}(z) &amp; \{\ndd_{n,k}\}_{n\geq 1} \\ \hline 1 &amp; \sec t &amp; 1 &amp; 1, 1, 2, 5, 16, 61, \ldots\\
2 &amp; \frac{1+t^2}{\cos t-t\sin t}&amp; 1+z &amp; 2, 10, 14, 85, 376, 3457,\ldots\\
3 &amp; \frac{4+12t^2+t^4}{(2-t^2)\cos t-4t\sin t}&amp;  2+4z+z^2 &amp; 3, 12, 44, 423, 2436, 35398, \ldots\\
4 &amp; \frac{36+216t^2+45t^4+t^6}{(6-9t^2)\cos t -(18t-t^3)\sin t}&amp; 6+18z+9z^2+z^3
&amp; 4, 22, 100, 1315, 9356, 185804,\ldots
\end{array}
\]


In fact, we shall show that the generating functions $C(t)$, $D(t)$,
$E(t)$ and $F(t)$  are special cases of more general generating functions
which keep track of more statistics over more general
sets of elements in $C_k \wr S_n$.  That is, for any $k \geq 2$, let
\begin{eqnarray}
(C_k \wr S_n)^{(2)} &amp;=&amp; \{(\sg,w) \in C_k \wr S_n: \Odd_{n-1} \subseteq
\Rise((\sg,w))\} \ \mbox{and} \\
(C_k \wr S_n)_{(2)}&amp;=&amp; \{(\sg,w) \in C_k \wr S_n:  \Odd_{n-1} \cap
\Des((\sg,w)) = \emptyset\}.
\end{eqnarray}
Thus $(C_k \wr S_n)^{(2)}$ is the set of $(\sg,w) \in C_k\wr S_n$ which are forced of
have rises at all odd positions and  $(C_k \wr S_n)_{(2)}$ is the set of $(\sg,w) \in C_k\wr S_n$ which do not have a descent  at
an odd position. Then we shall find generating functions for certain
statistics on $(C_k \wr S_n)^{(2)}$ which specialize to $C(t)$ and $D(t)$ and
generating functions for certain statistics on $(C_k \wr S_n)_{(2)}$ which specialize to $E(t)$ and $F(t)$.
The techniques that we shall use to derive our generating functions over
$(C_k \wr S_n)^{(2)}$ or $(C_k \wr S_n)_{(2)}$ are based on ideas
from a paper by Mendes, Remmel, and Riehl \cite{MRR}
who, for any $k \geq 2$ and $0 \leq j \leq k-1$, found generating functions
for permutations $\sg \in S_n$ such that  
$\Des(\sg) = \{j+sk: k \geq 0 \ \&amp; \  j+sk &lt; n\}$.  Mendes, Remmel, and
Riehl derived their generating functions by applying certain
ring homomorphisms defined on the ring of symmetric functions
$\Gamma$ over infinitely many variables $x_1, x_2, \ldots $ to simple symmetric function identities. We will also find our generating functions
over $(C_k \wr S_n)^{(2)}$ or $(C_k \wr S_n)_{(2)}$ by applying
ring homomorphisms defined on $\Lambda$ to simple symmetric function
identities. To derive our generating functions
over $(C_k \wr S_n)_{(2)}$, we shall also need to find the generating
function for $(\sg,w) \in C_k \wr S_n$ such that
$\Des((\sg,w)) = \emptyset$.



The outline of this paper is as follows. In Section 2, we shall
derive the generating functions $A(t)$ and $B(t)$. In Section 3,
we shall provide the necessary background on symmetric
functions that we shall need to derive the generating functions
$C(t)$, $D(t)$, $E(t)$ and $F(t)$. In Section 4, we shall give
the derivations of the generating functions that specialize to $C(t)$ and $D(t)$. Finally in Section 5, we shall give the derivations of the generating
functions that specialize to $E(t)$ and $F(t)$.


\section{The generating functions for up-down permutations}



In this section, we shall give expressions for the generating functions
for $A(t)$ and $B(t)$.  To state our results, we first need
some notation. Suppose that $f(t) = \sum_{n \geq 0} f_n t^n$ and
$g(t) = \sum_{n \geq 0} g_n t^n$.  Then the Hadamard product
$f(t) \otimes g(t)$ of $f$ and $g$ is defined by
\begin{equation}
f(t) \otimes g(t) = \sum_{n\geq 0} f_n g_n t^n.
\end{equation}
 Let
$\Pos^*$ denote the set of all words over the alphabet
$\Pos$ and $\Pos^+$ denote the set of all non-empty words in
$\Pos^*$. We let $\epsilon$ denote
the empty word. For any $w = w_1 w_2 \ldots w_n \in \Pos^+$,
we let $\ell(w) =n$ denote the length of $w$, $|w| = \sum_{i=1}^n w_i$,
and $x(w) = \prod_{i=1}^n x_{w_i}$. For example,
if $w = 1~2~1~3~2~4~5~4$, then $\ell(w) = 8$, $|w| = 22$, and
$x(w) = x_1^2 x_2^2 x_3 x_4^2 x_5$. Given
$w = w_1 w_2 \ldots w_n \in \Pos^+$, we define the descent
set $\Des(w)$, the weak descent set $\WDes(w)$, the rise
set $\Ris(w)$, and the weak rise set $\WRis(w)$ as follows:
\begin{eqnarray}
\Des(w) &amp;=&amp; \{i:w_i &gt; w_{i+1}\}, \\
\WDes(w) &amp;=&amp; \{i:w_i \geq w_{i+1}\}, \\
\Ris(w) &amp;=&amp; \{i:w_i &lt; w_{i+1}\}, \ \mbox{and} \\
\WRis(w) &amp;=&amp; \{i:w_i \leq  w_{i+1}\}.
\end{eqnarray}


\begin{definition} {\rm Let $w = w_1 w_2 \ldots w_n \in \Pos^+$.
\begin{enumerate}
\item We say that $w$ a {\em strict up-down} word if
$w_1 &lt; w_2 &gt; w_3 &lt; w_4 &gt; w_5 \cdots$, or, equivalently
if $\Ris(w) = \Odd_{n-1}$ and  $\Des(w) = \Ev_{n-1}$.
\item We say that $w$ a {\em strict down-up} word if
$w_1 &gt; w_2 &lt; w_3 &gt; w_4 &lt; w_5 \cdots$, or, equivalently
if $\Des(w) = \Odd_{n-1}$ and  $\Ris(w) = \Ev_{n-1}$.
\item We say that $w$ a {\em weak up-down} word if
$w_1 \leq w_2 \geq  w_3 \leq  w_4 \geq  w_5 \cdots$, or, equivalently
if $\WRis(w) = \Odd_{n-1}$ and  $\WDes(w) = \Ev_{n-1}$.
\item We say that $w$ a {\em weak down-up} word if
$w_1 \geq w_2 \leq  w_3 \geq w_4 \leq  w_5 \cdots$, or, equivalently
if $\WDes(w) = \Odd_{n-1}$ and  $\WRis(w) = \Ev_{n-1}$.
\end{enumerate}}
\end{definition}

We let $\SUP_n$, $\SDU_n$, $\WUD_n$, and $\WDU_n$ denote
set of all words in $\{1, \ldots,n\}^*$ which are  strict up-down, strict
down-up, weak up-down, and weak down-up, respectively. By convention, the empty word $\epsilon$ and all one letter
words belong to all four sets. Clearly, if $w = w_1 w_2 \ldots w_n \in \Pos_n^*$, then $w  \in
\SUD_n \ (\WUD_n, \ \mbox{respectively})$ if and only if the complement of $w$ relative to $n$,
$$w^{c,n} = (n+1-w_1) (n+1-w_2) \ldots (n+1-w_n) \in \SDU_n \ (\WUD_n, \ \mbox{respectively}).$$
We let $\SUP_{n,m}$, $\SDU_{n,m}$, $\WUD_{n,m}$, and $\WDU_{n,m}$ denote
set of all words in $\Pos_n^*$ of length $m$ which are  strict up-down, strict
down-up, weak up-down, and weak down-up, respectively.



Carlitz \cite{Car} proved analogues of Andr\'e's formulas
for  strict up-down words. In particular,
Carlitz \cite{Car} proved that 
\begin{equation}\label{Carexp1}
1 + \sum_{m \in \Ev} |\SUD_{n,m}|z^m =  \frac{1}{Q_n(z)} \ \mbox{and} \ 
\sum_{m \in \Odd} |\SUD_{n,m}|z^m = \frac{P_n(z)}{Q_n(z)}
\end{equation}
where
\begin{eqnarray}
P_n(z) &amp;=&amp; \sum_{k=0}^n (-1)^k \binom{n+k}{2k+1} z^{2k+1} \ \mbox{and} \\
Q_n(z) &amp;=&amp; \sum_{k=0}^n (-1)^k \binom{n+k-1}{2k} z^{2k}.
\end{eqnarray}
Rawlings \cite{Raw} proved analogues of
(\ref{Carexp1}) for weak down-up words. That is,
Rawlings
proved that
\begin{equation}\label{Rawexp1}
1 + \sum_{m \in \Ev} |\WDU_{n,m}| z^m =
\frac{1}{R_n(z)}
\ \mbox{and} \ 
\sum_{m \in \Odd} |\WDU_{n,m}| z^m = 
\frac{S_n(z)}{R_n(z)}
\end{equation}
where
\begin{eqnarray}
R_n(z) &amp;=&amp; \sum_{k \geq 0} (-1)^k \binom{n+k}{2k} z^{2k}
\ \mbox{and} \\
S_n(z) &amp;=&amp; \sum_{k \geq 0} (-1)^k\binom{n+k}{2k+1}z^{2k+1}.
\end{eqnarray}
By our observations above, these are also the generating functions
for weak up-down words. Carlitz and Rawlings proved their
generating functions by recursions. In fact, Carlitz
developed recursions for the up-down words $w$ weighted by
$x(w)$ and Rawlings actually proved a generating function
for weak down-up words $w$ weighted by $q^{|w|}z^{\ell(w)}$. Recently,
Fuller and Remmel \cite{FR} showed that the generating functions of
words $w$ according to the weight $x(w) z^{\ell(w)}$ of
words in either $\SUD_n$ and $\WU_n$ can be expressed in term
of quasi-symmetric functions. Fuller and Remmel proved their results
combinatorially via some simple involutions and their
methods actually extend to a much broader class of words
with regular up-down patterns.



Now it is easy to see that if
$(\sg,w) =(\sg_1 \cdots \sg_n,w_1 \cdots w_n) \in C_k \wr S_n$
where $\Ris((\sg,w)) = \Odd_{n-1}$ and $\Des((\sg,w)) = \Ev_{n-1}$, then
it must be the case that 
$\Ris(\sg) = \Odd_{n-1}$ and $\Des(\sg) = \Ev_{n-1}$ so that
$\sg$ is an up-down permutation and $w_1 \leq w_2 \geq w_3 \leq w_4 \cdots $ so
that $w$ is a weak up-down word over the
alphabet $\{0, \ldots, k-1\}$.
It then follows that
\begin{equation} \label{eq:A}
A(t) = \sum_{n \geq 0} \frac{\ud_{2n,k}t^{2n}}{(2n)!} = \left(\frac{1}{R_k(t)}\right)\otimes \sec t 
\end{equation}
and
\begin{equation} \label{eq:B}
B(t) = \sum_{n \geq 0} \frac{\ud_{2n+1,k}t^{2n+1}}{(2n+1)!} = \left(\frac{S_k(t)}{R_k(t)}\right)\otimes \tan t .
\end{equation}


We can also define a strong product order $&lt;_s$ on $\Pos \times
\{0, \ldots, k-1\}$ by defining
$(i_1,w_1) &lt;_s (i_2,w_2)$ if and only
if $i_1 &lt; i_2$ and $w_1 &lt; w_2$.
We then
define
\begin{eqnarray*}
\Des_s((\sg,w)) &amp;=&amp; \{i: (\sg_{i+1},w_i)\} &lt;_s(\sg_i,w_{i+1})\}  \ \mbox{and}\\
\Ris_s((\sg,w)) &amp;=&amp; \{i: (\sg_i,w_i) &lt;_s (\sg_{i+1},w_{i+1})\}.
\end{eqnarray*}
We say at that $(\sg,w) \in C_k \wr S_n$ is a {\em strong up-down}
permutation if $\Ris_s((\sg,w)) =  \Odd_{n-1}$ and
$\Des_s((\sg,w)) =  \Ev_{n-1}$. We let $s\ud_{n,k}$ denote
the number of strong up-down permutations of $C_k \wr S_n$. Then clearly,

\begin{equation} \label{eq:barA}
\bar{A}(t) = \sum_{n \geq 0} \frac{s\ud_{2n,k}t^{2n}}{(2n)!} =  \left(\frac{1}{G_k(t)}\right)\otimes \sec t 
\end{equation}
and
\begin{equation} \label{eq:barB}
\bar{B}(t) = \sum_{n \geq 0} \frac{s\ud_{2n+1,k}t^{2n+1}}{(2n+1)!}
=  \left(\frac{F_k(t)}{G_k(t)}\right)\otimes \tan t .
\end{equation}


\section{Symmetric Functions}


In this section we give the necessary background on symmetric
functions needed for our proofs of the generating functions
over $(C_k \wr S_n)^{(2)}$ or $(C_k \wr S_n)_{(2)}$.


Let $\Lambda$ denote the ring of symmetric functions
over infinitely many variables $x_1, x_2, \ldots $ with coefficients in
the field complex numbers $\C$.
The $n^{\text{th}}$ elementary symmetric function $e_n$ in the variables $x_1,x_2,\dots$ is
given by
\begin{equation*}
E(t) =  \sum_{n \geq 0} e_n t^n = \prod_i (1+x_i t)
\end{equation*}
and the $n^{\text{th}}$ homogeneous symmetric function $h_n$ in the variables $x_1,x_2,\dots$ is
given by
\begin{equation*}
H(t) =  \sum_{n \geq 0} h_n t^n = \prod_i \frac{1}{1-x_i t}.
\end{equation*}
Thus
\begin{equation}
\label{HE}
H(t) =  1/E(-t).
\end{equation}
Let $\la = (\la_1,\dots,\la_\ell)$ be an integer partition, that is,
$\la$ is a finite sequence of weakly increasing nonnegative
integers.  Let $\ell(\la)$ denote the number of nonzero integers in
$\la$. If the sum of these integers is $n$, we say that $\la$ is a
partition of $n$ and write $\la \vdash n$.  For any partition $\la =
(\la_1,\dots,\la_\ell)$, let $e_\la = e_{\la_1} \cdots
e_{\la_\ell}$. The well-known fundamental theorem of symmetric
functions says that $\{e_\la : \text{$\la$ is a partition}\}$ is a
basis for $\La$ or that $\{e_0,e_1,\ldots \}$ is an algebraically
independent set of generators for $\Lambda$.
Similarly, if we define  $h_\la = h_{\la_1} \cdots
h_{\la_\ell}$, then $\{h_\la : \text{$\la$ is a partition}\}$ is
also a basis for $\La$. Since $\{e_0,e_1, \ldots \}$ is an algebraically independent
set of generators for $\Lambda$, we can specify a ring homomorphism
$\theta$ on $\Lambda$ by simply defining $\theta(e_n)$ for all
$n \geq 0$.

Since the set of elementary symmetric functions $e_\lambda$ is a basis for
$\Lambda$, one can expresses $h_n = \sum_{\lambda \vdash n} 
a_{\lambda,n} e_\lambda$ for any $n &gt; 0$. 
 Up to a sign, the coefficient $a_{\lambda,n}$ equals the size of a certain set of combinatorial objects depending on $\lambda$.  A {\em
brick tabloid} of shape $(n)$ and type $\la =(\la_1,\ldots, \la_k)$ is a
filling of a row of $n$ squares of cells with brick of lengths
$\la_1, \ldots, \la_k$ such that bricks to not overlap.
One brick tabloid of shape
$(12)$ and type $(1,1,2,3,5)$ is displayed below.



\fig{brickt}{A brick tabloid of shape $(12)$ and type $(1,1,2,3,5)$.}

Let $\mathcal{B}_{\la,n}$ denote the set of all $\la$-brick tabloids of shape $(n)$ and let
$B_{\la,n} =|\mathcal{B}_{\la,n}|$.  Through simple recursions
stemming from \eqref{HE}, E\u{g}ecio\u{g}lu and Remmel proved in
\cite{ER} that
\begin{equation}
\label{omar}
h_n = \sum_{\la \vdash n} (-1)^{n - \ell(\la)} B_{\la,n} e_\la.
\end{equation}

Next we define a class of symmetric functions $p_{n,\nu}$ which have a relationship with $e_\lambda$
that is analogous to the relationship between $h_n$ and
$e_\lambda$.  These functions were  first introduced in \cite{LR} and
\cite{MendesTh}. Let $\nu$ be a function which maps the set of
nonnegative integers into the field $F$. Recursively define
$p_{n,\nu} \in \La_n$ by setting $p_{0,\nu} = 1$ and letting
\begin{equation*}
p_{n,\nu}
= (-1)^{n-1} \nu(n) e_n + \sum_{k=1}^{n-1}(-1)^{k-1}e_k p_{n-k,\nu}
\end{equation*}
for all $n \geq 1$.  By multiplying series, this means that
\begin{equation*}
\left(\sum_{n \geq 0}(-1)^n e_n t^n \right) \left(\sum_{n \geq 1}
p_{n,\nu} t^n \right)
= \sum_{n \geq 1} \left ( \sum_{k=0}^{n-1} p_{n-k,\nu} (-1)^k e_k
\right ) t^n
= \sum_{n \geq 1} (-1)^{n-1} \nu(n) e_n t^n,
\end{equation*}
where the last equality follows from the definition of $p_{n,\nu}$.
Therefore,
\begin{equation}\label{fund0}
\sum_{n \geq 1} p_{n,\nu}t^n
= \frac{\sum_{n \geq 1} (-1)^{n-1} \nu(n) e_n t^n}
{\sum_{n \geq 0} (-1)^n e_n t^n}
\end{equation}
or, equivalently,
\begin{equation}
\label{fund}
1+ \sum_{n \geq 1} p_{n,\nu}t^n
= \frac{1+ \sum_{n \geq 1} (-1)^{n}(e_n - \nu(n) e_n) t^n}
{\sum_{n \geq 0} (-1)^n e_n t^n}.
\end{equation}
When taking $\nu(n) = 1$ for all $n \geq 1$, \eqref{fund} becomes
\begin{equation*}
1 + \sum_{n \geq 1} p_{n,1} t^n 
= \frac{1}{\sum_{n \geq 0} (-1)^n e_n t^n}
= 1 + \sum_{n \geq 1} h_n t^n
\end{equation*}
which implies $p_{n,1} = h_n$.  Other special cases for $\nu$ give
well-known generating functions. For example, if $\nu(n) = n$ for $n
\geq 1$, then $p_{n,\nu}$ is the power symmetric function $\sum_{i}
x_i^n$.    By taking $\nu(n) = (-1)^k \chi(n \geq k+1)$ for some $k
\geq 1$, $p_{n,(-1)^k\chi(n \geq k+1)}$ is the Schur function
corresponding to the partition $(1^k,n)$.

This definition of $p_{n,\nu}$ is desirable because of its expansion in terms
of elementary symmetric functions.  The coefficient of $e_\la$ in $p_{n,\nu}$
has a nice combinatorial interpretation similar to that of the homogeneous
symmetric functions.  Suppose $T$ is a brick tabloid of shape $(n)$ and type
$\la$ and that the final brick in $T$ has length $\ell$.  Define the weight
of a brick tabloid $w_{\nu}(T)$ to be $\nu(\ell)$ and let
\begin{equation*}
w_{\nu}(B_{\la,n}) = \sum_{\substack{\text{$T$ is a brick tabloid} \\
\text{of shape $(n)$ and type $\la$}}} w_{\nu}(T).
\end{equation*}
 By the recursions found in the definition of $p_{n,\nu}$, it may be
shown that
\begin{equation*}
p_{n,\nu} = \sum_{\la \vdash n}(-1)^{n-\ell(\la)} w_{\nu}(B_{\lambda,n}) e_\la
\end{equation*}
in almost the exact same way that \eqref{omar} was proved in \cite{ER}.


For $n \geq 1$ and $\la \vdash n$, let
\begin{alignat*}{2}
[n]_{q}&amp;=\frac{1-q^n}{1-q}= q^0+q^1+\cdots+q^{n-1} &amp; [n]_{p,q} &amp; =\frac{p^n-q^n}{p-q}=p^{n-1} q^0+\cdots+p^0 q^{n-1}  \\
[n]_{q}! &amp; = [n]_{q} \cdots [1]_{q} &amp; [n]_{p,q}! 
&amp; = [n]_{p,q} \cdots [1]_{p,q} \\
\qbinom{n}{\la} &amp; = \frac{[n]_{q}!}{[\la_1]_{q}! \cdots [\la_\ell]_{q}!} &amp;  \pqbinom{n}{\la} &amp; = \frac{[n]_{p,q}!}{[\la_1]_{p,q}! \cdots
[\la_\ell]_{p,q}!} 
\end{alignat*}
be the $q$- and $p,q$-analogues of $n$, $n!$, and $\binom{n}{\la}$, respectfully.  We shall use the convention that $[0]_q = [0]_{p,q} = 0$ and $[0]_q!
=[0]_{p,q}! = 1$.
The $q$- and $p,q$-analogues for the exponential function are defined by
\begin{equation*}
\qexp[t] = \sum_{n \geq 0} \frac{t^n}{[n]_{q}!} q^{\binom{n}{2}} \qquad \qquad \pqexp[t] = \sum_{n \geq 0} \frac{t^n}{[n]_{p,q}!}
q^{\binom{n}{2}}.
\end{equation*}


For any permutation  $\sg \in S_n$, we define the number of inversions
$\inv(\sg)$ and the number of coinversions $\coinv(\sg)$ of $\sg$ by
\begin{equation*}
\inv(\sigma)  = \sum_{i &lt; j} \chi(\sigma_i &gt; \sigma_j) \ \mbox{and} \ 
\coinv(\sigma)  = \sum_{i &lt;j} \chi(\sigma_i &lt; \sigma_j)
\end{equation*}
where for any statement $A$, $\chi(A) =1$ is $A$ is true and
$\chi(A) =0$ if $A$ is false. Note that $\inv(\sg)$ and
$\coinv(\sg)$ make sense if $\sg$ is any sequence of non-negative
integers.

We end this section with three lemmas that
will be needed a later sections. All of the lemmas
follow from simple codings of a basic result of
Carlitz \cite{Car2} that
$$
\qbinom{n}{k} = \sum_{\mathcal{R}(1^k0^{n-k})} q^{\inv(r)}
$$
where $\mathcal{R}(1^k0^{n-k})$ is the number of rearrangements of
$k$ 1's and $n-k$ 0's.
We start with a lemma from \cite{MRR}.
Fix a brick tabloid $T = (b_1, \ldots,b_{\ell(\mu)}) \in \mathcal{B}_{\mu,n}$.  Let $IF(T)$
denote the set of all fillings of the cells of
$T = (b_1, \ldots, b_{\ell(\mu)})$ with the numbers
$1, \ldots, n$ so that the numbers increase within each brick
reading from left to right. We then think of each such filling as a
permutation of $S_n$ by reading the numbers from left to right in each row. For example,
Figure \ref{figure:fil1} pictures an
element of $IF(3,6,3)$ whose corresponding permutation
is $4~6~12~1~5~7~8~10~11~2~3~9$.

\fig{fil1}{An element of $IF(3,6,3)$}

Then the following lemma from \cite{MRR}
gives a combinatorial interpretation to \\
${p}^{\sum_{i=1}^{\ell(\mu)} \binom{b_i}{2}} \pqbinom{n}{b_1, \ldots, b_{\ell(\mu)}}$.
\begin{lemma}
\label{Carlitz}
If $T=(b_1, \ldots, b_{\ell(\mu)})$ is a brick tabloid in $\mathcal{B}_{\mu,n}$, then
\begin{equation*}
p^{\sum_i \binom{b_i}{2}} \pqbinom{n}{b_1, \ldots, b_{\ell(\mu)}} =
\sum_{\sg \in IF(T)} q^{\inv(\sg)} p^{\coinv(\sg)}.
\end{equation*}
\end{lemma}

Let $DF(T)$
denote the set of all fillings of the cells of $T = (b_1, \ldots, b_{\ell(\mu)})$ with the numbers
$1, \ldots, n$ so that the numbers decrease within each brick
reading from left to right. It is easy to see that
if $\sg \in IF(T)$, then $\sg^r \in DF((b_{\ell(\mu)}, \ldots, b_1))$
and $\inv(\sg) = \coinv(\sg^r)$ and $\coinv(\sg) = \inv(\sg^r)$. Thus we also
have the following lemma.

\begin{lemma}
\label{Carlitz2}
If $T=(b_1, \ldots, b_{\ell(\mu)})$ is a brick tabloid in $\mathcal{B}_{\mu,n}$, then
\begin{equation*}
q^{\sum_i \binom{b_i}{2}} \pqbinom{n}{b_1, \ldots, b_{\ell(\mu)}} =
\sum_{\sg \in DF(T)} q^{\inv(\sg)} p^{\coinv(\sg)}.
\end{equation*}
\end{lemma}

Another well-known combinatorial interpretation for
$\qbinom{n+k-1}{k-1}$ is that it is equal to sum of the sizes of the
partitions that are contained in a $n \times (k-1)$ rectangle.
Thus we have the following lemma.
\begin{lemma}
\label{Carlitz3}
\begin{equation*}
\sum_{0 \leq a_1 \leq \cdots \leq a_n \leq k-1} q^{a_1+ \cdots + a_n} =
\qbinom{n+k-1}{k-1}.
\end{equation*}
\end{lemma}


\section{The generating functions up-not up permutations}

In this section, we shall derive two generating functions
that can be specialized to give the generating functions
for $C(t)$ and $D(t)$ stated in the introduction.
If $(\sg,w) \in C_k \wr S_n$, we let \\
\begin{eqnarray}
\Ris_{\Ev}((\sg,w)) &amp;=&amp; \{2i: 2i \in Ris((\sg,w))\} \ \mbox{and} \\
\ris_{\Ev}((\sg,w)) &amp;=&amp; |\Ris_{\Ev}((\sg,w)) |.
\end{eqnarray}
We let
$(C_k \wr S_n)^{(2)}$ denote the set of $(\sg,w) \in C_k \wr S_n$ such
that $\Odd_{n-1} \subseteq \Ris((\sg,w))$. Thus if
$(\sg,w) \in (C_k \wr S_n)^{(2)}$, $(\sg,w)$ is forced to have
rises at all odd positions and $\ris_{\Ev}(\sg,w)$ counts
how many elements of the form $2i$ are in $\Ris((\sg,w))$. In particular,
if  $(\sg,w) \in (C_k \wr S_n)^{(2)}$ and $\ris_{\Ev}(\sg,w) =0$,
then $(\sg,w) \in \UNU_{n,k}$. 

Our first theorem of this section is the following.

\begin{theorem}\label{thm:Cg} For all $k \geq 2$, 
\begin{eqnarray}\label{eq:Cg}
&amp;&amp;\sum_{n\geq 0}\frac{t^{2n}}{[2n]_{p,q}!}\sum_{(\sg,w) \in
(C_k \wr S_{2n})^{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|} x^{\ris_{\Ev}((\sg,w))} = \nonumber \\
&amp;&amp;\frac{1-x}{1-x + \sum_{m\geq 1}
\frac{p^{\binom{m}{2}}(x-1)^mt^{2m}}{[2m]_{p,q}!}\rbinom{2m+k-1}{k-1}}
\end{eqnarray}
\end{theorem}

Note that when we set $x=0$ and $p=q =r =1$, then (\ref{eq:Cg}) reduces
to
\begin{eqnarray}
\sum_{n\geq 0}\frac{\unu_{2n,k} t^{2n}}{(2n)!} &amp;=&amp;
\frac{1}{\sum_{m\geq 0}
\frac{t^{2m}(-1)^m}{(2m)!}\frac{(2m+k-1)(2m-k-2) \cdots (2m+1)}{(k-1)!}}
\nonumber \\
&amp;=&amp; \frac{(k-1)!}{\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1}\cos t}.
\end{eqnarray}
which is the generating function of $C(t)$ claimed in the introduction.


\begin{proof}
Define a ring homomorphism
$\theta:\Lambda \rightarrow \mathbb{Q}(p,q,r,x)$, where $\mathbb{Q}$ is the 
set of the rational numbers,  by setting
\begin{equation}
\theta(e_{2n}) = (-1)^{2n-1}(x-1)^{n-1}\frac{\rbinom{2n+k-1}{k-1}}{[2n]_{p,q}!} p^{\binom{n}{2}}
\end{equation}
if $n \geq 1$ and
\begin{equation}
\theta(e_{2n+1}) = 0
\end{equation}
if $n \geq 0$.
Then we claim that
\begin{equation}\label{Cg0}
\theta(h_{2n+1}) = 0
\end{equation}
 for all $n \geq 0$ and
\begin{equation}\label{Cg1}
[2n]_{p,q}!\theta(h_{2n}) = \sum_{(\sg,w) \in
(C_k \wr S_{2n})^{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|} x^{\ris_{\Ev}((\sg,w))}
\end{equation}
for all $n \geq 1$. Note that
\begin{equation}\label{Cg2}
\theta(h_{n}) = \sum_{\mu\vdash n} (-1)^{n-\ell(\mu)}B_{\mu, (n)}
\theta(e_{\mu}).
\end{equation}
First suppose that $n$ is odd. Then clearly every partition $\mu$ of $n$ must have an odd part and, hence,
 $\theta(h_{n}) =0$ since $\theta(e_{2k+1})=0$ for all $k \geq 0$.
If $n$ is even, then the only $\mu$ such that $\theta(e_\mu) \neq 0$ on
the RHS of (\ref{Cg2}) are when all the parts of $\mu$ are even. That
is, $\mu$ must be of the form $2\la$ where $\la =(\la_1, \ldots,
\la_k)$ is partition of $n$ and
$2\la = (2\la_1,\ldots, 2\la_k)$. Thus
\begin{eqnarray}\label{Cg3}
&amp;&amp;\ [2n]_{p,q}!\theta(h_{2n}) \\
&amp;&amp;\ = [2n]_{p,q}! \sum_{\mu\vdash n} (-1)^{2n-\ell(\mu)}B_{2\mu, (2n)}\theta(e_{2\mu})  \nonumber \\
&amp;&amp; \ = [2n]_{p,q}! \sum_{\mu \vdash n} (-1)^{2n-\ell(\mu)}
\sum_{(2b_1, \ldots, 2b_{\ell(\mu)}) \in \mathcal{B}_{2\mu,(2n)}}
\prod_{j=1}^{\ell(\mu)} (-1)^{2b_j-1}(x-1)^{b_j-1}
\frac{\rbinom{2b_j+k-1}{k-1}}{[2b_j]_{p,q}!} p^{\binom{2b_j}{2}} \nonumber \\
&amp;&amp; \ = \sum_{\mu \vdash n} \sum_{(2b_1, \ldots, 2b_{\ell(\mu)}) \in \mathcal{B}_{2\mu,(2n)}} p^{\sum_{j=1}^{\ell(\mu)} \binom{2b_j}{2}}\pqbinom{2n}{2b_1,\ldots,2b_{\ell(\mu)}} \prod_{j=1}^{\ell(\mu)} (x-1)^{b_j-1}
\rbinom{2b_j+k-1}{k-1}. \nonumber 
\end{eqnarray}

Next we want to give a combinatorial interpretation to (\ref{Cg3}).
By Lemma \ref{Carlitz} for each brick tabloid
$T= (2b_1, \ldots, 2b_{\ell(\mu)})$, we can interpret
$p^{\sum_{j=1}^{\ell(\mu)} \binom{2b_j}{2}}
\pqbinom{2n}{2b_1,\ldots,2b_{\ell(\mu)}}$ as the sum of the weights of fillings of $T$ with
permutations $\sg \in S_{2n}$ such that $\sg$ is increasing in each brick
and we weight $\sg$ with $q^{\inv(\sg)}p^{\coinv(\sg)}$.  By Lemma
\ref{Carlitz3},
we can interpret the term $\prod_{j=1}^{\ell(\mu)}\rbinom{2b_j+k-1}{k-1}$ as
the sum of the weights of fillings  $w= w_1 \cdots w_{2n}$ of $T$ where
the elements of $w$ are between 0 and $k-1$ and are  weakly increasing
in each brick and we weight $w$ by $r^{|w|}$.  Finally,
we interpret $\prod_{j=1}^{\ell(\mu)} (x-1)^{b_j-1}$ as all ways of picking a label
of the even cells of each brick except the final cell
with either an $x$ or a $-1$. For completeness, we label the final
cell of each brick with $1$. We shall call all such objects that can be created
by these choices
{\em filled labeled brick tabloids} and we let
$\mathcal{F}_{2n}$ denote the set of all filled labeled brick tabloids.
Thus a $C \in \mathcal{F}_{2n}$ consists of
a brick tabloid $T$, a permutation $\sg \in S_{2n}$, a sequence
$w \in \{0,\ldots,k-1\}^{2n}$, and a labeling $L$ of the even cells of
$T$ with elements from $\{x,1,-1\}$ such that
\begin{enumerate}
\item all the bricks of $T$ have even length,
\item $\sg$ is strictly increasing in each brick,
\item $w$ is weakly increasing in each brick,
\item the final cell of each brick is labeled with 1, and
\item each even numbered cell which is not a final cell of a brick
is labeled with x or $-1$.
\end{enumerate}
We then define the weight $w(C)$ of $C$ to be
$q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|}$ times the product of all
the $x$ labels in $L$ and the sign $\sgn(C)$ of $C$ to be
the product of all the $-1$ labels in $L$. For example,
if $n =12$, $k=4$, and $T =(4,6,2)$, then Figure 
\ref{figure:fill1}
pictures such a composite object $C \in \mathcal{F}_{12}$ where
$w(C) = q^{23}p^{43}r^{17}x^2$ and $\sgn(C) =-1$.

Thus
\begin{equation}\label{Cg4}
[2n]_{p,q}!\theta(h_{2n}) = \sum_{C \in \mathcal{F}_{2n}}
\sgn(C) w(C).
\end{equation}



\fig{fill1}{A composite object $C \in \mathcal{F}_{12}$.}



Next we define a weight preserving sign-reversing involution
$I_1:\mathcal{F}_{2n} \rightarrow \mathcal{F}_{2n}$.  To define
$I_1(C)$, we scan the cells of $C =(T,\sg,w,L)$ from right to left
looking for the leftmost cell $2t$ such that either
(i) $2t$ is labeled
with $-1$ or (ii) $2t$ is at the end a brick $b_j$ and the
brick $b_{j+1}$ immediately following $b_j$ has the property
that $\sg$ is strictly increasing in all the cells corresponding
to $b_j$ and $b_{j+1}$ and $w$ is weakly  increasing in all the cells corresponding to $b_j$ and $b_{j+1}$.  In case (i),
$I_1(C) =(T',\sg',w',L')$ where $T'$ is the result of  replacing the brick
$b$ in $T$ containing $2t$ by
two bricks $b^*$ and $b^{**}$ where $b^*$ contains the
cell $2t$ plus all the cells in $b$ to the left of $2t$ and $b^{**}$ contains
all the cells of $b$ to the right of $2t$, $\sg' =\sg$, $w' = w$, and
$L'$ is the labeling that results from $L$ by changing the label
of cell $2t$ from $-1$ to $1$. In case (ii),
$I_1(C) =(T',\sg',w',L')$ where $T'$ is the result of replacing the bricks
$b_j$ and $b_{j+1}$ in $T$ by a single brick $b,$ $\sg' =\sg$, $w' = w$, and
$L'$ is the labeling that results from $L$ by changing the label
of cell $2t$ from $1$ to $-1$. If neither case (i) or case (ii) applies,
then we let $I_1(C) =C$. For example, if $C$ is the element of
$\mathcal{F}_{12}$ pictured in Figure \ref{figure:fill1}, then
$I_1(C)$ is pictured in Figure \ref{figure:fill2}.


\fig{fill2}{$I_1(C)$ for $C$ in Figure \ref{figure:fill1}.}

It is easy to see that $I_1$ is a weight-preserving sign-reversing
involution and hence $I_1$ shows that
\begin{equation}\label{Cg5}
[2n]_{p,q}!\theta(h_{2n}) = \sum_{C \in \mathcal{F}_{2n},I_1(C) = C}
\sgn(C) w(C).
\end{equation}

Thus we must examine the fixed points $C = (T,\sg,w,L)$ of $I_1$.
First
there can be no $-1$ labels in $L$ so that $sg(C) =1$. Moreover,  if
$b_j$ and $b_{j+1}$ are two consecutive bricks in $T$ and
$2t$ is that last cell of $b_j$, then it can not be the case
that $\sg_{2t} &lt; \sg_{2t+1}$ and $w_{2t} \leq w_{2t+1}$ since
otherwise we could combine $b_j$ and $b_{j+1}$.
For any such fixed point, we can think of 
the pair $(\sg,w)$ as an element of  $C_k \wr S_{2n}$. 
It follows that if cell $2t$ is at the end of a brick, then
$2t \not \in \Ris_{\Ev}((\sg,w))$. However
if $2v$ is a cell which is not at the end of brick, then
our definitions force
$\sg_{2v} &lt; \sg_{2v+1}$ and $w_{2v} \leq w_{2v+1}$  so that
$2v \in \Ris_{\Ev}((\sg,w))$. Since each such cell $2v$ must
be labeled with an $x$, it follows that
$\sgn(C)w(C) = q^{\inv(\sg)}p^{\coinv(\sg)}r^{|w|}x^{\ris_{\Ev}((\sg,w))}$.
Moreover our definitions force that $\Odd_{2n-1} \subseteq \Ris((\sg,w))$
so that $(\sg,w) \in (C_k \wr S_{2n})^{(2)}$.  Such a fixed point 
is pictured in Figure \ref{figure:fill3}.
Vice versa, if
$(\sg,w) \in (C_k \wr S_{2n})^{(2)}$, then we can create a fixed
point $C =(T,\sg,w,L)$ by having the bricks in $T$ end
at cells of the form $2t$ where $2t \not \in \Ris_{\Ev}((\sg,w)$ and 
labeling each cell $2t \in \Ris_{\Ev}((\sg,w))$ with $x$ and
labeling all other even numbered cells with $1$.
Thus we have shown that
\begin{equation*}
[2n]_{p,q}!\theta(h_2n) = \sum_{(\sg,w) \in
(C_k \wr S_{2n})^{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|} x^{\ris_{\Ev}((\sg,w))}
\end{equation*}
as desired.

\fig{fill3}{A fixed point of $I_1$.}

Applying $\theta$ to the identity $H(t) = (E(-t))^{-1}$, we get
\begin{eqnarray*}
\sum_{n \geq 0} \theta(h_n) t^n &amp;=&amp; \sum_{n\geq 0} \frac{t^{2n}}{[2n]_{p,q}!} \sum_{(\sg,w)\in (C_k\wr S_{2n})^{(2)}} q^{\inv(\sg)}p^{\coinv(\sg)}
r^{|w|}x^{\ris_{\Ev}(\sg,w)} \\
&amp;=&amp; \frac{1}{1+\sum_{n\geq 1} (-t)^n\theta(e_n)} \\
&amp;=&amp; \frac{1}{1+\sum_{m\geq 1}(-1)^{2m} t^{2m}
\frac{(-1)^{2m-1}(x-1)^{m-1}p^{\binom{2m}{2}}}{[2m]_{p,q}!}\rbinom{2m+k-1}{k-1}} \\
&amp;=&amp;
\frac{1-x}{1-x + \sum_{m\geq 1}\frac{p^{\binom{2m}{2}}(x-1)^mt^{2m}}{[2m]_{p,q}!}\binom{2m+k-1}{k-1}}
\end{eqnarray*}
which proves (\ref{eq:Cg}).

\end{proof}





\begin{theorem}\label{thm:Dg} For all $k \geq 2$, 
\begin{eqnarray}\label{eq:Dg}
&amp;&amp;\sum_{n\geq 0}\frac{t^{2n+1}}{[2n+1]_{p,q}!}\sum_{(\sg,w) \in
(C_k \wr S_{2n+1})^{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|} x^{\ris_{\Ev}((\sg,w))} = \nonumber \\
&amp;&amp;\frac{-\sum_{m \geq 1} \frac{p^{\binom{2m-1}{2}} (x-1)^m t^{2m-1}}{[2m-1]_{p,q}}
\rbinom{2m-1+k-1}{k-1}}{1-x + \sum_{m\geq 1}
\frac{p^{\binom{m}{2}}(x-1)^mt^{2m}}{[2m]_{p,q}!}\rbinom{2m+k-1}{k-1}}.
\end{eqnarray}
\end{theorem}

Note that when we set $x=0$ and $p=q =r =1$, then (\ref{eq:Cg}) reduces
to
\begin{eqnarray}
\sum_{n\geq 0}\frac{\unu_{2n+1,k} t^{2n+1}}{(2n+1)!} &amp;=&amp;
\frac{\sum_{m \geq 1} \frac{(-1)^{m-1}t^{2m-1}}{(2m-1)!} \frac{(2m+k-2) \cdots (2m)}{(k-1)!}}{\sum_{m\geq 0}
\frac{t^{2m}(-1)^m}{(2m)!}\frac{(2m+k-1)(2m-k-2) \cdots (2m+1)}{(k-1)!}}
\nonumber \\
&amp;=&amp; \frac{\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1}\sin t} {\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1}\cos t} 
\end{eqnarray}
which is the generating function of $D(t)$ claimed in the introduction.


\begin{proof}
Let $\theta$ be the ring homomorphism defined in Theorem \ref{thm:Cg}.
In this case, we will derive (\ref{eq:Dg}) by applying
$\theta$ to the identity
\begin{equation}\label{pnuid}
\sum_{n \geq 1} p_{n,\nu}t^n
= \frac{\sum_{n \geq 1} (-1)^{n-1} \nu(n) e_n t^n}
{\sum_{n \geq 0} (-1)^n e_n t^n}
\end{equation}
where
\begin{eqnarray}
\nu(2n) &amp;=&amp; \frac{[2n]_{p,q}[2n]_r}{p^{2n-1}[2n+k-1]_r} \\
        &amp;=&amp; \frac{p^{\binom{2n-1}{2}}}{p^{\binom{2n}{2}}}
\frac{[2n]_{p,q}!}{[2n-1]_{p,q}!} \frac{\rbinom{2n-1+k-1}{k-1}}{\rbinom{2n+k-1}{k-1}} \nonumber
\end{eqnarray}
for $n \geq 1$ and $\nu(2m+1) =0$ for $m \geq 0$. We
have defined $\nu$ so that
\begin{equation}\label{nu}
\nu(2n) \theta(e_{2n}) =
\frac{(-1)^{2n-1} (x-1)^{n-1} p^{\binom{2n-1}{2}}}{[2n-1]_{p,q}!}\rbinom{2n-1+k-1}{k-1}.
\end{equation}


Again it is easy to see that
\begin{equation}\label{Dg0}
\theta(p_{2n+1,\nu}) = 0
\end{equation}
 for all $n \geq 0$ since the expansion of $p_{2n+1,\nu}$ in terms
of the elementary symmetric functions only involves $e_\mu$'s where
$\mu$  contains an odd part.
The key fact that we have to prove is that
\begin{equation}\label{Dg1}
[2n+1]_{p,q}!\theta(p_{2n+2,\nu}) = \sum_{(\sg,w) \in
(C_k \wr S_{2n+1})^{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|} x^{\ris_{\Ev}((\sg,w))}
\end{equation}
for all $n \geq 0$. Note that
\begin{eqnarray}\label{Dg3}
&amp;&amp;\ [2n+1]_{p,q}!\theta(p_{2n+2,\nu})  \\
&amp;&amp; \ = [2n+1]_{p,q}! \sum_{\mu\vdash n+1} (-1)^{2n+2-\ell(\mu)}
w_\nu(B_{2\mu, (2n+2)})\theta(e_{2\mu})  \nonumber \\
&amp;&amp; \ = [2n+1]_{p,q}! \sum_{\mu \vdash n+1} (-1)^{2n+2-\ell(\mu)}
\sum_{(2b_1, \ldots, 2b_{\ell(\mu)}) \in \mathcal{B}_{2\mu,(2n+2)}}
\nu(2b_{\ell(\mu)}) \times \nonumber \\
&amp;&amp; \ \ \ \ \ \ \ \prod_{j=1}^{\ell(\mu)} (-1)^{2b_j-1}(x-1)^{b_j-1}
\frac{\rbinom{2b_j+k-1}{k-1}}{[2b_j]_{p,q}!} p^{\binom{2b_j}{2}} \nonumber \\
&amp;&amp; \ = [2n+1]_{p,q}!\sum_{\mu \vdash n+1} \sum_{(2b_1, \ldots, 2b_{\ell(\mu)}) \in \mathcal{B}_{2\mu,(2n+2)}}
\frac{p^{\binom{2b_{\ell(\mu)}-1}{2}} (x-1)^{b_{\ell(\mu)}-1}}{[2b_{\ell(\mu)}-1]_{p,q}!} \rbinom{2b_{\ell(\mu)}-1+k-1}{k-1} \times \nonumber \\
&amp;&amp; \ \ \ \ \ \ \ \prod_{j=1}^{\ell(\mu)-1} \frac{p^{\binom{2b_j}{2}}
(x-1)^{b_j -1}}{[2b_j]_{p,q}!} \rbinom{2b_j +k-1}{k-1} \nonumber \\
&amp;&amp; \ = \sum_{\mu \vdash n+1}
\sum_{(2b_1, \ldots, 2b_{\ell(\mu)}) \in \mathcal{B}_{2\mu,(2n+2)}}
p^{\binom{2b_{\ell(\mu)}-1}{2}}p^{\sum_{j=1}^{\ell(\mu)-1}\binom{2b_j}{2}}
\pqbinom{2n+1}{2b_1,\ldots,2b_{\ell(\mu)-1},2b_{\ell(\mu)}-1} \times \nonumber \\
&amp;&amp; \ \ \ \ \ \ \ (x-1)^{b_{\ell(\mu)}-1} \rbinom{2b_{\ell(\mu)}-1+k-1}{k-1}
\prod_{j=1}^{\ell(\mu)-1} (x-1)^{b_j-1}
\rbinom{2b_j+k-1}{k-1}. \nonumber 
\end{eqnarray}



Again we want to give a combinatorial interpretation to (\ref{Dg3}).
By Lemma \ref{Carlitz} for each brick tabloid
$T= (2b_1, \ldots, 2b_{\ell(\mu)})$, we can interpret
$$p^{\binom{2b_{\ell(\mu)}-1}{2}}p^{\sum_{j=1}^{\ell(\mu)-1}\binom{2b_j}{2}}\pqbinom{2n+1}{2b_1,\ldots,2b_{\ell(\mu)-1},2b_{\ell(\mu)-1}}$$
the sum of the weights of fillings of the first 2n+1 cells of $T$ with
a permutation $\sg \in S_{2n+1}$ such that $\sg$ is increasing in each brick
and where we weight $\sg$ with $q^{\inv(\sg)}p^{\coinv(\sg)}$.  Note
that $T$ has $2n+2$ cells so we will assume that the last cell of
$T$ is filled in  and we will not place anything in that cell.
By Lemma
\ref{Carlitz3},
we can interpret the term $\rbinom{2b_{\ell(\mu)}-1+k-1}{k-1}
\prod_{j=1}^{\ell(\mu)-1}\rbinom{2b_j+k-1}{k-1}$ as
giving the sum of the weights of fillings   $w= w_1 \cdots w_{2n+1}$ of the first $2n+1$ cells of
$T$ where
the elements of $w$ are between 0 and $k-1$ and are  weakly increasing
in each brick and where we weight $w$ by $r^{|w|}$.
Finally,
we interpret $ (x-1)^{2b_{\ell(\mu)}-1}\prod_{j=1}^{\ell(\mu)-1} (x-1)^{b_j-1}$ as all ways of
picking a label
of the even cells of each brick except the final cell
with either an $x$ or a $-1$. For completeness, we label the final
cell of each brick with $1$. We shall call all such objects that can be created in this way
filled labeled brick tabloids and let 
$\mathcal{G}_{2n+2}$ denote the set of all filled labeled brick tabloids.  Thus a $C \in \mathcal{G}_{2n+2}$ consists of
a brick tabloid $T$, a permutation $\sg \in S_{2n+1}$, a sequence
$w \in \{0,\ldots,k-1\}^{2n+1}$, and a labeling $L$ of the even cells of
$T$ with elements from $\{x,1,-1\}$ such that
\begin{enumerate}
\item all the bricks of $T$ have even length,
\item $\sg$ is strictly increasing in each brick and
fills in the first $2n+1$ cells,
\item $w$ is weakly increasing in each brick and
fills in the first $2n+1$ cells,
\item the final cell of each brick is labeled with 1, and
\item each even numbered cell which is not a final cell of a brick
is labeled with x or $-1$.
\end{enumerate}
We then define the weight $w(C)$ of $C$ to be
$q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|}$ times the product of all
the $x$ labels in $L$ and the sign $\sgn(C)$ of $C$ to be
the product of all the $-1$ labels in $L$. For example,
if $n =12$, $k=4$, and $T =(4,6,2)$, then Figure \ref{figure:fill1b}
pictures such a composite object $C \in \mathcal{G}_{12}$ where
$w(C) = q^{20}p^{35}r^{14}x^2$ and $\sgn(C) =-1$.

Thus
\begin{equation}\label{Dg4}
[2n+1]_{p,q}!\theta(p_{2n+2,\nu}) = \sum_{C \in \mathcal{G}_{2n+2}}
\sgn(C) w(C).
\end{equation}



\fig{fill1b}{A composite object $C \in \mathcal{G}_{12}$.}



Next we define a weight preserving sign-reversing involution
$I_2:\mathcal{G}_{2n+2} \rightarrow \mathcal{G}_{2n+2}$.
$I_2$ is essentially the same as $I_1$ of Theorem \ref{thm:Dg}.
That is,  we scan the cells of $C =(T,\sg,w,L)$ from right to left
looking for the leftmost cell $2t$ such that either
(i) $2t$ is labeled
with $-1$ or (ii) $2t$ is at the end a brick $b_j$ and the
brick $b_{j+1}$ immediately following $b_j$ has the property
that the $\sg$ is strictly increasing in all the cells corresponding
to $b_j$ and $b_{j+1}$ and $w$ is weakly  increasing in all the cells corresponding to $b_j$ and $b_{j+1}$.  In case (i),
$I_2(C) =(T',\sg',w',L')$ where $T'$ is the result of  replacing the brick
$b$ in $T$ containing $2t$ by
two bricks $b^*$ and $b^{**}$ where $b^*$ contains
cell $2t$ plus all the cells in $b$ to the left of $2t$ and $b^{**}$ contains
all the cells of $b$ to the right of $2t$, $\sg' =\sg$, $w'= w $, and
$L'$ is the labeling that results from $L$ by changing the label
of cell $2t$ from $-1$ to $1$. In case (ii),
$I_2(C) =(T',\sg',w',L')$ where $T'$ is the result of replacing the bricks
$b_j$ and $b_{j+1}$ in $T$ by a single brick $b,$ $\sg'=\sg $, $w'= w $, and
$L'$ is the labeling that results from $L$ by changing the label
of cell $2t$ from $1$ to $-1$. If neither case (i) or case (ii) applies,
then we let $I_2(C) =C$. For example, if $C$ is the element of
$\mathcal{G}_{12}$ pictured in Figure \ref{figure:fill1b}, then
$I_2(C)$ is pictured in Figure \ref{figure:fill2b}.


\fig{fill2b}{$I_2(C)$ for $C$ in Figure \ref{figure:fill1b}.}

Again, it is easy to see that $I_2$ is a weight-preserving sign-reversing
involution so that
\begin{equation}\label{Dg5}
[2n+1]_{p,q}!\theta(p_{2n+2,\nu}) = \sum_{C \in \mathcal{G}_{2n+2},I_2(C) = C}
\sgn(C) w(C).
\end{equation}

Thus we must examine the fixed points $C = (T,\sg,w,L)$ of $I_2$.
First
there can be no $-1$ labels in $L$ so that $sg(C) =1$. Moreover,  if
$b_j$ and $b_{j+1}$ are two consecutive bricks in $T$ and
$2t$ is that last cell of $b_j$, then it can not be the case
that $\sg_{2t} &lt; \sg_{2t+1}$ and $w_{2t} \leq w_{2t+1}$ since
otherwise we could combine $b_j$ and $b_{j+1}$.
For any such fixed point, we can think of $(\sg,w)$ as an element of 
$C_k \wr S_{2n+1}$. 
It follows that if cell $2t$ is at the end of a brick, then
$2t \not \in \Ris_{\Ev}((\sg,w))$. However
if $2v$ is a cell which is not at the end of brick, then
our definitions force
$\sg_{2v} &lt; \sg_{2v+1}$ and $w_{2v} \leq w_{2v+1}$  so that
$2v \in \Ris_{\Ev}((\sg,w))$. Since each such cell $2v$ must
be labeled with an $x$, it follows that
$\sgn(C)w(C) = q^{\inv(\sg)}p^{\coinv(\sg)}r^{|w|}x^{\ris_{\Ev}((\sg,w))}$.
Moreover our definitions force that $\Odd_{2n-1} \subseteq \Ris((\sg,w))$
so that $(\sg,w) \in (C_k \wr S_{2n+1})^{(2)}$.  Such a fixed 
point is pictured in Figure \ref{figure:fill3b}. Vice versa, if
$(\sg,w) \in (C_k \wr S_{2n+1})^{(2)}$, then we can create a fixed
point $C =(T,\sg,w,L)$ by having the bricks in $T$ end
at cells of the form $2t$ where $2t \not \in \Ris_{\Ev}((\sg,w)$
 and labeling each cell $2t \in \Ris_{\Ev}((\sg,w))$ with $x$ and
labeling all other even numbered cells with $1$.
Thus we have shown that
\begin{equation*}
[2n+1]_{p,q}!\theta(p_{2n+2,\nu}) = \sum_{(\sg,w) \in
(C_k \wr S_{2n+1})^{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|} x^{\ris_{\Ev}((\sg,w))}
\end{equation*}
as desired.

\fig{fill3b}{A fixed point of $I_2$.}

Applying $\theta$ to the identity (\ref{pnuid}), we get
\begin{eqnarray*}
\sum_{n \geq 1} \theta(p_{n,\nu}) t^n &amp;=&amp; \sum_{n\geq 1}
\frac{t^{2n+2}}{[2n+1]_{p,q}!} \sum_{(\sg,w) \in (C_k \wr S_{2n+1})^{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)}r^{|w|} x^{\ris_{\Ev}((\sg,w))} \\
&amp;=&amp; \frac{\sum_{m \geq 1} (-1)^{2m-1} t^{2m} \nu(2m) \theta(e_{2m})}{1+\sum_{n\geq 1} (-t)^n\theta(e_n)} \\
&amp;=&amp; \frac{\sum_{m\geq 1} t^{2m} \frac{p^{\binom{2m-1}{2}}(x-1)^{m-1}}{[2n-1]_{p,q}} \rbinom{2n-1+k-1}{k-1}}{1+\sum_{m\geq 1}(-1)^{2m} t^{2m}
\frac{(-1)^{2m-1}(x-1)^{m-1}p^{\binom{2m}{2}}}{[2m]_{p,q}!}\rbinom{2m+k-1}{k-1}} \\
&amp;=&amp; \frac{-\sum_{m\geq 1} t^{2m} \frac{p^{\binom{2n-1}{2}}(x-1)^{m}}{[2n-1]_{p,q}} \rbinom{2n-1+k-1}{k-1}}{1-x + \sum_{m\geq 1}\frac{p^{\binom{2m}{2}}(x-1)^mt^{2m}}{[2m]_{p,q}!}\binom{2m+k-1}{k-1}}
\end{eqnarray*}
That is, we have shown that
\begin{eqnarray}\label{Dgf}
&amp;&amp;\sum_{n\geq 0} \frac{t^{2n+2}}{[2n+1]_q!} \sum_{(\sg,w) \in (C_k \wr S_{2n+1})^{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)}r^{|w|} x^{\ris_{\Ev}((\sg,w))} = \\
&amp;&amp;\frac{-\sum_{m\geq 1} t^{2m} \frac{p^{\binom{2n-1}{2}}(x-1)^{m}}{[2n-1]_{p,q}} \rbinom{2n-1+k-1}{k-1}}{1-x + \sum_{m\geq 1}\frac{p^{\binom{m}{2}}(x-1)^mt^{2m}}{[2m]_q!}\rbinom{2m+k-1}{k-1}}. \nonumber
\end{eqnarray}
Then dividing both sides of (\ref{Dgf}) by $t$ yields (\ref{eq:Dg}).

\end{proof}


\section{The generating functions for not down-down permutations}

In this section, we shall prove two generating functions
which specialize to the generating functions
$E(t)$ and $F(t)$ described in the introduction. In particular,
we let $(C_k \wr S_n)_{(2)}$ denote the set of all
$(\sg, w) \in C_k \wr S_n$ such that $\Odd_{n-1} \cap
\Des((\sg,w)) = \emptyset$.  We let
\begin{eqnarray}
\NonDes_{\Ev}((\sg,w)) &amp;=&amp; \{2i: 2i \not \in \Des((\sg,w))\} \ \mbox{and} \\
\nondes_{\Ev}((\sg,w)) &amp;=&amp; |\NonDes_{\Ev}((\sg,w))|.
\end{eqnarray}

It is easy to see that the generating functions 
\begin{equation}\label{Eg}
1+ \sum_{n \geq 1} \frac{t^{2n}}{[2n]_{p,q}!}
\sum_{(\sg,w) \in \ (C_k \wr S_{2n})_{(2)}}
q^{\inv(\sg)} p^{\coinv(\sg)} r^{|w|} x^{\nondes_{\Ev}((\sg,w))}.
\end{equation}
and 
\begin{equation}\label{Fg}
\sum_{n \geq 0} \frac{t^{2n+1}}{[2n+1]_{p,q}!}
\sum_{(\sg,w) \in \ (C_k \wr S_{2n+1})_{(2)}}
q^{\inv(\sg)} p^{\coinv(\sg)} r^{|w|} x^{\nondes_{\Ev}((\sg,w))}.
\end{equation}
specialize to $E(t)$ and $F(t)$ respectively when we set 
$x=0$ and $p=q=r=1$. 


Our strategy for finding these  generating functions
is very similar to finding the generating function
(\ref{eq:Cg}) and (\ref{eq:Dg}). That is, if one 
reflects on the proof of Theorem \ref{thm:Cg}, 
the main role of the definition of 
a ring homomorphism
$\theta:\Lambda \rightarrow \mathbb{Q}(p,q,r,x)$ was to 
ensure that $[2n]_{p,q}!\theta(h_{2n})$ could be interpreted 
as the sum of the weights of labeled fillings $(T,L,\sg,w)$ such 
that $(\sg,w)$ was strictly increasing within each brick 
relative to the product  
ordering. Then the combinatorics of the 
involution $I_1$ showed that 
\begin{equation*}
[2n]_{p,q}!\theta(h_{2n}) = \sum_{(\sg,w) \in
(C_k \wr S_{2n})^{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|} x^{\ris_{\Ev}((\sg,w))}
\end{equation*}
from which we could find the generating function 
by applying the ring homomorphism to the identity 
$H(t)= 1/E(-t)$. 
Now suppose that we could define a ring homomorphism
$\Delta:\Lambda \rightarrow \mathbb{Q}(p,q,r,x)$ so 
that $[2n]_{p,q}!\Delta(h_{2n})$ could be interpreted 
as the sum of the weights of labeled fillings $(T,L,\sg,w)$ such 
that $(\sg,w)$ was non-increasing within each brick relative to the product  
ordering. Then it is not difficult to see 
that  we can define an 
analogue of the involution $I_1$ where replace the condition 
that $(\sg,w)$ is strictly increasing in each brick by the condition  
that $(\sg,w)$ is non-increasing in each brick to show that 
\begin{equation}\label{eq:Ekey}
[2n]_{p,q}!\Delta(h_{2n}) = \sum_{(\sg,w) \in
(C_k \wr S_{2n})_{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|}  x^{\nondes_{\Ev}((\sg,w))}
\end{equation}

We shall show at the end of this section that 
\begin{eqnarray}\label{eq:Z}
Z(p,q,r,t) &amp;=&amp; \sum_{n\geq 0} \frac{t^{n}}{[n]_{p,q}!} \sum_{(\sg,w)\in ND_{n,k}} q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|} \\
&amp;=&amp; \frac{1}{1+ \sum_{m\geq 1}\frac{q^{\binom{m}{2}}(-t)^m}{[2m]_{p,q}!}\rbinom{m+k-1}{k-1}} \nonumber
\end{eqnarray}
where $ND_{n,k}$ is the set of permutations $\sg \in C_k \wr S_n$ such 
that $\Des((\sg,w)) = \emptyset$. 
Then clearly
\begin{eqnarray*}
\frac{Z(p,q,r,t) + Z(p,q,r,-t)}{2} &amp;=&amp; 1+\sum_{n\geq 1} \frac{t^{2n}}{[2n]_{p,q}!} \sum_{(\sg,w)\in ND_{2n,k}} q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|} \ \mbox{and}\\
\frac{Z(p,q,r,t) - Z(p,q,r,-t)}{2} &amp;=&amp; \sum_{n\geq 0} \frac{t^{2n+1}}{[2n+1]_{p,q}!} \sum_{(\sg,w)\in ND_{2n+1,k}} q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|}.
\end{eqnarray*}
Hence for all $n \geq 1$,
\begin{eqnarray}
\frac{Z(p^2,qp,r,t) + Z(p^2,qp,r,-t)}{2}|_{\frac{t^{2n}}{[2n]_{p,q}!}}
&amp;=&amp; \sum_{(\sg,w)\in ND_{2n,k}} (pq)^{\inv(\sg)}(p^2)^{\coinv(\sg)} r^{|w|}
\nonumber \\
&amp;=&amp; p^{\binom{2n}{2}}\sum_{(\sg,w)\in ND_{2n,k}} q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|}
\end{eqnarray}
since for all $\sg \in S_{2n}$, $\inv(\sg)+\coinv(\sg) = \binom{2n}{2}$.
Similarly,
\begin{eqnarray}
\frac{Z(p^2,qp,r,t) - Z(p^2,qp,r,-t)}{2}|_{\frac{t^{2n+1}}{[2n+1]_{p,q}!}}
&amp;=&amp; \sum_{(\sg,w)\in ND_{2n+1,k}} (pq)^{\inv(\sg)}
(p^2)^{\coinv(\sg)} r^{|w|}
\nonumber \\
&amp;=&amp; p^{\binom{2n+1}{2}}\sum_{(\sg,w)\in ND_{2n+1,k}} q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|}
\end{eqnarray}
since for all $\sg \in S_{2n+1}$, $\inv(\sg)+\coinv(\sg) = \binom{2n+1}{2}$.


We define our desired ring homomorphism 
$\Delta:\Lambda \rightarrow \mathbb{Q}(p,q,r,x)$ by setting
\begin{eqnarray}
\Delta(e_{2n}) &amp;=&amp; \frac{(-1)^{2n-1}(x-1)^{n-1}}{[2n]_{p,q}!}
\left(\frac{Z(p^2,pq,r,t) + Z(p^2,pq,r,-t)}{2}|_{\frac{t^{2n}}{[2n]_{p,q}!}}\right) \nonumber \\
&amp;=&amp; \frac{(-1)^{2n-1}(x-1)^{n-1}}{[2n]_{p,q}!}p^{\binom{2m}{2}}
\sum_{(\sg,w) \in ND_{2n,k}} q^{\inv(\sg)}p^{\coinv(\sg)}r^{|w|}.
\end{eqnarray}
if $n \geq 1$ and
\begin{equation}
\Delta(e_{2n+1}) = 0
\end{equation}
if $n \geq 0$.
Again it is easy to see that
\begin{equation}\label{Eg0}
\Delta(h_{2n+1}) = 0
\end{equation}
 for all $n \geq 0$.
Now 
\begin{eqnarray}\label{Eg3}
&amp;&amp;\ [2n]_{p,q}!\Delta(h_{2n})  \\
&amp;&amp; \ = [2n]_{p,q}! \sum_{\mu\vdash n} (-1)^{2n-\ell(\mu)}B_{2\mu, (2n)}
\Delta(e_{2\mu}) \nonumber \\
&amp;&amp; \ = [2n]_{p,q}! \sum_{\mu \vdash n} (-1)^{2n-\ell(\mu)}
\sum_{(2b_1, \ldots, 2b_{\ell(\mu)}) \in \mathcal{B}_{2\mu,(2n)}}
\prod_{j=1}^{\ell(\mu)} \frac{(-1)^{2b_j-1}(x-1)^{b_j-1}}{[2b_j]_{p,q}!} \times \nonumber \\
&amp;&amp; \ \ \ \ \ \ \ \ \
\left(\frac{Z(p^2,pq,r,t) + Z(p^2,pq,r,-t)}{2}|_{\frac{t^{2b_j}}{[2b_j]_{p,q}!}}\right) \nonumber \\
&amp;&amp; \ = \sum_{\mu \vdash n} \sum_{(2b_1, \ldots, 2b_{\ell(\mu)}) \in \mathcal{B}_{2\mu,(2n)}} p^{\sum_{j=1}^{\ell(\mu)} p^{\binom{2b_j}{2}}}
\pqbinom{2n}{2b_1,\ldots,2b_{\ell(\mu)}}
\prod_{j=1}^{\ell(\mu)} (x-1)^{b_j-1} \times \nonumber \\
&amp;&amp; \ \ \ \ \ \ \ \ \ \prod_{j=1}^{\ell(\mu)} \left( \sum_{(\sg,w) \in ND_{2b_j,k}} q^{\inv(\sg)} p^{\coinv(\sg)}r^{|w|}
\right). \nonumber
\end{eqnarray}

Next we want to give a combinatorial interpretation to (\ref{Eg3}).
By Lemma \ref{Carlitz}, for each brick tabloid
$T= (2b_1, \ldots, 2b_{\ell(\mu)})$, we can interpret
$p^{\sum_{j=1}^{\ell(\mu)} \binom{2b_j}{2}}
\pqbinom{2n}{2b_1,\ldots,2b_{\ell(\mu)}}$ as the sum of the weights of fillings of $T$ with
a permutation $\tau \in S_{2n}$ such that $\tau$ is increasing in each brick
and we weight $\tau$ with $q^{\inv(\tau)}p^{\coinv(\tau)}$.  Next
the product
$$\prod_{j=1}^{\ell(\mu)}
\sum_{(\sg,w) \in ND_{2b_j,k}} q^{\inv(\sg)}p^{\coinv(\sg)}r^{|w|}$$
can be interpreted as all ways to pick a permutation $(\sg^{(j)},w^{(j)}) \in
C_k \wr S_{2b_i}$ for each brick $2b_j$ in $T$ such that
$\Des(\sg^{(j)},w^{(j)})) = \emptyset$ with weight
$q^{\inv(\sg^{(j)},w^{(j)})}p^{\coinv(\sg^{(j)},w^{(j)}))}
r^{|w^{(j)}|}$.  For example, Figure
\ref{figure:fill1E} pictures such a choice for
$\sg$ and choices for $(\sg^{(1)},w^{(2)}), (\sg^{(2)},w^{(2)}),
(\sg^{(3)},w^{(3)})$ for the brick tabloid $T = (4,6,2)$. Here
we have written the $(\sg^{(j)},w^{(j)})$'s in two line arrays as
we did in the previous proofs, namely, the bottom line of
the array gives $\sg^{(j)}$ and the top line of the array gives $w^{(j)}$.  
We can then combine these
two diagrams into single diagram which is pictured at the bottom
of Figure \ref{figure:fill1E} by rearranging the elements of $\sg$
in each brick $b_j$ according to the permutation $\sg^{(j)}$ and
bringing down the top sequence  $w^{(j)}$ to be the top sequence
in each brick.  The result is a pair
$(\sg,w)$ such that $(\sg,w)$ has no descents that occur between 
two cells in the same brick 
and where we weight the pair $(\sg,w)$ by
$q^{\inv(\sg)}p^{\coinv(\sg)}r^{|w|}$.
Finally,
we interpret $\prod_{j=1}^{\ell(\mu)} (x-1)^{b_j-1}$ as all ways of picking a label
of the even cells of each brick except the final cell
with either an $x$ or a $-1$. For completeness, we label the final
cell of each brick with $1$. We shall call such objects
filled labeled brick tabloids and we let
$\mathcal{K}_{2n}$ denote the set of all filled labeled brick tabloids
that arise in this way.  Thus a $C \in \mathcal{K}_{2n}$ consists of
a brick tabloid $T$, a permutation $\sg \in S_{2n}$, a sequence
$w \in \{0,\ldots,k-1\}^{2n}$, and a labeling $L$  of the even cells of
$T$ with elements from $\{x,1,-1\}$ such that 
\begin{enumerate}
\item all the bricks of $T$ have even length,
\item if $i \in \Des((\sg,w))$, then $i$ must be the final
cell of some brick,
\item the final cell of each brick is labeled with 1, and
\item each even numbered cell which is not a final cell of a brick
is labeled with x or $-1$.
\end{enumerate}
We then define the weight $w(C)$ of $C$ to be
$q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|}$ times the product of all
the $x$ labels in $L$ and the sign $\sgn(C)$ of $C$ to be
the product of all the $-1$ labels in $L$. For example,
if $n =12$, $k=4$, and $T =(4,6,2)$, then the composite object
$C$ pictured at the bottom of Figure \ref{figure:fill1E}
is an element of $\mathcal{K}_{12}$ where
$w(C) = q^{33}p^{33}r^{15}x^2$ and $\sgn(C) =-1$.

Thus
\begin{equation}\label{Eg4}
[2n]_{p,q}!\Delta(h_{2n}) = \sum_{C \in \mathcal{K}_{2n}}
\sgn(C) w(C).
\end{equation}

\fig{fill1E}{A composite object $C \in \mathcal{K}_{12}$.}


At this point, we can follow the analogous steps in 
Theorem \ref{thm:Cg} to prove that 
\begin{equation*}
[2n]_{p,q}!\Delta(h_{2n}) = \sum_{(\sg,w) \in
(C_k \wr S_{2n})_{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|}  x^{\nondes_{\Ev}((\sg,w))}.
\end{equation*}

Applying $\Delta$ to the identity $H(t) = (E(-t))^{-1}$, we get
\begin{eqnarray*}
\sum_{n \geq 0} \Delta(h_n) t^n &amp;=&amp; \sum_{n\geq 0} \frac{t^{2n}}{[2n]_{p,q}!} \sum_{(\sg,\ep)\in \ (C_k\wr S_{2n})_{(2)}} q^{\inv(\sg)}p^{\coinv(\sg)}
r^{|\ep|}x^{\nondes_{\Ev}(\sg,\ep)} \\
&amp;=&amp; \frac{1}{1+\sum_{n\geq 1} (-t)^n\Delta(e_n)} \\
&amp;=&amp; \frac{1}{1+\sum_{m\geq 1}(-1)^{2m} t^{2m}
\frac{(-1)^{2m-1}(x-1)^{m-1}}{[2m]_{p,q}!}
\left(\frac{Z(p^2,pq,r,t) +Z(p^2,pq,r,-t)}{2}|_{\frac{t^{2m}}{[2m]_{p,q}!}}\right)} \\
&amp;=&amp;
\frac{1-x}{1-x + \sum_{m\geq 1}\frac{((x-1)^{1/2}t)^{2m}}{[2m]_{p,q}!}
\left(\frac{Z(p^2,pq,r,t) +Z(p^2,pq,r,-t)}{2}|_{\frac{t^{2m}}{[2m]_{p,q}!}}\right)}
\\
&amp;=&amp; \frac{1-x}{-x+ \frac{Z(p^2,pq,r,(x-1)^{1/2}t) +Z(p^2,pq,r,-(x-1)^{1/2}t)}{2}}.
\end{eqnarray*}

Thus we have proved the following. 

\begin{theorem}\label{thm:Eg} For all $k \geq 2$, 
\begin{eqnarray}\label{eq:Eg}
&amp;&amp;1+ \sum_{n \geq 1} \frac{t^{2n}}{[2n]_{p,q}!} \sum_{(\sg,w) \in
(C_k \wr S_{2n})_{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|} x^{\nondes_{\Ev}((\sg,w))}
= \nonumber \\
&amp;&amp;\frac{1-x}{-x + \frac{Z(p^2,qp,r,(x-1)^{1/2}t) + Z(p^2,qp,r,-(x-1)^{1/2}t)}{2}}.
\end{eqnarray}
\end{theorem}

Note that setting $x=0$ and $p=q=r=1$ in (\ref{eq:Eg}) and using
Corollary \ref{cor:NDg}, we obtain
that
\begin{eqnarray*}
\sum_{n \geq 0} \frac{\ndd_{2n,k} t^{2n}}{(2n)!} &amp;=&amp;
\frac{1}{\frac{Z(1,1,1,it) + Z(1,1,1,-it)}{2}} \\
&amp;=&amp; \frac{1}{\frac{1}{2}\left(\frac{1}{\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1} e^{-it}} + \frac{1}{\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1} e^{it}}\right)} \\
&amp;=&amp; \frac{(\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1} e^{-it})
(\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1} e^{it})}{\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1} \left( \frac{e^{-it} +
e^{it}}{2}\right)}\\
&amp;=&amp; \frac{(\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1} e^{-it})(\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1} e^{it})}{\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1} \cos t}.
\end{eqnarray*}
Let
\begin{equation}
P_{k-1}(t) = \frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1} e^{it}
\end{equation}
for $k \geq 2$.
Observe that if $D = \frac{\dd}{\dd t}$ is the ordinary differential
operator, then
\begin{equation}
D^n(f(t) \cdot g(t)) = \sum_{k=0}^n \binom{n}{k} D^k(f(t)) D^{n-k}(g(t)).
\end{equation}
Hence in the special case where $f(t) = e^{it}$ and $g(t) = t^n$, we
have that
\begin{eqnarray*}
P_n(t) &amp;=&amp; \sum_{k=0}^n \binom{n}{k} i^k e^{it} (n)\downarrow_{n-k} t^k \\
&amp;=&amp; e^{it} \sum_{k=0}^n \binom{n}{k}^2 (n-k)! i^k t^k
\end{eqnarray*}
where $(n)\downarrow_0 =1$ and $(n)\downarrow_s =n(n-1) \cdots (n-s+1)$ for
$s \geq 1$.
It follows that
\begin{eqnarray*}
P_n(it)P_n(-it) &amp;=&amp; \sum_{s=0}^{2n} t^s \sum_{r=0}^s
\binom{n}{r}^2 (n-r)! i^r
\binom{n}{s-r}^2 (n-(s-r))! (-i)^{s-r}  \\
&amp;=&amp; \sum_{s=0}^{2n}(i)^s t^s \sum_{r=0}^s (-1)^{s-r}
\binom{n}{r}^2 (n-r)!  \binom{n}{s-r}^2 (n-(s-r))!.
\end{eqnarray*}
Note that when
$s$ is odd, then term
$$\sum_{r=0}^s (-1)^{s-r}
\binom{n}{r}^2 (n-r)!   \binom{n}{s-r}^2 (n-(s-r))! = 0
$$
since the r-th term in the sum is the negative of $(s-r)$-th term in
the sum.
Thus
\begin{equation}\label{hyper1}
P_n(it)P_n(-it) = \sum_{s=0}^{n} t^{2s} \sum_{r=0}^{2s} (-1)^{s-r}
\binom{n}{r}^2 (n-r)!
\binom{n}{2s-r}^2 (n-(2s-r))!.
\end{equation}
We can rewrite the sum 
$$\sum_{r=0}^{2s} (-1)^{s-r}
\binom{n}{r}^2 (n-r)!  \binom{n}{s-r}^2 (n-(s-r))!$$ 
as a hypergeometric 
series. That is, we can rewrite this sum 
in terms of rising factorials $(a)_n$ where 
$(a)_0 =1$ and $(a)_n = a(a+1) \cdots (a+n-1)$ for $n \geq 1$ to obtain that 
\begin{eqnarray}\label{hyper2}
&amp;&amp;\sum_{r=0}^{2s} (-1)^{s-r}
\binom{n}{r}^2 (n-r)!  \binom{n}{s-r}^2 (n-(s-r))! = \nonumber \\
&amp;&amp;\frac{(-1)^s n!n! (-n)_{2s}}{(2s)!(2s)!} 
\sum_{r=0}^{2s} \frac{(-n)_r (-2s)_r (-2s)_r}{(n-2s+1)_r(1)_r}\frac{1}{r!} 
=\nonumber \\
&amp;&amp; \frac{(-1)^s n!n! (-n)_{2s}}{(2s)!(2s)!}\  _3F_2(-n,-2s,-2s;n-2s+1,1;1).
\end{eqnarray}
This is a special case of the following hypergeometric series 
identity found in \cite{PWZ}:
\begin{equation}\label{hyper3}
_3F_2(b,c,-2n;1-b-2n,1-c-2n;1) = \frac{(2n)! (b)_n (c)_n (b+c)_{2n}}{n! (b)_{2n}(c)_{2n} (b+c)_n}.
\end{equation}
Using (\ref{hyper3}), we see that (\ref{hyper2}) is equal to 
\begin{eqnarray*}
&amp;&amp;\frac{(-1)^s n!n! (-n)_{2s}}{(2s)!(2s)!}\frac{(2s)! (-n)_s (-2s)_s (-n-2s)_{2s}}{s! (-n)_{2s}(-2s)_{2s} (-n-2s)_s} = \\
&amp;&amp;\frac{(-1)^s n!n!}{(2s)!}\frac{(-1)^s n\downarrow_s (-1)^s (2s)\downarrow_s 
(-1)^{2s} (n+2s)\downarrow_{2s}}{s! (-1)^{2s} (2s)! (-1)^s (n+2s)\downarrow_s} 
= \\
&amp;&amp; \frac{(n!)^2}{(2s)!} \binom{n}{s} \binom{n+s}{s}
\end{eqnarray*}
where $a\downarrow_0 =1$ and $a\downarrow_n = a(a-1) \cdots (a-n+1)$ for 
$n \geq 1$. Hence
\begin{equation}\label{hyper4}
P_n(it)P_n(-it) = \sum_{s=0}^{n}  \frac{(n!)^2}{(2s)!} \binom{n}{s} \binom{n+s}{s} t^{2s}.
\end{equation}


 


Thus we have the following corollary.

\begin{corollary}\label{cor:Eg} For $k \geq 2$,
\begin{equation}
1+\sum_{n\geq 1} \frac{\ndd_{2n,k}t^{2n}}{(2n)!} =
\frac{\sum_{s=0}^{k-1}  \frac{((k-1)!)^2}{(2s)!} \binom{k-1}{s} \binom{k-1+s}{s} t^{2s}}{\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1} \cos t}.
\end{equation}
\end{corollary}



We can also prove an analogue of Theorem \ref{thm:Dg}.  That is, suppose 
that we define 
\begin{eqnarray}
\nu(2n) &amp;=&amp; \frac{1}{\Delta(e_{2n})}\frac{(-1)^{2n-1}(x-1)^{n-1}}{[2n-1]_{p,q}!} \left(\frac{Z(p^2,pq,r,t)+Z(p^2,pq,r,-t)}{2}|_{\frac{t^{2n-1}}{[2n-1]_{p,q}!}}
\right) \nonumber \\
&amp;=&amp; \frac{1}{\Delta(e_{2n})}\frac{(-1)^{2n-1}p^{\binom{2n-1}{2}}(x-1)^{n-1}}{[2n-1]_{p,q}!}\sum_{(\sg,w) \in ND_{2n-1,k}}q^{\inv(\sg,w)}p^{\coinv(\sg,w)}
r^{|w|}
\end{eqnarray}
for $n \geq 1$ and $\nu(2m+1) =0$ for $m \geq 0$. In this case we 
have defined $\nu$ so that
\begin{eqnarray}\label{nuDelta}
\nu(2n) \Delta(e_{2n}) &amp;=&amp;
\frac{(-1)^{2n-1}(x-1)^{n-1}}{[2n-1]_{p,q}!}
\left(\frac{Z(p^2,pq,r,t)-Z(p^2,pq,r,-t)}{2}|_{t^{2n-1}{[2n-1]_{p,q}!}}\right)
\nonumber \\
&amp;=&amp; \frac{(-1)^{2n-1}p^{\binom{2n-1}{2}}(x-1)^{n-1}}{[2n-1]_{p,q}!}\sum_{(\sg,w) \in ND_{2n-1,k}}q^{\inv(\sg,w)}p^{\coinv(\sg,w)}
r^{|w|}.
\end{eqnarray}

We can then follow the same sequence of steps as in the proof of 
Theorem \ref{thm:Dg} to prove that 

\begin{equation*}
[2n+1]_{p,q}!\Delta(p_{2n+2,\nu}) = \sum_{(\sg,w) \in
(C_k \wr S_{2n+1})_{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|} x^{\nondes_{\Ev}((\sg,w))}.
\end{equation*}





Applying $\Delta$ to the identity (\ref{pnuid}), we get
\begin{eqnarray*}
\sum_{n \geq 1} \Delta(p_{n,\nu}) t^n &amp;=&amp; \sum_{n\geq 1}
\frac{t^{2n+2}}{[2n+1]_{p,q}!} \sum_{(\sg,w) \in (C_k \wr S_{2n+1})_{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)}r^{|w|} x^{\nondes_{\Ev}((\sg,w))} \\
&amp;=&amp; \frac{\sum_{m \geq 1} (-1)^{2m-1} t^{2m} \nu(2m) \Delta(e_{2m})}{1+\sum_{n\geq 1} (-t)^n\Delta(e_n)} \\
&amp;=&amp; \frac{\sum_{m\geq 1} (-1)^{2m-1}t^{2m}
\frac{(-1)^{2m-1}(x-1)^{m-1}}{[2m-1]_{p,q}!}
\left(\frac{Z(p^2,pq,r,t)-Z(p^2,pq,r,-t)}{2}|_{t^{2m-1}{[2m-1]_{p,q}!}}\right)}{1+\sum_{m \geq 1} (-1)^{2m}t^{2m} \frac{(-1)^{2m-1}(x-1)^{m-1}}{[2m]_{p,q}!}
\left(\frac{Z(p^2,pq,r,t)+Z(p^2,pq,r,-t)}{2}|_{t^{2m}{[2m]_{p,q}!}}\right)}\\
&amp;=&amp; \frac{-t(x-1)^{1/2}\sum_{m\geq 1}
\frac{((x-1)^{1/2}t)^{2m-1} }{[2m-1]_{p,q}!}
\left(\frac{Z(p^2,pq,r,t)-Z(p^2,pq,r,-t)}{2}|_{t^{2m-1}{[2m-1]_{p,q}!}}\right)}{1+\sum_{m \geq 1} (t^{2m} \frac{((x-1)^{1/2}t)^{2m}}{[2m]_{p,q}!}
\left(\frac{Z(p^2,pq,r,t)+Z(p^2,pq,r,-t)}{2}|_{t^{2m}{[2m]_{p,q}!}}\right)}\\
&amp;=&amp; \frac{-t(x-1)^{1/2}(\frac{Z(p^2,pq,r,t)-Z(p^2,pq,r,-t)}{2})}{-x+\frac{Z(p^2,pq,r,t)+Z(p^2,pq,r,-t)}{2}}\\
&amp;=&amp;\frac{-t(x-1)^{1/2}(Z(p^2,pq,r,t)-Z(p^2,pq,r,-t))}{-2x+Z(p^2,pq,r,t)+Z(p^2,pq,r,-t)}.
\end{eqnarray*}
That is, we have shown that
\begin{eqnarray}\label{Fgf}
&amp;&amp;\sum_{n\geq 0} \frac{t^{2n+2}}{[2n+1]_q!} \sum_{(\sg,w) \in (C_k \wr S_{2n+1})_{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)}r^{|w|} x^{\ris_{\Ev}((\sg,w))} \\
&amp;&amp; = \frac{-t(x-1)^{1/2}(Z(p^2,pq,r,t)-Z(p^2,pq,r,-t))}{-2x+Z(p^2,pq,r,t)+Z(p^2,pq,r,-t)} \nonumber
\end{eqnarray}
Then dividing both sides of (\ref{Fgf}) by $t$ yields the following 
result.




\begin{theorem}\label{thm:Fg} For all $k \geq 2$, 
\begin{eqnarray}\label{eq:Fg}
&amp;&amp;\sum_{n\geq 0}\frac{t^{2n+1}}{[2n+1]_{p,q}!}\sum_{(\sg,w) \in
(C_k \wr S_{2n+1})_{(2)}}
q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|} x^{\nondes_{\Ev}((\sg,w))} = \nonumber \\
&amp;&amp;\frac{-(x-1)^{1/2}\left(Z(p^2,pq,r,(x-1)^{1/2}t)-Z(p^2,pq,r,-(x-1)^{1/2}t)\right)}{-2x + Z(p^2,pq,r,(x-1)^{1/2}t)+Z(p^2,pq,r,-(x-1)^{1/2}t)}
\end{eqnarray}
\end{theorem}

Note that when we set $x=0$ and $p=q =r =1$, then (\ref{eq:Fg}) reduces
to
\begin{eqnarray*}
\sum_{n\geq 0}\frac{\ndd_{2n+1,k} t^{2n+1}}{(2n+1)!} &amp;=&amp;
\frac{-i(Z(1,1,1,it)-Z(1,1,1,-it))}{Z(1,1,1,it)+Z(1,1,1,-it))} \nonumber \\
&amp;=&amp; \frac{-i\left(\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1} e^{-it}-\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1} e^{it}\right)}{\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1} e^{-it}+\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1} e^{it}}\\
&amp;=&amp; \frac{-i\frac{\dd^{k-1}}{\dd t^{k-1}}(e^{it} -e^{-it})}
{\frac{\dd^{k-1}}{\dd t^{k-1}}(e^{it} +e^{-it})}\\
&amp;=&amp; \frac{\frac{\dd^{k-1}}{\dd t^{k-1}} \sin t}{\frac{\dd^{k-1}}{\dd t^{k-1}} \cos t}.
\end{eqnarray*}
which is the generating function of $F(t)$ claimed in the introduction.

We note that the generating functions of 
Theorems \ref{thm:Dg} and \ref{thm:Fg} are two different generating 
functions that can be specialized to 
$$\frac{\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1}\sin t}{\frac{\dd^{k-1}}{\dd t^{k-1}}t^{k-1}\cos t}.$$


We end this section by proving a result which specializes to (\ref{eq:Z}).  


\begin{theorem}\label{thm:NDg} For all $k \geq 2$, 
\begin{eqnarray}\label{eq:NDg}
&amp;&amp;1+ \sum_{n \geq 1} \frac{t^n}{[n]_{p,q}!}
\sum_{(\sg,w) \in C_k \wr S_{n}} q^{\inv(\sg)} p^{\coinv(\sg)}
r^{|w|} x^{des((\sg,w))} = \nonumber \\
&amp;&amp;\frac{1-x}{1-x + \sum_{n \geq 1}
\frac{q^{\binom{n}{2}}((x-1)t)^n}{[n]_{p,q}!} \rbinom{n+k-1}{k-1}}.
\end{eqnarray}
\end{theorem}

\begin{proof}
Define a ring homomorphism
$\Gamma:\Lambda \rightarrow \mathbb{Q}(p,q,r,x)$ by setting
\begin{equation}
\Gamma(e_n) = (-1)^{n-1}(x-1)^{n-1}\frac{\rbinom{n+k-1}{k-1}}{[n]_{p,q}!}
q^{\binom{n}{2}}.
\end{equation}
Then we claim that
\begin{equation}\label{NDg1}
[n]_{p,q}!\Gamma(h_n) = \sum_{(\sg,w) \in
C_k \wr S_{n}}
q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|} x^{des((\sg,w))}
\end{equation}
for all $n \geq 1$.
That is,
\begin{eqnarray}\label{NDg3}
&amp;&amp;\ [n]_{p,q}!\Gamma(h_{n})  \\
&amp;&amp; \ = [n]_{p,q}! \sum_{\mu\vdash n} (-1)^{n-\ell(\mu)}B_{\mu, (n)}\Gamma(e_{\mu}) \nonumber \\
&amp;&amp; \ = [n]_{p,q}! \sum_{\mu \vdash n} (-1)^{n-\ell(\mu)}
\sum_{(b_1, \ldots, b_{\ell(\mu)}) \in \mathcal{B}_{\mu,(n)}}
\prod_{j=1}^{\ell(\mu)} (-1)^{b_j-1}(x-1)^{b_j-1}
\frac{\rbinom{b_j+k-1}{k-1}}{[b_j]_{p,q}!} q^{\binom{b_j}{2}} \nonumber \\
&amp;&amp; \ = \sum_{\mu \vdash n} \sum_{(2b_1, \ldots, 2b_{\ell(\mu)}) \in \mathcal{B}_{2\mu,(2n)}} q^{\sum_{j=1}^{\ell(\mu)} \binom{b_j}{2}}\pqbinom{n}{b_1,\ldots,b_{\ell(\mu)}} \prod_{j=1}^{\ell(\mu)} (x-1)^{b_j-1}
\rbinom{b_j+k-1}{k-1}. \nonumber 
\end{eqnarray}

Next we want to give a combinatorial interpretation to (\ref{NDg3}).
By Lemma \ref{Carlitz2} for each brick tabloid
$T= (b_1, \ldots, b_{\ell(\mu)})$, we can interpret
$q^{\sum_{j=1}^{\ell(\mu)} \binom{b_j}{2}}
\pqbinom{n}{b_1,\ldots,b_{\ell(\mu)}}$ as the sum of the weights of all fillings of $T$ with
a permutation $\sg \in S_{n}$ such that $\sg$ is decreasing in each brick
and we weight $\sg$ with $q^{\inv(\sg)}p^{\coinv(\sg)}$.  By Lemma
\ref{Carlitz3},
we can interpret the term $\prod_{j=1}^{\ell(\mu)}\rbinom{b_j+k-1}{k-1}$ as
the sum of the weights of  fillings  $w= w_1 \cdots w_{n}$ where
the elements of $w$ are between 0 and $k-1$ and are weakly decreasing
in each brick and where we weight $w$ by $r^{|w|}$.  Finally,
we interpret $\prod_{j=1}^{\ell(\mu)} (x-1)^{b_j-1}$ as all ways of picking a label
of the cells of each brick except the final cell
with either an $x$ or a $-1$. For completeness, we label the final
cell of each brick with $1$. We shall call all such objects created in this way
filled labeled brick tabloids and let 
$\mathcal{H}_{n}$ denote the set of all filled labeled brick tabloids
that arise in this way.  Thus a $C \in \mathcal{H}_{n}$ consists of
a brick tabloid $T$, a permutation $\sg \in S_{n}$, a sequence
$w \in \{0,\ldots,k-1\}^{n}$, and a labeling $L$ of the cells of
$T$ with elements from $\{x,1,-1\}$ such that
\begin{enumerate}
\item $\sg$ is strictly decreasing in each brick,
\item $w$ is weakly decreasing in each brick,
\item the final cell of each brick is labeled with 1, and
\item each cell which is not a final cell of a brick
is labeled with x or $-1$.
\end{enumerate}
We then define the weight $w(C)$ of $C$ to be
$q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|}$ times the product of all
the $x$ labels in $L$ and the sign $\sgn(C)$ of $C$ to be
the product of all the $-1$ labels in $L$. For example,
if $n =12$, $k=4$, and $T =(4,3,3,2)$, then Figure \ref{figure:fill1n}
pictures such a composite object $C \in \mathcal{H}_{12}$ where
$w(C) = q^{35}p^{31}r^{17}x^5$ and $\sgn(C) =-1$.

Thus
\begin{equation}\label{NDg4}
[n]_{p,q}!\Gamma(h_{n}) = \sum_{C \in \mathcal{H}_{n}}
\sgn(C) w(C).
\end{equation}



\fig{fill1n}{A composite object $C \in \mathcal{H}_{12}$.}



Next we define a weight preserving sign-reversing involution
$I_3:\mathcal{H}_{n} \rightarrow \mathcal{H}_{n}$.  To define
$I_3(C)$, we scan the cells of $C =(T,\sg,s,L)$ from right to left
looking for the leftmost cell $t$ such that either
(i) $t$ is labeled
with $-1$ or (ii) $t$ is at the end a brick $b_j$ and the
brick $b_{j+1}$ immediately following $b_j$ has the property
that the $\sg$ is strictly decreasing in all the cells corresponding
to $b_j$ and $b_{j+1}$ and $w$ is weakly  decreasing in all the cells corresponding to $b_j$ and $b_{j+1}$.  In case (i),
$I_3(C) =(T',\sg',w',L')$ where $T'$ is the result of  replacing the brick
$b$ in $T$ containing $t$ by
two bricks $b^*$ and $b^{**}$ where $b^*$ contains the
cell $t$ plus all the cells in $b$ to the left of $t$ and $b^{**}$ contains
all the cells of $b$ to the right of $t$, $\sg' =\sg$, $w' = w$, and
$L'$ is the labeling that results from $L$ by changing the label
of cell $t$ from $-1$ to $1$. In case (ii),
$I_3(C) =(T',\sg',w',L')$ where $T'$ is the result of replacing the bricks
$b_j$ and $b_{j+1}$ in $T$ by a single brick $b,$ $\sg' =\sg$, $w' = w$, and
$L'$ is the labeling that results from $L$ by changing the label
of cell $t$ from $1$ to $-1$. If neither case (i) or case (ii) applies,
then we let $I_3(C) =C$. For example, if $C$ is the element of
$\mathcal{H}_{12}$ pictured in Figure \ref{figure:fill1n}, then
$I_3(C)$ is pictured in Figure \ref{figure:fill2n}.


\fig{fill2n}{$I_3(C)$ for $C$ in Figure \ref{figure:fill1n}.}

It is easy to see that $I_3$ is a weight-preserving sign-reversing
involution and hence $I_3$ shows that
\begin{equation}\label{NDg5}
[n]_{p,q}!\Gamma(h_n) = \sum_{C \in \mathcal{H}_{n},I_3(C) = C}
\sgn(C) w(C).
\end{equation}

Thus we must examine the fixed points $C = (T,\sg,w,L)$ of $I_3$.
First
there can be no $-1$ labels in $L$ so that $sg(C) =1$. Moreover,  if
$b_j$ and $b_{j+1}$ are two consecutive bricks in $T$ and
$t$ is that last cell of $b_j$, then it can not be the case
that $\sg_{t} &gt; \sg_{t+1}$ and $w_t \geq w_{t+1}$ since
otherwise we could combine $b_j$ and $b_{j+1}$. 
For any such fixed point, we can think of $(\sg,w)$ as an 
element of  $C_k \wr S_{n}$. Such a fixed point is pictured 
in \ref{figure:fill3n}. 
It follows that if cell $t$ is at the end of a brick, then
$t \not \in \Des((\sg,w))$. However
if $v$ is a cell which is not at the end of brick, then
our definitions force
$\sg_{v} &gt; \sg_{v+1}$ and $w_v \geq w_{v+1}$  so that
$v \in \Des((\sg,w))$. Since each such cell $v$ must
be labeled with an $x$, it follows that
$\sgn(C)w(C) = q^{\inv(\sg)}p^{\coinv(\sg)}r^{|w|}x^{des((\sg,w))}$.
  Vice versa, if
$(\sg,w) \in C_k \wr S_{n}$, then we can create a fixed
point $C =(T,\sg,w,L)$ by having the bricks in $T$ end
as cells of the form $t$ where $t \not \in \Des((\sg,w)$, labeling each cell $t \in \Des((\sg,w))$ with $x$, and
labeling the remaining cells with $1$.
Thus we have shown that
\begin{equation*}
[n]_{p,q}!\Gamma(h_n) = \sum_{(\sg,w) \in C_k \wr S_{2n}}
q^{\inv(\sg)}p^{\coinv(\sg)} r^{|w|} x^{des((\sg,w))}
\end{equation*}
as desired.

\fig{fill3n}{A fixed point of $I_3$.}

Applying $\Gamma$ to the identity $H(t) = (E(-t))^{-1}$, we obtain 
\begin{eqnarray*}
\sum_{n \geq 0} \Gamma(h_n) t^n &amp;=&amp; \sum_{n\geq 0} \frac{t^{n}}{[n]_{p,q}!} \sum_{(\sg,w)\in C_k\wr S_{n}} q^{\inv(\sg)}p^{\coinv(\sg)}
r^{|w|}x^{des(\sg,w)} \\
&amp;=&amp; \frac{1}{1+\sum_{n\geq 1} (-t)^n\Gamma(e_n)} \\
&amp;=&amp; \frac{1}{1+\sum_{m\geq 1}(-1)^{m} t^{m}
\frac{(-1)^{m-1}(x-1)^{m-1}q^{\binom{m}{2}}}{[m]_{p,q}!}\rbinom{m+k-1}{k-1}} \\
&amp;=&amp;
\frac{1-x}{1-x + \sum_{m\geq 1}\frac{q^{\binom{m}{2}}(x-1)^mt^{m}}{[m]_{p,q}!}\rbinom{m+k-1}{k-1}}
\end{eqnarray*}
which proves (\ref{eq:NDg}).
\end{proof}

Observe that if we set $x =0$ in (\ref{eq:NDg}), we obtain 
(\ref{eq:Z}) as desired. Moreover, if we set 
$x =0$ and $r=1$ in (\ref{eq:NDg}), then we obtain that 
\begin{eqnarray*}
&amp;&amp;1+ \sum_{n \geq 1} \frac{t^n}{[n]_{p,q}!}
\sum_{(\sg,w) \in ND_{n,k}} q^{\inv(\sg)} p^{\coinv(\sg)}  = \\
&amp;&amp;\frac{1}{1 + \sum_{n \geq 1} \frac{q^{\binom{n}{2}}(-t)^n}{[n]_{p,q}!}
\frac{(n+k-1)(n+k-2) \cdots (n+1)}{(k-1)!}} = \\
&amp;&amp;\frac{(k-1)!}{(k-1)! + \sum_{n \geq 1}
\frac{q^{\binom{n}{2}}(-t)^n}{[n]_{p,q}!}
(n+k-1)(n+k-2) \cdots (n+1)} = \\
&amp;&amp; \frac{(k-1)!}{\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1}e_{p,q}(-t)}.
\end{eqnarray*}

Thus we have the following corollary.
\begin{corollary}\label{cor:NDg} For all $k \geq 2$,
\begin{equation}
1+ \sum_{n \geq 1} \frac{t^n}{[n]_{p,q}!}
\sum_{(\sg,w) \in ND_{n,k}} q^{\inv(\sg)} p^{\coinv(\sg)} =
\frac{(k-1)!}{\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1} e_{p,q}(-t)}.
\end{equation}
and
\begin{equation}
1+ \sum_{n \geq 1} \frac{nd_{n,k} t^n}{n!} =
\frac{(k-1)!}{\frac{\dd^{k-1}}{\dd t^{k-1}} t^{k-1}e^{-t}}
\end{equation}
where $nd_{n,k} = |ND_{n,k}|$.
\end{corollary}







\begin{thebibliography}{20}

\bibitem{AR} R. M. Adin and Y. Roichman, The flag major index and
group actions on polynomial rings, {\it European J. of Combinatorics},
\textbf{22} (2001), 431--446.

\bibitem{Andre1}
D. {Andr\'{e}}, D\'eveloppements de sec $x$ et de tang $x$,
{\it C. R. Acad. Sci. Paris} \textbf{88} (1879), 965--967.

\bibitem{Andre2}
D. {Andr\'{e}}, M\'{e}moire sur les permutations altern\'{e}es,
{\it J. Math. Pures. Appl.} \textbf{7} (1881), 167--184.

\bibitem{Car}
L.~Carlitz, Enumeration of up-down sequences, 
{\it Discrete Math.} \textbf{4} (1973), 273--286.

\bibitem{Car1}
L. Carlitz and R. Scoville, Up-down sequences, {\it Duke Math. J.}
\textbf{39} (1972), 583--598.

\bibitem{Car2}
Leonard Carlitz, Sequences and inversions, {\it Duke Math. J.}
\textbf{37} (1970), 193--198.

\bibitem{ER}
{\"O}mer E{\u{g}}ecio{\u{g}}lu and Jeffrey Remmel, Brick tabloids and the
connection matrices between bases of symmetric functions, {\it Discrete Appl.
Math.} \textbf{34} (1991), 107--120.

\bibitem{FR} E. Fuller and J. B. Remmel, Quasi-symmetric functions and
up-down words, preprint.

\bibitem{LR}
T.~M. Langley and J.~B. Remmel, Enumeration of {$m$}-tuples of
permutations and a new class of power bases for the space of symmetric
functions, {\it Adv. in Appl. Math.} \textbf{36} (2006), 30--66.

\bibitem{Mac}
I.~G. Macdonald, {\it Symmetric Functions and {H}all polynomials}, 2nd ed.,
Oxford Mathematical Monographs, Oxford University Press,
1995. With contributions by A. Zelevinsky.

\bibitem{MendesTh}
Anthony Mendes, {Building generating functions brick by brick}, Ph.D.
  thesis, University of California, San Diego, 2004.

\bibitem{MenRem2}
Anthony Mendes and Jeffrey Remmel, {Generating functions for statistics on
  {$C\sb k\wr S\sb n$}}, {\it S\'em. Lothar. Combin.}
  \textbf{54A} (2005/07), Art.  B54At, 40 pp. (electronic).

\bibitem{MRR} T. Mendes, J. Remmel, and A. Riehl,
Permutations with $k$-regular
descent patterns, to appear in 
\emph{Permutation Patterns}, (S. Linton, N. Ru\u{s}kuc, V. 
Vatter, eds.), London. Math. Soc. Lecture Notes 376. 

\bibitem{LM}
D. J. Lemming and R. A. MacLeod, {Some properties of the
generalized Euler numbers}, {\it Canad. J. Math.}
\textbf{33} (1981), 606--617.


\bibitem{PWZ} M. Petkovek, H. S. Wilf, and D.
Zeilberger, {\em $A=B$}, A. K. Peters, 1996.

\bibitem{Raw} D. Rawlings, {Restricted words by adjacencies},
{\it Discrete Math.} {\bf 220} (2000), 183--200.

\bibitem{Sta}
Richard Stanley, {Binomial posets, {M}\"obius inversion, and permutation
enumeration}, {\it J. Combinatorial Theory Ser. A} \textbf{20} (1976),
336--356.

\bibitem{Stan}
R. P. Stanley, \emph{Enumerative Combinatorics},  Vol. 1,
Cambridge Studies in Advanced Mathematics, Cambridge University Press,
1997.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A05; Secondary 05A15.\\


\noindent  {\it Keywords}:  

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences 
\seqnum{A000111},
\seqnum{A000182}, and 
\seqnum{A122045}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  
December 19 2009;
revised version received May 5 2010.
Published in {\it Journal of Integer Sequences}, May 5 2010.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}
</pre></body></html>