%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt]{article}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Package usage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{times}              % Font family selection
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{epsfig}
\usepackage{psfig}
\usepackage{cite}
\usepackage{graphicx}

\catcode`\@=11
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\catcode`\@=12


%\usepackage{verbatim}           % for `comment' environment
%\usepackage{subfigure}
%\usepackage[sf,bf]{caption}
%\usepackage{multicol}

%\usepackage{fancybox}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% for marginal adjustment
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\normalsize               % set normal \baselineskip
\setlength{\topmargin}{0pt}
\setlength{\headheight}{0pt}
\setlength{\marginparwidth}{0pt}
\setlength{\footskip}{36pt}
\setlength{\textheight}{49\baselineskip} %%% 51-10pt. 49-11pt, 44-12pt
\setlength{\textwidth}{6.3in}
\setlength{\oddsidemargin}{10pt}
\setlength{\headsep}{0pt}

\setlength{\hoffset}{0pt} % 1 inch left margin
\setlength{\voffset}{0pt} % 1 inch top margin

\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}

\newcommand{\bbm}{\begin{bmatrix}}
\newcommand{\ebm}{\end{bmatrix}}

\newcommand{\bp}{\begin{proof}}
\newcommand{\ep}{\end{proof}}
\newcommand{\bcor}{\begin{cor}}
\newcommand{\ecor}{\end{cor}}
\newcommand{\bthm}{\begin{thm}}
\newcommand{\ethm}{\end{thm}}
\newcommand{\blmm}{\begin{lmm}}
\newcommand{\elmm}{\end{lmm}}
\newcommand{\bdefn}{\begin{defn}}
\newcommand{\edefn}{\end{defn}}
\newcommand{\bprop}{\begin{prop}}
\newcommand{\eprop}{\end{prop}}
\newcommand{\bconj}{\begin{conj}}
\newcommand{\econj}{\end{conj}}
\newcommand{\bopm}{\begin{opm}}
\newcommand{\eopm}{\end{opm}}
\newcommand{\brmk}{\begin{rmk}}
\newcommand{\ermk}{\end{rmk}}

\newcommand{\qnom}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}

\newcommand{\suchthat}{\ | \ }
\newcommand{\inner}[1]{\langle #1 \rangle}
\newcommand{\deriv}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\vol}[1]{\mbox{vol } #1}
\newcommand{\var}[1]{\mbox{Var }[#1]}
\newcommand{\cov}[1]{\mbox{Cov }[#1]}
\newcommand{\per}[1]{\mbox{per } #1}
\newcommand{\kphi}[6]{ {}_{#1}\phi_{#2} 
                       \left( 
%                         \left. {#3 \atop #4}
                         \left. \genfrac{}{}{0pt}{}{#3}{#4}
                         \right| #5, #6 
                       \right)}

\theoremstyle{plain}                   % default
\newtheorem{thm}{Theorem}[section]
\newtheorem{lmm}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{claim}{Claim}

\theoremstyle{definition}              % Examples and all
\newtheorem{pbm}[thm]{Problem}
\newtheorem{opm}[thm]{Open Problem}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{ex}[thm]{Example}
\newtheorem{defn}[thm]{Definition}
\newtheorem{alg}[thm]{Algorithm}

\theoremstyle{remark}
\newtheorem{rmk}[thm]{Remark}
\newtheorem*{note}{Note}

\newcommand{\postscript}[2]
 {\setlength{\epsfxsize}{#2\hsize}
  \centerline{\epsfbox{#1}}}


\title{$\mathbb{P}$-Species and the $q$-Mehler Formula}

\author{
Hung Quang Ngo
\thanks{
Computer Science and Engineering Department,
201 Bell Hall,
State University of New York at Buffalo,
Amherst, NY 14260, U.S.A.
\texttt{hungngo@cse.buffalo.edu}}
}

\date{}
\begin{document}
\maketitle

\begin{abstract}
In this paper, we present a bijective proof of the $q$-Mehler formula.
The proof is in the same style as Foata's proof of the Mehler formula.
Since Foata's proof was extended to show the Kibble-Slepian formula,
a very general multilinear extension of the Mehler formula, 
we hope that the proof provided in this paper helps 
find some multilinear extension of the $q$-Mehler formula.

The basic idea to obtain this proof comes from generalizing a result by
Gessel. The generalization leads to the notion of species on permutations and
the $q$-generating series for these species. The bijective proof is then
obtained by applying this new exponential formula to a certain type of
species on permutations and a weight preserving bijection relating this
species to the $q$-Mehler formula.
Some by-products of the $q$-exponential formula shall also be derived.
\end{abstract}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Intro
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}

The Hermite polynomials 
are well-studied and have applications in diverse areas of Mathematics
\cite{MR2000g:33001, MR58:1979}.
They can be defined in terms of their generating function,
whose bilinear extension is the well-known Mehler formula.
The most general multilinear extension
is known as the Kibble-Slepian formula \cite{MR7:65f, MR47:3722}.
Foata \cite{MR58:16322} discovered a combinatorial proof of the
Mehler formula, which was later extended to show the Kibble-Slepian
formula combinatorially by Foata and Garcia \cite{MR81a:05007}.

A $q$-analogue of the Hermite polynomials, called the $q$-Hermite polynomials,
was introduced by Rogers \cite{Rogers-1893}, 
who used them to prove Rogers-Ramanujan identities. 
Up to rescaling, there are other variants of the $q$-Hermite polynomials
\cite{MR33:5967, cigler-1982, desarmenien-1982, MR89h:33015}.
The Mehler formula for the $q$-Hermite is known, but no
$q$-analogue of the Kibble-Slepian formula has been discovered yet.
Similar to the normal Hermite polynomials,
one hopes that a Foata-style combinatorial approach to the $q$-Mehler formula 
helps find a $q$-Kibble-Slepian.
A few proofs of the $q$-Mehler formula is known (see, e.g.,
\cite{cigler-1982, MR81f:33009, MR89h:33015}), of which the one
in \cite{MR89h:33015} is combinatorial. However, the combinatorial objects
were vector spaces over finite fields, which are difficult to be dealt with
in bijective arguments.

This paper presents a Foata-style proof of the $q$-Mehler formula.
Along the way, we also introduce
a new kind of species and a few consequences.
Throughout this paper, we use $[1,n]$ (avoiding confusion with $[n]_q$)
to denote the set of integers from $1$ to $n$. 
The following standard notations shall also be used:
\begin{eqnarray*}
(a)_n = (a; q)_n & := & (1-a)(1-aq) \dots (1-aq^{n-1}) \\
\left[0\right]_q & := & 0 \\
\left[n\right]_q & := & 1+q+\dots + q^{n-1}, n \geq 1 \\
\qnom{n}{k}_q    & := & \frac{(q)_n}{(q)_{n-k}(q)_k} = 
                        \frac{(1-q^n)\dots(1-q^{n-k+1})}
                             {(1-q^k)\dots(1-q)}, 0 \leq k \leq n.
\end{eqnarray*}
Most often, the subscript $q$ is dropped when there is no
potential confusion.
Lastly, we use $M_n$ to denote the set of all matchings on $n$ points $[1,n]$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Intro
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}


\section{Preliminaries}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Mehler
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The Mehler formula and its extensions}
\label{subsection:Mehler}

There are several variations of the Hermite polynomials, which are all
the same up to rescaling.
A typical definition of the Hermite polynomials and their generating function,
respectively, are 
\begin{equation} \label{eqn:H_n(x)}
H_n(x) := (-1)^ne^{x^2} \frac{d^ne^{-x^2}}{dx^n},
\end{equation}
\begin{equation} \label{eqn:H_n(x)-genfunc}
\sum_{n=0}^{\infty} H_n(x)\frac{r^n}{n!}
 = e^{2xr - r^2}.
\end{equation}

To interpret the Hermite polynomials combinatorially, another
variant of the Hermite polynomials, denoted by $\tilde{H}_n(x)$, was introduced.
The definition of the $\tilde{H}_n(x)$, their generating function and its
bilinear extension are as follows, respectively:
\begin{eqnarray} 
\tilde{H}_n(x) 
 & := & \frac{H_n(x/\sqrt{2})}{2^{n/2}} \label{eqn:tilde{H}_n(x)} ,\\
\sum_{n=0}^{\infty} \tilde{H}_n(x)\frac{t^n}{n!}
 & = & e^{xt - t^2/2}  \label{eqn:tilde{H}_n(x)-genfunc}, \\
\sum_{n=0}^{\infty} \tilde{H}_n(x) \tilde{H}_n(y) \frac{t^n}{n!}
 & = & \frac{1}{\sqrt{1-t^2}} 
    \exp \left( \frac{2txy-t^2(x^2+y^2)}{2(1-t^2)} \right).
\label{eqn:Mehler}
\end{eqnarray}
Identity \eqref{eqn:Mehler} is the celebrated Mehler's formula, which
was shown combinatorially by Foata \cite{MR58:16322}.
For a discussion of this proof and its relation to other combinatorial
results on orthogonal polynomials, the reader is referred to Stanton
\cite{Stanton2000}.

Carlitz \cite{MR41:3846, MR43:5076} found several multilinear extensions.
Kibble \cite{MR7:65f}, and later independently 
Slepian \cite{MR47:3722} found an extension, 
known as the Kibble-Slepian formula,
whose specializations include all other extensions. 
Louck \cite{MR83a:81036} proposed another extension which was proved 
combinatorially
to be equivalent to the Kibble-Slepian formula by Foata \cite{MR84a:33021}.

To describe the Kibble-Slepian formula, let us first introduce some
notation. 
For each integer $n \geq 2$, define a symmetric $n \times n$ matrix
$R$ by
\[
(R)_{ij} = \begin{cases} r_{ij} & \text{ if $i \neq j$,} \\
                         1      & \text{ otherwise,}
           \end{cases}
\]
where $\{ r_{ij} \}_{i,j \geq 1}$ is an infinite sequence of 
indeterminates.
Let $z = (z_1,\dots,z_n)^T$ be a vector of $n$ indeterminates.
Let $\mathcal{N}$ be the set of all symmetric matrices $N = (\nu_{ij})$
($1 \leq i,j \leq n$) of order $n$ such that $\nu_{ii} = 0$ for all $i \leq n$,
and that $\nu_{ij}$ is a non-negative integer for all $i \neq j$.
Also, for a fixed $N \in \mathcal{N}$, let the $i$th row sum of $N$ be
\[
s_i = \nu_{i1}+\nu_{i2}+\dots+\nu_{in}.
\]

The Kibble-Slepian formula reads
\begin{equation} \label{eqn:Kibble-Slepian}
\sum_{N \in \mathcal{N}}
 \tilde{H}_{s_1}(z_1) \dots \tilde{H}_{s_n}(z_n)
 \frac{\displaystyle{\prod_{i<j} r_{ij}^{\nu_{ij}}}}
      {\displaystyle{\prod_{i<j} \nu_{ij}!}}
=
 \frac{1}{\sqrt{\det R}}
 \exp \left( \frac{1}{2} \bigl( z^Tz - z^TR^{-1}z \bigr) \right).
\end{equation}

Foata and Garsia \cite{MR81a:05007} extended Foata's proof 
\cite{MR58:16322} of the Mehler
formula to give a combinatorial proof of the Kibble-Slepian formula.
The left hand side of \eqref{eqn:Kibble-Slepian} was interpreted as
the exponential generating function of the so-called
\emph{$n$-involutionary graphs}, while the right hand side could
be written as the exponential of the series
\begin{equation} \label{eqn:exponent}
\frac{1}{2} \ln \frac{1}{\det R} +
\frac{1}{2} \sum_{i,j} \bigl(\delta_{ij} - (R^{-1})_{ij}\bigr) z_iz_j. 
\end{equation}
They showed that expression \eqref{eqn:exponent} 
is the generating function for the
``connected components'' of the $n$-involutionary graphs.
Consequently, the exponential formula applies, proving 
\eqref{eqn:Kibble-Slepian}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% q-Mehler
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The $q$-Mehler formula and its extensions}
\label{subsection:qMehler}

A $q$-analogue of the Hermite polynomials
called the $q$-Hermite polynomials,
obtained from the so-called Rogers-Szeg\H o polynomials 
\cite{Rogers-1893, MR81f:33009, desarmenien-1982, MR89h:33015}
can be defined by their generating function $H(x,t \ | \ q)$ as follows:
\begin{equation} \label{eqn:q-Hermite_def}
H(x,t \ | \  q) := 
\sum_{n=0}^{\infty} H_n(x \ | \  q) \frac{t^n}{(q)_n}
=
\prod_{k=0}^{\infty} \frac{1}{(1-2xtq^k+t^2q^{2k})}, \ |t| < 1.
\end{equation}
To get the corresponding $q$-version $\tilde{H}_n(x\ | \ q)$ of 
$\tilde{H}_n(x)$, we also normalize the $H_n(x\ | \ q)$. Define
\begin{equation} \label{eqn:def-tildeH_n}
\tilde{H}_n(x\ | \ q) := \frac{H_n(\frac{x}{2}\sqrt{1-q} \ | \  q)}{(1-q)^{n/2}},
\end{equation}
with the new three term recurrence:
\begin{equation} \label{eqn:normalized_Hermite_3term}
\tilde{H}_{n+1}(x\ | \ q) = x \tilde{H}_n(x\ | \ q) - 
                       (1 + q + \dots + q^{n-1})\tilde{H}_{n-1}(x\ | \ q).
\end{equation}
This recurrence relation yields a combinatorial
interpretation for $\tilde{H}_n(x\ | \ q)$ \cite{MR89h:33015}.
The interpretation gives
$\tilde{H}_n(x\ | \ q)$ as a $q$-analogue of the matching polynomials
$\tilde{H}_n(x)$.
Notice that each matching
$\alpha \in M_n$ can be viewed as an involution on $[1,n]$.
Define a new statistic on $\alpha$ as follows:
\[
s(\alpha) := \sum_{e \in \alpha} s(e),
\]
where  the sum goes over all edges $e$ of $\alpha$, 
and if $e = (i,j)$, $i < j$,  then
\[
s(e) := \left| \{ k \suchthat i < k < j, \text{ and } \alpha(k) < j \}\right|.
\]
Pictorially, imagine putting $n$ points $1,\dots,n$ in this order
on a horizontal line,
then drawing all edges of $\alpha$ on the upper half plane. 
The statistic $s(e)$ for an edge $e$ is
the number of points $k$ lying between $i$ and $j$ such that
$k$ is either a fixed point or an end-point of some edge $e' \in \alpha$,
both of whose end-points are on the left of $j$ (see Figure \ref{fig:s(e)}).
Let $|\alpha|$ denote the number of edges in the matching $\alpha$, and let $F(\alpha)=n-2|\alpha|$ be the number of
fixed points of $\alpha$.
\begin{figure}[hbtp] 
\centerline{ 
\begin{picture}(0,0)%
\includegraphics{s_alpha.pstex}%
\end{picture}%
\setlength{\unitlength}{2171sp}%
%
\catcode`\@=11
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\catcode`\@=12
\begin{picture}(5866,4509)(218,-3874)
\put(226,-3811){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$1$\special{ps: grestore}}}}
\put(2326,-3811){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i$\special{ps: grestore}}}}
\put(4876,-3811){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$j$\special{ps: grestore}}}}
\put(6001,-3811){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$n$\special{ps: grestore}}}}
\put(3451,-3811){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$k$\special{ps: grestore}}}}
\put(1351,-3811){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\alpha(k)$\special{ps: grestore}}}}
\put(226,-2086){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$1$\special{ps: grestore}}}}
\put(2326,-2086){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i$\special{ps: grestore}}}}
\put(4876,-2086){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$j$\special{ps: grestore}}}}
\put(6001,-2086){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$n$\special{ps: grestore}}}}
\put(3151,-2086){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$k$\special{ps: grestore}}}}
\put(4051,-2086){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\alpha(k)$\special{ps: grestore}}}}
\put(226,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$1$\special{ps: grestore}}}}
\put(2326,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i$\special{ps: grestore}}}}
\put(4876,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$j$\special{ps: grestore}}}}
\put(6001,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$n$\special{ps: grestore}}}}
\put(3151,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$k$\special{ps: grestore}}}}
\put(4501,389){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e$\special{ps: grestore}}}}
\put(4501,-1261){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e$\special{ps: grestore}}}}
\put(4501,-2986){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e$\special{ps: grestore}}}}
\put(3976,-1486){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'$\special{ps: grestore}}}}
\put(3451,-3211){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'$\special{ps: grestore}}}}
\end{picture}
}
\caption{Illustration of $s(e)$, where $e = (i,j)$, $i < j$.}
\label{fig:s(e)}
\end{figure}        
It follows that
\begin{equation} \label{eqn:comb-tilde{H}_n(x|q)}
\tilde{H}_n(x\ | \ q) = \sum_{\alpha \in M_n} \tilde{w}(\alpha),
\end{equation}   
where
\begin{equation} \label{eqn:tilde{w}(alpha)}
\tilde{w}(\alpha) = (-1)^{|\alpha|}x^{F(\alpha)}q^{s(\alpha)}.
\end{equation}

On the same line of reasoning as in the previous section, one would hope
that \eqref{eqn:comb-tilde{H}_n(x|q)} helps 
combinatorially discover the $q$-analogues of the Mehler formula
and its extensions. This turned out to be not easy.
There are several known equivalent forms of the $q$-Mehler formula
\cite{MR81f:33009, MR89h:33015}.
In terms of $H_n(x\ | \ q)$, it reads
\begin{multline} \label{eqn:qMehler2}
\sum_{n=0}^{\infty} H_n(x \ | \  q) H_n(y \ | \  q) \frac{t^n}{(q)_n} = \\
\frac{(t^2)_\infty}{\displaystyle{\prod_{k=0}^{\infty}
               \left( 1-4tq^kxy+2t^2q^{2k}(-1+2x^2+2y^2)
	              - 4t^3q^{3k}xy+t^4q^{4k}
	       \right)
               }
              }.
\end{multline}
On the other hand, let $h_n(x\ | \ q)$ be the generating function for the
number of subspaces of $\mathbb{F}_q^n$:
$h_n(x\ | \ q) = \sum_{k=0}^{n} \qnom{n}{k}x^k$,
then
\begin{equation} \label{eqn:qMehler3}
\sum_{n=0}^{\infty} h_n(x \ | \  q) h_n(y \ | \  q) 
\frac{t^n}{(q;q)_n} = 
\frac{(xyt^2)_\infty}{(t)_\infty (xt)_\infty (yt)_\infty (xyt)_\infty}.
\end{equation}
It is this form of the $q$-Mehler formula which has the only known
combinatorial proof \cite{MR89h:33015} using the
vector space interpretation.
However, it does not seem to be possible to extend this proof along Foata
and Garsia's \cite{MR81a:05007} line to
find a multilinear extension of the $q$-Mehler formula.
Firstly, we need a $q$-analogue of the exponential formula, which is
not known in general.
(A somewhat specialized $q$-analogue of the exponential formula
was devised by Gessel \cite{MR84d:05013}, but I do not know how to use
his method on linear spaces over finite fields.)
Secondly, linear subspaces, although very useful in 
enumeration arguments, are difficult to be dealt with in bijective arguments.
Hence, beside needing a $q$-analogue of the exponential formula,
we also need a different combinatorial proof of $q$-Mehler formula which
uses some easier-to-describe combinatorial objects, which is precisely the
main result presented in this paper.

Several multilinear extensions have been found by
Karande and Thakare \cite{MR58:22706}, and
Ismail and Stanton \cite{MR89m:33003}.
However, their formulas all involve an infinite sum, and not as general
as the Kibble-Slepian formula.
It would be interesting to have combinatorial proofs of their findings.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{A $q$-exponential formula}
\label{subsection:qExponential}

Gessel \cite{MR84d:05013} gave a partial answer to the question raised near the 
end of the previous section. 
Let us briefly summarize here his main result which we shall make use of later.
Define a $q$-analogue of the derivative:
\begin{equation} \label{eqn:mathcal{D}}
\mathcal{D} f(t) = \frac{f(t)-f(qt)}{(1-q)t}.
\end{equation}
Suppose $f$ is a function with $f(0)=0$ and $q$-exponential form 
\begin{equation}
f(t) = \sum_{n=0}^\infty f_n \frac{t^n}{n!_q}.
\end{equation}
Let $g=e[f]$ be the $q$-analogue of the function $e^f$, namely
\begin{equation}
g(t) = \sum_{n=0}^\infty g_n \frac{t^n}{n!_q},
\end{equation}
where the coefficients $g_n$ are defined recursively by
\begin{equation} \label{eqn:g-from-f}
g_{n+1}  = \begin{cases} 1 & \text{ if } n=0 ,\\
                     \sum_{k=0}^n \qnom{n}{k}g_{n-k}f_{k+1} & \text{ if }
                     n \geq 1.
       \end{cases}
\end{equation}
Then, we can write $g(t)$ as an infinite product:
\begin{equation} \label{eqn:infinite-prod-e[f]}
g(t) = \prod_{n=0}^\infty 
 \frac{1}{\left( 1-(1-q)q^nt \cdot \mathcal{D}f(q^nt) \right)}.
\end{equation}

\section{Main Results}
\subsection{Main theorem and approach}
\label{subsection:theorem-approach}

The main result of this paper is to provide a $q$-analogue of Foata's proof
of the Mehler's formula. This is done by first introducing another variant
of the $q$-Hermite polynomials denoted $\bar{H}_n(x\ | \ q)$. The
new variant is just a rescaling of the old $\tilde{H}_n(x\ | \ q)$,
and can also be defined combinatorially.
The $q$-Mehler formula for the $\bar{H}_n(x\ | \ q)$ is then obtained
by generalizing Gessel's result summarized in Section 
\ref{subsection:qExponential}.

Specifically, define
\begin{equation} \label{eqn:new-Hn}
\bar{H}_n(x\ | \ q) := i^n q^{\frac{n}{2}} \tilde{H}_n 
           \left( \frac{-ix}{\sqrt{q}} \ | \  q \right).
\end{equation}
Then, these new $q$-Hermite polynomials can be combinatorially defined as 
follows.
\bprop
Let $\bar{w}$ be a weight function on matchings defined by
\begin{equation} \label{eqn:def-barw}
\bar{w}(\alpha) := x^{F(\alpha)} q^{|\alpha| + s(\alpha)}.
\end{equation}
Then,
\begin{equation} \label{eqn:def-barH_n}
\bar{H}_n(x \ | \  q) = \sum_{\alpha \in M_n} \bar{w}(\alpha).
\end{equation}
\eprop
\bp
Recall the combinatorial interpretation \eqref{eqn:comb-tilde{H}_n(x|q)}
of the $\tilde{H}_n(x \ | \ q)$, we get
\begin{eqnarray*}
\bar{H}_n(x\ | \ q)
 & = & i^n q^{n/2} \tilde{H}_n \left( \frac{-ix}{\sqrt{q}} \ | \  q \right) \\
 & = & i^n q^{\frac{n}{2}} \sum_{\alpha \in M_n} 
                 (-1)^{|\alpha|} q^{s(\alpha)} 
                 \left( \frac{-ix}{\sqrt{q}} \right)^{F(\alpha)} \\
 & = & \sum_{\alpha \in M_n}
       \left( i^n (-1)^{|\alpha|} (-i)^{F(\alpha)} \right)
       x^{F(\alpha)}
       q^{\frac{n}{2} - \frac{F(\alpha)}{2} + s(\alpha)} \\
 & = & \sum_{\alpha \in M_n} x^{F(\alpha)} q^{|\alpha| + s(\alpha)}.
\end{eqnarray*}
\ep
The following is the main theorem of the paper.
\bthm
The polynomials $\bar{H}_n(x \ | \ q)$ satisfy the following Mehler-type
identity:
\begin{multline} \label{eqn:qMehler4}
\sum_{n=0}^\infty \bar{H}_n(x\ | \ q) \bar{H}_n(y\ | \ q) \frac{t^n}{n!_q} = \\
\frac{(q^2t^2)_\infty}
     {\prod_{k=0}^\infty
      \left[
        (1-t^2q^{2k+2})^2 - t(1-q)q^k 
         \bigl( (1+t^2q^{2k+2})xy + tq^{k+1}(x^2+y^2) \bigr)
      \right] 
     }.
\end{multline}
\label{thm:main}
\ethm
Note that \eqref{eqn:qMehler4} is the same as \eqref{eqn:qMehler2}
and \eqref{eqn:qMehler3}, up to a change of variables.

Theorem \ref{thm:main} shall be shown in several steps.
Notice that the right hand
side of \eqref{eqn:qMehler4} looks similar to the right hand side of
\eqref{eqn:infinite-prod-e[f]}.
We shall find a function $f$ so that the two are identical.
The coefficients $f_n$ in the $q$-exponential expansion of $f$ shall be
interpreted as enumerating a certain kind $\mathcal{F}$ of new species 
(Section \ref{subsection:involGraphs}) called 
$\mathbb{P}$-species (Section \ref{subsection:moreGeneral2.1}).
Another $\mathbb{P}$-species $\mathcal{G}$ defined from $\mathcal{F}$
is enumerated by a sequence $g_n$ which satisfes
relation \eqref{eqn:g-from-f}.
The $\mathbb{P}$-species basically gives a combinatorial interpretation
of relation \eqref{eqn:g-from-f}.
The last step is to bijectively show that 
$g_n = \bar{H}_n(x\ | \ q) \bar{H}_n(y\ | \ q)$ 
(Section \ref{subsection:bijective}).
The species $\mathcal{G}$ is completely analogous to the bicolored involutionary
graphs introduced by Foata in his proof of the Mehler's formula.
Thus, our proof of Theorem \ref{thm:main} can be thought of as a $q$-analogue
of Foata's proof.
A few simple by-products of the new kind of species shall also be derived.

\subsection{Weighted $\mathbb{P}$-species}
\label{subsection:moreGeneral2.1}

In this section, we generalize
Theorem 5.2 in \cite{MR84d:05013} by introducing a new kind of species
\cite{MR2000a:05008}, which then gives
a combinatorial interpretation of identity \eqref{eqn:g-from-f}.

Let $S_n$ denote the symmetric group on $[1,n]$ as usual.
More generally, we use $Sym(N)$ to denote the set of all permutations
on a totally ordered set $N$ of size $n$.
Each word $\beta = i_1 \dots i_n$ where $\{i_1,\dots,i_n\} = N$
could be thought of as a permutation on $N$
written in one line notation, i.e. $\beta \in Sym(N)$.
The set $N$ is called the \emph{content} of $\beta$, and
is denoted by $cont(\beta)$.
For any $\sigma \in Sym(N)$, we use $I(\sigma)$ to denote the number of
inversions in $\sigma$.
For any two subsets $X$ and $Y$ of $N$,
let $I(X,Y)$ denote the number of inversions
created by pairs of elements in $X$ and $Y$, namely
\[
I(X,Y) = |\{ (i,j) \suchthat i > j, i \in X, j \in Y \}|.
\]

Let $\mathbb{K} \subseteq \mathbb{C}$ be an integral domain and
$\mathbb{A} = \mathbb{K}[\![q,t_1,t_2,\dots]\!]$ be a ring of formal power
series or of polynomials over $\mathbb{K}$ on the variables
$q, t_1, \dots$.
An \emph{$\mathbb{A}$-weighted set} is a pair $(A,w)$ where $A$ is a set 
and $w: A \to \mathbb{A}$ is a function associating a weight $w(a)$ to each
element $a \in A$.
An $\mathbb{A}$-weighted set $(A,w)$ is said to be \emph{summable} if
for each monomial $\mu = q^{n_0}t_1^{n_1}t_2^{n_2} \dots$, 
the number of elements
$a \in A$ whose weight $w(a)$ contributes a non-zero coefficient to $\mu$
is finite.
We are now ready to describe the new species.

\bdefn
An \emph{$\mathbb{A}$-weighted $\mathbb{P}$-species}
is a rule $\mathcal{F}$ which
\bi
\item[(i)]
to each totally ordered set $N$, and each permutation $\sigma \in Sym(N)$,
\emph{associates} an $\mathbb{A}$-weighted set $(\mathcal{F}[N,\sigma],w)$,
\item[(ii)]
to each increasing bijection $\gamma: N_1 \longrightarrow N_2$, and each 
permutation $\sigma \in S_{|N_1|}$ ($=S_{|N_2|}$),
\emph{associates} a weight-preserving bijection
\[
\mathcal{F}[\gamma, \sigma]: 
(\mathcal{F}[N_1,\sigma_1],w) \longrightarrow (\mathcal{F}[N_2,\sigma_2],w),
\]
where $\sigma_1 \in Sym(N_1)$ and $\sigma_2 \in Sym(N_2)$ are derived from
$\sigma$ in the natural way.
\ei

Moreover, these functions $\mathcal{F}[\gamma, \sigma]$ must also satisfy the
\emph{functorial properties}:
\begin{eqnarray}
\mathcal{F}[Id_N, \sigma] & = & Id_{\mathcal{F}[N,\sigma]} ,\\
\mathcal{F}[\beta \circ \gamma, \sigma] & = &
 \mathcal{F}[\beta, \sigma] \circ \mathcal{F}[\gamma, \sigma].
\end{eqnarray}
\edefn

Basically, the functorial properties say that the weighted sets 
$(\mathcal{F}[N,\sigma], w)$ depend only on the fact that $N$ is totally 
ordered and on $N$'s cardinality.
When $|N|=n$ we shall use $\mathcal{F}[n,\sigma]$ to denote
$\mathcal{F}[N,\sigma]$, and $\mathcal{F}[n]$ to denote
$\bigcup_{\sigma \in S_n} \mathcal{F}[n, \sigma]$.

\bdefn
Let $\mathcal{F}$ be an $\mathbb{A}$-weighted $\mathbb{P}$-species with weight
function $w$.
The \emph{$\mathbb{P}$-generating series} of $\mathcal{F}$ is the $q$-exponential
formal power series $F_w(t \ | \ q)$ with 
coefficients in $\mathbb{A}$ defined by
\begin{equation}
F_w(t \ | \ q) := \sum_{n \geq 0} |\mathcal{F}[n]|_w 
                  \frac{t^n}{n!_q},
\end{equation}
where the \emph{$q$-inventory} $|\mathcal{F}[n]|_w$ is defined by
\begin{equation}
|\mathcal{F}[n]|_w := \sum_{\sigma \in S_n} \sum_{a \in \mathcal{F}[n,\sigma]} w(a)q^{I(\sigma)}.
\end{equation}
\edefn

Theorem 5.2 of \cite{MR84d:05013} was about partitioning permutations 
into basic blocks
with a multiplicative weight function on the blocks.
We generalize this notion by defining the so-called
permutation partition.
\bdefn
Given $\sigma \in S_n$, a \emph{permutation partition} $\pi$ of $\sigma$ is
a sequence of non empty words $\pi = (\sigma_1,\dots,\sigma_k)$ such that
\[
\sigma = \sigma_1 \sigma_2 \dots \sigma_k
\]
in one line notation, and that the largest elements of 
$\sigma_1,\dots,\sigma_k$ form an increasing sequence.
We shall write
$ \pi \vdash \sigma $ for ``$\pi$ is a permutation partition of $\sigma$.''
\edefn
We are now ready to define a $\mathbb{P}$-species whose ``connected components''
are structures of another $\mathbb{P}$-species.
\bdefn
Let $\mathcal{F}_v$ be a weighted $\mathbb{P}$-species with weight function 
$v$. Define the $\mathbb{P}$-species 
$\mathcal{G}_w = \mathcal{E}(\mathcal{F})_w$ with weight function $w$ 
as follows.
For each totally ordered set $N$ and $\sigma \in Sym(N)$, define
\begin{equation}
\mathcal{G}[N,\sigma] :=
 \bigcup_{\pi \vdash \sigma} 
 \mathcal{F}[N_1,\sigma_1] \times \dots \times \mathcal{F}[N_k,\sigma_k],
\end{equation}
where
$\pi = (\sigma_1, \dots, \sigma_k)$, and
$N_i = cont(\sigma_i)$, for all  $i=1,\dots,k$.
Moreover, for each 
\[
G=(F_1, \dots, F_k) \in 
\mathcal{F}[N_1,\sigma_1] \times \dots \times \mathcal{F}[N_k,\sigma_k]
\]
we associate
\begin{equation}
w(G) = v(F_1) \dots v(F_k).
\end{equation}
\edefn
This is the analogue of the multiplicative property in Theorem 5.2 of
\cite{MR84d:05013}.
The fact that $\mathcal{E}(\mathcal{F})_w$ is a $\mathbb{P}$-species is
easy to verify.
At last, the promised generalization of Theorem 5.2 in \cite{MR84d:05013}
can now be stated:

\bthm
Let $\mathcal{F}_v$ be a $\mathbb{P}$-species of structures with weight
function $v$. Let $\mathcal{G}_w$ be the $\mathbb{P}$-species
$\mathcal{E}(\mathcal{F})_w$ defined as above.
Define a sequence $\{g_n\}_{n=0}^\infty$ by $g_0=1$ and
\[
g_n = |\mathcal{G}[n]|_w, \ \ \text{$n \geq 1$}.
\]  
Let $\{f_n\}_{n=0}^\infty$ be the sequence defined
by $f_0=0$, and
\[
f_{k+1} = |\mathcal{F}[k+1]|_v, \ \ \text{for $k\geq 0$}.
\]
Then,
\begin{equation}
1 + \sum_{n=1}^\infty g_n \frac{t^n}{n!_q} =
e \left[ \sum_{n=1}^\infty f_n \frac{t^n}{n!_q} \right]
=
\prod_{n=0}^\infty
 \frac{1}{\left( 1-(1-q)q^nt \cdot \mathcal{D}F_v(q^nt) \right)}.
\end{equation}
namely
\begin{equation}
G_w(t \ | \ q) = e[F_v(t \ | \ q)].
\end{equation}
\label{thm:hngo2.1}
\ethm
\bp
We only need to verify that the sequences $g_n$ and $f_n$ satisfy
relation \eqref{eqn:g-from-f}.
Recall that each $G \in \mathcal{G}[n+1]$ is a sequence
of structures of $\mathcal{F}$: $G = (F_1,\dots,F_m)$.
Let $\sigma_1,\dots,\sigma_m$ be the corresponding permutations
(or words) underlying $F_1, \dots, F_m$.
Let $N_i = cont(\sigma_i)$, for each $i=1, \dots, m$.
Notice that $n+1 \in N_m$.
Suppose $|F_m| = k+1$, $k \geq 0$. Let $V := N_m$,
$K := V-\{n+1\}$, and $\bar{V} := [1,n+1]-V$.
Note that $I(\bar{V},V)=I(\bar{V},K)$ since $n+1 \in V$.
Furthermore, let $G' \in \mathcal{G}[\bar{V}]$ be the structure of
species $\mathcal{G}$ obtained from $G$ by removing $F_m$.
For each structure $C$ of a $\mathcal{P}$-species, we
use $\sigma(C)$ to denote the underlying permutation of $C$.

It is clear that
\[
I(\sigma(G)) = I(\bar{V},K) + I(\sigma(G')) + I(\sigma(F_m)),
\]
and that
\[
w(G) = w(G') v(F_m).
\]
 
In order to form a $G \in \mathcal{G}[n+1]$, we
can first pick a $k$-subset $K$ of $[1,n]$ ($0\leq k \leq n$),
then form $V = K \cup \{ n+1 \}$, and finally concatenate
any pair of $G' \in \mathcal{G}[\bar{V}]$ and
$F_m \in \mathcal{F}[V]$.
Consequently, 
\begin{eqnarray*}
g_{n+1}
 &=& \sum_{G \in \mathcal{G}[n+1]} w(G) q^{I(\sigma(G))} \\
 &=& \sum_{k=0}^n
     \sum_{K, |K|=k}
     \sum_{G' \in \mathcal{G}[\bar{V}]}
     \sum_{F_m \in \mathcal{F}[V]}
     q^{I(\bar{V},K)} \times w(G')q^{I(\sigma(G'))} \times v(F_m) q^{I(\sigma(F_m))} \\
 &=& \sum_{k=0}^n
     \sum_{K, |K|=k}
     \sum_{G' \in \mathcal{G}_{n-k}}
     \sum_{F_m \in \mathcal{F}_{k+1}}
     q^{I(\bar{V},K)} \times w(G')q^{I(\sigma(G'))} \times v(F_m) q^{I(\sigma(F_m))} \\
 &=& \sum_{k=0}^n
     \left( \sum_{K, |K|=k} q^{I([n]-K,K)} \right)
     \left( \sum_{G' \in \mathcal{G}_{n-k}} w(G')q^{I(\sigma(G'))} \right)
     \left( \sum_{F_m \in \mathcal{F}_{k+1}} v(F_m) q^{I(\sigma(F))} \right) \\
 &=& \sum_{k=0}^n \qnom{n}{k}g_{n-k}f_{k+1}.
\end{eqnarray*}
\ep 

\begin{ex}
Theorem \ref{thm:hngo2.1} implies Theorem 5.2 in \cite{MR84d:05013} and thus
all its consequences as derived by Gessel.
\end{ex}

\begin{ex}
Take $v \equiv 1$ so that $w \equiv 1$ in Theorem \ref{thm:hngo2.1}, we obtain
\begin{equation}
1 + \sum_{n=1}^\infty g_n \frac{t^n}{n!_q} =
\frac{(t;q)_\infty (tq;q)_\infty}
     {\prod_{n=0}^\infty \bigl( 1-2tq^n+t^2q^{2n+1}\bigr)},
\label{eqn:example1}
\end{equation}
where,
\[
g_n = 
\sum_{\sigma \in S_n} |\{ \pi \suchthat \pi \vdash \sigma \}| q^{I(\sigma)}.
\]
In fact, when $q \to 1$, $g_n$ counts the number of sets of words on $[1,n]$
whose contents are disjoint and whose union of contents is exactly $[1,n]$.
While, when $q \to 1$ the right hand side of \eqref{eqn:example1} goes
to $\exp \bigl( t/(1-t) \bigr)$. Thus, we could have proven
easily identity \eqref{eqn:example1} combinatorially when $q=1$.
\end{ex}

Following Gessel's line of derivation we can generalize the previous
example as follows.
\bcor
Let $\pi = (\sigma_1,\dots,\sigma_k)$ be any permutation partition of
$\sigma \in S_n$. 
Let $b_i(\pi)$ be the number of words of size $i$ of $\pi$.
Define a weight function $w$ for $\pi$ by 
$w(\pi) = \prod_i x_i^{b_i(\pi)}$, and let
\begin{equation}
g_n = \sum_{\sigma \in S_n} \sum_{\pi \vdash \sigma} w(\pi)q^{I(\sigma)}.
\end{equation}
Then,
\begin{equation}
G_w(t \ | \ q) = \prod_{n=0}^{\infty}
\frac{1}{\bigl( 1-(1-q)q^ntX(q^nt) \bigr)},
\end{equation}
where 
\[ X(t) = \sum_{n=0}^\infty x_{n+1}[n+1]_qt^n. \]
\label{cor:X(t)}
\ecor
\begin{ex}
Write $\pi \vdash_k \sigma$ if $\pi \vdash \sigma$ and all words of $\pi$
are of size at most $k$. Set $X(t) = x + (1+q)t$, so that
\[
w(\pi) = \begin{cases} x^{b_1(\pi)} & \text{ if $\pi \vdash_2 \sigma$ } \\
                        0            & \text{ otherwise,}
          \end{cases}
\]   
and hence
\[
g_n(x \ | \ q) = \sum_{\sigma \in S_n} \sum_{\pi \vdash_2 \sigma}
                 x^{b_1(\pi)} q^{I(\sigma)}.
\]

Corollary \ref{cor:X(t)} gives
\begin{eqnarray}
G_w(x,t \ | \  q) = \sum_{n=0}^\infty g_n(x \ | \  q) \frac{t^n}{n!_q}
&=& \prod_{n=0}^\infty \frac{1}{1-(1-q)q^nt X(q^{n}t)}     \nonumber \\
&=& \prod_{k=0}^\infty \frac{1}{1-2uzq^k + z^2q^{2k}},
\label{eqn:gen-g2}
\end{eqnarray}  
where $u=\frac{-it}{2}\sqrt{\frac{1-q}{1+q}}$ and 
$z=it\sqrt{1-q^2}$. We now get
\begin{equation}
g_n(x \ | \ q) = i^n(1+q)^{n/2} 
               \tilde{H}_n\left( \left. \frac{-ix}{\sqrt{1+q}} \right| q \right)
\label{eqn:anotherId1}.
\end{equation}
Thus,
\begin{equation}
\sum_{\sigma \in S_n} \sum_{\pi \vdash_2 \sigma}
                 x^{b_1(\pi)} q^{I(\sigma)} = 
\sum_{\alpha \in M_n} (1+q)^{|\alpha|} q^{s(\alpha)}x^{F(\alpha)},
\label{eqn:anotherId2}
\end{equation}
an interesting combinatorial identity.
\end{ex}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{A $q$-analogue of the bicolored $n$-involutionary graphs}
\label{subsection:involGraphs}

The previous section gives a combinatorial view of identity
\eqref{eqn:g-from-f}. As outlined at the end of section 
\ref{subsection:theorem-approach}, the next step in the proof of
Theorem \ref{thm:main} is to find a $\mathbb{P}$-species
$\mathcal{F}_v$ whose $\mathbb{P}$-generating series
$f(t) = \mathcal{F}_v(t \ | \ q)$ is such that the right hand side
of \eqref{eqn:infinite-prod-e[f]} is the same as that of 
\eqref{eqn:qMehler4}.
The $\mathbb{P}$-species $\mathcal{G}_w = \mathcal{E}(\mathcal{F})_w$
is a $q$-analogue of the bicolored 
$n$-involutionary graphs. 
We actually will start defining $\mathcal{G}$ first.

\bdefn
A graph $G=(N,E)$ is called an 
\emph{ordered bicolored $n$-involutionary graph}
if $G$ satisfies the following conditions:
%
\be
%
\item $G$ has $n$ vertices labeled by $n$ distinct positive integers in $N$.
%
\item $G$ has no multiple edges, but can have loops.
%
\item The $n$ vertices of $G$ line up on a horizontal line, so that
we can speak of a vertex being on the left or right of another, and 
so that the vertices of $G$ forms a permutation 
$\pi(G) = \pi_1\pi_2\dots\pi_n \in Sym(N)$.
%
\item Each edge of $G$ is colored  either red or blue.
%
\item Each vertex of $G$ is incident to exactly $2$ edges of different colors.
%
\item A non-loop edge of $G$ can only connect some $\pi_i$ to $\pi_{i+1}$
unless it completes a cycle of $G$.
\item Let $C_1, \dots, C_m$ be the connected components of $G$ from
left to right. 
Let $L(C)$ denote the largest vertex number in a connected component $C$
of $G$, then $\pi(G)$ must satisfy the condition that
$L(C_1) < \dots < L(C_m)$.
%
\item For each connected component $C$, the vertex numbered $L(C)$
has to be on the left of the blue edge incident to it.
%
\item If a connected component $C$ is a cycle, then the vertex
numbered $L(C)$ has to be the left most vertex among all vertices of $C$.
It is not difficult to see that the connected components of $G$ can 
only be in one of $5$ forms as shown in Figure \ref{fig:CC-types}.
In the figure, the bold lines represent blue edges and the thin lines
represent red edges.
\begin{figure}[hbtp] 
\centerline{ 
\begin{picture}(0,0)%
\includegraphics{CC-types.pstex}%
\end{picture}%
\setlength{\unitlength}{2171sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(12232,4122)(185,-3649)
\put(226,-1486){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x$\special{ps: grestore}}}}
\put(5326,-1486){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y$\special{ps: grestore}}}}
\put(9976, 89){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$Blue$\special{ps: grestore}}}}
\put(9976,-511){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$Red$\special{ps: grestore}}}}
\put(1576,-736){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$L(C)$\special{ps: grestore}}}}
\put(226,-3586){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y$\special{ps: grestore}}}}
\put(5326,-3586){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y$\special{ps: grestore}}}}
\put(3301,-2011){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$L(C)$\special{ps: grestore}}}}
\put(376,-2911){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$L(C)$\special{ps: grestore}}}}
\put(6976,-1486){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y$\special{ps: grestore}}}}
\put(12076,-1486){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x$\special{ps: grestore}}}}
\put(12076,-3586){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x$\special{ps: grestore}}}}
\put(6976,-3586){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x$\special{ps: grestore}}}}
\put(8251,-2011){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$L(C)$\special{ps: grestore}}}}
\put(7651,-2986){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$L(C)$\special{ps: grestore}}}}
\end{picture}
}
\caption{Possible connected component types of an ordered bicolored 
         $n$-involutionary graph.}
\label{fig:CC-types}
\end{figure}                
\ee
\edefn

Let $\mathcal{G}_N$ denote the set of all ordered 
bicolored $n$-involutionary graphs on $N$, 
where $N$ is an $n$-set of positive integers.
Let $\mathcal{C}_N$ be the set of all graphs in $\mathcal{G}_N$
which have exactly one connected component. 
When $N=[1,n]$, $\mathcal{G}_n$ and $\mathcal{C}_n$ shall be used
for convenience.

Let $\phi: N \to [1,n]$ be the trivial one-to-one correspondence between
$N$ and $[1,n]$ which preserves order.
For each $G \in \mathcal{G}_N$, let $red(G)$ denote the
graph obtained from $G$ by renumbering each vertex $v$ of $G$ by $\phi(v)$.
Conversely, we also use $N(G)$ to denote the set of vertices of $G$.

\bdefn
A weight function $w$ defined on $\mathcal{G}_N$ with values over some
commutative algebra over the rationals is said to be
\emph{multiplicative} if it satisfies the following conditions:
\bi
\item[(i)] $w(G) = w(red(G))$.
\item[(ii)] If $\gamma_1, \dots, \gamma_k$ are the connected components
of $G$ (which are ordered bicolored involutionary graphs themselves), then
$w(G) = w(\gamma_1) \dots w(\gamma_k)$.
\ei
\edefn

The following theorem is obviously a very special case of
Theorem \ref{thm:hngo2.1}
applied to the ordered bicolored involutionary graphs.

\bthm
Supposed $w$ is a multiplicative function on $\mathcal{G}_n$.
For $n \geq 0$, define a sequence $\{g_n\}_{n=0}^\infty$
\[
g_n = \sum_{G \in \mathcal{G}_n} w(G) q^{I(\pi(G))}.
\]
Let $\{f_n\}_{n=0}^\infty$ be the sequence defined
by $f_0=0$, and 
\[
f_{k+1} = \sum_{C \in \mathcal{C}_{k+1}} w(C) q^{I(\pi(C))}
\]
for $k\geq 0$.
Then,
\[
\sum_{n=0}^\infty g_n \frac{t^n}{n!_q} = 
e \left[ \sum_{n=1}^\infty f_n \frac{t^n}{n!_q} \right].
\]
\label{thm:myVersion}
\ethm

\bdefn
Let $G$ be a graph in $\mathcal{G}_N$.
For each edge $e$ (respectively vertex $i$) of $G$, let $C(e)$ 
(respectively $C(i)$)
denote the connected component containing $e$ (respectively $i$).
Define a weight function $\theta$ on each edge $e$ of $G$ as follows:
\[
\theta(e) = 
\begin{cases}
q & \text{if $e$ is a non-loop red edge} ,\\
q & \text{if $e$ is non-loop, blue and to the left of $L(C(e))$} ,\\
1 & \text{if $e$ is non-loop, blue and to the right of $L(C(e))$} ,\\
y & \text{if $e$ is a red loop} ,\\
x & \text{if $e$ is a blue loop}.
\end{cases}
\]
Let $\theta$ be a weight function defined on $\mathcal{G}_N$ by:
\[
\theta(G) = \prod_{e \in E(G)}\theta(e),
\]
then obviously $\theta$ is multiplicative.
\edefn

We call an ordered bicolored $n$-involutionary graphs with the weight
$\theta$ associated a
\emph{bicolored $(q,n)$-involutionary graph}.
Figure \ref{fig:involutionary} shows an example of such a graph.
\begin{figure}[hbtp] 
\centerline{ 
\begin{picture}(0,0)%
\includegraphics{involutionary.pstex}%
\end{picture}%
\setlength{\unitlength}{2171sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(10267,2649)(260,-1942)
\put(451,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$3$\special{ps: grestore}}}}
\put(2251,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$1$\special{ps: grestore}}}}
\put(3151,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\mathbf{10}$\special{ps: grestore}}}}
\put(3751,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$8$\special{ps: grestore}}}}
\put(1051,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\mathbf{9}$\special{ps: grestore}}}}
\put(4951,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$7$\special{ps: grestore}}}}
\put(1651,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$5$\special{ps: grestore}}}}
\put(4351,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$4$\special{ps: grestore}}}}
\put(6451,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$12$\special{ps: grestore}}}}
\put(7651,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$11$\special{ps: grestore}}}}
\put(9451,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\bfdefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\mathbf{15}$\special{ps: grestore}}}}
\put(8851,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$13$\special{ps: grestore}}}}
\put(10051,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$2$\special{ps: grestore}}}}
\put(301,164){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x$\special{ps: grestore}}}}
\put(751, 14){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$q$\special{ps: grestore}}}}
\put(1351, 14){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$1$\special{ps: grestore}}}}
\put(1951, 14){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$q$\special{ps: grestore}}}}
\put(4051,539){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$q$\special{ps: grestore}}}}
\put(3526, 14){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$1$\special{ps: grestore}}}}
\put(4051, 14){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$q$\special{ps: grestore}}}}
\put(4651, 14){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$1$\special{ps: grestore}}}}
\put(5851,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$6$\special{ps: grestore}}}}
\put(7051,-436){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\mathbf{14}$\special{ps: grestore}}}}
\put(5701,164){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y$\special{ps: grestore}}}}
\put(2401,164){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x$\special{ps: grestore}}}}
\put(7801,164){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y$\special{ps: grestore}}}}
\put(8701,164){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x$\special{ps: grestore}}}}
\put(10201,164){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y$\special{ps: grestore}}}}
\put(6151, 14){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$q$\special{ps: grestore}}}}
\put(6751, 14){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$q$\special{ps: grestore}}}}
\put(7351, 14){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$1$\special{ps: grestore}}}}
\put(9151, 14){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$q$\special{ps: grestore}}}}
\put(9751, 14){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$1$\special{ps: grestore}}}}
\put(1201,-1186){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\pi = (3, 9, 5, 1, 10, 8, 4, 7, 6, 12, 14, 11, 13, 15, 2)$\special{ps: grestore}}}}
\put(8176,-1186){\makebox(0,0)[lb]{\smash{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$I(\pi) = 33$\special{ps: grestore}}}}
\put(4051,-1861){\makebox(0,0)[lb]{\smash{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\theta(G)q^{I(\pi)} = q^{7}x^3y^3 \times q^{33}$\special{ps: grestore}}}}
\end{picture}
}
\caption{An example of a bicolored $(q,n)$-involutionary graph.}
\label{fig:involutionary}
\end{figure}                
In the figure, the largest vertex number $L(C)$ in each component $C$
has been put in bold face.

\blmm
Let $\theta$ be the function defined above, and $\{f_n\}_{n=0}^\infty$
be a sequence defined by $f_0=0$ and 
\[
f_n = \sum_{C \in \mathcal{C}_n} \theta(C) q^{I(\pi(C))},
\ \text{when $n \geq 1$}.
\]
Moreover, let
\[
f(t\ | \ q) := \sum_{n=0}^\infty f_n \frac{t^n}{n!_q}.
\]
Then,
\begin{equation}
\mathcal{D}f(t\ | \ q) = 
\frac{(1-t^2q^2)tq^2 + (1+t^2q^2)xy + tq(x^2+y^2)}
     {(1-t^2q^2)(1-t^2q^3)}
\label{eqn:toprove}.
\end{equation}
\label{lmm:f}
\elmm
\bp
Firstly, we claim that
\[
f_{2k+1} = ([k]+[k+1])q^{2k}(2k)!_q xy.
\]
To see this, let us consider Figure \ref{fig:CC-types}. The components
in $\mathcal{C}_{2k+1}$ can only be the paths which start and end with
different colored loops, and have largest vertex number $2k+1$.
Summing $\theta(C) q^{I(\pi(C))}$ over all components $C$ which start
with a blue loop and end with a red loop we get the term
\[
[k] q^{2k} (2k)!_q xy,
\]
while the components which start red and end blue introduce the term
\[
[k+1] q^{2k} (2k)!_q xy.
\]
The details are easy to be verified and hence omitted here.

Secondly, we claim that
\[
f_{2k+2} = q^{3k+2} (2k+1)!_q + [k+1]q^{2k+1}(2k+1)!_q (x^2+y^2).
\]
Here, the term $q^{3k+2} (2k+1)!_q$ is from the cycle components,
$[k+1]q^{2k+1}(2k+1)!_q x^2$ from the paths which start and end with a blue 
loop, and $[k+1]q^{2k+1}(2k+1)!_q y^2$ from the paths which start and end
with a red loop.

By definition, 
\begin{eqnarray*}
f(t\ | \ q) &=& \sum_{n=0}^\infty f_n \frac{t^n}{n!_q} \\
&=& \sum_{k=0}^\infty ([k]+[k+1])q^{2k}(2k)!_q xy \frac{t^{2k+1}}{(2k+1)!_q} \\
&&+ \sum_{k=0}^\infty \left( q^{3k+2} (2k+1)!_q + [k+1]q^{2k+1}(2k+1)!_q 
                            (x^2+y^2)
                     \right) \frac{t^{2k+2}}{(2k+2)!_q}.
\end{eqnarray*}
Hence,
\begin{multline}
\mathcal{D}f(t\ | \ q) = 
\sum_{k=0}^\infty ([k]+[k+1])q^{2k} xy t^{2k} + 
\sum_{k=0}^\infty q^{3k+2} t^{2k+1}  \\
+\sum_{k=0}^\infty [k+1]q^{2k+1}(x^2+y^2) t^{2k+1}.
\label{eqn:Df}
\end{multline}

Now, we calculate each term of \eqref{eqn:Df} separately as follows:
\begin{equation} \label{eqn:term1}
\begin{split}
xy \sum_{k=0}^\infty ([k]+[k+1]) q^{2k} t^{2k}
& = xy (1+t^2q^2) \sum_{k=0}^\infty [k+1] q^{2k} t^{2k} \\
& = xy (1+t^2q^2) \sum_{k=0}^\infty 
    \left( \sum_{j=0}^k q^{2(k-j)+3j} \right) t^{2k} \\
& = xy (1+t^2q^2) \sum_{i=0}^\infty t^{2i}q^{2i}
    \sum_{j=0}^\infty t^{2j}q^{3j} \\
& = \frac{(1+t^2q^2)xy}{(1-t^2q^2)(1-t^2q^3)}.
\end{split}
\end{equation}
Similarly,
\begin{equation} \label{eqn:term2}
\sum_{k=0}^\infty q^{3k+2} t^{2k+1}
= \frac{tq^2}{1-t^2q^3},
\end{equation}
and
\begin{equation} \label{eqn:term3}
\begin{split}
(x^2+y^2) \sum_{k=0}^\infty [k+1]q^{2k+1}t^{2k+1}
& = (x^2+y^2)tq \sum_{k=0}^\infty 
                \left( \sum_{j=0}^k q^{2k+j} \right) t^{2k} \\
& = (x^2+y^2)tq \sum_{k=0}^\infty 
                \left( \sum_{j=0}^k q^{2(k-j)+3j} \right) t^{2(k-j)+2j} \\
& =  (x^2+y^2)tq \sum_{i=0}^\infty t^{2i}q^{2i} 
                  \sum_{j=0}^\infty t^{2j}q^{3j} \\
& = \frac{tq(x^2+y^2)}{(1-t^2q^2)(1-t^2q^3)}.
\end{split}
\end{equation}

Combining \eqref{eqn:term1}, \eqref{eqn:term2} and \eqref{eqn:term3}
yields \eqref{eqn:toprove}.
\ep

\bcor
Let $\theta$ be the function defined above, and $\{g_n\}_{n=0}^\infty$
be a sequence defined by
\begin{equation}
g_n = \sum_{G \in \mathcal{G}_n} \theta(G) q^{I(\pi(G))}.
\label{eqn:g_n}
\end{equation}
Then,
\[
g(t\ | \ q) =
\frac{(q^2t^2)_\infty}
     {\prod_{k=0}^\infty
      \left[
       (1-t^2q^{2k+2})^2 - t(1-q)q^k 
       \bigl( (1+t^2q^{2k+2})xy + tq^{k+1}(x^2+y^2) \bigr)
      \right] 
     },
\]
where 
\[
g(t\ | \ q) = \sum_{n=0}^\infty g_n \frac{t^n}{n!_q}.
\]
\label{cor:myCor}
\ecor
\bp
This is straightforward from Theorem \ref{thm:myVersion},
Lemma \ref{lmm:f} and equation \eqref{eqn:infinite-prod-e[f]}.
\ep

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{A bijection}
\label{subsection:bijective}

This section completes the last step of the proof of Theorem
\ref{thm:main}.
We are left to demonstrate that
$\bar{H}_n(x\ | \ q) \bar{H}_n(y\ | \ q) = g_n$.
We shall show this relation combinatorially as formally put in the
following theorem.

\bthm
Let 
$\bar{H}_n$ be defined combinatorially by 
equation \eqref{eqn:def-barH_n}, and $g_n$ 
by equation \eqref{eqn:g_n}. Then,
\[
\bar{H}_n(x\ | \ q) \bar{H}_n(y\ | \ q) = g_n.
\]
\label{thm:bijective}
\ethm
\bp
We want to find a weight-preserving bijection $\varphi$ which maps a pair 
$(\alpha, \alpha') \in M_{n+1} \times M_{n+1}$
to a graph $G \in \mathcal{G}_{n+1}$.
Let $(\alpha, \alpha')$ be a pair of matchings in $M_{n+1} \times M_{n+1}$, 
where the fixed points of $\alpha$ are weighted by $x$ and of $\alpha'$ by $y$.
As before, we view the vertices $1, \dots, n+1$ of $\alpha$ and $\alpha'$ 
as lying on a horizontal line from left to right in that order, 
with the edges drawn on the upper half plane.
Let $p_1, \dots, p_a$ ($a \leq n+1$) be the sequence of vertices of
$\alpha$ starting from the right which are not left end-points
of $\alpha$'s edges.
Similarly, let $p'_1, \dots, p'_{a'}$ be the corresponding sequence
for $\alpha'$.
Notice that $p_1 = p'_1 = n+1$.
Let $e_1, \dots, e_{|\alpha|}$ 
(respectively $e'_1, \dots, e'_{|\alpha'|}$) be the set of edges
of $\alpha$ (respectively $\alpha'$)
ordered by their right end-points starting from the right.

Our idea is to start from the right, look simultaneously at
$p_1$ and $p'_1$, $p_2$ and $p'_2$, ... determine the ``right place'' to
stop and build up the right most connected component of $G$ based on
the relative distribution of edges and points of $\alpha$ and $\alpha'$
seen so far. Then, remove certain points and edges from $\alpha$ and $\alpha'$
to get $\beta$ and $\beta'$ respectively, and re-apply the method
to get the next (from the right) connected component of $G$, and so on.

Looking at $p_1$ and $p'_1$, $p_2$ and $p'_2$, ... there will roughly
be $5$ situations as follows.
\be
\item At some $k+1$, all of $p_i$ and $p'_i$, $1 \leq i \leq k+1$,
are right end-points of edges in $\alpha$ and $\alpha'$ respectively,
and $j=k+1$ is the least integer such that $s(e_j)=0$.
\item We meet a fixed point $p_{m+1}$ of $\alpha$ and then a fixed point
$p_{k+1}$ of $\alpha'$ where $m \leq k$. 
For this case to be disjoint from case 1, it is necessary
that all edges $e$ of $\alpha$ whose right end-points are on the right
of $p_{m+1}$ have $s(e) > 0$.
\item We meet a fixed point $p'_{m+1}$ of $\alpha'$ strictly before
a fixed point $p_{k+1}$ of $\alpha$.
\item Two fixed points of $\alpha$ are met before any fixed points of $\alpha'$.
\item Two fixed points of $\alpha'$ are met before any fixed points of $\alpha$.
\ee
Note that similar to case 2, the cases 3, 4, and 5 need to be defined
so that they are disjoint from case 1.
These cases determine our ``right place'' to stop as mentioned above.

Formally, we consider $5$ cases as follows.

\bi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Case 1
\item[Case 1.] There exists a $k$, $0 \leq k \leq \frac{(n-1)}{2}$, such that 
\bi
\item[(i)] $j=k+1$ is the smallest integer where $s(e_j) = 0$.
(i.e. $s(e_j) > 0$ for all $j \leq k$.)
\item[(ii)] For all $j=1, \dots,k+1$, $e_j$ has right end-point $p_j$
and $e'_j$ has right end-point $p'_j$.
\ei
The situation is depicted in Figure \ref{fig:case1}. 
\begin{figure}[hbtp] 
\centerline{ 
\begin{picture}(0,0)%
\includegraphics{case1.pstex}%
\end{picture}%
\setlength{\unitlength}{1973sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(12105,2898)(279,-2224)
\put(7276,-961){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$n+1$\special{ps: grestore}}}}
\put(12151,-961){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_1$\special{ps: grestore}}}}
\put(11626,-961){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_2$\special{ps: grestore}}}}
\put(8026,-961){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_{2k+1}$\special{ps: grestore}}}}
\put(8626,-961){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_{2k}$\special{ps: grestore}}}}
\put(4726,464){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_1$\special{ps: grestore}}}}
\put(4726,-961){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_1$\special{ps: grestore}}}}
\put(3526,464){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_k$\special{ps: grestore}}}}
\put(2101, 14){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_{k+1}$\special{ps: grestore}}}}
\put(2851,-961){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_{k+1}$\special{ps: grestore}}}}
\put(3451,-961){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_k$\special{ps: grestore}}}}
\put(6301,-661){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\varphi$\special{ps: grestore}}}}
\put(4951,-586){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$p_1$\special{ps: grestore}}}}
\put(3826,-586){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$p_k$\special{ps: grestore}}}}
\put(3151,-586){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$p_{k+1}$\special{ps: grestore}}}}
\put(4951,-2161){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$p'_1$\special{ps: grestore}}}}
\put(3151,-2161){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$p'_{k+1}$\special{ps: grestore}}}}
\put(3751,-2161){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$p'_k$\special{ps: grestore}}}}
\put(6001,-1786){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$0 \leq k \leq \frac{n-1}{2}$\special{ps: grestore}}}}
\end{picture}
}
\caption{Illustration of case 1.}
\label{fig:case1}
\end{figure}                
Let $\beta$ (respectively $\beta'$) be the matching obtained by
removing $e_1, \dots, e_{k+1}$ and their end-points 
(respectively $e'_1, \dots, e'_{k+1}$ and their end-points) from $\alpha$
(respectively $\alpha'$).
We shall construct $G = \varphi(\alpha, \alpha')$ such that the last
connected component of $G$ is a cycle $C = (n+1,i_{2k+1},\dots,i_1)$,
and that $\varphi(\beta, \beta')$ forms the rest of the components of $G$.
Let $R = \{ i_{2k+1}, \dots, i_1 \}$ be the set of 
the rest of the points on the cycle as shown. 
To do this, we need to pick a 
permutation $\sigma = i_{2k+1}\dots i_1 \in Sym(R)$,
where $R=\{ i_{2k+1}, \dots, i_1 \}$ is a set of distinct integers in $[1,n]$,
such that the contribution $w_C$ of this cycle $C$ to the
weight of $G$ is exactly equal to 
the contribution $w_E$ of $e_1, \dots, e_{k+1}$ to the weight of $\alpha$ plus
the contribution $w'_E$ of  $e'_1, \dots, e'_{k+1}$ to the weight of $\alpha'$.
Notice that removing the edges $e_j$ and $e'_j$ does not have any
effect on the total weights of the rest of edges of $\alpha$ and $\alpha'$.
Let $U = [1,n] - R$,
and  $I(U,R)$ be the number of inversions 
created by pairs of numbers in $U \times R$, namely the number
of pairs $(u,r) \in U \times R$ such that $u > r$.

As each red edge on $C$ is weighted $q$ and each blue edge weighted $1$,
it is easy to see that
\begin{eqnarray}
w_C  &=& q^{I(U,R)+I(\sigma)+2k+1} \cdot q^{k+1} ,\\
w_E  &=& q^{k+1} \cdot q^{\sum_{j=1}^{k+1}s(e_j)} ,\\
w'_E  &=& q^{k+1} \cdot q^{\sum_{j=1}^{k+1}s(e'_j)}.
\end{eqnarray}
Hence, we need to pick $\sigma$ such that 
\begin{equation} 
I(U,R) + I(\sigma) = \sum_{j=1}^{k+1}s(e_j) + \sum_{j=1}^{k+1}s(e'_j) - k.
\label{eqn:topick-case1}
\end{equation}
Observe that
\begin{eqnarray}
s(e_{k+1}) & = & 0, \\
1 \leq s(e_j)  & \leq & n+1-2j, \ \ \ \forall j=1, \dots,k, \\
0 \leq s(e'_j) & \leq & n+1-2j, \ \ \ \forall j=1, \dots,k+1.
\end{eqnarray}
Now, define a function $f$ on $\{1, \dots, 2k+1\}$ by
\[
f(t) =
\begin{cases}
 n-t+2-s(e_j) & \text{ if } t = 2j, j=1,\dots,k ,\\
 n-t+1-s(e'_j) & \text{ if } t = 2j-1, j=1,\dots,k+1.
\end{cases}
\]
Then, recursively determine $i_1, \dots, i_{2k+1}$,
element by element starting from $i_1$, working toward $i_{2k+1}$ as follows:
\begin{equation}
i_t = \text{the $f(t)$th smallest number in} \ [1,n] - \{i_1,\dots,i_{t-1}\}.
\label{eqn:i_t}
\end{equation}
It is easy to check that $1 \leq f(t) \leq n-(t-1)$ for all $t=1,\dots,2k+1$
so that $i_t$ is well defined.
Moreover, 
\begin{eqnarray*}
I(U,R)+I(\sigma) 
  & = & \sum_{t=1}^{2k+1}
        |\{ j \suchthat \text{$j$ preceeds $i_t$, $j > i_t$, $j\neq n+1$} \}| \\
  & = & \sum_{t=1}^{2k+1} \bigl( n-(t-1)-f(t) \bigr) \\
  & = & \sum_{j=1}^k \bigl( n-(2j-1)-f(2j) \bigr) +
        \sum_{j=1}^{k+1} \bigl( n-(2j-2)-f(2j-1) \bigr) \\
  & = & \sum_{j=1}^{k+1}s(e_j) + \sum_{j=1}^{k+1}s(e'_j) - k,
\end{eqnarray*}
which is exactly \eqref{eqn:topick-case1}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Case 2
\item[Case 2.] There exists a $k$, $0 \leq k \leq \frac{n}{2}$, and
an $m$, $0 \leq m \leq k$ such that
\bi
\item[(i)] For all $j=1, \dots,m$, $p_j$ is the right end-point of $e_j$,
and $s(e_j) > 0$.
Moreover, $p_{m+1}$ is a fixed point, which is weighted by $x$. 
And, for all $j=m+2, \dots,k+1$, $p_j$ is the right end-point of $e_{j-1}$.
\item[(ii)] For all $j=1, \dots, k$, $p'_j$ is the right end-point of $e'_j$.
And, $p'_{k+1}$ is a fixed point weighted by $y$.
\ei
The situation is depicted in Figure \ref{fig:case2}. 
\begin{figure}[hbtp] 
\centerline{ 
\begin{picture}(0,0)%
\includegraphics{case2.pstex}%
\end{picture}%
\setlength{\unitlength}{1973sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(12588,2693)(204,-2019)
\put(12451,-586){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x$\special{ps: grestore}}}}
\put(12301,-1111){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_1$\special{ps: grestore}}}}
\put(11776,-1036){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_2$\special{ps: grestore}}}}
\put(10501,-1036){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_{2m}$\special{ps: grestore}}}}
\put(9751,-661){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$n+1$\special{ps: grestore}}}}
\put(9226,-1036){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_{2m+1}$\special{ps: grestore}}}}
\put(7276,-586){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y$\special{ps: grestore}}}}
\put(7426,-1111){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_{2k}$\special{ps: grestore}}}}
\put(4576,-1036){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_1$\special{ps: grestore}}}}
\put(4651,464){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_1$\special{ps: grestore}}}}
\put(3376,464){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_m$\special{ps: grestore}}}}
\put(2251,464){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_{m+1}$\special{ps: grestore}}}}
\put(976,464){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_k$\special{ps: grestore}}}}
\put(1576,-1036){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_k$\special{ps: grestore}}}}
\put(2701,-1036){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_{m+1}$\special{ps: grestore}}}}
\put(3376,-1036){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_m$\special{ps: grestore}}}}
\put(3151,-286){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x$\special{ps: grestore}}}}
\put(1351,-1786){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y$\special{ps: grestore}}}}
\put(6226,-1786){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$0 \leq k \leq \frac{n}{2}, \ \ \ 0 \leq m \leq k$\special{ps: grestore}}}}
\put(6226,-736){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\varphi$\special{ps: grestore}}}}
\end{picture}
}
\caption{Illustration of case 2.}
\label{fig:case2}
\end{figure}                
This time, the last component $C$ of $G$ starts with a red loop and ends
with a blue loop. 
The point $n+1$ is the $(2m+1)$st point from the right.
Let $\sigma$, $R$, $U$ be defined as in the previous case,
then the corresponding $w_C$, $w_E$ and $w'_E$ are as follows:
\begin{eqnarray}
w_C &=& q^{I(U,R) + I(\sigma) + 2m} \cdot q^{2k-m} \cdot xy ,\\
w_E  &=& q^k \cdot q^{\sum_{j=1}^ks(e_j)} \cdot x   ,\\
w'_E  &=& q^k \cdot q^{\sum_{j=1}^ks(e'_j)} \cdot y.
\end{eqnarray}
Hence, we need to pick $\sigma$ so that
\begin{equation} 
I(U,R) + I(\sigma) = \sum_{j=1}^ks(e_j) + \sum_{j=1}^ks(e'_j) - m.
\label{eqn:topick-case2}
\end{equation}
For $t = 1,\dots, 2k$, the corresponding $f(t)$ is:
\begin{equation}
f(t) = 
\begin{cases}
n-t+2-s(e_j) & \text{if $t=2j$, $j=1,\dots,m$}, \\
n-t+1-s(e_j) & \text{if $t=2j$, $j=m+1,\dots,k$}, \\
n-t+1-s(e'_j) & \text{if $t=2j-1$, $j=1,\dots,k$}.
\end{cases}
\end{equation}
As in the previous case, $i_t$ is defined by \eqref{eqn:i_t}.
To show that $i_t$ is well defined and that
they satisfy \eqref{eqn:topick-case2}, we only need to observe that
\begin{eqnarray}
1 \leq s(e_j)  & \leq & n+1-2j,     \ \ \ j=1,\dots,m ,\\
0 \leq s(e_j)  & \leq & n+1-(2j+1), \ \ \ j=m+1,\dots,k, \\
0 \leq s(e'_j) & \leq & n+1-2j,     \ \ \ j=1,\dots,k.
\end{eqnarray}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Case 3
\item[Case 3.] There exists a $k$, $1 \leq k \leq \frac{n}{2}$, and
an $m$, $0 \leq m \leq k-1$, such that 
\bi
\item[(i)] For all $j=1, \dots, k$, $p_j$ is the right end-point of 
$e_j$, and $p_{k+1}$ is a fixed point weighted $x$.
\item[(ii)] For all $j=1, \dots, m$, $s(e_j) > 0$.
\item[(iii)] For all $j=1, \dots, m$, $p_j$ is the right end-point of $e'_j$,
$p_{m+1}$ is a fixed point weighted $y$,
and for all $j=m+2, \dots, k+1$
$p_j$ is the right end-point of $e'_{j-1}$.
\ei
The situation is depicted in Figure \ref{fig:case3}. 
\begin{figure}[hbtp] 
\centerline{ 
\begin{picture}(0,0)%
\includegraphics{case3.pstex}%
\end{picture}%
\setlength{\unitlength}{1973sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(12498,2693)(204,-2019)
\put(4576,464){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_1$\special{ps: grestore}}}}
\put(1576,464){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_k$\special{ps: grestore}}}}
\put(2701,464){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_{m+1}$\special{ps: grestore}}}}
\put(3376,464){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_m$\special{ps: grestore}}}}
\put(1351,-286){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x$\special{ps: grestore}}}}
\put(4651,-1036){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_1$\special{ps: grestore}}}}
\put(3376,-1036){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_m$\special{ps: grestore}}}}
\put(2251,-1036){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_{m+1}$\special{ps: grestore}}}}
\put(976,-1036){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_k$\special{ps: grestore}}}}
\put(3151,-1786){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y$\special{ps: grestore}}}}
\put(6226,-1936){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$1 \leq k \leq \frac{n}{2}, \ \ \ 0 \leq m \leq k-1$\special{ps: grestore}}}}
\put(6076,-811){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\varphi$\special{ps: grestore}}}}
\put(12376,-661){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y$\special{ps: grestore}}}}
\put(12226,-1186){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_1$\special{ps: grestore}}}}
\put(11701,-1111){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_2$\special{ps: grestore}}}}
\put(9676,-736){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$n+1$\special{ps: grestore}}}}
\put(7201,-661){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x$\special{ps: grestore}}}}
\put(7351,-1186){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_{2k}$\special{ps: grestore}}}}
\put(10426,-1111){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_{2m+1}$\special{ps: grestore}}}}
\put(9151,-1111){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_{2m+2}$\special{ps: grestore}}}}
\end{picture}
}
\caption{Illustration of case 3.}
\label{fig:case3}
\end{figure}                
In this case, we have
\begin{eqnarray}
w_C  &=& q^{I(U,R) + I(\sigma) + 2m+1} \cdot q^{2k-(m+1)} \cdot xy ,\\
w_E  &=& q^k \cdot q^{\sum_{j=1}^ks(e_j)} \cdot x                  ,\\
w'_E &=& q^k \cdot q^{\sum_{j=1}^ks(e'_j)} \cdot y.
\end{eqnarray}
Hence, we need to pick $\sigma$ so that
\begin{equation}
I(U,R) + I(\sigma) = \sum_{j=1}^ks(e_j) + \sum_{j=1}^ks(e'_j) - m.
\label{eqn:topick-case3}
\end{equation}
For $t = 1, \dots, 2k$, the corresponding $f(t)$ is:
\begin{equation}
f(t) =
\begin{cases}
n-t+2-s(e_j)  & \text{if $t=2j$,   $j=1,\dots,m$}   ,\\
n-t+1-s(e'_j) & \text{if $t=2j$,   $j=m+1,\dots,k$} ,\\
n-t+1-s(e'_j) & \text{if $t=2j-1$, $j=1,\dots,m$}   ,\\
n-t+1-s(e_j)  & \text{if $t=2j-1$, $j=m+1,\dots,k$.}
\end{cases}
\end{equation}
As in the previous case, $i_t$ is defined by \eqref{eqn:i_t}.
To show that $i_t$ is well defined and that
they satisfy \eqref{eqn:topick-case3}, we only need to observe that
\begin{eqnarray}
1 \leq s(e_j)  & \leq & n+1-2j,     \ \ \ j=1,\dots,m  , \\
0 \leq s(e_j)  & \leq & n+1-2j,     \ \ \ j=m+1,\dots,k ,\\
0 \leq s(e'_j) & \leq & n+1-2j,     \ \ \ j=1,\dots,m  , \\
0 \leq s(e'_j) & \leq & n+1-(2j+1), \ \ \ j=m+1,\dots,k.
\end{eqnarray}                                                  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Case 4
\item[Case 4.] There exists a $k$, $0 \leq k \leq \frac{(n-1)}{2}$, and
an $m$, $0 \leq m \leq k$, such that 
\bi
\item[(i)] For all $j=1, \dots, m$, $p_j$ is the right end-point
of $e_j$, and $s(e_j) > 0$.
Moreover, $p_{m+1}$ and $p_{k+2}$ are fixed points weighted $x$.
For all $j=m+2, \dots, k+1$, $p_j$ is the right end-point
of $e_{j-1}$.
\item[(ii)]  For all $j=1, \dots, k+1$, $p'_j$ is the right end-point
of $e'_j$.
\ei
The situation is depicted in Figure \ref{fig:case4}. 
\begin{figure}[hbtp] 
\centerline{ 
\begin{picture}(0,0)%
\includegraphics{case4.pstex}%
\end{picture}%
\setlength{\unitlength}{1973sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(12438,2693)(204,-2019)
\put(4576,464){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_1$\special{ps: grestore}}}}
\put(3376,464){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_m$\special{ps: grestore}}}}
\put(2176,464){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_{m+1}$\special{ps: grestore}}}}
\put(976,464){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_k$\special{ps: grestore}}}}
\put(4576,-1036){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_1$\special{ps: grestore}}}}
\put(976,-1036){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_{k+1}$\special{ps: grestore}}}}
\put(3151,-286){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x$\special{ps: grestore}}}}
\put(751,-286){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x$\special{ps: grestore}}}}
\put(7201,-811){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x$\special{ps: grestore}}}}
\put(12301,-811){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$x$\special{ps: grestore}}}}
\put(12151,-1336){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_1$\special{ps: grestore}}}}
\put(8026,-1261){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_{2k}$\special{ps: grestore}}}}
\put(7426,-1336){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_{2k+1}$\special{ps: grestore}}}}
\put(10276,-886){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$n+1$\special{ps: grestore}}}}
\put(11551,-1261){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_2$\special{ps: grestore}}}}
\put(10951,-1261){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_{2m}$\special{ps: grestore}}}}
\put(6001,-1861){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$0 \leq k \leq \frac{n-1}{2}, \ \ \ 0 \leq m \leq k$\special{ps: grestore}}}}
\put(6151,-961){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\varphi$\special{ps: grestore}}}}
\end{picture}
}
\caption{Illustration of case 4.}
\label{fig:case4}
\end{figure}
In this case, we have
\begin{eqnarray}
w_C  &=& q^{I(U,R) + I(\sigma) + 2m} \cdot q^{2k+1-m} \cdot x^2 ,\\
w_E  &=& q^k \cdot q^{\sum_{j=1}^ks(e_j)} \cdot x^2           , \\
w'_E &=& q^{k+1} \cdot q^{\sum_{j=1}^{k+1}s(e'_j)}.
\end{eqnarray}
Hence, we need to pick $\sigma$ so that
\begin{equation}
I(U,R) + I(\sigma) = \sum_{j=1}^ks(e_j) + \sum_{j=1}^{k+1}s(e'_j) - m.
\label{eqn:topick-case4}
\end{equation}
For $t = 1, \dots, 2k+1$, the corresponding $f(t)$ is:
\begin{equation}
f(t) =
\begin{cases}
n-t+2-s(e_j)  & \text{if $t=2j$,   $j=1,\dots,m$}, \\
n-t+1-s(e_j)  & \text{if $t=2j$,   $j=m+1,\dots,k$},    \\
n-t+1-s(e'_j) & \text{if $t=2j-1$, $j=1,\dots,k+1$}.
\end{cases}
\end{equation}
As in the previous case, $i_t$ is defined by \eqref{eqn:i_t}.
To show that $i_t$ is well defined and that
they satisfy \eqref{eqn:topick-case4}, we only need to observe that
\begin{eqnarray}
1 \leq s(e_j)  & \leq & n+1-2j,     \ \ \ j=1,\dots,m ,\\
0 \leq s(e_j)  & \leq & n+1-(2j+1), \ \ \ j=m+1,\dots,k, \\
0 \leq s(e'_j) & \leq & n+1-2j,     \ \ \ j=1,\dots,k+1.
\end{eqnarray}                                              

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Case 5
\item[Case 5.] There exists a $k$, $0 \leq k \leq \frac{(n-1)}{2}$, and
an $m$, $0 \leq m \leq k$, such that 
\bi
\item[(i)] For all $j=1, \dots, m$, $p'_j$ is the right end-point
of $e'_j$.
Moreover, $p'_{m+1}$ and $p'_{k+2}$ are fixed points weighted $y$.
For all $j=m+2, \dots, k+1$, $p'_j$ is the right end-point
of $e'_{j-1}$.
\item[(ii)]  For all $j=1, \dots, k+1$, $p_j$ is the right end-point
of $e_j$.
\item[(iii)] For all $j=1, \dots, m$, $s(e_j) > 0$.
\ei
The situation is depicted in Figure \ref{fig:case5}. 
\begin{figure}[hbtp] 
\centerline{ 
\begin{picture}(0,0)%
\includegraphics{case5.pstex}%
\end{picture}%
\setlength{\unitlength}{1973sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(12423,2693)(354,-2169)
\put(3301,-1936){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y$\special{ps: grestore}}}}
\put(901,-1936){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y$\special{ps: grestore}}}}
\put(4726,314){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_1$\special{ps: grestore}}}}
\put(1126,314){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e_{k+1}$\special{ps: grestore}}}}
\put(4726,-1186){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_1$\special{ps: grestore}}}}
\put(3526,-1186){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_m$\special{ps: grestore}}}}
\put(2326,-1186){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_{m+1}$\special{ps: grestore}}}}
\put(1126,-1186){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$e'_k$\special{ps: grestore}}}}
\put(7351,-961){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y$\special{ps: grestore}}}}
\put(12451,-961){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$y$\special{ps: grestore}}}}
\put(12301,-1486){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_1$\special{ps: grestore}}}}
\put(8176,-1411){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_{2k}$\special{ps: grestore}}}}
\put(7576,-1486){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_{2k+1}$\special{ps: grestore}}}}
\put(10426,-1036){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$n+1$\special{ps: grestore}}}}
\put(6526,-2086){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$0 \leq k \leq \frac{n-1}{2}, \ \ \ 0 \leq m \leq k$\special{ps: grestore}}}}
\put(6376,-1111){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$\varphi$\special{ps: grestore}}}}
\put(11101,-1411){\makebox(0,0)[lb]{\smash{\SetFigFont{7}{8.4}{\rmdefault}{\mddefault}{\updefault}\special{ps: gsave 0 0 0 setrgbcolor}$i_{2m+1}$\special{ps: grestore}}}}
\end{picture}
}
\caption{Illustration of case 5.}
\label{fig:case5}
\end{figure}                
In this case, we have
\begin{eqnarray}
w_C  &=& q^{I(U,R) + I(\sigma) + 2m+1} \cdot q^{2k+1-(m+1)} \cdot y^2 ,\\
w_E  &=& q^{k+1} \cdot q^{\sum_{j=1}^{k+1}s(e_j)}, \\
w'_E &=& q^k \cdot q^{\sum_{j=1}^ks(e'_j)} \cdot y^2.
\end{eqnarray}
Hence, we need to pick $\sigma$ so that
\begin{equation}
I(U,R) + I(\sigma) = \sum_{j=1}^{k+1}s(e_j) + \sum_{j=1}^ks(e'_j) - m.
\label{eqn:topick-case5}
\end{equation}
For $t = 1, \dots, 2k+1$, the corresponding $f(t)$ is:
\begin{equation}
f(t) =
\begin{cases}
n-t+2-s(e_j)  & \text{if $t=2j$,   $j=1,\dots,m$} ,\\
n-t+1-s(e'_j) & \text{if $t=2j$,   $j=m+1,\dots,k$}, \\
n-t+1-s(e'_j) & \text{if $t=2j-1$, $j=1,\dots,m$} ,\\
n-t+1-s(e_j)  & \text{if $t=2j-1$, $j=m+1,\dots,k+1$}.
\end{cases}
\end{equation}
As in the previous case, $i_t$ is defined by \eqref{eqn:i_t}.
To show that $i_t$ is well defined and that
they satisfy \eqref{eqn:topick-case5}, we only need to observe that
\begin{eqnarray}
1 \leq s(e_j)  & \leq & n+1-2j,     \ \ \ j=1,\dots,m, \\
0 \leq s(e_j)  & \leq & n+1-2j,     \ \ \ j=m+1,\dots,k+1, \\
0 \leq s(e'_j) & \leq & n+1-2j,     \ \ \ j=1,\dots,m ,\\
0 \leq s(e'_j) & \leq & n+1-(2j+1), \ \ \ j=m+1,\dots,k.
\end{eqnarray}                                         
\ei

\ep


\section*{Acknowledgements}

I would like to thank Prof. Dennis Stanton at the School of Mathematics,
University of Minnesota, U.S.A., for many helpful discussions and insightful
suggestions, which made this work possible. This problem was suggested by
him as part of my mathematics Masters thesis at the University of Minnesota.
I would also like to thank Prof. Dominique Foata 
at
the D\'epartement de math\'ematique,
Universit\'e Louis Pasteur, France,
for various detailed comments
which have greatly improved the presentation of this paper.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% APPENDICES & BIBLIOGRAPHY & INDICES
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Options could be :
%%  abbrv, alpha, ieeetr, siam, acm, apalike, plain, unsrt
%%
{

\begin{thebibliography}{10}

\bibitem{MR33:5967}
{\sc W.~A. Al-Salam and L.~Carlitz}, {\em Some orthogonal $q$-polynomials},
  Math. Nachr., 30 (1965), pp.~47--61.

\bibitem{MR2000g:33001}
{\sc G.~E. Andrews, R.~Askey, and R.~Roy}, {\em Special functions}, Cambridge
  University Press, Cambridge, 1999.

\bibitem{MR2000a:05008}
{\sc F.~Bergeron, G.~Labelle, and P.~Leroux}, {\em Combinatorial species and
  tree-like structures}, Cambridge University Press, Cambridge, 1998.
\newblock Translated from the 1994 French original by Margaret Readdy, with a
  foreword by Gian-Carlo Rota.

\bibitem{MR81f:33009}
{\sc D.~M. Bressoud}, {\em A simple proof of {M}ehler's formula for
  $q$-{H}ermite polynomials}, Indiana Univ. Math. J., 29 (1980), pp.~577--580.

\bibitem{MR41:3846}
{\sc L.~Carlitz}, {\em An extension of {M}ehler's formula}, Boll. Un. Mat.
  Ital. (4), 3 (1970), pp.~43--46.

\bibitem{MR43:5076}
{\sc L.~Carlitz}, {\em Some extensions of the {M}ehler formula}, Collect.
  Math., 21 (1970), pp.~117--130.

\bibitem{MR58:1979}
{\sc T.~S. Chihara}, {\em An introduction to orthogonal polynomials}, Gordon
  and Breach Science Publishers, New York, 1978.
\newblock Mathematics and its Applications, Vol. 13.

\bibitem{cigler-1982}
{\sc J.~Cigler}, {\em Elementare q-Identit\"aten}, S\'em. Lothar. Combin., 5
  (1981), Art.\ B05a, 29~pp.\ (electronic).

\bibitem{desarmenien-1982}
{\sc J.~D{\'e}sarm{\'e}nien}, {\em Les $q$-analogues des polyn\^omes
  d'Hermite}, S\'em. Lothar. Combin., 6 (1982), Art.\ B06b, 
12~pp.\ (electronic).

\bibitem{MR58:16322}
{\sc D.~Foata}, {\em A combinatorial proof of the {M}ehler formula}, J.
  Combinatorial Theory Ser. A, 24 (1978), pp.~367--376.

\bibitem{MR84a:33021}
\leavevmode\vrule height 2pt depth -1.6pt width 23pt, {\em Some {H}ermite
  polynomial identities and their combinatorics}, Adv. in Appl. Math., 2
  (1981), pp.~250--259.

\bibitem{MR81a:05007}
{\sc D.~Foata and A.~M. Garsia}, {\em A combinatorial approach to the {M}ehler
  formulas for {H}ermite polynomials}, in Relations between combinatorics and
  other parts of mathematics (Proc. Sympos. Pure Math., Ohio State Univ.,
  Columbus, Ohio, 1978), Amer. Math. Soc., Providence, R.I., 1979,
  pp.~163--179.

\bibitem{MR84d:05013}
{\sc I.~M. Gessel}, {\em A $q$-analog of the exponential formula}, Discrete
  Math., 40 (1982), pp.~69--80.

\bibitem{MR89m:33003}
{\sc M.~E.~H. Ismail and D.~Stanton}, {\em On the {A}skey-{W}ilson and {R}ogers
  polynomials}, Canad. J. Math., 40 (1988), pp.~1025--1045.

\bibitem{MR89h:33015}
{\sc M.~E.~H. Ismail, D.~Stanton, and G.~Viennot}, {\em The combinatorics of
  $q$-{H}ermite polynomials and the {A}skey-{W}ilson integral}, European J.
  Combin., 8 (1987), pp.~379--392.

\bibitem{MR58:22706}
{\sc B.~K. Karande and N.~K. Thakare}, {\em On certain $q$-orthogonal
  polynomials}, Indian J. Pure Appl. Math., 7 (1976), pp.~728--736.

\bibitem{MR7:65f}
{\sc W.~F. Kibble}, {\em An extension of a theorem of {M}ehler's on {H}ermite
  polynomials}, Proc. Cambridge Philos. Soc., 41 (1945), pp.~12--15.

\bibitem{MR83a:81036}
{\sc J.~D. Louck}, {\em Extension of the {K}ibble-{S}lepian formula for
  {H}ermite polynomials using boson operator methods}, Adv. in Appl. Math., 2
  (1981), pp.~239--249.

\bibitem{Rogers-1893}
{\sc L.~J. Rogers}, {\em On a three-fold symmetry in the elements of Heine's
  series}, Proc. London Math. Soc., 24 (1893), pp.~337--352.

\bibitem{MR47:3722}
{\sc D.~Slepian}, {\em On the symmetrized {K}ronecker power of a matrix and
  extensions of {M}ehler's formula for {H}ermite polynomials}, SIAM J. Math.
  Anal., 3 (1972), pp.~606--616.

\bibitem{Stanton2000}
{\sc D.~Stanton}, {\em Orthogonal polynomials and combinatorics}, in Special
  Functions 2000: Current Perspective and future directions, Kluwer, 2000,
  pp.~389--410.

\end{thebibliography}

}

\end{document}
