\documentclass[12pt,reqno]{amsart}

\setlength{\textwidth}{6.3in}
\setlength{\textheight}{8.7in}
\hoffset-2truecm
\voffset-.5truecm
%\setlength{\topmargin}{0pt}
%\setlength{\headsep}{0pt}
%\setlength{\headheight}{0pt}
%\setlength{\oddsidemargin}{0pt}
%\setlength{\evensidemargin}{0pt}

\usepackage{amsfonts,amssymb,amsmath,epsfig,amsthm,color,graphicx,euscript}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newcommand{\fig}[1]{\vspace{1ex} \begin{center} \input{#1.pstex_t} 
\end{center} \vspace{1ex}}
\newcommand{\La}{\Lambda}
\newcommand{\la}{\lambda} 
\newcommand{\qbin}[3]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{#3}}
\newcommand{\sg}{\sigma}


\begin{document}

\newbox\Adr
\setbox\Adr\vbox{
\centerline{\sc Anthony Mendes}
\vskip10pt
\centerline{\small Department of Mathematics}
\centerline{\small California Polytechnic State University}
\centerline{\small San Luis Obispo, CA 93407. USA}
\centerline{\small \texttt{aamendes@calpoly.edu}}
\vskip18pt
\centerline{and}
\vskip18pt
\centerline{\sc Jeffrey Remmel$^1$} 
\vskip10pt
\centerline{\small Department of Mathematics}
\centerline{\small University of California, San Diego}
\centerline{\small La Jolla, CA 92093-0112. USA}
\centerline{\small \texttt{jremmel@ucsd.edu}}
}


\title{Generating Functions for Statistics on $C_k \wr S_n$}

\author[Anthony Mendes and Jeffrey Remmel]{\box\Adr}

\thanks{$^1$ Partially supported by NSF Grant DMS 0400507
and DMS 0502858}

\date{}

\dedicatory{Dedicated to Adriano Garsia on the occasion of his 78-th Birthday.}

\begin{abstract}
Foata and Han [{\it Adv. in Appl. Math.}
  \textbf{18} (1997), 489--509;
{\it Electron.\ J. Combin.} \textbf{4} (1997), Article~\#R9] proved 
 some remarkable generating functions for statistics 
on the hyperoctahedral group $B_n$.  These generating functions can be 
specialized to give a large number of generating functions for permutation 
statistics appearing in the literature.  In this paper, we give a new 
proof of Foata and Han's result by defining a homomorphism on the ring of 
symmetric functions and applying it to a simple symmetric function 
identity.  Our methods easily extend to derive several 
natural extensions of Foata and Han's generating functions. In particular, 
we show that there exists a natural family of generating 
functions for permutation statistics over wreath products $C_k \wr S_n$ 
of cyclic groups $C_k$ with the symmetric group $S_n$ which can be viewed as generalizations of 
the Foata-Han generating functions.  We also prove some new generating 
functions for the Foata-Han statistics for tuples of permutations of 
$B_n$ or $C_k \wr S_n$ 
whose common descent set contain a final sequence of at least $s$ or 
whose common descent set contain a final sequence of exactly size $s$. 
\end{abstract}

\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 54A \rms (2007), Article~B54At\hfill}
\def\thepage{}
%
%

\section{Introduction and Preliminaries}

Let $G$ be a finite group and $S_n$ the symmetric group on $n$ letters.  
This work is the continuation of a series of papers that show how various 
generating functions for permutation statistics on wreath products 
$G \wr S_n$ can be derived by applying appropriate homomorphisms on the 
ring of symmetric functions to simple symmetric function identities.  

This idea was first used by Brenti \cite{Bre}.  Beck and Remmel then gave 
combinatorial proofs of Brenti's results by exploiting combinatorial 
interpretations of the entries of the transitions matrices 
between bases of symmetric functions \cite{Bec3,Bec4}.  
This combinatorial approach allowed for $q$-analogues of Brenti's results as 
well as generalizations of Brenti's results for the hyperoctahedral group 
$B_n$.  Wagner extended these results to study permutation 
statistics on groups of the form $C_k \wr S_n$ where $C_k$ is the cyclic 
group of order $k$ \cite{wagner}. Since then, there has been a series of 
papers that have developed these methods, see 
\cite{Lan-Rem,Mendes-Rem1,Mendes-Rem2}.  
A systematic treatment of these ideas is currently being developed by
the authors \cite{Book}. 

The goal of this paper is to show how such methods can be used to prove 
a remarkable generating function for permutation statistics on the 
hyperoctahedral group $B_n$ first proved by Foata and Han \cite{FH1,FH2}. 
Foata and Han's generating function is significant because
it can be specialized to give a large number of generating function for 
permutation statistics for $S_n$ and $B_n$.  Their paper includes a flow chart
recording the many different specializations. 

Our proof has a number of important features. 
\begin{itemize}
\item It can be easily extended to give an entire family of extensions of the 
Foata-Han generating function to groups of the form $C_k \wr S_n$ for 
$k \geq 2$ ($B_n$ is isomorphic to $C_2 \wr S_n$). 
\item It allows us to define a new set of permutation statistics on $B_n$ that 
have the same distribution as the permutation statistics that appear in the 
Foata-Han result. 
\item It provides an archetypal example of a result found in the literature 
with the property that the homomorphism required in our proof can be read 
directly from the generating function itself.  
Then, once one has proved the given generating function by our methods, it 
can immediately be generalized to give a number of new results. 
\item It exploits a symmetric function identity that involves a new 
class of symmetric functions which have properties similar to 
the power symmetric functions.  Special cases of these 
symmetric functions have appeared in the work of Langley and Remmel 
\cite{Lan-Rem} and Mendes and Remmel \cite{Mendes-Rem2}. 

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL ANTHONY MENDES AND JEFFREY REMMEL}{\SMALL GENERATING FUNCTIONS FOR STATISTICS ON $C_k \wr S_n$}
%
%

\item Finally, as with many other cases of our method, once we have proved a given result, we can modify the combinatorics involved in the proof to prove new results. In this case, we will show that we can easily modify our proof to give generating functions for tuples of permutations in $C_k \wr S_n$ whose final common decreasing sequence has size at least $s$ or exactly $s$ for any $s \geq 2$, relative 
to the statistics involved in our generalization of the Foata-Han result. These results are completely new even in the case where $k =2$ and 
$C_k \wr S_n = B_n$.   
\end{itemize}

The outline of this paper is as follows.   
In Section 2, we shall define the various permutation 
statistics for $B_n$ that we shall use and state the Foata-Han result. In particular, we shall state a variation of the Foata-Han result which uses a more 
natural version of an inversion statistics than was originally used by Foata and Han. This result is new and does not follow from the previous results of Foata and Han. In Section 3, 
we shall define our new class of symmetric
functions and prove a simple identity (\ref{fund}) involving our new class of symmetric functions to which will apply various homomorphisms defined on 
the ring of symmetric functions to derive our results. In Section 4, 
we shall define the homomorphism $\xi$ which can be applied to the symmetric 
function identity  (\ref{fund}) to yield both the Foata-Han generating 
function relative to their definition of inversions for signed permutations 
and our new generating 
function relative to a more natural definition of inversions for signed 
permutations. We shall give a very careful proof that $\xi$ applied to 
(\ref{fund}) yields both generating functions since if one understands the proof in this case, then one can see that relatively simple variations of that proof will yield our family of extensions of these results to $C_k \wr S_n$ for 
any $k \geq 3$ as well as the new generating functions for tuples of permutations in $C_k \wr S_n$ whose final common decreasing sequence has size at least $s$ or exactly $s$ for any $s \geq 2$. The proof that we present in section 4 could be simplified if our goal was just to prove the results stated in section 2. However, the main goal of this paper is to prove the generalizations and extensions of the results stated in section 2 to 
the groups $C_k \wr S_n$.  The reader will see that the proof presented 
in section 4 is a template for the proofs of those 
generalizations and extensions. 
In Section 5, we extend our 
methods to give some new families of generating functions for permutation 
statistics on $C_k \wr S_n$. Some of the identities that we prove were first 
proved by Wagner \cite{wagner2} using the methods of Foata and Han. 
Finally, in 
Section 6, we shall use the combinatorics developed in Section 5 to prove a new class of generating functions for tuples of permutations in $C_k \wr S_n$ whose final common decreasing segment has size at least $s$ or exactly $s$ for any $s \geq 2$. 

\section{Permutation Statistics and Generating Functions for $B_n$} 

Following Foata and Han, we shall think of an element of $B_n$ as pair 
$(\sg,\epsilon)$ where $\sg \in S_n$ and $\epsilon \in \{x,y\}^n$.
Then we define the following statistics on $B_n$.  

We call $i$ a descent of $(\sg,\epsilon)$ if either 
\begin{itemize}
\item[(i)] $\epsilon(i) = \epsilon(i+1)$ and $\sg_i > \sg_{i+1}$, 
\item[(ii)] $\epsilon(i) = x$ and $\epsilon(i+1) = y$, or 
\item[(iii)] $i = n$ and $\epsilon(n) = x$.
\end{itemize}
Let $Des(\sg,\epsilon)$ denote the set of descents $(\sg, \epsilon) \in B_n$.

A pair $(i,j)$ is a FH-inversion (respectively FH-coinversion) of $(\sg,\epsilon)$ if 
\begin{itemize}
\item[(i)]  $i < j$, $\epsilon(i) = \epsilon(j)$ and $\sg_i > \sg_{j}$  
(respectively $\sg_i < \sg_{j}$), or 
\item[(ii)] $\epsilon(i) = y$ and $\epsilon(j) = x$, and 
$\sg_i > \sg_{j}$.
\end{itemize}
We say that a pair $(i,j)$ is an inversion (respectively coinversion) of 
$(\sg,\epsilon)$ if $i < j$ and $\sg_i > \sg_j$ (respectively $\sg_i < \sg_j$),
i.e. we say that $(i,j)$ is an inversion (respectively coinversion) of 
$(\sg,\epsilon)$ 
if it is an inversion (respectively coinversion) of $\sigma$.  In \cite{FH1,FH2}, Foata and
Han used the term inversion and coinversion for what we are 
calling FH-inversion and FH-coinversion respectively. They did not consider the usual notion of 
inversion and coinversion as we have defined.

Next we consider the restriction of $(\sg,\epsilon)$ to its $x$ part 
$\sg_{\epsilon | x}$, the restriction of $(\sg,\epsilon)$ to its $y$ part 
$\sg_{\epsilon | y}$, and their inverses $\sg^{-1}_{\epsilon | x}$ and 
$\sg^{-1}_{\epsilon | y}$. These are best understood with an example. Suppose 
\begin{equation*}
(\sg,\epsilon) = 
(6 ~ 2 ~ 7 ~ 4 ~ 3 ~ 1 ~ 5 ~ 8 ~ 9, x ~ x ~ y ~ y ~ y ~ y ~ x ~ x ~ x).
\end{equation*}
We may think of $(\sg,\epsilon)$ as an array:
\begin{center}
$\begin{array}{cclllllllll}
         &   &1&2&3&4&5&6&7&8&9 \\
\sigma   & = &6&2&7&4&3&5&1&8&9 \\
\epsilon & = &x&x&y&y&y&y&x&x&x
\end{array}$
\end{center}
Then $\sg_{\epsilon | x}$ and $\sg_{\epsilon | y}$ may be found by 
looking at the columns corresponding to the $x$'s and $y$'s, respectively: 
\begin{center}
$\begin{array}{cclllll}
                       &   &1&2&7&8&9 \\
\sigma_{\epsilon | x}  & = &6&2&1&8&9 \\
\end{array}$
\qquad and \qquad
$\begin{array}{ccllll}
                       &   &3&4&5&6 \\
\sigma_{\epsilon | y}  & = &7&4&3&5 \\
\end{array}$.
\end{center}
We will let $\ell(\sg_{\epsilon | x})$ be the length of $\sg_{\epsilon | x}$.
To find the inverses $\sg^{-1}_{\epsilon | x}$ and $\sg^{-1}_{\epsilon | y}$, 
we take the arrays corresponding to $\sg_{\epsilon | x}$ and 
$\sg_{\epsilon | y}$, interchange the numbers in each column, then reorder the
columns so the numbers in the top row corresponding are increasing.  In our 
case, the process would result in the following arrays:
\begin{center}
$\begin{array}{cclllll}
                           &   &1&2&6&8&9 \\
\sigma_{\epsilon | x}^{-1} & = &7&2&1&8&9 \\
\end{array}$
\qquad and \qquad
$\begin{array}{ccllll}
                            &   &3&4&5&7 \\
\sigma_{\epsilon | y}^{-1}  & = &5&4&6&3 \\
\end{array}$.
\end{center}

For any sequence $\tau = \tau_1 \cdots \tau_n$ of distinct integers,
we define the usual notions of descents, rises, major index, 
comajor index, inversion and coinversions:
\begin{align*}
Des(\tau) & = \{i < n: \tau_i > \tau_{i+1}\}, & 
Rise(\tau) & = \{i < n: \tau_i < \tau_{i+1}\}, \\
des(\tau) & = |Des(\tau)|, & 
rise(\tau) & = |Rise(\tau)|, \\
maj(\tau) & = \sum_{i \in Des(\tau)} i, & 
comaj(\tau) & = \sum_{i \in Rise(\tau)} i, \\
inv(\tau) & = \{(i,j): 1 \leq i < j \leq n, \tau_i > \tau_j\}, &
coinv(\tau) & = \{(i,j): 1 \leq i < j \leq n, \tau_i < \tau_j\}.
\end{align*}
In addition, we define  
\begin{equation*} 
\overline{inv}(\sg_{\epsilon | x}, \sg_{\epsilon | y}) = 
|\{ (i,j): \epsilon(i) = y, \epsilon(j) = x, \sg_i > \sg_{j}\}|.
\end{equation*}
In our example, 
$\overline{inv}(\sg_{\epsilon | x}, \sg_{\epsilon | y}) = 9$. 
We can now give the following two statistics on elements $(\sg, \epsilon)$
in $B_n$. Let 
\begin{align*}
imaj(\sg, \epsilon) 
& =  maj(\sg^{-1}_{\epsilon | x}) + maj(\sg^{-1}_{\epsilon | y}) + 
\overline{inv}(\sg_{\epsilon | x}, \sg_{\epsilon | y}), \qquad \text{and} \\ 
icomaj(\sg, \epsilon) 
& =  comaj(\sg^{-1}_{\epsilon | x}) + comaj(\sg^{-1}_{\epsilon | y}) 
+ \overline{inv}(\sg_{\epsilon | x}, \sg_{\epsilon | y}).
\end{align*}

Our definitions of FH-inversion, FH-coinversions, inversions and coinversions 
for elements $(\sg, \epsilon)$ in $B_n$ satisfy the following relationships:
\begin{align*}
FHinv(\sg, \epsilon) 
& =  inv(\sg_{\epsilon | x}) + inv (\sg_{\epsilon | y}) + 
\overline{inv}(\sg_{\epsilon | x}, \sg_{\epsilon | y}), \\
FHcoinv(\sg, \epsilon) 
& =  coinv(\sg_{\epsilon | x}) + coinv (\sg_{\epsilon | y}) + 
\overline{inv}(\sg_{\epsilon | x}, \sg_{\epsilon | y}), \\
inv(\sg, \epsilon) & = inv(\sg), \qquad \text{and} \\
coinv(\sg, \epsilon) & =  coinv(\sg). 
\end{align*}

We will write $(\sg^{(1)}, \sg^{(2)}, \ldots, \sg^{(k)}; \epsilon)$ for the sequence of 
elements $(\sg^{(1)},\epsilon)$, $(\sg^{(2)},\epsilon)$, \ldots, 
$(\sg^{(k)},
\epsilon)$ of 
$B_n$ (the second elements of all pairs are the same).  Define 
\begin{equation*}
Comdes((\sg^{(1)},\epsilon), (\sg^{(2)},\epsilon), \ldots, (\sg^{(k)},\epsilon)) 
= Comdes(\sg^{(1)}, \sg^{(2)}, \ldots, \sg^{(k)};\epsilon)
= \bigcap_{i} Des(\sg^{(i)},\epsilon)
\end{equation*}
and
\begin{eqnarray*}
comdes((\sg^{(1)},\epsilon), (\sg^{(2)},\epsilon), \ldots, (\sg^{(2)},\epsilon)) &=& 
comdes(\sg^{(1)}, \sg^{(2)}, \ldots, \sg^{(k)};\epsilon)\\
&=&
|Comdes(\sg^{(1)}, \sg^{(2)}, \ldots, \sg^{(k)};\epsilon)|.
\end{eqnarray*}

Suppose we are given two sequences of variables, 
${\bf Q} = (Q_1, \ldots, Q_L)$ and ${\bf q} = (q_1, \ldots, q_{\ell})$.  We 
will use the following notation: 
\begin{align*}
{\bf Q}^{\binom{n}{2}} & = Q_1^{\binom{n}{2}} \cdots Q_L^{\binom{n}{2}}, \\
({\bf Q},{\bf Q})_n & = \prod_{i=1}^L (Q_i,Q_i)_n, \\
({\bf q},{\bf q})_n & = \prod_{i=1}^{\ell} (q_i,q_i)_n, \qquad \text{and} \\ 
J(u,{\bf Q},{\bf q}) & = \sum_{n \geq 0} 
\frac{(-1)^n u^n {\bf Q}^{\binom{n}{2}}}
{({\bf Q},{\bf Q})_n \ ({\bf q},{\bf q})_n}
\end{align*}
where $(a,q)_0 = 1$ and $(a,q)_n = (1-a)(1-aq) \cdots (1 -aq^{n-1})$ for 
$n > 0$.  The usual $q$-analogues of the factorial, binomial coefficients, and
multinomial coefficients will be used: 
\begin{align*}
[n]_q & = q^0 + \cdots + q^{n-1} = \frac{1-q^n}{1-q}, \\
[n]_q! & = [1]_q [2]_q \cdots [n]_q = \frac{(q,q)_n}{(1-q)^n}, \\
\qbin{n}{k}{q} & = \frac{[n]_q!}{[k]_q![n-k]_q!} = 
\frac{(q,q)_n}{(q,q)_k (q,q)_{n-k}}, \qquad \text{and} \\
\qbin{n}{b_1,\ldots,b_k}{q} & = \frac{[n]_q!}{[b_1]_q! \cdots [b_k]_q!} 
= \frac{(q,q)_n}{(q,q)_{b_1} \cdots  (q,q)_{b_k}}.
\end{align*}

If ${\bf \Sigma} = (\Sigma^{(1)}, \ldots,\Sigma^{(L)})$ 
and ${\bf \sigma} = (\sigma^{(1)}, \ldots,\sigma^{(\ell)})$ are 
sequences of permutations
in $S_n$ and $\epsilon \in \{x,y\}^n$, we let
\begin{equation}
\label{eqn:1}
{\bf Q}^{inv ({\bf \Sigma};\epsilon)} = \prod_{i = 1}^L Q_i^{inv 
(\Sigma^{(i)},\epsilon)} \ 
\mbox{and} \ {\bf q}^{inv ({\bf \sigma};\epsilon)} = 
\prod_{i = 1}^{\ell} q_i^{inv (\sigma^{(i)},\epsilon)}.
\end{equation}
We may replace the ``inv'' in \eqref{eqn:1} with any other permutation
statistic like ``imaj'', ``icomaj'', ``FHinv'', etc.  


If ${\bf \Sigma} = (\Sigma^{(1)},\dots,\Sigma^{(L)})$ and 
${\bf \sg} = (\sg^{(1)},\dots,\sg^{(\ell)})$ are sequences in the 
symmetric group
$S_n$ and $\epsilon$ is a word of length $n$ in the letters $\{x,y\}$, 
we will denote $$(\Sigma^{(1)}, \ldots,\Sigma^{(L)},
\sg^{(1)}, \ldots,\sg^{(\ell)}; 
\epsilon)$$ as $({\bf \Sigma},{\bf \sg}; \epsilon)$.
The last definitions we will need to make before we can state the results of
Foata and Han are as follows.  Let 
\begin{align*}
W^{(1)}_n(X,Y,t,{\bf Q},{\bf q}) &= 
\sum_{({\bf \Sigma},{\bf \sg};\epsilon)} X^{\ell({\epsilon | x})}
Y^{\ell({\epsilon | y})} t^{comdes({\bf \Sigma},{\bf \sg};\epsilon)} 
{\bf Q}^{FHinv({\bf \Sigma};\epsilon)} 
{\bf q}^{FHcoinv({\bf \sg};\epsilon)},  \\
W^{(2)}_n(X,Y,t,{\bf Q},{\bf q}) &=
\sum_{({\bf \Sigma},{\bf \sg};\epsilon)} X^{\ell({\epsilon | x})}Y^{\ell({\epsilon | y})} t^{comdes({\bf \Sigma},{\bf \sg};\epsilon)} 
{\bf Q}^{inv({\bf \Sigma};\epsilon)} 
{\bf q}^{coinv({\bf \sg};\epsilon)}, \qquad \text{and} \\
W^{(3)}_n(X,Y,t,{\bf Q},{\bf q}) & = 
\sum_{({\bf \Sigma},{\bf \sg};\epsilon)} X^{\ell({\epsilon | x})}
Y^{\ell({\epsilon | y})} t^{comdes({\bf \Sigma},{\bf \sg};\epsilon)} 
{\bf Q}^{imaj({\bf \Sigma};\epsilon)} 
{\bf q}^{icomaj({\bf \sg};\epsilon)}
\end{align*}
where the sums run over all $\epsilon \in \{x,y\}^n$ and all sequences 
$(\Sigma^{(1)}, \ldots,\Sigma^{(L)},
\sg^{(1)}, \ldots,\sg^{(\ell)}) \in S_n^{L + \ell}$.
Foata and Han proved the following theorem. 
\begin{theorem} 
\label{thm:FH1}
For $i = 1$ and $i = 3$, 
\begin{equation*}
\sum_{n \geq 0} 
\frac{W^{(i)}_n(X,Y,t,{\bf Q},{\bf q})u^n}
{({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n} 
= \frac{(1-t) J((1-t)Xu; {\bf Q}, {\bf q})}
{-t + J((1-t)uX; {\bf Q}, {\bf q})J((1-t)Yu; {\bf Q}, {\bf q})}.
\end{equation*}
\end{theorem}

An immediately corollary of this theorem is that 
$$W^{(1)}_n(X,Y,t,{\bf Q},{\bf q}) = W^{(3)}_n(X,Y,t,{\bf Q},{\bf q}).$$ 
Indeed, Foata and Han gave a bijection showing this fact by proving the
following theorem. 

\begin{theorem} 
\label{thm:FH2}
For all pairs of nonnegative integers $L$ and $\ell$, let
$\Gamma_{B_n,L,\ell}$ be the set of all 
$({\bf \Sigma},{\bf \sg}; \epsilon) = 
(\Sigma^{(1)}, \ldots,\Sigma^{(L)},
\sg^{(1)}, \ldots,\sg^{(\ell)}; \epsilon)$ such 
that $\epsilon \in \{x,y\}^n$ and $\Sigma^{(i)},\sigma^{(j)} \in S_n$ for all 
$i$ and $j$. Then there is a bijection $\Psi_n: \Gamma_{B_n,L,\ell}  
\rightarrow \Gamma_{B_n,L,\ell}$ such 
that if $\Psi_n(({\bf \Sigma},{\bf \sg}; \epsilon)) = 
({\bf \Sigma}^\prime,{\bf \sg}^\prime; \epsilon^\prime)$, then 
\begin{align*}
\ell(\epsilon|x) & = \ell(\epsilon^\prime | x), \\
comdes({\bf \Sigma},{\bf \sg}; \epsilon) & = 
comdes({\bf \Sigma}^\prime,{\bf \sg}^\prime; \epsilon^\prime), \\
imaj({\bf \Sigma},\epsilon)
& = FHinv({\bf \Sigma}^\prime ; \epsilon^\prime) \qquad \text{and} \\
icomaj({\bf \sigma},\epsilon) & = 
FHcoinv({\bf \sigma}^\prime ; \epsilon^\prime).   
\end{align*}
\end{theorem}

We shall see that the proof of Theorem \ref{thm:FH1} in section 4 can also 
be modified to give a proof of the following theorem which is a new result. 
\begin{theorem}
\label{thm:FH-var} 
\begin{equation*}
\sum_{n \geq 0} 
\frac{ W^{(2)}_n(X,Y,t,{\bf Q},{\bf q})u^n}{ ({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n} = \frac{(1-t) J((1-t)Xu; {\bf Q}, {\bf q})}{-t + J((1-t)uX; {\bf Q}, {\bf q})J((1-t)Yu; {\bf Q}, {\bf q})}.
\end{equation*}
\end{theorem}
 

\section{Symmetric Functions} 

In this section, we shall give the necessary background on symmetric 
functions and the combinatorics of the entries of the transition matrix 
that we need before we can give our proofs of 
Theorems \ref{thm:FH1} and \ref{thm:FH-var}.

A symmetric polynomial $p$ in the variables $x_1,\dots,x_N$ is a polynomial 
over a field $F$ of characteristic 0 with the property that 
\begin{equation*}
p(x_1,\dots,x_N) = p(x_{\sg_1},\dots,x_{\sg_N})
\end{equation*}
for all $\sg = \sg_1 \cdots \sg_N \in S_N$.  Let $\La^N$ be the ring of 
symmetric polynomials in $x_1,\dots,x_N$ and $\La^N_n$ be the subset of 
$\La^N$ containing the homogeneous elements of degree $n$.  Using the 
surjective ring homomorphism from $\La^{N+1}_n$ to $\La^{N}_n$ defined by 
taking $x_{N+1} = 0$, let $\La_n = \varprojlim_{N} \La^N_n$ for each 
$n \geq 0$.  Define $\La = \bigoplus_{n \geq 0} \La_n$ to be the ring of 
symmetric functions over $F$.  A symmetric function in the variables 
$x_1,x_2,\dots$ may be thought of as a symmetric polynomial in an infinite
number of variables. 

For instance, the elementary symmetric function $e_n = e_n(x_1,x_2,\dots)$ 
may be defined by
\begin{equation*}
\sum_{n \geq 0} e_n t^n 
= (1+x_1 t)(1+x_2 t) \cdots.
\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.  We
will 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}$.
It is well known that that $\{e_\la : \text{$\la$ is a partition}\}$
is a basis for $\La$.

The homogeneous symmetric function $h_n = h_n(x_1,x_2,\dots)$ is defined such that 
\begin{equation*}
\sum_{n \geq 0} h_n t^n = \frac{1}{1-x_1 t} \cdot \frac{1}{1-x_2 t} \cdots. 
\end{equation*}
Therefore, 
\begin{equation}
\label{h and e gen fun}
\sum_{n \geq 0} h_n t^n
= \frac{1}{1-x_1 t} \cdot \frac{1}{1-x_2 t} \cdots 
= \left( (1 - x_1 t)(1 - x_2 t) \cdots \right)^{-1}
= \left( \sum_{n \geq 0} e_n (-t)^{n} \right)^{-1}.
\end{equation}

The coefficient of the homogeneous symmetric functions when written in
terms of the elementary symmetric function basis is a sum of
combinatorial objects.  A rectangle of height $1$ and length $n$
chopped into ``bricks'' of lengths found in the partition $\la$ is
known as a brick tabloid of shape $(n)$ and type $\la$.  One brick
tabloid of shape $(9)$ and type $(1,1,2,5)$ is displayed in Figure \ref{fig:FHfig1}.  

\begin{figure}
\fig{FHfig1}
\caption{A brick tabloid.}
\label{fig:FHfig1}
\end{figure}

Let $B_{\la,n}$ be the number of such objects.  Through simple recursions
stemming from \eqref{h and e gen fun}, E\u{g}ecio\u{g}lu and Remmel proved in 
\cite{Eg1} that   
\begin{equation}
\label{omar}
h_n = \sum_{\la \vdash n} (-1)^{n - \ell(\la)} B_{\la,n} e_\la.
\end{equation}

A large number of generating functions for various statistics are the result 
of applying an appropriate homomorphism to \eqref{omar}, see 
\cite{Men}.  However to prove Theorems \ref{thm:FH-var} and \ref{thm:FH1} and 
their extensions, we will need to have an increased amount of flexibility 
than is available in the relationship between the homogeneous and 
elementary symmetric functions.  
To this end, we define the following class of symmetric functions.

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{equation:general p gen fun}
\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 
= 1 + \frac{\sum_{n \geq 1} (-1)^{n-1} e_n t^n}
{\sum_{n \geq 0} (-1)^n e_n 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.  Taking 
$\nu$ such that $\nu(n) = n$ for $n \geq 1$, $p_{n,n}$ is the power symmetric 
function $\sum_{i} x_i^n$.  Let $\chi(S)$ be equal to $1$ if $S$ is true
and $0$ if false for any statement $S$.  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}
\label{eqn:weighting}
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}
When $\nu(n) = 1$ for $n \geq 1$, $B_{\la,n}$ and $w_{\nu}(B_{\la,n})$ are 
the same.  By the recursions found in the definition of $p_{n,\nu}$, it may be
shown that
\begin{equation}
\label{equation:weighted}
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{Eg1}.  
A detailed proof may be found in \cite{Men}.

We are now ready to give our proof of Theorems \ref{thm:FH-var} and 
\ref{thm:FH1}. 

\section{Our proof of Theorems \ref{thm:FH1} and \ref{thm:FH-var}}

In this section, we shall prove Theorem \ref{thm:FH1} in the case 
where $i=1$ and Theorem \ref{thm:FH-var} by applying a homomorphism 
$\xi$ defined on the ring of symmetric functions to the identity 
(\eqref{fund}) for an appropriate weight function $\nu$. The case where 
$i =3$ of  Theorem \ref{thm:FH1} will then follow by applying the 
bijection of Foata and Han described in Theorem \ref{thm:FH2}.
The remarkable fact is that we can essentially 
read the required homomorphism $\xi$ and the required function $\nu$ directly
from the right hand side of the statement of Theorem \ref{thm:FH-var}. 
Rewrite this expression as
\begin{multline*}
\frac{(1-t) J((1-t)Xu; {\bf Q}, {\bf q})}
{1-t + \left(J((1-t)Xu; {\bf Q}, {\bf q})J((1-t)Yu; 
{\bf Q}, {\bf q}) -1\right)} \\
= \frac{ 1+ \sum_{n \geq 1} (-1) ^n X^n u^n (1-t)^n 
\frac{{\bf Q}^{\binom{n}{2}}}{({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n}}
{1 + \sum_{n \geq 1} (-1)^n u^n  (1-t)^{n-1} \sum_{k =0}^n 
\frac{ X^k {\bf Q}^{\binom{k}{2}} Y^{n-k} {\bf Q}^{\binom{n-k}{2}}}
{({\bf Q},{\bf Q})_k ({\bf q},{\bf q})_k({\bf Q},{\bf Q})_{n-k} 
({\bf q},{\bf q})_{n-k}}}.
\end{multline*}
This suggests that we should set 
\begin{equation}\label{eq:hom}
\xi(e_n) =  (1-t)^{n-1} \sum_{k =0}^n 
\frac{ X^k {\bf Q}^{\binom{k}{2}} Y^{n-k} {\bf Q}^{\binom{n-k}{2}}}
{({\bf Q},{\bf Q})_k ({\bf q},{\bf q})_k({\bf Q},{\bf Q})_{n-k} 
({\bf q},{\bf q})_{n-k}}
\end{equation}
and 
\begin{equation}\label{eq:wt}
\xi(e_n) - \nu(n) \xi(e_n) 
= \frac{(1-t)^n X^n {\bf Q}^{\binom{n}{2}}}
{({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n}.
\end{equation}
Solving (\ref{eq:wt}) for $\nu(n)$, we see that  
\begin{equation}
\nu(n) 
= \frac{1}{\xi(e_n)} \left( \xi(e_n) - \frac{(1-t)^{n-1} X^n 
{\bf Q}^{\binom{n}{2}}}{({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n} + 
\frac{t(1-t)^{n-1} X^n {\bf Q}^{\binom{n}{2}}}
{({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n}\right).
\end{equation}
Therefore, to prove Theorem \ref{thm:FH1}, we need only show that 
\begin{equation*}
\xi(p_{n,\nu}) 
= \frac{W_n^{(1)}(X,Y,t,{\bf Q},{\bf q})}
{({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n}
\end{equation*}
or, equivalently, that 
\begin{equation}
\label{eq:FH4}
({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \xi(p_{n,\nu}) 
= W_n^{(1)}(X,Y,t,{\bf Q},{\bf q}).
\end{equation}
Similarly, to prove Theorem \ref{thm:FH-var}, we need only show that 
\begin{equation*}
\xi(p_{n,\nu}) 
= \frac{W_n^{(2)}(X,Y,t,{\bf Q},{\bf q})}
{({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n}
\end{equation*}
or, equivalently, that 
\begin{equation}\label{eq:goal}
({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \xi(p_{n,\nu}) 
= W_n^{(2)}(X,Y,t,{\bf Q},{\bf q}).
\end{equation}

We start by using \eqref{equation:weighted} to express $p_{n,\nu}$ in terms 
of the elementary symmetric functions.  We have 
\begin{align} 
({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \xi(p_{n,\nu}) \nonumber
&= ({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n 
\sum_{\mu \vdash n} (-1)^{n - \ell(\mu)} w_\nu(B_{\mu,n}) \xi(e_\mu) \\
&= \sum_{\mu \vdash n} (-1)^{n - \ell(\mu)} \sum_{T = (b_1, \ldots,b_k) \in 
{\it B}_{\mu,n}}  ({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \nu(b_k) 
\prod_{i=1}^k \xi(e_{b_i}).
\label{eqn:first} 
\end{align}

Focusing on the term $({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \nu(b_k) 
\prod_{i=1}^k \xi(e_{b_i})$, we have for $i < k$,  
\begin{align*}
\xi(e_{b_i}) 
& = (1-t)^{b_i-1} \sum_{j=0}^k \frac{ X^j {\bf Q}^{\binom{j}{2}} 
Y^{b_i-j}{\bf Q}^{\binom{b_i-j}{2}}}
{({\bf Q},{\bf Q})_j ({\bf q},{\bf q})_j({\bf Q},{\bf Q})_{b_i-j} 
({\bf q},{\bf q})_{b_i-j}} \\
&= (1-t)^{b_i-1} \sum_{r_i +s_i = b_i} \frac{ X^{r_i} Y^{s_i} 
{\bf Q}^{\binom{r_i}{2}}  {\bf Q}^{\binom{s_i}{2}}}
{({\bf Q},{\bf Q})_{r_i} ({\bf q},{\bf q})_{r_i}
({\bf Q},{\bf Q})_{s_i} ({q},{q})_{s_i}}.
\end{align*}
For $i=k$, 
\begin{align*}
\xi(e_{b_k})\nu(b_k) 
& = \xi(e_{b_k}) \frac{1}{\xi(e_{b_k})} 
\left( \xi(e_{b_k}) - \frac{(1-t)^{b_k-1} X^{b_k} 
{\bf Q}^{\binom{b_k}{2}}}
{({\bf Q},{\bf Q})_{b_k} ({\bf q},{\bf q})_{b_k}} + 
\frac{t(1-t)^{b_k-1} X^{b_k} 
{\bf Q}^{\binom{b+k}{2}}}{({\bf Q},{\bf Q})_{b_k} 
({\bf q},{\bf q})_{b_k}}\right) \\
& = (1-t)^{b_k-1} \left( \sum_{j =0}^{b_k-1} 
\frac{ X^j {\bf Q}^{\binom{j}{2}} Y^{b_k-j} 
{\bf Q}^{\binom{b_k-j}{2}}}{({\bf Q},{\bf Q})_j 
({\bf q},{\bf q})_j({\bf Q},{\bf Q})_{b_k-j} 
({\bf q},{\bf q})_{b_k-j}}\right) \\
&\kern8cm
+ \frac{t(1-t)^{b_k-1} X^{b_k} 
{\bf Q}^{\binom{b+k}{2}}}{({\bf Q},{\bf Q})_{b_k} 
({\bf q},{\bf q})_{b_k}} \\
& = (1-t)^{b_k-1} \left( \sum_{r_k +s_k =b_k, r_k \neq b_k} 
\frac{ X^{r_k} Y^{s_k} {\bf Q}^{\binom{r_k}{2}} 
{\bf Q}^{\binom{s_k}{2}}}{({\bf Q},{\bf Q})_{r_k} 
({\bf q},{\bf q})_{r_k}({\bf Q},{\bf Q})_{s_k} 
({\bf q},{\bf q})_{s_k}}\right) \\
&\kern8cm
+ \frac{t(1-t)^{b_k-1} X^{b_k} 
{\bf Q}^{\binom{b_k}{2}}}{({\bf Q},{\bf Q})_{b_k} ({\bf q},{\bf q})_{b_k}}.
\end{align*}
The net effect of taking the weight $\xi(e_{b_k})$ versus the weight 
$\nu(b_k) \xi(e_{b_k})$ is that the last term summand for $\xi(e_{b_k})$ is 
\begin{equation*}
\frac{(1-t)^{b_k-1} X^{b_k} {\bf Q}^{\binom{b_k}{2}}}
{({\bf Q},{\bf Q})_{b_k} ({\bf q},{\bf q})_{b_k}}
\end{equation*}
while the last term in the summand for $\nu(b_k) \xi(e_{b_k})$ has an extra 
factor of $t$, 
\begin{equation*}
\frac{t(1-t)^{b_k-1} X^{b_k} {\bf Q}^{\binom{b_k}{2}}}
{({\bf Q},{\bf Q})_{b_k} ({\bf q},{\bf q})_{b_k}}.
\end{equation*}

Thus, \eqref{eqn:first} is equal to 
\begin{multline*}
\sum_{\mu \vdash n} (-1)^{n - \ell(\mu)} \sum_{T = (b_1, \ldots,b_k) \in 
{\it B}_{\mu,n}} \sum_{r_i+s_i = b_i} (1-t)^{n-\ell(\mu)} 
X^{r_1+\cdots + r_k} Y^{s_1 + \cdots + s_k} \\
\times \frac{({\bf Q},{\bf Q})_n} {({\bf Q,\bf Q})_{r_1} 
({\bf Q}, {\bf Q})_{s_1}\cdots ({\bf Q},{\bf Q})_{r_k}({\bf Q},{\bf Q})_{s_k}}\\
\times
{\bf Q}^{\sum \binom{r_i}{2} + \sum \binom{s_i}{2}} 
\frac{({\bf q},{\bf q})_n}{({\bf q},{\bf q})_{r_1} 
({\bf q},{\bf q})_{s_1}\cdots ({\bf q},{\bf q})_{r_k}({\bf q},{\bf q})_{s_k}}
t^{\chi (r_k = b_k)} \\
= \sum_{\mu \vdash n} (t-1)^{n - \ell(\mu)} \sum_{T = (b_1, \ldots,b_k)\in 
{\it B}_{\mu,n}} \sum_{r_i+ s_i = b_i} X^{r_1+ \cdots + r_k} 
Y^{s_1 + \cdots + s_k}  t^{\chi (r_k = b_k)} \\
\times \prod_{a=1}^L \qbin{n}{r_1,s_1, \ldots, r_k,s_k}{Q_a} 
Q_a^{\sum_{i=1}^k (\binom{r_i}{2} + \binom{s_i}{2})} 
\prod_{b=1}^{\ell} {\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{q_b}}. 
\end{multline*}

Fix a brick tabloid $T = (b_1, \ldots,b_k) \in {\it B}_{\mu,n}$ and fix a 
sequence $r_1,s_1, \ldots, r_k,s_k$ such that for all 
$i =1, \ldots, k$, $r_i + s_i = b_i$.  We wish to give a combinatorial 
interpretation to the term  
\begin{equation}
\label{FHmult}
X^{r_1+ \cdots + r_k} 
Y^{s_1 + \cdots + s_k} \prod_{a=1}^L
\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{Q_a} 
Q_a^{\sum_{i=1}^k (\binom{r_i}{2} + \binom{s_i}{2})} 
\prod_{b=1}^{\ell} {\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{q_b}}. 
\end{equation}
Take the brick tabloid $T = (b_1, \ldots, b_k)$ and divide each brick 
$b_i$ into two pieces, the first of
size $r_i$ and the second of size $s_i$.  Place $X$'s at the top of all the 
cells corresponding to $r_1, \ldots, r_k$ and $Y$'s at the top of all the 
cells corresponding to $s_1, \ldots, s_k$.  Further divide the brick tabloid 
$T$ into $L + \ell$ rows and consider the set of all fillings 
${\mathcal F}_{T,L,\ell,r_1,s_1, \ldots, r_k,s_k}$ of $T$ with integers such that 
\begin{enumerate}
\item within each row $j$, each brick $b_i$ is filled with subsets 
$R_{i,j},S_{i,j} \subseteq \{1,\ldots, n\}$ such that $|R_{i,j}| =r_i$, 
$|S_{i,j}| = s_i$, the numbers in $R_{i,j}$ occupy the first $r_i$ cells of 
row $j$ in the brick $b_i$ in decreasing order, and the numbers 
in $S_{i,j}$ occupy the last $s_i$ cells of row $j$ in the brick $b_i$ in 
decreasing order, and 
\item for each row $j$, $\bigcup_{i=1}^k (R_{i,j} \cup S_{i,j}) = 
\{1,\ldots,n\}$.
\end{enumerate}
If we read to numbers from left to right in the first $L$ rows, we will 
obtain permutations $\Sigma^{(1)}, \ldots \Sigma^{(L)}$ in $S_n$.  
If we read to 
numbers from left to right in the last $\ell$ rows, we will obtain 
permutations $\sigma^{(1)}, \ldots \sigma^{(\ell)}$ in $S_n$. For example, if 
$T = (4,5)$, $r_1 = s_1 =2$, $r_2 =2$ and $s_2 =3$, and $L = \ell =2$,  
then and element of ${\mathcal F}_{T,L,\ell,r_1,s_1, \ldots, r_k,s_k}$
is pictured in Figure \ref{fig:FHfig2}

\begin{figure}
\fig{FHfig2} 
\caption{An element of ${\mathcal F}_{T,L,\ell,r_1,s_1, \ldots, r_k,s_k}$}
\label{fig:FHfig2} 
\end{figure}

In the special case where the configuration $F$ has only one permutation, 
i.e. when either $L=1$ and $\ell =0$ or $L = 0$ and $\ell =1$, we shall 
denote ${\mathcal F}_{T,L,\ell,r_1,s_1, \ldots, r_k,s_k}$ by simply 
${\mathcal F}_{T,r_1,s_1, \ldots, r_k,s_k}$. 

Our goal is to interpret \eqref{FHmult} as a weighted sum over all elements 
$F \in {\mathcal F}_{T,L,\ell,r_1,s_1, \ldots, r_k,s_k}$.  Carlitz showed in 
\cite{Car} that the $q$-multinomial coefficient can be interpreted as 
\begin{equation*}
\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{q} = 
\sum_{r \in {\mathcal R}(1^{r_1}{2}^{s_1} 3^{r_2} 4^{s_2} \cdots 
(2k-1)^{r_k}  (2k)^{s_k})} q^{inv(r)}.
\end{equation*}
where 
${\mathcal R}(1^{r_1}2^{s_1} 3^{r_2} 4^{s_2} \cdots 
(2k-1)^{r_k}  (2k)^{s_k})$ is the set of all possible
rearrangements of $1^{r_1}2^{s_1} 3^{r_2} 4^{s_2} \cdots 
(2k-1)^{r_k}  (2k)^{s_k}$. Similarly, 
\begin{equation*}
\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{q} = 
\sum_{r \in {\mathcal R}(1^{r_1}2^{s_1} 3^{r_2} 4^{s_2} \cdots 
(2k-1)^{r_k}  (2k)^{s_k})} q^{coinv(r)}.
\end{equation*}

Given a rearrangement $r \in {\mathcal R}(1^{r_1}2^{s_1} 3^{r_2} 4^{s_2} \cdots 
(2k-1)^{r_k}  (2k)^{s_k})$, we can associate a permutation $\sigma_r$ by 
labeling the 1's from right to left with $1, \ldots, r_1$, labeling the 
2's from right to left with $r_1 +1, \ldots, r_1+s_1$, etc.  It is not
difficult to see that $inv(\sg_r) = inv(r) + \sum_{i=1}^k \left( 
\binom{r_i}{2} + \binom{s_i}{2} \right)$ and that $\sg_r^{-1}$ consists of a 
list of the positions of the 1's in $r$ in decreasing order, 
followed by a list of positions of the 2's in $r$ in decreasing order, etc.

For instance, we consider the example where  $n = 9$, $b_1 =4$, $b_2 =5$, 
$r_1 = s_1 =2$, $r_2 = 2$ and $s_2 =3$.  If the rearrangement 
$r = 1~3~4~2~1~4~3~4~2$, then we would obtain
\begin{center}
$\begin{array}{cclllllllll}
r          & = &1&3&4&2&1&4&3&4&2\,, \\
\sg_r      & = &2&6&9&4&1&8&5&7&3\,, \\
\sg_r^{-1} & = &5&1&9&4&7&2&8&6&3\,.
\end{array}$
\end{center}
Thus such a $\sg_r^{-1}$ corresponds to a legitimate filling of one of the 
rows of a configuration of $F$ in ${\mathcal F}_{T,L,\ell,r_1,s_1,\ldots,r_k,s_k}$.
Since we can reverse the labeling process, it is easy to see the map 
$r \rightarrow \sg_r^{-1}$ is bijection from 
${\mathcal R}(1^{r_1}2^{s_1} 3^{r_2} 4^{s_2} \cdots 
(2k-1)^{r_k}  (2k)^{s_k})$ onto 
${\mathcal F}_{T,r_1,s_1, \ldots, r_k,s_k}$.
Our labeling ensures that 
\begin{align*}
inv(\sg_r) 
&= inv(r) + \sum_{i=1}^k \binom{r_i}{2} + \sum_{i=1}^k \binom{s_i}{2} 
\qquad \text{and}\\
coinv(\sg_r)
&= coinv(r).
\end{align*}
Since $inv(\sg_r) = inv(\sg_r^{-1})$ and $coinv(\sg_r) = coinv(\sg_r^{-1})$, 
it follows that
\begin{align}
\label{FHmult3}
q^{\sum_{i=1}^k \binom{r_i}{2} + \sum_{i=1}^k \binom{s_i}{2}} 
\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{q} 
& = \sum_{\sg \in {\mathcal F}_{T,r_1,s_1, \ldots, r_k,s_k}} q^{inv(\sg)}
\qquad \text{and} \\
\label{FHmult4}
\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{q} 
& = \sum_{\sg \in {\mathcal F}_{T,r_1,s_1, \ldots, r_k,s_k}} q^{coinv(\sg)}.
\end{align}

It follows from \eqref{FHmult3} and \eqref{FHmult4} that if 
we let $\epsilon = x^{r_1}y^{s_1} \cdots x^{r_k}y^{s_k}$, then 
we have the following. 
\begin{lemma}
\label{lem:FHmult1}
\begin{multline*}
X^{r_1+ \cdots + r_k} Y^{s_1 + \cdots + s_k} \prod_{a=1}^L
\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{Q_a} 
Q_a^{\sum_{i=1}^k (\binom{r_i}{2} + \binom{s_i}{2})} 
\prod_{b=1}^{\ell} {\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{q_b}} \\
= X^{\ell(\epsilon |x)} Y^{\ell(\epsilon |y)} 
\sum_{F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)}) 
\in {\mathcal F}_{T,L,\ell,r_1,s_1, \ldots, r_k,s_k}} 
{\bf Q}^{ inv(\Sigma^{(1)}, \ldots, \Sigma^{(L)};\epsilon)} 
{\bf q}^{coinv(\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)}.
\end{multline*}
\end{lemma}

By slightly modify our labeling, we can get an analogue of Lemma 
\ref{lem:FHmult1} where we replace the statistics $inv$ and $coinv$ by 
$FHinv$ and $FHcoinv$ respectively.  That is, it is also that case that 
\begin{equation*}
\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{q} = 
\sum_{r \in {\mathcal R}(1^{s_1}{2}^{s_2} \cdots k^{s_k} (k+1)^{r_1} 
(k+2)^{r_2} \cdots (2k)^{r_k})} q^{inv(r)}.
\end{equation*}

As before, given a rearrangement 
$r \in {\mathcal R}(1^{s_1}{2}^{s_2} \cdots k^{s_k} (k+1)^{r_1} 
(k+2)^{r_2} \cdots (2k)^{r_k})$, we associate a permutation $\sigma_r$ 
by labeling the 1's from right to left with $1, \ldots, s_1$, labeling the 
2's from right to left  with $s_1 +1, \ldots, s_1+s_2$, etc.  As before, 
$\sg_r^{-1}$ consists of a list of the positions of the 1's in $r$ in 
decreasing order, followed by a list of positions of the 2's in $r$ in 
decreasing order, etc.

For example, consider the case where  $n = 9$, $b_1 =4$, $b_2 =5$, 
$r_1 = 1$, $s_1 =3$, $r_2 = 2$ and $s_2 =3$ and where the rearrangement is 
$r = 1~3~1~2~1~4~2~4~2$. Since in the end we want the positions corresponding 
to the $r_i$'s weighted by $X$ and the position of the $s_j$'s weighted by 
$Y$, we place the appropriate $X$ and $Y$ on top of the letters.  Doing this,
we would obtain
\begin{center}
$\begin{array}{cclllllllll}
  &   &Y&X&Y&Y&Y&X&Y&X&Y \\
r & = &1&3&1&2&1&4&2&4&2,
\end{array}$
\end{center}
\begin{center}
$\begin{array}{cclllllllll}
      &   &Y&X&Y&Y&Y&X&Y&X&Y \\
\sg_r & = &3&7&2&6&1&9&5&8&4,
\end{array}$
\end{center}
and
\begin{center}
$\begin{array}{cclllllllll}
           &   &Y&Y&Y&Y&Y&Y&X&X&X \\
\sg_r^{-1} & = &5&3&1&9&7&4&2&8&6.
\end{array}$
\end{center}
At this point $\sg_r^{-1}$ does not correspond to a legitimate filling of 
a configuration of $F \in {\mathcal F}_{T,r_1,s_1, \ldots, r_k,s_k}$ since it 
consists of decreasing sequences of lengths $s_1, \ldots, s_k,r_1,\ldots,r_k$,
respectively.  However, we can easily obtain a legitimate filling of 
a configuration of $F \in {\mathcal F}_{T, r_1,s_1, \ldots, r_k,s_k}$ by simply 
bringing the decreasing sequence corresponding to $r_1$ in front of 
the decreasing sequence corresponding to $s_1$, then bringing the decreasing 
sequence corresponding to $r_2$ immediately in front of the decreasing 
sequence corresponding to $s_2$, etc.  Let us call the result of this 
rearrangement $\sg_r^*$. In our example,
\begin{center}
$\begin{array}{cclllllllll}
           &   &X&Y&Y&Y&X&X&Y&Y&Y \\
\sg_r^{*} & = &2&5&3&1&8&6&9&7&4.
\end{array}$
\end{center}
If we let $\epsilon = y^{s_1 + \cdots + s_k} x^{r_1 + \cdots + r_k}$ and 
$\epsilon^* = x^{r_1} y^{s_1} x^{r_2} y^{s_2} \cdots x^{r_k} y^{s_k}$, then, 
since all the $Y$'s precede all the $X$'s in $\sg_r^{-1}$, we have 
\begin{align*}
\sum_{i=1}^k \binom{r_i}{2} + \sum_{i=1}^k \binom{s_i}{2} + inv(r) 
& = inv(\sg_r) = inv(\sg_r^{-1}) \\
& = inv((\sg_r^{-1})_{\epsilon | x}) + inv((\sg_r^{-1})_{\epsilon | y}) \\
&\kern2cm
+ \sum_{i,j} \chi(\epsilon_i = y, \epsilon_j = x, (\sg_r^{-1})_i > 
(\sg_r^{-1})_j).
\end{align*}
But clearly
\begin{multline*}
inv((\sg_r^{-1})_{\epsilon | x}) + inv((\sg_r^{-1})_{\epsilon | y}) 
+ \sum_{i,j} \chi(\epsilon_i = y, \epsilon_j = x, \ \& \ (\sg_r^{-1})_i > 
(\sg_r^{-1})_j) \\
= inv((\sg_r^*)_{\epsilon^* | x}) + inv((\sg_r^*)_{\epsilon^* | y}) 
+ \sum_{i,j} \chi(\epsilon^*_i = y, \epsilon^*_j = x, \ \& \ (\sg_r^*)_i > 
(\sg_r^*)_j),
\end{multline*}
which in turn is equal to $FHinv(\sg_r^*)$. 
It follows that 
\begin{equation}
\label{FHmult7}
q^{\sum_{i=1}^k \binom{r_i}{2} + \sum_{i=1}^k \binom{s_i}{2}} 
\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{q} 
= \sum_{\sg \in {\mathcal F}_{T,r_1,s_1, \ldots, r_k,s_k}} q^{FHinv(\sg)}.
\end{equation}

We also need to show that 
\begin{equation}
\label{FHmult8}
\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{q} 
= \sum_{\sg \in {\mathcal F}_{T,r_1,s_1, \ldots, r_k,s_k}} q^{FHcoinv(\sg)}.
\end{equation}
In this case, we need a slightly different labeling. That is, it is the case 
that   
\begin{equation*}
\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{q} 
= \sum_{r \in {\mathcal R}(1^{r_1}{2}^{r_2} \cdots k^{r_k} (k+1)^{s_1} 
(k+2)^{s_2} \cdots (2k)^{s_k})} q^{coinv(r)}.
\end{equation*}
As before, given a rearrangement 
$r \in {\mathcal R}(1^{r_1}{2}^{r_2} \cdots k^{r_k} (k+1)^{s_1} 
(k+2)^{s_2} \cdots (2k)^{s_k})$, we can associate a permutation $\sigma_r$ 
by labeling the 1's from right to left with $1, \ldots, r_1$, labeling the 
2's from right to left  with $r_1 +1, \ldots, r_1+r_2$, etc. As before 
$\sg_r^{-1}$ consists of a list of the positions of the 1's in $r$ in 
decreasing order, followed by a list of positions of the 2's in $r$ in 
decreasing order, etc.  

For instance, let us return to our example where $n = 9$, $b_1 =4$, $b_2 =5$, 
$r_1 = 1$, $s_1 =3$, $r_2 = 2$ and $s_2 =3$.  Consider the rearrangement 
$r = 1~3~4~2~3~4~3~4~2$.  Since in the end we want the positions 
corresponding to the $r_i$'s weighted by $X$ and the position of the $s_j$'s 
weighted by $Y$ we shall again place the appropriate $X$ and $Y$ on top of 
the letters. Thus we would obtain
\begin{center}
$\begin{array}{cclllllllll}
  &   &X&Y&Y&X&Y&Y&Y&Y&X \\
r & = &1&3&4&2&3&4&3&4&2,
\end{array}$
\end{center}
\begin{center}
$\begin{array}{cclllllllll}
      &   &X&X&Y&X&Y&X&Y&X&X \\
\sg_r & = &1&6&9&3&5&8&4&7&2,
\end{array}$
\end{center}
and
\begin{center}
$\begin{array}{cclllllllll}
           &   &X&X&X&Y&Y&Y&Y&Y&Y \\
\sg_r^{-1} & = &1&9&4&7&5&2&8&6&3.
\end{array}$
\end{center}
At this point $\sg_r^{-1}$ does not correspond to a legitimate filling of 
a configuration of $F \in {\mathcal F}_{r_1,s_1, \ldots, r_k,s_k}$ since it 
consists of decreasing sequences of lengths $r_1,\ldots, r_k,s_1,\ldots,s_k$,
respectively.  However, we can obtain a legitimate filling of 
a configuration of $F \in {\mathcal F}_{r_1,s_1, \ldots, r_k,s_k}$ by 
placing the decreasing sequence corresponding to $s_1$ immediately after  
the decreasing sequence corresponding to $r_1$, then placing the decreasing 
sequence corresponding to $s_2$ immediately after the decreasing sequence 
corresponding to $r_2$, etc.  Call the result of this rearrangement 
$\sg_r^{**}$.  In our example,
\begin{center}
$\begin{array}{cclllllllll}
           &   &X&Y&Y&Y&X&X&Y&Y&Y \\
\sg_r^{**} & = &1&7&5&2&9&4&8&6&3.
\end{array}$
\end{center}
If we let $\epsilon^\prime = y^{r_1 + \cdots + r_k} x^{s_1 + \cdots + s_k}$ 
and $\epsilon^{**} = x^{r_1} y^{s_1} x^{r_2} y^{s_2} \cdots x^{r_k} y^{s_k}$, 
it is easy to see that since all the $X$'s precede all the $Y$'s in 
$\sg_r^{-1}$, we have 
\begin{align*}
coinv(r) = coinv(\sg_r) &= coinv(\sg_r^{-1}) \\
&= coinv((\sg_r^{-1})_{\epsilon^\prime | x}) + 
coinv((\sg_r^{-1})_{\epsilon^\prime | y}) \\
&\kern2cm
+ \sum_{i,j} 
\chi(\epsilon_i = y, \epsilon_j = x, (\sg_r^{-1})_i > (\sg_r^{-1})_j).
\end{align*}
Clearly,  
\begin{multline*}
coinv((\sg_r^{-1})_{\epsilon^\prime | x}) + 
coinv((\sg_r^{-1})_{\epsilon^\prime | y}) + 
\sum_{i,j} \chi(\epsilon_i = y, \epsilon_j = x, (\sg_r^{-1})_i > 
(\sg_r^{-1})_j) \\
=coinv((\sg_r^{**})_{\epsilon^{**} | x}) + inv((\sg_r^*)_{\epsilon^{**} | y}) 
+ \sum_{i,j} \chi(\epsilon^{**}_i = y, \epsilon^{**}_j = x, (\sg_r^{**})_i 
> (\sg_r^{**})_j),
\end{multline*}
which in turn is equal to $FHcoinv(\sg_r^{**})$.  
Thus, \eqref{FHmult8} is true. 

Since \eqref{FHmult7} and \eqref{FHmult8} have been proved, if 
we let $\epsilon = x^{r_1}y^{s_1} \cdots x^{r_k}y^{s_k}$, then 
we have the following. 
\begin{lemma}
\begin{multline*}
X^{r_1+ \cdots + r_k} Y^{s_1 + \cdots + s_k} \prod_{a=1}^L
\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{Q_a} 
Q_a^{\sum_{i=1}^k (\binom{r_i}{2} + \binom{s_i}{2})} 
\prod_{b=1}^{\ell} {\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{q_b}} \\
= X^{\ell(\epsilon |x)} Y^{\ell(\epsilon |y)} \kern12cm\\
\times
\sum_{F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)}) 
\in {\mathcal F}_{T,L,\ell,r_1,s_1, \ldots, r_k,s_k}} 
{\bf Q}^{FHinv(\Sigma^{(1)}, \ldots, \Sigma^{(L)};\epsilon)} 
{\bf q}^{FHcoinv(\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)}.
\end{multline*}
\end{lemma}

We are in the position to give two different combinatorial interpretations 
for\break $(Q,Q)_n (q,q)_n \xi(p_{n,\nu})$.  Recall that we have already shown
that $(Q,Q)_n (q,q)_n \xi(p_{n,\nu})$ is equal to 
\begin{multline*}
\sum_{\mu \vdash n} (t-1)^{n - \ell(\mu)}  \sum_{T = (b_1, \ldots,b_k)
  \in {\it B}_{\mu,n}} \sum_{r_i+ s_i = b_i} X^{r_1+ \cdots + r_k} 
Y^{s_1 + \cdots + s_k} \\
\times \prod_{a=1}^L \qbin{n}{r_1,s_1, \ldots, r_k,s_k}{Q_a} 
Q^{\sum \binom{r_i}{2} + \sum \binom{s_i}{2}} 
\prod_{b=1}^{\ell}\qbin{n}{r_1,s_1, \ldots, r_k,s_k}{q_b} 
t^{\chi (r_k = b_k)}.
\end{multline*}
We can interpret this equation as follows.  For each brick 
$T = (b_1, \ldots,b_k) \in {\it B}_{\mu,n}$ and for each choice $
r_1,s_1, \ldots, r_k,s_k$ from the sum  $\sum_{r_i+ s_i = b_i}$, the term
\begin{equation*}
X^{r_1+ \cdots + r_k} Y^{s_1 + \cdots + s_k} 
\prod_{a=1}^L \qbin{n}{r_1,s_1, \ldots, r_k,s_k}{Q_a} 
Q^{\sum \binom{r_i}{2} + \sum \binom{s_i}{2}} 
\prod_{b=1}^{\ell} \qbin{n}{r_1,s_1, \ldots, r_k,s_k}{q_b}
\end{equation*}
can be viewed either as the sum 
\begin{equation*}
X^{\ell(\epsilon |x)} Y^{\ell(\epsilon |y)} 
\sum_{F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)}) 
\in {\mathcal F}_{T,L,\ell,r_1,s_1, \ldots, r_k,s_k}} 
{\bf Q}^{inv(\Sigma^{(1)}, \ldots, \Sigma^{(L)};\epsilon)} 
{\bf q}^{coinv(\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)}
\end{equation*}
or the sum 
\begin{equation*}
X^{\ell(\epsilon|x)} Y^{\ell(\epsilon |y)} 
\sum_{F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)}) 
\in {\mathcal F}_{T,L,\ell,r_1,s_1, \ldots, r_k,s_k}} 
{\bf Q}^{FHinv(\Sigma^{(1)}, \ldots, \Sigma^{(L)};\epsilon)} 
{\bf q}^{FHcoinv(\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)}
\end{equation*}
where $\epsilon = x^{r_1}y^{s_1} \cdots x^{r_k}y^{s_k}$.  

Now, if $s_k \neq 0$, then we have a factor of $(t-1)^{n - \ell(\mu)}$. For 
each 
$$F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$$ 
in 
${\mathcal F}_{T,L,\ell,r_1,s_1, \ldots, r_k,s_k}$, we create a new set of 
weighted  
objects by placing a $t$ or a $-1$ in cell of $T$ which is not at the end of a
brick and placing a 1 in each cell which at the end of the brick. 

For example, if we let $T=(4,5)$ and $r_1 =2$, $s_1 =2$, $r_2= 2$ and 
$s_2 = 3$, then we would obtain configuration $C$ as pictured in 
Figure \ref{splitbrick2}.  
We then let $w(C)$ be the product of the all the $-1$'s, $t$'s, $X$'s and 
$Y$'s appearing in the configuration. For the configuration 
appearing Figure \ref{splitbrick2}, $w(C) = -t^4 X^4 Y^5$. 

\begin{figure}
\fig{FHfig3}
\caption{A combinatorial object.}
\label{splitbrick2}
\end{figure}

If $s_k = 0$ so that $r_k = b_k$, we have a factor of 
$t (t-1)^{n - \ell(\mu)}$.  As before, for each member 
$F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$ of the set 
${\mathcal F}_{T,L,\ell, r_1,s_1, \ldots, r_k,s_k}$, we 
create a new set of weighted objects by placing a $t$ or a $-1$ in cell of 
$T$ which is not at the end of a brick and placing a 1 in each cell which at 
the end of the brick which is not the final brick and placing a $t$ in the 
last cell of the final brick. 

For example, if we let $T=(4,5)$ and $r_1 =2$, $s_1 =2$, $r_2= 5$ and 
$s_2 = 0$, then we would obtain configuration $C'$ as pictured 
in Figure \ref{another figure}.  
Let $w(C')$ be the product of the all the $-1$'s, $t$'s, $X$'s and 
$Y$'s appearing in the configuration.  For the configuration below, 
$w(C') = t^5 X^7 Y^2$.

\begin{figure}
\fig{FHfig4}
\caption{A configuration similar to Figure \ref{splitbrick2}
but with a slightly different labeling.}
\label{another figure}
\end{figure}

Let ${\mathcal C}_{T,L,\ell,r_1,s_1, \ldots, r_k,s_k}$ denote the 
set of all configurations $C$ as constructed from elements \\
$F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$ of the set
${\mathcal F}_{T,L,\ell,r_1,s_1, \ldots, r_k,s_k}$ and let 
\begin{equation*}
{\mathcal C}_n 
= \bigcup_{\mu \vdash n} 
\bigcup_{T = (b_1, \ldots,b_k) \in {\it B}_{\mu,n}} 
\bigcup_{r_i+s_i = b_i} 
{\mathcal C}_{T,L, \ell, r_1,s_1, \ldots, r_k,s_k}.
\end{equation*}
Define two different weights on configurations $C \in {\mathcal C}_n$.  
If $C \in {\mathcal C}_{T,L, \ell, r_1,s_1, \ldots, r_k,s_k}$ is constructed from 
$F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)}) 
\in {\mathcal F}_{T,r_1,s_1, \ldots, r_k,s_k}$, let 
\begin{align*}
U_1(C) 
& = w(C){\bf Q}^{FHinv(\Sigma^{(1)}, \ldots, \Sigma^{(L)};\epsilon)} 
{\bf q}^{FHcoinv(\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)} 
\qquad \text{and} \\
U_2(C) & = w(C) {\bf Q}^{inv(\Sigma^{(1)}, \ldots, \Sigma^{(L)};\epsilon)} 
{\bf q}^{coinv(\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)} 
\end{align*}
where $\epsilon = x^{r_1}y^{s_1} \cdots x^{r_k}y^{s_k}$. 
It follows that 
\begin{align}
\label{interp1}
(Q,Q)_n (q,q)_n \xi(p_{n,\nu}) & = \sum_{C \in {\mathcal C}_n} U_1(C)
\qquad \text{and} \\
\nonumber 
(Q,Q)_n (q,q)_n \xi(p_{n,\nu}) & = \sum_{C \in {\mathcal C}_n} U_2(C).
\end{align}

It follows from \eqref{eq:FH4} and \eqref{interp1} that to prove 
Theorem \ref{thm:FH1}, we need to show that
\begin{equation}
\label{FH13}
\sum_{C \in {\mathcal C}_n} U_1(C) = W_n^{(1)}(X,Y,t,{\bf Q},{\bf q})
\end{equation}
Similarly, to prove Theorem \ref{thm:FH-var}, we need to show that 
\begin{equation}
\label{FH14}
\sum_{C \in {\mathcal C}_n} U_2(C) 
= W_n^{(2)}(X,Y,t,{\bf Q},{\bf q}).
\end{equation}
To prove both \eqref{FH13} and \eqref{FH14}, we will define a sign-reversing 
weight-preserving involution $I$ on ${\mathcal C}_n$ so that the fixed points of 
$I$ will give the desired right hand side of \eqref{FH13} or \eqref{FH14}. 
In fact, the same involution will work for both \eqref{FH13} or \eqref{FH14}. 

Suppose that $C$ is constructed from 
$$F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)}) 
\in {\mathcal F}_{T,L,\ell,r_1,s_1, \ldots, r_k,s_k},$$ 
then 
we say that a sequence of cells in $c,c+1, \ldots, c+k$ in $C$ forms
a decreasing sequence if the following three things happen: 
\begin{itemize}
\item[(i)] the labels at the top of the cells $c,c+1, \ldots, c+k$ when 
read from left to right is a word of the form $X^u Y^v$ for some 
$u,v \geq 0$, 

\item[(ii)] the entries in each of the rows corresponding to 
$\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)}$ are 
decreasing in cells whose label is $X$, i.e., in cells 
$c,c+1, \ldots, c+{u-1}$, and 

\item[(iii)] the entries in each of the rows corresponding to 
$\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)}$ are 
decreasing in cells whose label is $Y$, i.e., in cells 
$c+u,c+u+1, \ldots, c+{u+v-1}$. 
\end{itemize}
By definition, the cells corresponding to each brick in a configuration 
$C \in {\mathcal C}_n$ form a decreasing sequence.  

We define the involution $I$ as follows.  Given $C \in {\mathcal C}_n$, scan the 
cells of the $C$ from left to right until either 
\begin{itemize}
\item Case 1: there is a cell $c$ with a $-1$ in which case $I(C)$ is 
the result of changing the weight cell $c$ to 1 and breaking the brick $b_i$ 
which contains cell $c$ into two bricks $b'$ and $b''$ where $b'$ ends at cell
$c$, or  
\item Case 2: we find two consecutive bricks $b_i$ and $b_{i+1}$ such that 
cells corresponding to $b_i$ and $b_{i+1}$ form a decreasing sequence in which
case $I(C)$ is the result of replacing bricks $b_i$ and $b_{i+1}$ by a 
single brick $b$ and changing the weight of the last cell of $b_i$ from $1$ to
$-1$. 
\end{itemize}
If neither Case 1 or Case 2 holds, then define $I(C) =C$. 

For example, if we consider the configuration $C$ pictured in 
Figure \ref{splitbrick2}, then we are Case 1 with cell $c$ equal to 
cell 3 so that $I(C)= C'$ where $C'$ is pictured in Figure \ref{splitbrick4}.
However, $C'$ is in Case 2 because we can combine bricks $b_1$ and $b_2$ so 
that $I(C')$ is equal to $C$. 
 
\begin{figure}
\fig{FHfig5}
\caption{The image of Figure \ref{splitbrick2} under $I$.}
\label{splitbrick4}
\end{figure}

The definition of $I$ is designed so that the only change is the total number
of bricks.  The underlying
permutations $(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$ remain 
unchanged.  Moreover, since we do not change any of the labels at the top of 
the column, it follows that if cell $n$ has an $X$ at the top of the column, 
then the last brick of both $C$ and $I(C)$ must contain all $X$'s since 
the cells in each brick must form a decreasing sequence and hence the 
weight of the final cell in both $C$ and $I(C)$ is equal to $t$. 

Our definitions ensure that if $I(C) \neq C$, then $U_1(C) = - U_1(I(C))$, 
$U_2(C) = - U_2(I(C))$, and $I(I(C)) = C$.  Let 
$Fix_I = \{C \in {\mathcal C}_n: I(C) = C\}$.  Then $I$ shows that 
\begin{align*}
\sum_{C \in {\mathcal C}_n} U_1(C) & = \sum_{C \in Fix_I} U_1(C), 
\qquad \text{and}  \\
\sum_{C \in {\mathcal C}_n} U_2(C) & = \sum_{C \in Fix_I} U_2(C).
\end{align*}

Consider the fixed points of $I$. Suppose that $C \in Fix_I$ and $C$ is 
constructed from an element 
$F = (\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$ of the set
${\mathcal F}_{T,L,\ell,r_1,s_1, \ldots, r_k,s_k}$.  No cell of $C$ can have label 
$-1$ and the sequence of cells in any two consecutive bricks do not form a 
decreasing sequence.  This means that if $b_i$ and $b_{i+1}$ are two 
consecutive bricks in $C$, $s$ is last cell in $b_i$, $s+1$ is the first cell 
of $b_{i+1}$, and $\epsilon = x^{r_1}y^{s_1}\cdots x^{r_k}y^{s_k}$, then 
either 
\begin{itemize}
\item $\epsilon_s =y$ and $\epsilon_{s+1} =x$, 
\item $\epsilon_s =x$ and $\epsilon_{s+1} =x$ and there is some $i$ such that
$\Sigma^{(i)}(s) < \Sigma^{(i)}(s+1)$ or there is some $j$ such that 
$\sigma^{(j)}(s) < \sigma^{(j)}(s+1)$, or 
\item $\epsilon_s =y$ and $\epsilon_{s+1} =y$ and there is some $i$ such that 
$\Sigma^{(i)}(s) < \Sigma^{(i)}(s+1)$ or there is some $j$ such that 
$\sigma^{(j)}(s) < \sigma^{(j)}(s+1)$.
\end{itemize}
It follows that $s$ is not a member of $Comdes(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$ and that the weight of cell $s$ is 
1.  If $s =n$, then $s \in Comdes(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$ if and only if $\epsilon_n = x$. 
Thus if $\epsilon_n =y$, $s$ is not an element of 
$Comdes(\Sigma^{(1)}, \ldots, \Sigma^{(L)},
\sigma^{(1)}, \ldots, \sigma^{(\ell)})$ and the weight of cell $s$ is 1.  If 
$\epsilon_n =x$, $s \in Comdes(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$ and that the weight of cell $s$ is $t$.
If $s$ is not the last cell of a brick, then our definitions ensure 
that $s \in Comdes(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$ and that the weight of cell $s$ is $t$.  Therefore  
$w(C) = t^{comdes({\bf \Sigma},{\bf \sigma};\epsilon)}$. 
Thus if $C \in Fix_I$ and $C$ is constructed from 
a member of ${\mathcal F}_{T,L,\ell,r_1,s_1, \ldots, r_k,s_k}$, then 
\begin{align*}
U_1(C) & = 
t^{comdes({\bf \Sigma},{\bf \sigma};\epsilon)} 
{\bf Q}^{FHinv({\bf \Sigma},{\bf \sigma};\epsilon)} 
{\bf q}^{FHcoinv({\bf \Sigma},{\bf \sigma};\epsilon)}, \qquad \text{and} \\
U_2(C) & = t^{comdes({\bf \Sigma},{\bf \sigma};\epsilon)} 
{\bf Q}^{inv({\bf \Sigma},{\bf \sigma};\epsilon)} 
{\bf q}^{coinv({\bf \Sigma},{\bf \sigma};\epsilon)}. \\
\end{align*}

Finally, if we are given 
$({\bf \Sigma},{\bf \sigma};\epsilon) = 
(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)$, then 
we can construct a configuration $C \in Fix_I$ such that 
\begin{align*}
U_1(C) &=  t^{comdes({\bf \Sigma},{\bf \sigma};\epsilon)} 
{\bf Q}^{FHinv({\bf \Sigma},{\bf \sigma};\epsilon)} 
{\bf q}^{FHcoinv({\bf \Sigma},{\bf \sigma};\epsilon)} \qquad \text{and} \\
U_2(C) & =  t^{comdes({\bf \Sigma},{\bf \sigma};\epsilon)} 
{\bf Q}^{inv({\bf \Sigma},{\bf \sigma};\epsilon)} 
{\bf q}^{coinv({\bf \Sigma},{\bf \sigma};\epsilon)}
\end{align*}
as follows.  Let rows of $C$ correspond the sequence of permutations 
$$(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)}:\epsilon)$$ 
and 
label the top of column $i$ with $X$ if $\epsilon_i =x$ and with $Y$ if 
$\epsilon_i =y$.  Next, let 
$$E= \{1, \ldots, n-1\}- Comdes(\Sigma^{(1)}, 
\ldots, 
\Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)}).$$ If $E = \emptyset$, then $C$ has a 
single brick of length $n$ and if $E= \{i_1 < \cdots < i_k\}$, then we have 
bricks ending at $i_1,\ldots,i_k,n$. Then we label each cell $i$ with a $t$ if 
$i \in Comdes(\Sigma^{(1)}, \ldots,\break \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$ and
with a 1 if 
$i \notin Comdes(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, 
\sigma^{(\ell)})$ and $i \neq n$. We label the last cell with a 1 if 
the last cell has a $Y$ at the top of the column and with $t$ is the last cell has an $X$ at the top of the column. It is then easy to check that $C \in Fix_I$.  It follows that
\begin{align*}
\sum_{C \in {\mathcal C}_n} U_1(C) 
& = \sum_{C \in Fix_I} U_1(C) 
= W_n^{(1)}(X,Y,t,{\bf Q},{\bf q}) \qquad \text{and} \\
\sum_{C \in {\mathcal C}_n} U_2(C) 
& = \sum_{C \in Fix_I} U_2(C) 
= W_n^{(2)}(X,Y,t,{\bf Q},{\bf q})
\end{align*}
as desired. This completes the proof of Theorems \ref{thm:FH1} and 
\ref{thm:FH-var}.

In the next section, we shall show how we can modify this proof to 
prove a whole family of extensions of Theorem \ref{thm:FH1} and 
\ref{thm:FH-var} to groups of the form $C_k \wr S_n$. 

\section{Permutation Statistics and Generating Functions for $C_k \wr S_n$} 

For the rest of the paper, assume $k \geq 2$.  An element of $C_k \wr S_n$ is 
a pair $(\sg,\epsilon)$ where $\sg \in S_n$ and 
$\epsilon \in \{x_1, \ldots,x_k\}^n$.  Define the following statistics on 
$C_k \wr S_n$.  For $1 \leq d \leq k$, we call $i$ a descent of type $d$ of 
$(\sg,\epsilon)$ if either 
\begin{itemize}
\item[(i)] $\epsilon(i) = \epsilon(i+1)$ and $\sg_i > \sg_{i+1}$, 
\item[(ii)] $\epsilon(i) = x_s$ and $\epsilon(i+1) = x_t$ where $s < t$, or 
\item[(iii)] $i = n$ and $\epsilon(n) \in \{x_1, \ldots, x_d\}$.
\end{itemize}
A pair $(i,j)$ is a FH-inversion (respectively FH-coinversion) of $(\sg,\epsilon)$ if 
\begin{itemize}
\item[(i)]  $i < j$, $\epsilon(i) = \epsilon(j)$ and $\sg_i > \sg_{j}$  
(respectively $\sg_i < \sg_{j}$), or 
\item[(ii)] $\epsilon(i) = x_t$ and $\epsilon(j) = x_s$ where $t > s$  and 
$\sg_i > \sg_{j}$.
\end{itemize}
A pair $(i,j)$ is an inversion (respectively coinversion) of $(\sg,\epsilon)$ if $i < j$ 
and $\sg_i > \sg_j$ (respectively $\sg_i < \sg_j$), i.e. we say that $(i,j)$ is an 
inversion (respectively coinversion) of $(\sg,\epsilon)$ if it is an inversion 
(respectively coinversion) of $\sigma$. 

Let $Des^d(\sg,\epsilon)$ denote the set of all descents of type $d$ for 
elements $(\sg, \epsilon) \in C_k \wr S_n$. 

The restriction of $(\sg,\epsilon)$ to its $x_i$ part will be denoted  
$\sg_{\epsilon | x_i}$ for $i = 1, \ldots, k$.  The inverses to these sequences
will be denoted $\sg^{-1}_{\epsilon | x_i}$.  These are found in the same 
manner as displayed in the second 2.  Let 
\begin{equation*}
\overline{inv}(\sg_{\epsilon | x_1}, \ldots, \sg_{\epsilon | x_k}) = 
|\{ (i,j): \epsilon(i) = x_t, \epsilon(j) = x_s, t > s, \sg_i > \sg_{j}\}|
\end{equation*}
This given, we define the following two statistics for elements 
$(\sg, \epsilon) \in C_k \wr S_n$. 
\begin{align*}
imaj(\sg, \epsilon) & =  \overline{inv}(\sg_{\epsilon | x_1}, \ldots, 
\sg_{\epsilon | x_k}) + \sum_{i=1}^k maj((\sg^{-1})_{\epsilon | x_i}) \\
icomaj(\sg, \epsilon) & =  \overline{inv}(\sg_{\epsilon | x_1}, \ldots, 
\sg_{\epsilon | x_k}) + \sum_{i=1}^k comaj((\sg^{-1})_{\epsilon | x_i}).
\end{align*}

Our definitions imply that
\begin{align*}
FHinv(\sg, \epsilon) 
& = \overline{inv}(\sg_{\epsilon | x_1}, \ldots \sg_{\epsilon | x_k}) +
\sum_{i=1}^k inv(\sg_{\epsilon | x_i}), \\
FHcoinv(\sg, \epsilon) 
& = \overline{inv}(\sg_{\epsilon | x_1}, \ldots \sg_{\epsilon | x_k}) +
\sum_{i=1}^k coinv(\sg_{\epsilon | x_i}), \\
inv(\sg, \epsilon) & = inv(\sg), \qquad \text{and} \qquad 
coinv(\sg, \epsilon) =  coinv(\sg). 
\end{align*}

We will write $(\sg^{(1)}, \sg^{(2)}, \ldots, \sg^{(k)}; \epsilon)$ for the sequence of 
elements 
$$(\sg^{(1)},\epsilon), (\sg^{(2)},\epsilon), \ldots, (\sg^{(k)},\epsilon)$$ 
of 
$C_k \wr S_n$.  For each $1 \leq d \leq k$, let 
\begin{multline*}
Comdes^d((\sg^{(1)},\epsilon), (\sg^{(2)},\epsilon), \ldots, (\sg^{(k)},\epsilon)) \\=  
Comdes^d(\sg^{(1)}, \sg^{(2)}, \ldots, \sg^{(k)};\epsilon) =  
\bigcap_{i} Des^d(\sg^{(i)},\epsilon) 
\end{multline*}
and 
\begin{align*}
comdes^d((\sg^{(1)},\epsilon), (\sg^{(2)},\epsilon), \ldots, (\sg^{(k)},\epsilon)) &=  
comdes^d(\sg^{(1)}, \sg^{(2)}, \ldots, \sg^{(k)};\epsilon)\\
&=  
|Comdes^d(\sg^{(1)}, \sg^{(s)}, \ldots, \sg^{(k)};\epsilon)|.
\end{align*}

We will employ the same convention as found in \eqref{eqn:1}, namely, if
${\bf \Sigma} = (\Sigma^{(1)}, \ldots, \Sigma^{(L)})$ is a sequence of permutations
in $C_k \wr S_n$, then we let
\begin{equation*}
{\bf Q}^{inv ({\bf \Sigma};\epsilon)} = \prod_{i = 1}^L Q_i^{inv (\Sigma^{(i)},
\epsilon)} \ \mbox{and} \ {\bf q}^{inv ({\bf \sigma};\epsilon)} = \prod_{i = 1}^{\ell} q_i^{inv (\sigma^{(i)},\epsilon)}
\end{equation*}
where $inv$ may be replaced with any other statistic.  If 
${\bf \Sigma} = (\Sigma^{(1)}, \ldots, \Sigma^{(L)})$ and 
${\bf \sg} = (\sg^{(1)},\dots,\sg^{(\ell)})$ are lists of elements in $S_n$, we let 
$({\bf \Sigma},{\bf \sg}; \epsilon) = 
(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sg^{(1)},\dots,\sg^{(\ell)}; \epsilon)$.  

Our $C_k \wr S_n$ 
analogues of $W^{(1)}$,$W^{(2)}$, and $W^{(3)}$ are:
\begin{align*}
W^{(1,d)}_n(X,Y,t,{\bf Q},{\bf q}) & = 
\sum_{({\bf \Sigma},{\bf \sg};\epsilon)} \left( \prod_{i=1}^k 
X_i^{\ell({\epsilon | x_i})} \right)
 t^{comdes^d({\bf \Sigma},{\bf \sg};\epsilon)} 
{\bf Q}^{FHinv({\bf \Sigma};\epsilon)} 
{\bf q}^{FHcoinv({\bf \sg};\epsilon)},  \\
W^{(2,d)}_n(X,Y,t,{\bf Q},{\bf q}) & =
\sum_{({\bf \Sigma},{\bf \sg};\epsilon)} 
\left( \prod_{i=1}^k X_i^{\ell({\epsilon | x_i})}  \right)
t^{comdes^d({\bf \Sigma},{\bf \sg};\epsilon)} 
{\bf Q}^{inv({\bf \Sigma};\epsilon)} 
{\bf q}^{coinv({\bf \sg};\epsilon)}, \qquad \text{and} \\
W^{(3,d)}_n(X,Y,t,{\bf Q},{\bf q}) & = 
\sum_{({\bf \Sigma},{\bf \sg};\epsilon)} \prod_{i=1}^k 
\left( X_i^{\ell({\epsilon | x_i})} \right)
t^{comdes^d({\bf \Sigma},{\bf \sg};\epsilon)} 
{\bf Q}^{imaj({\bf \Sigma};\epsilon)} 
{\bf q}^{icomaj({\bf \sg},\epsilon)}
\end{align*}
where the sums run over all $\epsilon \in \{x_1, \ldots, x_k\}^n$ and all 
$(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sg^{(1)}, \ldots,\sg^{(\ell)}) \in (C_k \wr S_n)^{L+\ell}$. 
Our next theorem gives a family of generating functions which can be viewed as natural analogues of Theorem \ref{thm:FH1}  for $C_k \wr S_n$. 
\begin{theorem} 
\label{thm:kNew1}
For $i =1$, $i = 2$ and $d = 1, \ldots, k$, 
\begin{equation*}
\sum_{n \geq 0} 
\frac{ W^{(i,d)}_n(X,Y,t,{\bf Q},{\bf q})u^n}
{ ({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n} = 
\frac{(1-t) \prod_{i=1}^d J((1-t)X_iu; {\bf Q}, {\bf q})}{-t + 
\prod_{j=1}^k J((1-t)X_j u; {\bf Q}, {\bf q})}.
\end{equation*}
\end{theorem}

The fact that $W^{(1,d)}_n(X,Y,t,{\bf Q},{\bf q}) 
= W^{(3,d)}_n(X,Y,t,{\bf Q},{\bf q})$ can be proved using the same bijection 
that Foata and Han used to prove Theorem \ref{thm:FH2}, implying that 
Theorem \ref{thm:kNew1} holds when $i = 3$ as well. 

We will prove a more general theorem than Theorem \ref{thm:kNew1} which may 
be specialized to give Theorem \ref{thm:kNew1} for either $i=1$ or $i=2$.  Fix 
nonnegative integers $L_1$, $L_2$, $L$, $\ell_1$, $\ell_2$, and $\ell$ such 
that $L_1 + L_2 = L$ and $\ell_1 + \ell_2 = \ell$.  Let
\begin{align*}
W^{(4,d)}_n(X_1,\ldots,X_k,t,{\bf Q},{\bf q}) 
& = \sum_{({\bf \Sigma},{\bf \sg};\epsilon)} \left( \prod_{i=1}^k 
X_i^{\ell({\epsilon | x_i})}  \right) 
t^{comdes^d({\bf \Sigma},{\bf \sg};\epsilon)} 
\prod_{i=1}^{L_1} Q_i^{FHinv(\Sigma^{(i)},\epsilon)} \\
& \qquad \times \prod_{i=L_1+1}^L Q_i^{inv(\Sigma^{(i)},\epsilon)}  
\prod_{i=1}^{\ell_1} q_i^{FHcoinv(\sigma^{(i)},\epsilon)}  
 \prod_{i=1+\ell_1}^{\ell} q_i^{coinv(\sigma^{(i)},\epsilon)} 
\end{align*}
where the sums run over all $\epsilon \in \{x_1, \ldots, x_k\}^n$ and all 
$(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sg^{(1)}, \ldots,\sg^{(\ell)}) \in (C_k \wr S_n)^{L+\ell}$. 
We shall prove the following result. 
\begin{theorem} 
\label{thm:kNew2}
For $d = 1, \ldots, k$, 
\begin{equation*}\label{eq:kNew2}
\sum_{n \geq 0} \frac{ W^{(4,d)}_n(X,Y,t,{\bf Q},{\bf q})u^n}
{ ({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n} 
= \frac{(1-t) \prod_{i=1}^d J((1-t)X_i u; {\bf Q}, {\bf q})}{-t + 
\prod_{j=1}^k J((1-t)X_j u; {\bf Q}, {\bf q})}.
\end{equation*}
\end{theorem}

\begin{proof}
Our idea is that for each $d =1, \ldots, k$ the identity in the statement of 
the theorem should be the result of applying a homomorphism $\xi_{d}$ to the 
identity found in \eqref{fund} for an appropriate function $\nu_d$. Indeed, 
there is a single homomorphism $\xi$ that works for all $d$.  However, the weighting
function $\nu_d$ does vary as $d$ varies.  

As before, we can read what the required homomorphism $\xi$ and the required 
function $\nu_d$ are from directly from the right hand side of statement of the 
Theorem \ref{thm:kNew2}.  This is we can rewrite (\ref{eq:kNew2}) as follows:
\begin{equation*}
\frac{ 1+ \sum_{n \geq 1} (-1) ^n u^n (1-t)^n \sum_{a_i \geq 0, a_1 + 
\cdots + a_d = n} \prod_{i=1}^d
\frac{ X_i^{a_i}{\bf Q}^{\binom{a_i}{2}}}{({\bf Q},{\bf Q})_{a_i} 
({\bf q},{\bf q})_{a_i}}}{1 + \sum_{n \geq 1} (-1)^n u^n  (1-t)^{n-1} 
\sum_{f_i \geq 0, f_1+ \cdots + f_k =n} \prod_{j=1}^k 
\frac{ X_i^{f_i} {\bf Q}^{\binom{f_i}{2}}}{({\bf Q},{\bf Q})_{f_i} 
({\bf q},{\bf q})_{f_i}}}.
\end{equation*}
This suggests that for $d=1, \ldots, k$, we should set 
\begin{align*}
\xi(e_n) 
& = (1-t)^{n-1}  \sum_{f_j \geq 0, f_1 + \cdots + f_k = n} \prod_{j=1}^k 
\frac{ X^{f_i} {\bf Q}^{\binom{f_i}{2}}}{({\bf Q},{\bf Q})_{f_i} 
({\bf q},{\bf q})_{f_i}} \qquad \text{and} \\
\xi(e_n) - \nu_d(n) \xi(e_n) 
& = \frac{(1-t)^n \sum_{a_i\geq 0, a_1 + \cdots + a_d =n} \prod_{i=1}^d 
X^{a_i} {\bf Q}^{\binom{n}{2}}}{({\bf Q},{\bf Q})_{a_i} 
({\bf q},{\bf q})_{a_i}},
\end{align*}
so that $\nu_d(n)$ is equal to 
\begin{equation*}
1 - \frac{(1-t)^{n-1} \sum_{a_i \geq 0, a_1+ \cdots + a_d = n} 
\prod_{i=1}^d X_i^n {\bf Q}^{\binom{a_i}{2}}}
{\xi(e_n) ({\bf Q},{\bf Q})_{a_i} ({\bf q},{\bf q})_{a_i}} 
+ \frac{t(1-t)^{n-1} \sum_{a_i \geq 0, a_1+ \cdots + a_d = n} 
{\prod_{i=1}^d X_i^{a_i} {\bf Q}^{\binom{a_i}{2}}}}
{\xi(e_n) ({\bf Q},{\bf Q})_{a_i} ({\bf q},{\bf q})_{a_i}} 
\end{equation*}

Therefore, to prove Theorem \ref{thm:kNew2}, we will show that
\begin{equation*}
\xi(p_{n,\nu_d}) = \frac{W_n^{(4,d)}(X,Y,t,{\bf Q},{\bf q})}{({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n}
\end{equation*}
or, equivalently, 
\begin{equation}
\label{eq:kFH4}
({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \xi(p_{n,\nu_d}) 
= W_n^{(4,d)}(X,Y,t,{\bf Q},{\bf q}).
\end{equation}

We begin by using \eqref{equation:weighted} to express $p_{n,\nu_d}$ in terms 
of the elementary symmetric functions: 
\begin{align*} 
({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \xi(p_{n,\nu_d}) 
& = ({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \sum_{\mu \vdash n} 
(-1)^{n - \ell(\mu)} w_\nu(B_{\mu,n}) \xi(e_\mu) \\
& = \sum_{\mu \vdash n} (-1)^{n - \ell(\mu)} \sum_{T = (b_1, \ldots,b_m) 
\in {\it B}_{\mu,n}}  ({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \nu_d(b_m) 
\prod_{s=1}^m \xi(e_{b_s}).
\end{align*}

Focusing on the $({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \nu_d(b_m) 
\prod_{s=1}^m \xi(e_{b_s})$ term, we have for $s < m$,  
\begin{equation*}
\xi(e_{b_s}) 
= (1-t)^{b_s-1} \sum_{f_j \geq 0, f_1+ \cdots + f_k =b_{s}} 
\prod_{j=1}^k\frac{ X_j^{f_j} {\bf Q}^{\binom{f_j}{2}}}
{({\bf Q},{\bf Q})_{f_j} ({\bf q},{\bf q})_{f_j}}.
\end{equation*}
For $s=m$, we have $\xi(e_{b_m}) \nu_d(b_m)$ is equal to
\begin{multline*}
 \xi(e_{b_m}) \frac{1}{\xi(e_{b_m})} \left( \xi(e_{b_m}) - 
(1-t)^{b_m-1} \sum_{a_i \geq 0, a_1 + \cdots a_d =b_m} 
\prod_{i=1}^d \frac{X_i^{a_i} {\bf Q}^{\binom{a_i}{2}}}
{({\bf Q},{\bf Q})_{a_i} ({\bf q},{\bf q})_{a_i}} \right. \\
\left. + t(1-t)^{b_m-1} \sum_{a_i \geq 0, a_1 + \cdots a_d =b_m} 
\prod_{i=1}^d\frac{X^{a_i} {\bf Q}^{\binom{a_i}{2}}}
{({\bf Q},{\bf Q})_{a_i} ({\bf q},{\bf q})_{a_i}} \right)
\end{multline*}
which in turn is equal to 
\begin{multline*}
(1-t)^{b_m-1}  \sum_{(f_1, \ldots,f_k) \in A_d(b_m)} 
\prod_{j=1}^k\frac{X^{f_j} {\bf Q}^{\binom{f_j}{2}}}
{({\bf Q},{\bf Q})_{f_j} ({\bf q},{\bf q})_{f_j}} \\+
t (1-t)^{b_m-1} 
\sum_{(f_1, \ldots,f_k) \in B_d(b_m)} 
\prod_{j=1}^k\frac{X^{f_j} {\bf Q}^{\binom{f_j}{2}}}
{({\bf Q},{\bf Q})_{f_j} ({\bf q},{\bf q})_{f_j}} 
\end{multline*}
where 
\begin{itemize}
\item[(i)] $A_d(b_m)$ is the set of $k$-tuples $(f_1, \ldots, f_k)$ such 
that $\sum_{j=1}^k f_j = b_m$ and at least one of $f_{d+1}, \ldots f_d$ is 
nonzero, and
\item[(ii)] $B_d(b_m-1)$ is the set of all tuples $(f_1, \ldots, f_k)$ such 
that $\sum_{j=1}^k f_j = b_m$ and $f_{d+1} = \cdots = f_d = 0$. 
\end{itemize}

The effect of taking the weight $\xi(e_{b_m})$ versus the 
weight $\nu_d(b_m) \xi(e_{b_m})$ is that the terms corresponding 
to the sequences $(f_1, \ldots, f_k)$ where 
 $f_{d+1}= \cdots = f_d = 0$ in the summand for $\xi(e_{b_m})$ are of the 
form  
\begin{equation*}
(1-t)^{b_m-1} \prod_{j=1}^k\frac{X^{f_j} {\bf Q}^{\binom{f_j}{2}}}
{({\bf Q},{\bf Q})_{f_j} ({\bf q},{\bf q})_{f_j}}
\end{equation*}
while the corresponding sequences in the summand for  
$\nu_d(b_m) \xi(e_{b_m})$ have an extra factor of $t$, 
\begin{equation*}
t (1-t)^{b_m-1} \prod_{j=1}^k\frac{X^{f_j} {\bf Q}^{\binom{f_j}{2}}}
{({\bf Q},{\bf Q})_{f_j} ({\bf q},{\bf q})_{f_j}}.
\end{equation*}
Therefore $({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \xi(p_{n,\nu})$ is equal to
\begin{multline*}
\sum_{\mu \vdash n} (-1)^{n - \ell(\mu)} \sum_{T = (b_1, \ldots,b_m) \in 
{\it B}_{\mu,n}} \sum_{f^i_j \geq 0, f^i_1 + \cdots f^i_k = b_i} 
(1-t)^{n-\ell(\mu)} \left( \prod_{t=1}^k X_t^{f^1_t +\cdots + f^m_t}\right)  
{\bf Q}^{\sum_{i=1}^m \sum_{j=1}^k \binom{f^i_j}{2}} \\
\times \frac{({\bf Q},{\bf Q})_n}
{\prod_{i=1}^m \prod_{j=1}^k ({\bf Q,\bf Q})_{f_j^i}} 
\frac{({\bf q},{\bf q})_n}{\prod_{i=1}^m \prod_{j=1}^k  
({\bf q},{\bf q})_{f_j^i}} t^{\chi (f^m_{d+1} + \cdots + f^m_{k} = 0)}
\end{multline*}
which in turn is equal to
\begin{multline*}
 \sum_{\mu \vdash n} (t-1)^{n - \ell(\mu)} \sum_{T = (b_1, \ldots,b_m) \in 
{\it B}_{\mu,n}} \sum_{f^i_j \geq 0, f^i_1 + \cdots f^i_k = b_i} 
\left( \prod_{t=1}^k X_t^{f^1_t +\cdots + f^m_t}\right)
t^{\chi (f^m_{d+1} + \cdots + f^m_{k} = 0)} \\
\times \prod_{a=1}^L \qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1,\ldots,f^m_k}
{Q_a} Q_a^{\sum_{i=1}^m \sum_{j=1}^k \binom{f^i_j}{2}} \prod_{b=1}^{\ell}
{\qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1,\ldots, f^m_k}{q_b}}.
\end{multline*}

Fix a brick tabloid $T = (b_1, \ldots,b_m) \in {\it B}_{\mu,n}$ and a 
sequence $f^1_1, \ldots, f^1_k,\ldots, f^m_1, \ldots, f^m_k$ such 
that for all $i =1, \ldots, k$, $f^i_1 + \cdots f^i_k = b_i$. 
As in our proofs of Theorem \ref{thm:FH1} and Theorem \ref{thm:FH-var}, the first step is to give a 
combinatorial interpretation to the term  
\begin{multline}
\label{kFHmult}
\prod_{i=1}^m X_i^{\sum_{j=1}^k f^i_j} \prod_{a=1}^L
\qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}{Q_a} 
Q_a^{\sum_{i=1}^m \sum_{j=1}^k \binom{f^i_j}{2}} 
\\
\times\prod_{b=1}^{\ell} 
\qbin{n}{f^1_1, \ldots, f^1_k,\ldots, f^m_1, \ldots, f^m_k}{q_b}. 
\end{multline}

Take the brick tabloid $T = (b_1, \ldots, b_m)$ and divide each brick $b_i$
into pieces of size $f^i_1, \ldots, f^i_k$ reading from left to right.  Place 
$X_j$'s at the top of all the cells corresponding to $f^1_j,\ldots, f^m_j$ for
$j=1, \ldots k$.  Further divide the brick tabloid $T$ into $L + \ell$ rows 
and consider the set of all fillings 
${\mathcal F}_{T,L,\ell,f^1_k,\ldots,f^m_1,\ldots,f^m_k}$ of $T$ with integers 
such that 
\begin{enumerate}
\item within each row $s$, each brick $b_i$ is filled with sets 
$R_{i,1,s},R_{i,2,s}, \ldots, R_{i,k,s} \subseteq \{1,\ldots, n\}$ 
such that $|R_{i,j,s}| =f^i_j$, the numbers 
in $R_{i,j,s}$ occupy the cells $1+\sum_{t=1}^{j-1}f^i_t, \ldots, 
f^i_j+\sum_{t=1}^{j-1} f^i_t$ within the brick $b_i$ in row $s$  and 
are arranged in 
decreasing order, and 
\item for each row $s$, $\bigcup_{i=1}^m \bigcup_{j=1}^k 
R_{i,j,s}  = \{1,\ldots,n\}$.
\end{enumerate}
If we read to numbers from left to right in the first $L$ rows, we find 
permutations $\Sigma^{(1)},\ldots,\Sigma^{(L)}$ in $S_n$.  If we read to numbers from
left to right in the last $\ell$ rows, we will obtain permutations  
$\sigma^{(1)}, \ldots \sigma^{(\ell)}$ in $S_n$. 

For instance, if $k =3$, $T = (6,5)$, $f^1_1 =2, f^1_2 =1, f^1_3 =3, 
f^2_1 =2, f^2_2 =2, f^2_3=1$, and $L = \ell =2$, then an element of 
${\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots, f^m_1, \ldots, f^m_k}$
is found in Figure \ref{3splitbrick}.

\begin{figure}
\fig{FHfig6}
\caption{A combinatorial object arising from \eqref{kFHmult}.}
\label{3splitbrick}
\end{figure}

In the case where there is a single permutation, i.e., when 
either $L = 1$ and $\ell =0$ or $L = 0$ and $\ell =1$, we shall 
simply write ${\mathcal F}_{T,f^1_1, \ldots, f^1_k,\ldots, f^m_1, \ldots, f^m_k}$ for ${\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots, f^m_1, \ldots, f^m_k}$.

Our goal is to interpret \eqref{kFHmult} as a weighted sum over all elements 
$$F \in {\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}.$$ 
The $q$-multinomial coefficient can be interpreted as
\begin{equation*}
\qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}{q} 
= \sum_{r \in {\mathcal R}({1}^{f^1_1} \cdots {k}^{f^1_k}
\cdots ((m-1)k+1)^{f^m_1} ((m-1)k+2)^{f^m_2} \cdots (mk)^{f^m_k})} q^{inv(r)}.
\end{equation*}
Similarly, 
\begin{equation*}
\qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}{q} 
= \sum_{r \in {\mathcal R}({1}^{f^1_1} \cdots {k}^{f^1_k}
\cdots ((m-1)k+1)^{f^m_1} ((m-1)k+2)^{f^m_2} \cdots (mk)^{f^m_k})} 
q^{coinv(r)}.
\end{equation*}
Given a rearrangement 
\begin{equation*}
r \in {\mathcal R}({1}^{f^1_1} {2}^{f^1_2} \cdots {k}^{f^1_k} \cdots 
((m-1)k+1)^{f^m_1} ((m-1)k+2)^{f^m_2} \cdots (mk)^{f^m_k}),
\end{equation*}
we may associate a permutation $\sigma_r$ by labeling 
the 1's from right to left with $1, \ldots, f^1_1$, labeling the 
2's from right to left  with $f^1_1 +1, \ldots, f^1_1+f^1_2$, etc.  Then 
$inv(\sg_r) = inv(r) + \sum_{i=1}^m \sum_{j=1}^k \binom{f^i_j}{2}$ and 
$\sg_r^{-1}$ consists of a list of the positions of the 1's in $r$ in 
decreasing order, followed by a list of positions of the 2's in $r$ in 
decreasing order, etc.

For example, suppose $n = 11$, $b_1 =6$, $b_2 =5$, 
and $f^1_1 =2, f^1_2 =1, f^1_3 =3, f^2_1 =2, f^2_2 =2$ and $f^2_3=1$.  Then if we 
consider the  rearrangement $r = 1~3~4~2~1~4~3~4~2$,  we find
\begin{center}
$\begin{array}{ccccccccccccc}
r          & = &1&3&4&2&1&5&3&4&6&3&5\,, \\
\sg_r      & = &2&6&8&3&1&10&5&7&11&4&9\,, \\
\sg_r^{-1} & = &5&1&4&10&7&2&8&3&11&6&9\,. 
\end{array}$
\end{center}
Such a $\sg_r^{-1}$ corresponds to a legitimate filling of one of the rows of 
a configuration of an element $F$ of 
${\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$.  
Since this labeling process can be reversed, the map 
$r \rightarrow \sg_r^{-1}$ is bijection from 
\begin{equation*}
{\mathcal R}({1}^{f^1_1} {2}^{f^1_2} \cdots {k}^{f^1_k} 
\cdots ((m-1)k+1)^{f^m_1} ((m-1)k+2)^{f^m_2} \cdots (mk)^{f^m_k})
\end{equation*}
onto ${\mathcal F}_{T,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$.
Our labeling insures that 
\begin{equation*}
inv(\sg_r) = inv(r) + \sum_{i=1}^m \sum_{j=1}^k \binom{f^i_j}{2} 
\qquad \text{and} \qquad 
coinv(\sg_r) = coinv(r).
\end{equation*}
Since $inv(\sg_r) = inv(\sg_r^{-1})$ and $coinv(\sg_r) = coinv(\sg_r^{-1})$, 
it follows that
\begin{align}
\label{kFHmult3}
q^{\sum_{i=1}^m \sum_{j=1}^k \binom{f^i_j}{2}} 
\qbin{n}{f^1_1, \ldots, f^1_k,\ldots, f^m_1, \ldots, f^m_k}{q} 
&= \sum_{\sg \in {\mathcal F}_{T,f^1_1, \ldots, f^1_k,\ldots,f^m_1,\ldots,f^m_k}} 
q^{inv(\sg)} \qquad \text{and} \\
\label{kFHmult4}
\qbin{n}{f^1_1, \ldots, f^1_k,\ldots, f^m_1, \ldots, f^m_k}{q} 
& = \sum_{\sg \in {\mathcal F}_{T,f^1_1, \ldots, f^1_k,\ldots,f^m_1, 
\ldots, f^m_k}} q^{coinv(\sg)}.
\end{align} 
 
It follows from \eqref{kFHmult3} and \eqref{kFHmult4} that if we let 
$\epsilon = x_1^{f^1_1} \cdots x_k^{f^1_k} \cdots x_1^{f^1_m} \cdots 
x_k^{f^1_m}$, then we have the following. 
\begin{lemma}
\label{lem:kFHmult1}
\begin{multline*}
\prod_{j=1}^k X_j^{f^1_j + \cdots + f^m_j} \prod_{a=1}^L
\qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}{Q_a} 
Q_a^{\sum_{i=1}^m \sum_{j=1}^k  \binom{f^i_j}{2}} \\
\times\prod_{b=1}^{\ell} 
{\qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}{q_b}} \\
= \prod_{j=1}^k X_j^{\ell(\epsilon |x_j)}  
\sum_{F =(\Sigma^{(1)}, \ldots,\Sigma^{(L)},\sg^{(1)}, \ldots, \sg^{(\ell)}) 
\in {\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots, f^m_1, \ldots, f^m_k}} 
{\bf Q}^{inv(\Sigma^{(1)}, \ldots,\Sigma^{(L)};\epsilon)} 
{\bf q}^{coinv(\sg^{(1)}, \ldots, \sg^{(\ell)};\epsilon)}.\kern-9pt
\end{multline*}
\end{lemma}

Next we show that modifications of our labeling allows us to prove an 
analogue of Lemma \ref{lem:kFHmult1} where we replace the statistics $inv$ 
and $coinv$ with $FHinv$ and $FHcoinv$. 

Given a rearrangement 
\begin{equation*}
r \in {\mathcal R}(1^{f^1_k} \cdots m^{f^m_k} (m+1)^{f^1_{k-1}} \cdots 
(2m)^{f^m_{k-1}}  \cdots ((k-1)m+1)^{f^1_1} ((k-1)m +2)^{f^2_1} 
\cdots (km)^{f^m_1}),
\end{equation*}
we can associate a permutation $\sigma_r$ by labeling 
the 1's from right to left with $1, \ldots, f^1_k$, labeling the 
2's from right to left  with $f^1_k +1, \ldots, f^1_k+f^2_k$, etc. 
As before, $\sg_r^{-1}$ consists of a list of the positions of the 1's in 
$r$ in decreasing order, followed by a list of positions of the 2's in $r$ in 
decreasing order, etc.

For example, suppose that $n = 11$, $b_1 =6$, $b_2 =5$, 
and $f^1_1 =2, f^1_2 =1, f^1_3 =3, f^2_1 =2, f^2_2 =2, f^2_3=1$ and we 
consider 
the rearrangement $r = 6~1~5~1~2~1~4~2~5~4~6~3$.  Since in the end we want the
positions corresponding to the $f^i_j$'s weighted by $X_j$, we place the $X_j$
on top of all the numbers corresponding to $f^i_j$'s.  Doing this, we would
find
\begin{center}
$\begin{array}{ccccccccccccc}
           &   &X_1&X_3&X_1&X_3&X_2&X_3&X_2&X_3&X_1&X_2&X_1 \\
r          & = &6&1&5&1&3&1&4&2&5&4&6\\
\end{array}$
\end{center}
\begin{center}
$\begin{array}{ccccccccccccc}
           &   &X_1&X_3&X_1&X_3&X_2&X_3&X_2&X_3&X_1&X_2&X_1 \\
\sg_r      & = &11&3&9&2&5&1&7&4&9&6&10 \\
\end{array}$
\end{center}
and
\begin{center}
$\begin{array}{ccccccccccccc}
           &   &X_3&X_3&X_3&X_3&X_2&X_2&X_2&X_1&X_1&X_1&X_1 \\
\sg_r^{-1} & = &6&4&2&8&5&10&7&9&3&11&1 \\
\end{array}$
\end{center}

At this point $\sg_r^{-1}$ does not correspond to a legitimate filling of a 
configuration of an element in ${\mathcal F}_{T,f^1_1, \ldots, f^1_k,\ldots,f^m_1,
\ldots, f^m_k}$ since it consists of decreasing sequences of lengths 
$f^1_k, \ldots,f^m_k,\ldots,f^1_1,f^2_1, \ldots, f^k_1$.  However, we can 
obtain a legitimate filling of a configuration of 
$F \in {\mathcal F}_{T,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$ by 
rearranging the decreasing sequences corresponding to $f^i_j$ so that the 
decreasing sequences correspond to the order 
$f^1_1, \ldots, f^1_k,\ldots, f^m_1, \ldots, f^m_k$.  Let us call the 
result of this rearrangement $\sg_r^*$. In our example. 
\begin{center}
$\begin{array}{ccccccccccccc}
           &   &X_1&X_1&X_2&X_3&X_3&X_3&X_1&X_1&X_2&X_2&X_3 \\
\sg_r^{*} & = &9&3&5&6&4&2&11&1&10&7&8 \\
\end{array}$
\end{center}

If we let 
$\epsilon = x_k^{\sum_{i=1}^m f_k^i} \cdots x_1^{\sum_{i=1}^m f_1^i}$ and 
$\epsilon^* = x_1^{f^1_1} \cdots x_k^{f^1_k}
\cdots x_1^{f^1_m} \cdots x_k^{f^1_m}$, it 
may be seen that, since in $\sg_r^{-1}$, all the $X_m$'s precede all the $X_i$'s for 
$i=1, \ldots, m-1$, all the $X_{m-1}$'s precede all the $X_i$'s for 
$i=1, \ldots, m-2$, etc., we have  
\begin{align*}
\sum_{i=1}^m \sum_{j=1}^k \binom{f^i_j}{2} &+  inv(r) 
 = inv(\sg_r) \\
& = inv(\sg_r^{-1}) \\
& = \sum_{j-1}^k inv((\sg_r^{-1})_{\epsilon | x_j}) + 
\sum_{i,j} \chi(\epsilon_i = x_t, \epsilon_j = x_s, t > s, 
(\sg_r^{-1})_i > (\sg_r^{-1})_j) \\
& = \sum_{j=1}^k inv((\sg_r^*)_{\epsilon^* | x_j}) + 
\sum_{i,j} \chi(\epsilon_i = x_t, \epsilon_j = x_s, t > s, (\sg_r^{*})_i > 
(\sg_r^{*})_j) \\
& = FHinv(\sg_r^*).
\end{align*}
It follows that 
\begin{equation}
\label{kFHmult7}
q^{\sum_{i=1}^m \sum_{j=1}^k \binom{f^i_j}{2}} 
\qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}{q} = 
\sum_{\sg \in {\mathcal F}_{T,f^1_1, \ldots, f^1_k,\ldots,f^m_1,\ldots,f^m_k}} 
q^{FHinv(\sg)}.
\end{equation}

We also need to prove that 
\begin{equation}
\label{kFHmult8}
\qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}{q} 
= \sum_{\sg \in {\mathcal F}_{T,f^1_1, \ldots, f^1_k,\ldots, 
f^m_1, \ldots, f^m_k}} q^{FHcoinv(\sg)}.
\end{equation}
This case requires a slightly different labeling.  Given a rearrangement 
\begin{equation*}
r \in {\mathcal R}(1^{f^1_1} \cdots m^{f^m_1} 
\cdots ((k-1)m+1)^{f^1_k} \cdots (km)^{f^m_k}),
\end{equation*}
we may associate a permutation $\sigma_r$ by labeling the 1's from right to 
left with $1, \ldots, f^1_1$, labeling the 2's from right to left with 
$f^1_1 +1, \ldots, f^1_1+f^2_1$, etc.  As before, $\sg_r^{-1}$ consists of a 
list of the positions of the 1's in $r$ in decreasing order, followed by a 
list of positions of the 2's in $r$ in decreasing order, etc.
For example, consider the case where $n = 11$, $b_1 =6$, $b_2 =5$, 
and $f^1_1 =2, f^1_2 =1, f^1_3 =3, f^2_1 =2, f^2_2 =2, f^2_3=1$ and the 
rearrangement $r = 1~5~6~2~2~4~3~5~4~1~5$.  Placing an $X_j$ on top of all the
numbers corresponding to $f^i_j$'s, we find 
\begin{center}
$\begin{array}{ccccccccccccc}
           &   &X_1&X_3&X_3&X_1&X_1&X_2&X_2&X_3&X_2&X_1&X_3 \\
r          & = &1&5&6&2&2&4&3&5&4&1&5\\
\end{array}$
\end{center}
\begin{center}
$\begin{array}{ccccccccccccc}
           &   &X_1&X_3&X_3&X_1&X_1&X_2&X_2&X_3&X_2&X_1&X_3 \\
\sg_r      & = &2&10&11&4&3&7&5&9&6&1&8 \\
\end{array}$
\end{center}
and
\begin{center}
$\begin{array}{ccccccccccccc}
           &   &X_1&X_1&X_1&X_1&X_2&X_2&X_2&X_3&X_3&X_3&X_3 \\
\sg_r^{-1} & = &10&1&5&4&7&9&6&11&8&2&3. \\
\end{array}$
\end{center}

At this point $\sg_r^{-1}$ does not correspond to a legitimate filling of 
a configuration of a member of ${\mathcal F}_{T,f^1_1, \ldots, 
f^1_k,\ldots,f^m_1, \ldots, f^m_k}$.  To find a legitimate filling, 
move the decreasing sequences corresponding to $f^i_j$ so that the decreasing 
sequences correspond to the order $f^1_1, \ldots, f^1_k,\ldots,f^m_1, 
\ldots, f^m_k$.  This rearrangement will be called
$\sg_r^{**}$. 

In our example,
\begin{center}
$\begin{array}{ccccccccccccc}
           &   &X_1&X_1&X_2&X_3&X_3&X_3&X_1&X_1&X_2&X_2&X_3 \\
\sg_r^{**} & = &10&1&7&11&8&2&5&4&9&6&3 \\
\end{array}$
\end{center}
By letting $\epsilon = x_1^{\sum_{i=1}^m f_1^i} 
\cdots x_k^{\sum_{i=1}^m f_k^i}$ and 
$\epsilon^{**} = x_1^{f^1_1} \cdots x_k^{f^1_k} \cdots x_1^{f^1_m} 
\cdots x_k^{f^1_m}$, we see that $coinv(r)$, \\
$coinv(\sg_r)$, and
$coinv(\sg_r^{-1})$ are all equal to  
\begin{equation*}
\sum_{j-1}^k coinv((\sg_r^{-1})_{\epsilon | x_j}) + 
\sum_{i,j} \chi(\epsilon_i = x_t, \epsilon_j = x_s, t > s, 
(\sg_r^{-1})_i > (\sg_r^{-1})_j).
\end{equation*}
However, this is equal to 
\begin{equation*}
\sum_{j=1}^k coinv((\sg_r^{**})_{\epsilon^{**} | x_j}) + 
\sum_{i,j} \chi(\epsilon_i = x_t, \epsilon_j = x_s, t > s, (\sg_r^{**})_i > 
(\sg_r^{**})_j),
\end{equation*}
which in turn is equal to $FHcoinv(\sg_r^{**})$.  This shows that 
\eqref{kFHmult8} holds. 

Combining the results from 
\eqref{kFHmult3}, \eqref{kFHmult4}, \eqref{kFHmult7}, and \eqref{kFHmult8},
if we let 
$$\epsilon = x_1^{f^1_1} \cdots x_k^{f^1_k} \cdots 
x_1^{f^1_m} \cdots x_k^{f^1_m},$$ 
$L= L_1 + L_2$, and $\ell = \ell_1 +\ell_2$, 
then we arrive at the following lemma.
\begin{lemma}
\begin{multline*}
\prod_{j=1}^k X_j^{\sum_{i=1}^m f^i_j} \prod_{a=1}^L
\qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}{Q_a} 
Q_a^{\sum_{i=1}^m \sum_{j=1}^k \binom{f^i_j}{2}} \\
\times
\prod_{b=1}^{\ell} 
{\qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1,\ldots,f^m_k}{q_b}} \\
= \prod_{j=1}^k X_j^{\ell(\epsilon |x_j)}  
\sum_{F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)}) 
\in {\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}} 
\prod_{i=1}^{L_1} Q_i^{FHinv(\Sigma^{(i)},\epsilon)} \\
\times \prod_{i=L_1+1}^L Q_i^{inv(\Sigma^{(i)},\epsilon)}  
\prod_{i=1}^{\ell_1} q_i^{FHcoinv(\sigma^{(i)},\epsilon)}  
 \prod_{i=1+\ell_1}^{\ell} q_i^{coinv(\sigma^{(i)},\epsilon)} .
\end{multline*}
\end{lemma}

We now are in position to give our combinatorial interpretation
of $(Q,Q)_n (q,q)_n \xi(p_{n,\nu_d})$.
Recall that we have shown $(Q,Q)_n (q,q)_n \xi(p_{n,\nu_d})$ is equal to
\begin{multline}
\label{kFH10}
\sum_{\mu \vdash n} (t-1)^{n - \ell(\mu)} \sum_{T = (b_1, \ldots,b_m) \in 
{\it B}_{\mu,n}} \sum_{f^i_j \geq 0, f^i_1 + \cdots f^i_k = b_i} 
\left( \prod_{t=1}^k X_t^{f^1_t +\cdots + f^m_t}\right)
t^{\chi (f^m_{d+1} + \cdots + f^m_{k} = 0)} \\
\times \prod_{a=1}^L \qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1,\ldots,f^m_k}
{Q_a} Q_a^{\sum_{i=1}^m \sum_{j=1}^k \binom{f^i_j}{2}} \prod_{b=1}^{\ell}
{\qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1,\ldots, f^m_k}{q_b}}.
\end{multline}
We interpret \eqref{kFH10} as follows.  For each brick 
$T = (b_1, \ldots,b_m) \in {\it B}_{\mu,n}$ and for 
each choice for the values of 
$f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k$ from the sums  
$\sum_{i=1}^m \sum_{f^i_1 + \cdots + f^i_k = b_i}$, the term
\begin{multline*}
\prod_{j=1}^k X_j^{\sum_{i=1}^m f^i_j} \prod_{a=1}^L
\qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}{Q_a} 
Q_a^{\sum_{i=1}^m \sum_{j=1}^k \binom{f^i_j}{2}} \\
\times
\prod_{b=1}^{\ell} {\qbin{n}{f^1_1, \ldots, f^1_k, \ldots, f^m_1, 
\ldots, f^m_k}{q_b}}
\end{multline*}
can be viewed as the sum 
\begin{multline*}
\prod_{j=1}^k X_j^{\ell(\epsilon |x_j)}  
\sum_{F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)}) 
\in {\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}} 
\prod_{i=1}^{L_1} Q_i^{FHinv(\Sigma^{(i)},\epsilon)} \\
\times \prod_{i=L_1+1}^L Q_i^{inv(\Sigma^{(i)},\epsilon)}  
\prod_{i=1}^{\ell_1} q_i^{FHcoinv(\sigma^{(i)},\epsilon)}  
 \prod_{i=1+\ell_1}^{\ell} q_i^{coinv(\sigma^{(i)},\epsilon)} 
\end{multline*}
where $\epsilon = x_1^{f^1_1} \cdots x_k^{f^1_k} \cdots x_1^{f^1_m} 
\cdots x_k^{f^1_m}$. 

If $f^m_{d+1} + \cdots + f^m_k \neq 0$, then we have a factor of 
$(t-1)^{n - \ell(\mu)}$.  For each 
$$F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$$ 
in ${\mathcal F}_{T,L,\ell, f^1_1, \ldots, f^1_k,\ldots,f^m_1,\ldots,f^m_k}$, 
create a new set of weighted objects by placing a $t$ or a $-1$ in cell 
of $T$ which is not at the end of a brick and placing a 1 in 
each cell which at the end of the brick. 

For example, if we let $k=3$, $d=2$, $T=(6,5)$ and 
$f^1_1 =2, f^1_2 =1, f^1_3 =3, f^2_1 =2, f^2_2 =2, f^2_3 =1$, then we would 
obtain configuration $C$ as the one pictured in Figure \ref{3splitbrick2}. 
We then let $w(C)$ be the product of the all the $-1$'s, $t$'s, $X_j$'s 
appearing in the configuration. For the configuration 
appearing in Figure \ref{3splitbrick2}, $w(C) = -t^6 X_1^4 X_2^3 X_3^4$. 

\begin{figure}  
\fig{FHfig7}
\caption{An example of a configuration arising from \eqref{kFH10}.}
\label{3splitbrick2}
\end{figure}

If $f^m_{d+1} + \cdots + f^m_k = 0$, then we have a factor of 
$t (t-1)^{n - \ell(\mu)}$.  As before, for each member 
$F=(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$ of the set
${\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$, we 
create a new set of weighted objects by placing a $t$ or a $-1$ in cell 
of $T$ which is not at the end of a brick and placing a 1 in 
each cell which at the end of the brick which is not the final brick 
and placing a $t$ in the last cell of the final brick. 

Let ${\mathcal C}_{T,L,\ell,f^1_1, \ldots, f^1_k,f^2_1, \ldots, f^2_k,\ldots, 
f^m_1, \ldots, f^m_k}$ denote the set of all configurations $C$ constructed 
from one of the  $F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)}) 
\in {\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$ and 
let 
\begin{equation*}
{\mathcal C}_n = \bigcup_{\mu \vdash n} \bigcup_{T = (b_1, \ldots,b_m) \in 
{\it B}_{\mu,n}} \bigcup_{i=1}^m\bigcup_{f^i_1 + \cdots f^i_m  = b_i} 
{\mathcal C}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}.
\end{equation*}
If $C \in {\mathcal C}_{T,L,\ell,f^1_1, \ldots, 
f^1_k,\ldots,f^m_1, \ldots, f^m_k}$ is constructed from an element 
$$F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$$ 
which is a member 
of ${\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$, 
then we let 
\begin{equation*}
U_d(C) 
= w(C) 
\prod_{i=1}^{L_1} Q_i^{FHinv(\Sigma^{(i)},\epsilon)} 
\prod_{i=1+L_1}^{L} Q_i^{inv(\Sigma^{(i)},\epsilon)}
\prod_{i=1}^{\ell_1} q_i^{FHcoinv(\sigma^{(i)},\epsilon)} 
\prod_{i=1+\ell_1}^{\ell} q_i^{coinv(\sigma^{(i)},\epsilon)}.
\end{equation*}
It follows that 
\begin{equation}
\label{kinterp1}
({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \xi(p_{n,\nu_d}) = \sum_{C \in {\mathcal C}_n} U_d(C).
\end{equation}

In order to use \eqref{eq:kFH4} and \eqref{kinterp1} to prove Theorem 
\ref{thm:kNew2}, we need to show that 
\begin{equation}
\label{kFH13}
\sum_{C \in {\mathcal C}_n} U_d(C) 
= W_n^{(4,d)}(X_1,\ldots, X_k,t,{\bf Q},{\bf q}).
\end{equation}
To do this, we will define a sign-reversing involution $I$ on 
${\mathcal C}_n$ so that the fixed points of $I$ will give the desired 
right hand side of \eqref{kFH13}.  Our involution $I$ is essentially the same 
as the one we used in the proofs of Theorems \ref{thm:FH1} and 
\ref{thm:FH-var}. 

To define $I$, we first need the concept of when a sequence of cells in $C$ 
forms a decreasing sequence.  Suppose $C$ is constructed from 
$F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$ which is a member of the
set \\
${\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$.  
Then we say that a sequence of cells in $c, \ldots, c+k$ in $C$ forms
a decreasing sequence if
\begin{itemize}
\item[(i)] the labels at the top of the cells $c,c+1, \ldots, c+k$ when 
read from left to right is a word of the form $X_1^{u_1} \cdots X_k^{u_k}$ 
for some $u_i \geq 0$ and  
\item[(ii)] the entries in each of the rows corresponding to 
$\Sigma^{(1)},\ldots,\Sigma^{(L)},\sigma^{(1)},\ldots,\sigma^{(\ell)}$ are 
decreasing in cells whose labels are $X_j$ for $j = 1,\ldots k$. 
\end{itemize}
By definition, the cells corresponding to each brick in a configuration 
$C \in {\mathcal C}_n$ form a decreasing sequence.  This given, we can define our 
involution $I$ as follows.

Given $C \in {\mathcal C}_n$, scan the cells of the $C$ from left to right until 
either 
\begin{itemize}
\item Case 1: there is a cell $c$ with a $-1$ in which case $I(C)$ is the 
result of changing the weight cell $c$ to 1 and breaking the 
brick $b_i$ which contains cell $c$ 
into two bricks $b'$ and $b''$ where $b'$ ends at cell $c$, or  
\item Case 2: we find two consecutive bricks $b_i$ and $b_{i+1}$ such 
that cells corresponding to $b_i$ and $b_{i+1}$ form a decreasing 
sequence in which case $I(C)$ is the result of combining bricks 
$b_i$ and $b_{i+1}$ into a single brick $b$ and changing the weight of 
the last cell of $b_i$ from $1$ to $-1$. 
\end{itemize}
If neither Case 1 or Case 2 holds, let $I(C) =C$. 

For example, if we consider the configuration $C$ pictured in 
Figure \ref{3splitbrick2}, then we are Case 1 with cell $c$ equal to 
cell 4 so that $I(C)= C'$ where $C'$ is pictured in Figure \ref{3splitbrick4}.
However, $C'$ is in Case 2 because we can combine bricks $b_1$ and $b_2$ so 
that $I(C')$ is equal to $C$. 

\begin{figure}
\fig{FHfig8}
\caption{The image of Figure \ref{3splitbrick2} under $I$}
\label{3splitbrick4}
\end{figure}

The definitions of $I$ leave the permutations 
$(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$ unchanged. 
Moreover, since we do not change any of the labels at the top of the 
column, it follows that if cell $n$ has an  $X_i$ for some 
$i\in \{1, \ldots, d\}$ at the top of the column, then cell $n$ of both $C$ 
and $I(C)$ must have an $X_i$ for some $i\in \{1, \ldots, d\}$ and hence the 
weight of cell $n$ in both $C$ and $I(C)$ is equal to $t$. 

Our definitions ensure that if $I(C) \neq C$, then $U_d(C) = - U_d(I(C))$ and  
$I(I(C)) = C$.  Let $Fix_I = \{C \in {\mathcal C}_n: I(C) = C\}$. Then $I$ shows 
that 
\begin{equation*}
\sum_{C \in {\mathcal C}_n} U_d(C) = \sum_{C \in Fix_I} U_d(C).
\end{equation*}

What are the fixed points of $I$?  Suppose that 
$C \in Fix_I$ and $C$ is constructed from an element 
$F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$ of the 
set ${\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$. 
Then no cell of $C$ can have label $-1$ and the sequence of cells in any two 
consecutive bricks do not form a decreasing sequence.  This means that if 
$b_i$ and $b_{i+1}$ are two consecutive bricks in $C$, $s$ is last cell in 
$b_i$, $s+1$ is the first cell of $b_{i+1}$, and 
$\epsilon = x_1^{f^1_1}x_2^{f^1_2}\cdots x_k^{f^1_k}\cdots 
x_1^{f^m_1}x_2^{f^m_2} \cdots x_k^{f^m_k}$, then either 
\begin{itemize}
\item[(a)] $\epsilon_s =x_i$ and $\epsilon_{s+1} =x_j$ for 
some $i > j$, or  
\item[(b)] $\epsilon_s =x_j$ and $\epsilon_{s+1} =x_j$ for some 
$i =j, \ldots, k$ and there is some $i$ such that 
$\Sigma^{(i)}(s) < \Sigma^{(i)}(s+1)$ or there is some $r$ such that 
$\sigma^{(r)}(s) < \sigma^{(r)}(s+1)$. 
\end{itemize}
It follows that $s \not \in 
Comdes^d(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, 
\sigma^{(\ell)};\epsilon)$ and 
that the weight of cell $s$ is 1.  For $s = n$, our definitions ensure that 
$s \in Comdes^d(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, 
\sigma^{(\ell)};\epsilon)$ if and only if $\epsilon_n = x_i$ for some $i$ in  
$\{1,\ldots,d\}$.  Thus if $\epsilon_n =x_j$ for some 
$j \in \{d+1, \ldots, k\}$, then $n \not \in 
Comdes^d(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)$ and 
cell $n$ has weight 1.  If $\epsilon_n =x_i$ where 
$i \in \{1, \ldots, d\}$, then  $n \in Comdes^d(\Sigma^{(1)}, \ldots, 
\Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)$ and the weight of cell $n$ is $t$. 
If $s$ is not the last cell of a brick, then our definitions 
ensure that if $s \in Comdes^d(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, 
\sigma^{(\ell)};\epsilon)$, then the weight of cell $s$ is $t$. It follows 
that \\
$w(C) = t^{comdes^d({\bf \Sigma},{\bf \sigma};\epsilon)}$.
 
Thus if $C \in Fix_I$ and $C$ is constructed from an element 
$$F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)$$ of the set  
${\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$, then 
\begin{equation*}
U_d(C) = t^{comdes^d({\bf \Sigma},{\bf \sigma},\epsilon)} 
\prod_{i=1}^{L_1} Q_i^{FHinv(\Sigma^{(i)},\epsilon)} 
\prod_{i=1+L_1}^{L} Q_i^{inv(\Sigma^{(i)},\epsilon)}
\prod_{i=1}^{\ell_1} q_i^{FHcoinv(\sigma^{(i)},\epsilon)} 
\prod_{i=1+\ell_1}^{\ell} q_i^{coinv(\sigma^{(i)},\epsilon)}.
\end{equation*}

Finally, suppose that we are given 
$({\bf \Sigma},{\bf \sigma},\epsilon) = (\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, 
\ldots, \sigma^{(\ell)};\epsilon)$, then 
we can construct a configuration $C \in Fix_I$ such that 
\begin{equation*}
U(C)=  t^{comdes^d({\bf \Sigma},{\bf \sigma},\epsilon)}
\prod_{i=1}^{L_1} Q_i^{FHinv(\Sigma^{(i)},\epsilon)} 
\prod_{i=1+L_1}^{L} Q_i^{inv(\Sigma^{(i)},\epsilon)}
\prod_{i=1}^{\ell_1} q_i^{FHcoinv(\sigma^{(i)},\epsilon)} 
\prod_{i=1+\ell_1}^{\ell} q_i^{coinv(\sigma^{(i)},\epsilon)}
\end{equation*}
as follows.  Let the rows of $C$ correspond to the sequence   
$(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$ and 
label the top of column $i$ with $X_j$ if $\epsilon_i =x_j$.
Next, let $$E= \{1, \ldots, n-1\}- Comdes^d(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)},  \ldots, \sigma^{(\ell)}; \epsilon).$$ 
If $E = \emptyset$, then $C$ has a single brick of 
length $n$ and if $E= \{i_1 < \cdots < i_k\}$, then we have bricks ending 
at $i_1,\ldots,i_k,n$. Label each cell $i$ with a $t$ if 
$i \in Comdes^d(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)},\break \ldots, \sigma^{(\ell)})$ 
and with a 1 if $i \notin Comdes^d(\Sigma^{(1)}, \ldots, \Sigma^{(L)},
\sigma^{(1)}, 
\ldots, \sigma^{(\ell)})$.  Then $C \in Fix_I$.  Therefore,
\begin{equation*}
\sum_{C \in {\mathcal C}_n} U_d(C) = 
\sum_{C \in Fix_I} U_d(C) =W_n^{(4,d)}(X,Y,t,{\bf Q},{\bf q}).
\end{equation*}
This completes the proof. 
\end{proof}

\section{Further generalizations of Theorem \ref{thm:kNew2}}

Theorem \ref{thm:kNew2} specializes to give all previous theorems recorded in
this document.  It is the most general theorem in this paper up to this 
point.  However, there are still further generalizations which may be found 
using the methods we are presenting.  To show that this is the case, this 
section extends Theorem \ref{thm:kNew2} according to certain restrictions on 
the set of common descents.   Given a tuple of permutations in 
$C_k \wr S_n$, $({\bf \Sigma},{\bf \sg};\epsilon)$, we shall say that 
it has a final common decreasing segment of size $s$ if 
$\{n-s+1, \ldots, n-1\}$ is a subset of $Comdes^d(({\bf \Sigma},{\bf \sg};\epsilon))$ and $n-s \notin Comes^d(({\bf \Sigma},{\bf \sg};\epsilon))$. Then the 
goal of this section is to derive generating functions for 
tuples of permutations in $C_k \wr S_n$ according to the statistics 
in Theorem \ref{thm:kNew2} which either have a final common decreasing 
sequence of size at least $s$ or size exactly $s$ for any given $s \geq 1$. 


The method we used to prove Theorem \ref{thm:kNew2} can be 
summarized as follows. First we had
a desired generating function in mind. Next we rewrote 
that generating function in
order to read the homomorphism $\xi$ and the weighting function $\nu_d$.  
Then we built combinatorial objects to interpret 
$({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \xi(p_{n,\nu_d})$
Finally we found a weight preserving sign reversing 
involution to simplify this collection of objects to 
prove that 
$({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \xi(p_{n,\nu_d}) =
W^{(4,d)}_n(X_1,\ldots,X_k,t,{\bf Q},{\bf q})$.  



In this section, we shall do something a bit different.  We will not have a
generating function in mind when trying to simplify a certain permutation 
statistic.  Instead, we will take the already known homomorphism $\xi$ and
weighting function $\nu_d$ and alter them a bit.  As a result, the 
combinatorial objects we constructed will be altered accordingly.  Then, the 
same involution $I$ will simplify things to leave a desired set of objects. 
In short, instead of being lead by the generating function, we will be lead by
the combinatorics.  

As in the previous section, let 
\begin{equation*}
\xi(e_n) 
= (1-t)^{n-1}  \sum_{f_j \geq 0, f_1 + \cdots + f_k = n} \prod_{j=1}^k 
\frac{ X^{f_i} {\bf Q}^{\binom{f_i}{2}}}{({\bf Q},{\bf Q})_{f_i} 
({\bf q},{\bf q})_{f_i}}.
\end{equation*}
Instead of keeping $\nu_{d}$ such that $\nu_d(n)$ is equal to 
\begin{multline*}
1 - \frac{(1-t)^{n-1} \sum_{a_i \geq 0, a_1+ \cdots + a_d = n} 
\prod_{i=1}^d X_i^n {\bf Q}^{\binom{a_i}{2}}}
{\xi(e_n) ({\bf Q},{\bf Q})_{a_i} ({\bf q},{\bf q})_{a_i}} \\
+ \frac{t(1-t)^{n-1} \sum_{a_i \geq 0, a_1+ \cdots + a_d = n} 
{\prod_{i=1}^d X_i^{a_i} {\bf Q}^{\binom{a_i}{2}}}}
{\xi(e_n) ({\bf Q},{\bf Q})_{a_i} ({\bf q},{\bf q})_{a_i}},
\end{multline*}
we make an adjustment.  Let $s \geq 1$ be an integer and  define 
$\nu_{d,s}(n) = (t/(t-1)^{s-1} \chi(n \geq s) \nu_d(n)$ for $d = 1,\ldots,k$. 
Thus $\nu_{d,s}$ is the function such that
\begin{equation}\label{nuds}
\nu_{d,s}(n) =
\begin{cases}
0 & \text{if $n < s$ and } \\
\begin{displaystyle}
\left( \frac{t}{t-1} \right)^{s-1} \nu_d(n) 
\end{displaystyle}
& \text{if $n \geq s$.}
\end{cases}
\end{equation}
for all $n = 1,2,\dots$.  Note $\nu_{d,1}= \nu_d$. 
The effect of this modification will occur in the 
last brick of a combinatorial object because \eqref{eqn:weighting} tells us 
that the function $\nu_{d,s}$ changes the weight on the last brick in a 
weighted brick tabloid. 

This change is relatively easy to describe.  We can proceed exactly 
as in the proof of Theorem \ref{thm:kNew2} to show that 
$({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \xi(p_{n,\nu_{d,s}})$ is equal to 
\begin{multline}
\label{altkFH10}
\sum_{\mu \vdash n} (t-1)^{n - \ell(\mu)}  \sum_{T = (b_1, \ldots,b_m) 
\in {\it B}_{\mu,n}} \sum_{i=1}^m \sum_{f^i_1 + \cdots+ f^i_k = b_i} 
\prod_{j=1}^k X_j^{\sum_{i=1}^m f^i_j} {\bf  (t/(t-1))^{s-1} \chi(b_m \geq s)}\\
\times 
\prod_{a=1}^L \qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1,\ldots,f^m_k}{Q_a} 
Q^{\sum_{i=1}^m \sum_{j=1}^k f^i_j}  \\
\times
\prod_{b=1}^{\ell}
\qbin{n}{f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}{q_b} 
t^{\chi (f^m_{d+1} + \cdots + f^m_k=0)}.
\end{multline}
The difference in this case is the extra factor of 
${\bf (t/(t-1)^{s} \chi(b_m \geq s)}$ that arises from replacing 
$\nu_d(n)$ by $\nu_{d,s}(n)$.  We can then interpret (\ref{altkFH10}) 
as a sum over weighted configurations  
$$F = (\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)}) \in 
{\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$$ 
as in the the proof of Theorem \ref{thm:kNew2} with two modifications. 
First the factor $\chi(b_m \geq s)$ has 
the effect of eliminating all brick tabloids $T=(b_1, \ldots, b_m)$ in 
the sum in (\ref{altkFH10}) such that $b_m <s$. Thus the only configurations 
that we need to consider have an underlying brick tabloid $T$ whose 
last brick has length greater than or equal to $s$. Now if 
$(b_1, \ldots, b_m)$ is such that $b_m \geq s$, then there will be a factor 
of $(t-1)^{n - \ell(\mu)} (t/(t-1)^{s-1}
t^{\chi (f^m_{d+1} + \cdots + f^m_k=0)}$ which can be 
rewritten as $t^{s-1}(t-1)^{b_m-1-(s-1)} t^{\chi (f^m_{d+1} + \cdots + f^m_k=0)}  
\prod_{i=1}^{m-1}(t-1)^{b_i-1}$. This term then effects the weight of 
a configuration as follows. For each of brick $b_i$ with $i < m$, we 
weight the cells as before, namely, the last cell in the brick gets weight 
1 and every other cell can have weight $t$ or $-1$. We  
use the remaining factor $t^{s-1}(t-1)^{b_m-1-(s-1)}t^{\chi (f^m_{d+1} + \cdots + f^m_k=0)}$ to weight the cells 
of the last brick of the configuration as follows. First the last cell 
gets weight 1 or $t$ depending on whether the label $X_i$ at the top of the last column has $i \in \{d+1, \ldots, k\}$ or has $i \in \{1, \ldots, d\}$. We 
then use the factor $t^{s-1}$ to weight the $s-1$ cells immediately 
to the left of the last cell of $b_m$ with $t$ and we use the factor 
$(t-1)^{b_m-1-(s-1)}$ to weight the remaining cells of 
$b_m$ with either $t$ or $-1$. As before, we let $w(C)$ be the product of all 
the $-1$'s, $t$'s, and $X_i$'s appearing in the configuration. 

Let ${\mathcal C}^s_{T,L,\ell,f^1_1, \ldots, f^1_k,f^2_1, \ldots, f^2_k,\ldots, 
f^m_1, \ldots, f^m_k}$ denote the set of all configurations $C$ constructed 
from one of the  $F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)}) 
\in {\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$ 
where $b_m \geq s$ in this manner and 
let 
\begin{equation*}
{\mathcal C}^s_n = \bigcup_{\mu \vdash n} \bigcup_{T = (b_1, \ldots,b_m), b_m \geq s) 
\in 
{\it B}_{\mu,n}} \bigcup_{i=1}^m\bigcup_{f^i_1 + \cdots f^i_m  = b_i} 
{\mathcal C}^s_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}.
\end{equation*}
If $C \in {\mathcal C}^s_{T,L,\ell,f^1_1, \ldots, 
f^1_k,\ldots,f^m_1, \ldots, f^m_k}$ is constructed from an element 
$$F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)})$$ 
which is a member 
of ${\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$, 
then we let 
\begin{equation*}
U_{d,s}(C) 
= w(C) 
\prod_{i=1}^{L_1} Q_i^{FHinv(\Sigma^{(i)},\epsilon)} 
\prod_{i=1+L_1}^{L} Q_i^{inv(\Sigma^{(i)},\epsilon)}
\prod_{i=1}^{\ell_1} q_i^{FHcoinv(\sigma^{(i)},\epsilon)} 
\prod_{i=1+\ell_1}^{\ell} q_i^{coinv(\sigma^{(i)},\epsilon)}.
\end{equation*}
It follows that 
\begin{equation}
\label{altkinterp1}
({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \xi(p_{n,\nu_{d,s}}) = \sum_{C \in {\mathcal C}^s_n} U_d(C).
\end{equation}
We can apply the same involution $I$ to ${\mathcal C}^s_n$ that we used in Theorem \ref{thm:kNew2}. 
Note that since the $s-1$ cells immediately to the left of last cell in 
each configuration are labeled with $t$, we will never try to split the 
last brick at any one of those cells and hence our involution will automatically ensure that the image of any element in ${\mathcal C}^s_n$ will have its last brick of size $ \geq s$ and, hence, $I$ maps  ${\mathcal C}^s_n$ onto 
${\mathcal C}^s_n$. The fixed points of $I$ restricted to   ${\mathcal C}^s_n$
will be exactly the same as in Theorem \ref{thm:kNew2} with the added condition that the size of the last brick is $ \geq s$. Thus if $C \in Fix_I \cap {\mathcal C}^s_n$ and $C$ is constructed from an element 
$F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)$ 
of the set  
${\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$, then 
just as before we will have that 
\begin{equation*}
U_d(C) = t^{comdes^d({\bf \Sigma},{\bf \sigma},\epsilon)} 
\prod_{i=1}^{L_1} Q_i^{FHinv(\Sigma^{(i)},\epsilon)} 
\prod_{i=1+L_1}^{L} Q_i^{inv(\Sigma^{(i)},\epsilon)}
\prod_{i=1}^{\ell_1} q_i^{FHcoinv(\sigma^{(i)},\epsilon)} 
\prod_{i=1+\ell_1}^{\ell} q_i^{coinv(\sigma^{(i)},\epsilon)}.
\end{equation*}
However, since the last brick is of size at least 
$s$, then we are guaranteed that 
$$\{n-s+1, \ldots, n-1\} \in 
Comes^d((\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon).$$ 
Finally if 
$F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)$ is an element 
of the set  
${\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$ is 
such that 
$\{n-s+1, \ldots, n-1\} \in 
Comes^d((\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)$, then we can use same argument as in Theorem \ref{thm:kNew2} 
to show that 
we can construct a unique 
$C \in Fix_I \cap {\mathcal C}^s_n$ whose underlying configuration is $F$.

Now if we let 
\begin{align*}
W^{(4,d,s)}_n(X_1,\ldots,X_k,t,{\bf Q},{\bf q}) 
& = \sum_{({\bf \Sigma},{\bf \sg};\epsilon)} \left( \prod_{i=1}^k 
X_i^{\ell({\epsilon | x_i})}  \right) 
t^{Comdes^d({\bf \Sigma},{\bf \sg};\epsilon)} 
\prod_{i=1}^{L_1} Q_i^{FHinv(\Sigma^{(i)},\epsilon)}  \\
& \qquad \times 
\prod_{i=1+L_1}^{L} Q_i^{inv(\Sigma^{(i)},\epsilon)}
\prod_{i=1}^{\ell_1} q_i^{FHcoinv(\sigma^{(i)},\epsilon)} 
\prod_{i=1+\ell_1}^{\ell} q_i^{coinv(\sigma^{(i)},\epsilon)}.
\end{align*}
where the sum runs over all $\epsilon \in \{x_1, \ldots, x_k\}^n$ and 
$({\bf \Sigma},{\bf \sg}) \in (C_k\wr S_n)^{L+ \ell}$ such that  
$\{n-s+1, \ldots, n-1\}$ is contained in $Comdes^d(({\bf \Sigma},{\bf \sg};\epsilon))$, then it follows that 
\begin{equation}\label{altresult}
({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \xi(p_{n,\nu_{d,s}}) = W^{(4,d,s)}_n(X_1,\ldots,X_k,t,{\bf Q},{\bf q}).
\end{equation}
Hence  
\begin{multline}
\sum_{n \geq 0} \frac{u^n}{({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n}W^{(4,d,s)}_n(X_1,\ldots,X_k,t,{\bf Q},{\bf q}) 
= 1+ \sum_{n \geq 1} \xi(p_{n,\nu_{d,s}})u^n  \\
=\frac{1+ \sum_{n \geq 1} (-1)^{n}u^n (\xi(e_n) - \nu_{d,s}(n) \xi(e_n))}
{\sum_{n \geq 0} (-1)^nu^n  \xi(e_n)}. 
\label{altgenfn}
\end{multline}
Now the denominator on the right-hand side of (\ref{altgenfn}) is 
\begin{align*}
\sum_{n \geq 0} (-1)^n u^n  \xi(e_n)  
&=\sum_{n \geq 0} (-1)^n u^n (1-t)^{n-1}
\sum_{b_j \geq 0, b_1 + \cdots +b_k = n} \prod_{j=1}^k 
\frac{X_j {\bf Q}^{\binom{b_j}{2}}}{({\bf Q},{\bf Q})_{b_j} 
({\bf q},{\bf q})_{b_j}} \\
&\kern-7pt= \frac{1}{1-t}\left( 1-t + \sum_{n \geq 1} (-1)^n u^n (1-t)^{n}
\sum_{b_j \geq 0, b_1 + \cdots +b_k = n} \prod_{j=1}^k 
\frac{X_j {\bf Q}^{\binom{b_j}{2}}}{({\bf Q},{\bf Q})_{b_j} ({\bf q},{\bf q})_{b_j}}\right) \\
&\kern-7pt=\frac{1}{1-t}\left(-t + \prod_{j=1}^k J((1-t)X_ju,{\bf Q},{\bf q})\right).
\end{align*}

The numerator on the right-hand side of (\ref{altgenfn}) is
{\allowdisplaybreaks
\begin{align*}
1+ \sum_{n \geq 1}& (-1)^{n}u^n (\xi(e_n) - \nu_{d,s}(n) \xi(e_n)) \\
&= 1+ \sum_{n \geq 1} (-1)^{n}u^n \xi(e_n)  
- \sum_{n \geq s} (-1)^n u^n \left(\frac{t}{t-1}\right)^{s-1} \\
&\kern4.4cm
\times
\left(\xi(e_n)  - (1-t)^{n} \sum_{a_i \geq 0, a_1+ \cdots + a_d = n} 
\prod_{i=1}^d \frac{X_i^{a_i} {\bf Q}^{\binom{a_i}{2}}}{({\bf Q},{\bf Q})_{a_i} ({\bf q},{\bf q})_{a_i}}\right)  \\
&= \left(1- \left(\frac{t}{t-1}\right)^{s-1}\right) \left( 1+ \sum_{n \geq 1} (-1)^{n} u^n \xi(e_n)\right) \\
&\kern1cm
+\left(\frac{t}{t-1}\right)^{s-1} \left(1 + \sum_{n=1}^{s-1} (-1)^n u^n \xi(e_n)\right) \\
&\kern1cm
+ \left(\frac{t}{t-1}\right)^{s-1}\left(1 + \sum_{n \geq 1} (-1)^n u^n (1-t)^{n} \sum_{a_i \geq 0, a_1+ \cdots + a_d = n} 
\prod_{i=1}^d \frac{X_i^{a_i} {\bf Q}^{\binom{a_i}{2}}}{({\bf Q},{\bf Q})_{a_i} ({\bf q},{\bf q})_{a_i}}\right)\\
&\kern1cm
- \left(\frac{t}{t-1}\right)^{s-1}\left(1 + \sum_{n = 1}^{s-1} (-1)^n u^n (1-t)^{n} \sum_{a_i \geq 0, a_1+ \cdots + a_d = n} 
\prod_{i=1}^d \frac{X_i^{a_i} {\bf Q}^{\binom{a_i}{2}}}{({\bf Q},{\bf Q})_{a_i} ({\bf q},{\bf q})_{a_i}}\right)  \\
&= \left(1- \left(\frac{t}{t-1}\right)^{s-1}\right) \left( 
\frac{1}{1-t}\left(-t + \prod_{j=1}^k J((1-t)X_ju,{\bf Q},{\bf q})\right)\right) \\
&\kern1cm
+ \left(\frac{t}{t-1}\right)^{s-1}\left(\prod_{i=1}^d J((1-t)X_iu,{\bf Q}, {\bf q})\right)\\
&\kern1cm
+ \left(\frac{t}{t-1}\right)^{s-1}\sum_{n = 1}^{s-1} (-1)^n u^n\\
&\kern4.4cm
\times\left(\xi(e_n) -(1-t)^{n} \sum_{a_i \geq 0, a_1+ \cdots + a_d = n} 
\prod_{i=1}^d \frac{X_i^{a_i} {\bf Q}^{\binom{a_i}{2}}}{({\bf Q},{\bf Q})_{a_i} ({\bf q},{\bf q})_{a_i}}\right)  \\
&= \left(1- \left(\frac{t}{t-1}\right)^{s-1}\right) \left( 
\frac{1}{1-t}(-t + \prod_{j=1}^k J((1-t)X_ju,{\bf Q},{\bf q}))\right) \\
&\kern1cm
+ \left(\frac{t}{t-1}\right)^{s-1}\left(\prod_{i=1}^d J((1-t)X_iu,{\bf Q}, {\bf q})\right)\\
&\kern1cm
+ \left(\frac{t}{t-1}\right)^{s-1}\sum_{n = 1}^{s-1} (-1)^n u^n (1-t)^{n-1}\\
&\kern5cm
\times
\sum_{b_j \geq 0, b_1+ \cdots + b_k = n} t^{\chi(b_{d+1}+ \cdots +b_k=0)}
\prod_{j=1}^k \frac{X_j^{b_j} {\bf Q}^{\binom{a_i}{2}}}{({\bf Q},{\bf Q})_{b_j} ({\bf q},{\bf q})_{b_j}}.
\end{align*}}
It then follows that we have the following theorem. 
\begin{theorem}\nonumber 
For all $k \geq 2$, $d =1, \ldots, k$, and $s \geq 1$, 
\begin{align}
&\sum_{n \geq 0} \frac{u^n}{({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n}W^{(4,d,s)}_n(X_1,\ldots,X_k,t,{\bf Q},{\bf q})\\
&=\left(1- \left(\frac{t}{t-1}\right)^{s-1}\right)  
+\left(\frac{t}{t-1}\right)^{s-1}\frac{(1-t)\prod_{i=1}^d J((1-t)X_iu,{\bf Q}, {\bf q})}{-t + \prod_{j=1}^k J((1-t)X_ju,{\bf Q},{\bf q})} \nonumber \\
&\kern.3cm
+\left(\frac{t}{t-1}\right)^{s-1}\frac{\sum_{n = 1}^{s-1} (-1)^n u^n(1-t)^{n}
\sum_{b_j \geq 0, b_1+ \cdots + b_k = n} t^{\chi(b_{d+1}+ \cdots +b_k=0)}
\prod_{j=1}^k \frac{X_j^{b_j} {\bf Q}^{\binom{b_j}{2}}}{({\bf Q},{\bf Q})_{b_j} ({\bf q},{\bf q})_{b_j}}}{-t + \prod_{j=1}^k J(u(1-t)X_j,{\bf Q},{\bf q})}.
\label{alt:thm} 
\end{align}
\end{theorem}


 
Next we present another modification which will product a 
generating functions for those tuples of permutations 
$({\bf \Sigma},{\bf \sg};\epsilon)$ in $C_k \wr S_n$ such that 
$\{n-s+1, \ldots, n-1\} \subseteq Comdes^d(({\bf \Sigma},{\bf \sg};\epsilon))$ but $n-s \notin Comdes^d(({\bf \Sigma},{\bf \sg};\epsilon))$
That is, for $d = 1,\ldots,k$, define a 
function $\overline{\nu}_{d,s}$ such that
\begin{equation*}
\overline{\nu}_{d,s}(n) =
\begin{cases}
0 & \text{if $n < s$,} \\
\begin{displaystyle}
\left( \frac{t}{t-1} \right)^{s-1} \nu_d(n) 
\end{displaystyle}
& \text{if $n = s$, and} \\
\begin{displaystyle}
\left( \frac{-1}{t-1} \right) 
\left( \frac{t}{t-1} \right)^{s-1} \nu_d(n) 
\end{displaystyle}
& \text{if $n > s$.}
\end{cases}
\end{equation*}
for all $n = 1,2,\dots$.  Again the effect of this modification will occur in the 
last brick of a combinatorial object because \eqref{eqn:weighting} tells us 
that the function $\nu_{d,s}$ changes the weight on the last brick in a 
weighted brick tabloid. 

This change is also relatively easy to describe.  Suppose the last brick of 
the underlying brick tabloid of a configuration  has a length $b$.  
If $b < s$, then 
the weight assigned by $\overline{\nu}_{d,s}$ is $0$ as before.  If $b=s$, 
then we use the extra factor of $(t/(t-1))^{s-1}$ that occurs in 
the $\overline{\nu}_{d,s}(s)$ to ensure that the weights of each of the 
$s-1$ cells immediately preceding the last cell of the configuration is $t$. 
If $b>s$, 
then we again we use the extra factor of $(t/(t-1))^{s-1}$ that occurs in 
the $\overline{\nu}_{d,s}(b)$ to ensure that the weights of each of the 
$s-1$ cells immediately preceding the last cell of the configuration is $t$.
However, in this case, we have another factor of $(-1)/(t-1)$ which use 
to ensure that the next cell to left has weight $-1$.  
That is, if $b > s$, we would take a combinatorial object as found in the proof of Theorem \ref{thm:kNew2}, erase the final $s$ choices of either $-1$ or $t$ 
made at the end of the last brick (the last cell in the brick will still be
$1$ or $t$).  Then, the sequence $-1~t~t~\cdots~t$ would be placed in the
cells instead. We let $\overline{{\mathcal C}}^s_n$ denote the set of 
configurations that we can produce in this manner. 

An example of a configuration in $\overline{{\mathcal C}}^s_n$ when $s=3$ 
may be found in Figure \ref{FHfig9}.

\begin{figure}
\fig{FHfig9}
\caption{A combinatorial object coming from $\xi$ and $\nu_{d,3}$.}
\label{FHfig9}
\end{figure}

The exact same involution $I$ may be used to simplify the set of objects
in $\overline{{\mathcal C}}^s_n$.  
Note that if the last brick of a configuration $C$
has length $>s$, then either we use the label $-1$ that is forced on cell 
$n-s$ to split at cell $n-s$ so that $I(C)$ will have its last brick of size $s$ or the involution either splits or combines bricks as some cell to the 
left of $n-s$ in which case the labels on the cells $n-s, \ldots, n-1$ are 
not effected. Thus our involution $I$ maps $\overline{{\mathcal C}}^s_n$ onto $\overline{{\mathcal C}}^s_n$.  Since the fixed points of $I$ have 
no cell with weight $-1$, it must be that all elements 
of $Fix_I \cap \overline{{\mathcal C}}^s_n$ have a last
brick of size $s$.  Thus if $C \in Fix_I \cap \overline{{\mathcal C}}^s_n$ and $C$ is constructed from an element 
$F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)$ 
of the set  
${\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$, then 
just as before we will have that 
\begin{equation*}
U_d(C) = t^{comdes^d({\bf \Sigma},{\bf \sigma},\epsilon)} 
\prod_{i=1}^{L_1} Q_i^{FHinv(\Sigma^{(i)},\epsilon)} 
\prod_{i=1+L_1}^{L} Q_i^{inv(\Sigma^{(i)},\epsilon)}
\prod_{i=1}^{\ell_1} q_i^{FHcoinv(\sigma^{(i)},\epsilon)} 
\prod_{i=1+\ell_1}^{\ell} q_i^{coinv(\sigma^{(i)},\epsilon)}.
 \end{equation*}
However, since the last brick is of size  
$s$, then we are guaranteed that 
$$\{n-s+1, \ldots, n-1\} \in 
Comes^d((\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)$$ 
and 
$n-s \notin Comes^d((\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)$. 
Finally by the same argument that we used in Theorem \ref{thm:kNew2}, we can 
show that if 
$F =(\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon)$ 
of the set  
${\mathcal F}_{T,L,\ell,f^1_1, \ldots, f^1_k,\ldots,f^m_1, \ldots, f^m_k}$ is 
such that 
\begin{eqnarray*}\{n-s+1, \ldots, n-1\} &\in& 
Comes^d((\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon) \ \mbox{and}  \\
n-s &\notin& Comes^d((\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon), 
\end{eqnarray*}
then we can construct a unique fixed 
$C \in Fix_I \cap \overline{{\mathcal C}}^s_n$ whose underlying 
configuration is $F$.

Now if we let 
\begin{align*}
\overline{W}^{(4,d,s)}_n(X_1,\ldots,X_k,t,{\bf Q},{\bf q}) 
& = \sum_{({\bf \Sigma},{\bf \sg};\epsilon)} \left( \prod_{i=1}^k 
X_i^{\ell({\epsilon | x_i})}  \right) 
t^{Comdes^d({\bf \Sigma},{\bf \sg};\epsilon)} 
\prod_{i=1}^{L_1} Q_i^{FHinv(\Sigma^{(i)},\epsilon)} \\
& \qquad \times  
\prod_{i=1+L_1}^{L} Q_i^{inv(\Sigma^{(i)},\epsilon)}
\prod_{i=1}^{\ell_1} q_i^{FHcoinv(\sigma^{(i)},\epsilon)} 
\prod_{i=1+\ell_1}^{\ell} q_i^{coinv(\sigma^{(i)},\epsilon)}
\end{align*}
where the sum runs over all $\epsilon \in \{x_1, \ldots, x_k\}^n$ and 
$({\bf \Sigma},{\bf \sg}) \in (C_k \wr S_n)^{L + \ell}$ such that 
\begin{eqnarray*}\{n-s+1, \ldots, n-1\} &\in& 
Comes^d((\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon) \ \mbox{and}  \\
n-s &\notin& Comes^d((\Sigma^{(1)}, \ldots, \Sigma^{(L)},\sigma^{(1)}, \ldots, \sigma^{(\ell)};\epsilon), 
\end{eqnarray*}
then we have shown that 
\begin{equation}\label{altresult2}
({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n \xi(p_{n,\overline{\nu}_{d,s}}) = 
\overline{W}^{(4,d,s)}_n(X_1,\ldots,X_k,t,{\bf Q},{\bf q}).
\end{equation}
It follows that 
\begin{align}\nonumber
\sum_{n \geq 0} \frac{u^n}{({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n}
\overline{W}^{(4,d,s)}_n(X_1,&\ldots,X_k,t,{\bf Q},{\bf q}) \\
&= 1+ \sum_{n \geq 1} \xi(p_{n,\overline{\nu}_{d,s}})u^n  \nonumber \\
&=\frac{1+ \sum_{n \geq 1} (-1)^{n}u^n (\xi(e_n) - \overline{\nu}_{d,s}(n) \xi(e_n))}
{\sum_{n \geq 0} (-1)^nu^n  \xi(e_n)}. 
\label{altgenfn2}
\end{align}


We can then carry out a computation similar to the one we used to 
prove Theorem \ref{alt:thm} to prove the following theorem. 



\begin{theorem}\label{alt:thm2} 
For all $k \geq 2$, $d =1, \ldots, k$, and $s \geq 1$, 
\begin{align}\nonumber 
&\sum_{n \geq 0} \frac{u^n}{({\bf Q},{\bf Q})_n ({\bf q},{\bf q})_n}
\overline{W}^{(4,d,s)}_n(X_1,\ldots,X_k,t,{\bf Q},{\bf q}) 
=\left(1+ \frac{t^{s-1}}{(t-1)^s}\right)  \nonumber \\
&+\left(\frac{t}{t-1}\right)^{s-1}\frac{\prod_{i=1}^d J((1-t)X_iu,{\bf Q}, {\bf q})}{-t + \prod_{j=1}^k J((1-t)X_ju,{\bf Q},{\bf q})} \nonumber \\
&-\frac{t^{s-1}}{(t-1)^s}\frac{\sum_{n = 1}^{s} (-1)^n u^n(1-t)^{n}
\sum_{b_j \geq 0, b_1+ \cdots + b_k = n} t^{\chi(n=s)}t^{\chi(b_{d+1}+ \cdots +b_k=0)}
\prod_{j=1}^k \frac{X_j^{b_j} {\bf Q}^{\binom{b_j}{2}}}{({\bf Q},{\bf Q})_{b_j} ({\bf q},{\bf q})_{b_j}}}{-t + \prod_{j=1}^k J((1-t)X_ju,{\bf Q},{\bf q})}.
\end{align}
\end{theorem}












%\bibliographystyle{amsalpha}
%\bibliography{FHbib}


\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{Wag00}

\bibitem[Bec93]{Bec3}
Desiree Beck, \emph{Permutation enumeration of the symmetric and
  hyperoctahedral group and the combinatorics of symmetric functions}, Ph.D.
  thesis, University of California, San Diego, 1993.

\bibitem[BR95]{Bec4}
Desiree Beck and Jeffrey Remmel, \emph{Permutation enumeration of the symmetric
  group and the combinatorics of symmetric functions}, J. Combin. Theory Ser. A
  \textbf{72} (1995), no.~1, 1--49.

\bibitem[Bre93]{Bre}
Francesco Brenti, \emph{Permutation enumeration symmetric functions, and
  unimodality}, Pacific J. Math. \textbf{157} (1993), no.~1, 1--28.

\bibitem[Car70]{Car}
Leonard Carlitz, \emph{Sequences and inversions}, Duke Math. J. \textbf{37}
  (1970), 193--198.

\bibitem[ER91]{Eg1}
{\"O}mer E{\u{g}}ecio{\u{g}}lu and Jeffrey Remmel, \emph{Brick tabloids and the
  connection matrices between bases of symmetric functions}, Discrete Appl.
  Math. \textbf{34} (1991), no.~1-3, 107--120, Combinatorics and theoretical
  computer science (Washington, DC, 1989). \MR{92j:05179}

\bibitem[FH97a]{FH1}
Dominique Foata and Guo-Niu Han, \emph{Calcul basique des permutations
  sign\'ees. {I}. {L}ongueur et nombre d'inversions}, Adv. in Appl. Math.
  \textbf{18} (1997), no.~4, 489--509.

\bibitem[FH97b]{FH2}
\bysame, \emph{Calcul basique des permutations sign\'ees. {II}. {A}nalogues
  finis des fonctions de {B}essel}, Electron. J. Combin. \textbf{4} (1997),
  no.~2, Research Paper 9, approx. 25 pp. (electronic), The Wilf Festschrift
  (Philadelphia, PA, 1996).

\bibitem[LR06]{Lan-Rem}
Thomas Langley and Jeffrey Remmel, \emph{Enumeration of $m$-tuples of
  permutations and a new class of power bases for the space of symmetric
  functions}, Adv. Appl. Math. \textbf{36} (2006), no.~1, 30--66.

\bibitem[Men04]{Men}
Anthony Mendes, \emph{Building generating functions brick by brick}, Ph.D.
  thesis, University of California, San Diego, 2004.

\bibitem[MRa]{Mendes-Rem1}
Anthony Mendes and Jeffrey Remmel, \emph{Descents, inversions, and major
  indices in permutation groups}, submitted to Discrete Math.

\bibitem[MRb]{Book}
\bysame, \emph{Generating functions via symmetric functions}, book in
  preparation.

\bibitem[MR06]{Mendes-Rem2}
\bysame, \emph{Permutations and words counted by consecutive patterns}, Adv.
  Appl. Math. \textbf{37} (2006), no.~4, 443--480.

\bibitem[Wag]{wagner2}
Jennifer Wagner, \emph{Personal communication}, 2001.

\bibitem[Wag00]{wagner}
\bysame, \emph{The combinatorics of the permutation enumeration of wreath
  products between cyclic and symmetric groups}, Ph.D. thesis, University of
  California, San Diego, 2000.

\end{thebibliography}


\end{document}



