\documentclass[12pt,reqno]{amsart}
\usepackage{amsmath,epsfig,amssymb,amsfonts,latexsym}
\usepackage[all]{xy}

\setlength{\textwidth}{6.3in} \setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}

\newtheorem{thm}{Theorem}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{property}[thm]{Property}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{defn}[thm]{Definition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{problem}[thm]{Problem}
\newtheorem{exam}{Example}
\def\qbinom#1#2{\begin{bmatrix}#1\\#2 \end{bmatrix}}
\def\inv{{\rm inv}}
\def\Cinv{{\rm Cinv}}
\def\rn{{\rm rn}}%restricted nesting
\def\rc{\mathrm{rc}}%restricted crossing
\def\bloc{\mathrm{block}}
\def\nes{\mathrm{nes}}
\def\sg{\mathrm{sg}}
\def\d{{\rm d}}
\def\fix{{\rm fix}}
\def\cyc{{\rm cyc}}
\def\id{{\rm id}}
\def\la{\lambda}
\def\L{\mathcal L}
\def\Z{\mathbb{Z}}
\def\pf{\noindent {\it Proof.} }
\numberwithin{equation}{section}

\begin{document}
\title{The Combinatorics of the Al-Salam-Chihara $q$-Charlier Polynomials}
\author{Dongsu Kim}~\thanks{The first author was partially
supported by KRF grant R05-2004-000-11511-0.}
\address{Department of Mathematics,
         KAIST, Daejeon 305-701, Korea}
\email{dskim@math.kaist.ac.kr}

\author{Dennis Stanton}~\thanks{The second author was partially
supported by NSF grant DMS-0503660.}
\address{School of Mathematics\\
         University of Minnesota\\
         Minneapolis, MN 55455}
\email{stanton@math.umn.edu}

\author{Jiang Zeng}
\address{Institut Camille Jordan,
        Universit\'e Claude Bernard (Lyon I)\\
        F-69622, Villeurbanne}
\email{zeng@math.univ-lyon1.fr}

\dedicatory{Dedicated to Xavier
Viennot on the occasion of his sixtieth birthday}

\begin{abstract}
We describe various aspects of the Al-Salam-Chihara $q$-Charlier
polynomials. These include combinatorial descriptions of the
polynomials, the moments, the orthogonality relation and a
combinatorial proof of Anshelevich's recent result on the
linearization coefficients.
\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 54 \rms (2006), Article~B54i\hfill}
\def\thepage{}
%
%

\section{Introduction}
The classical Charlier polynomials $C_n^a(x)$ have been studied
combinatorially by several authors~\cite{De, Ge, Ze}.
Recall~\cite{Chi} that these polynomials are defined by
\begin{equation}
\label{charrr}
C_n^a(x)=\sum_{k=0}^n{\binom n
k}(-a)^{n-k}x(x-1)\cdots (x-(k-1))
\end{equation}
and satisfy the three term-recurrence relation
\begin{equation}\label{eq:recur}
C_{n+1}^a(x)=(x-a-n)\,C_n^a(x)-an\,C_{n-1}^a(x),\quad n\geq 0,
\end{equation}
where $C_0^a(x)=1$, $C_{-1}^a(x)=0$.


A $q$-version $C_n^a(x;q)$ of these polynomials was studied in \cite{MSW}.
The three-term recurrence relation was
$$
C_{n+1}^a(x;q)=(x-aq^n-[n]_q)\,C_n^a(x;q)-aq^{n-1}[n]_q\,
C_{n-1}^a(x;q),
$$
where $[n]_q=1+q+\cdots+q^{n-1}$, $C_0^a(x;q)=1$, $C_{-1}^a(x;q)=0$.
The explicit formula analogous to \eqref{charrr} is given by
$$
C_n^a(x;q)=\sum_{k=0}^n {\qbinom n k}_q(-a)^{n-k} q^{\binom {n-k} 2} \prod_{i=0}^{k-1} (x-[i]_q).
$$

The linearization coefficients for the Charlier polynomials are
given by quotients of factorials (see \eqref{eq:lincoef}). The
combinatorial study of the $q$-analogues $C_n^a(x;q)$ in \cite{MSW}
included finding their linearization coefficients, which were given
by a double sum, not quotients of factorials, and as a polynomial in
$q$ and $a$ did not have positive coefficients (see \cite[Theorem
3]{MSW}).


Anshelevich~\cite{Ans} has  recently considered a $q$-analogue of
the three-term recurrence \eqref{eq:recur} for $C_n^a(x+a,a)$ and
proved that the linearization coefficients of the corresponding
polynomials are polynomials of $a$ and $q$ with positive integer
coefficients (see Theorem~6).

The aim of this paper is to study the combinatorial aspects of a
new $q$-analogue of Charlier polynomials, which is a re-scaled
version of Anshelevich's $q$-polynomials and turns out to be a
special re-scaled version of the Al-Salam-Chihara polynomials.
 We shall give a combinatorial
proof of Anshelevich's result by using the combinatorial
interpretations of the polynomials and their moments. It is inspired
by the beautiful proofs for other classical orthogonal polynomials
in \cite{CV,ISV}.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL DONGSU KIM, DENNIS STANTON, AND JIANG ZENG}{\SMALL THE COMBINATORICS OF THE AL-SALAM-CHIHARA $q$-CHARLIER POLYNOMIALS}
%
%

This paper is organized as follows: in the next two sections we give
the definitions and combinatorial interpretations of the new
$q$-Charlier polynomials and their moments,
Corollary~\ref{mainpolycomb} and Theorem~\ref{mainmomcomb}. The
explicit linearization coefficients are given in \S4 in
Corollary~\ref{maincor}. We then give the killing involution in \S5.
We present a variation $\hat C_n(x|q)$
of the polynomials
$C_n(x,a;q)$ in \S6, which has the advantage to include the
$q$-Hermite polynomials in \cite{ISV}
as a special case.

We collect here some well-known facts about Charlier polynomials.

The generating function is
\begin{equation}\label{eq:gen}
\sum_{n=0}^\infty C_n^a(x)\frac{t^n}{n!}=e^{-at}(1+at)^x.
\end{equation}
The moment sequence $\mu_n$ is given by the following formula:
\begin{equation}\label{eq:moment}
\mu_n=\L(x^n)=\sum_{x=0}^\infty x^n e^{-a}\frac{a^x}{x!}
=\sum_{k=1}^nS(n,k)a^k,
\end{equation}
where $S(n,k)$ denotes the Stirling number of the second kind. The
orthogonality reads:
\[
\L(C_m^a(x)C_n^a(x))=\sum_{k=0}^\infty C_m^a(k)C_n^a(k)\frac{e^{-a}a^k}{k!}= n!a^n\delta_{mn}.
\]
The linearization coefficient $c_{n_1n_2}^{n_3}$ is defined by:
$$
C_{n_1}^a(x)C_{n_2}^a(x)=\sum_{n_3}c_{n_1n_2}^{n_3}C_{n_3}^a(x).
$$
By  orthogonality we have $c_{n_1n_2}^{n_3}=\L(C_{n_1}^a(x)C_{n_2}^a(x)C_{n_3}^a(x))
/\L(C_{n_3}^a(x)C_{n_3}^a(x))$.

For Charlier polynomials it is easy to derive from \eqref{eq:gen} and \eqref{eq:moment} that
$$
\sum_{n_1,\ldots,n_k=0}^{\infty}\L(C_{n_1}^a(x)\ldots C_{n_k}^a(x))\frac{t_1^{n_1}}{n_1!}
\ldots\frac{t_k^{n_k}}{n_k!}=
e^{a(e_2(t_1,\ldots,t_k)+\ldots +e_k(t_1,\ldots,t_k))},
$$
where $e_i$ is the elementary symmetric function of degree $i$.
It follows that
\begin{equation}\label{eq:lincoef}
\L(C_{n_1}^a(x)C_{n_2}^a(x)C_{n_3}^a(x))=
\sum_{l}\frac{n_1!n_2!n_3!a^{l+n_3}}{l!(n_3-n_1+l)!(n_3-n_2+l)!(n_1+n_2-n_3-2l)!}.
\end{equation}
In the general case the above generating function implies that
$\L(C_{n_1}^a(x)\ldots C_{n_k}^a(x))$ ($k\geq 1$) is
a polynomial in $a$ with positive integer coefficients; a combinatorial
interpretation of this coefficient has been
given~\cite{Ge,Ze}.


\section{The new $q$-Charlier polynomials}
We define the new $q$-Charlier polynomials $C_n(x,a;q)$ by
\begin{equation}\label{eq:three-term}
C_{n+1}(x,a;q)=(x-a-[n]_q)\,C_n(x,a;q)-a[n]_q\,C_{n-1}(x,a;q).
\end{equation}
The first values of these polynomials are
\begin{align*}
C_1(x,a;q)&=x-a,\\
C_2(x,a;q)&= {x}^{2}-(2\,a+1)x+{a}^{2},\\
C_3(x,a;q)&={x}^{3}-(q+3\,a+2){x}^{2}+(aq+3\,{a}^{2}+2\,a+q+1)x-{a}^{3}.
\end{align*}
The explicit formula which is analogous to \eqref{charrr} is
\begin{equation}\label{eq:explicit}
C_n(x,a;q)=\sum_{k=0}^n{\qbinom n
k}_qq^{k(k-n)}(-a)^{n-k}\prod_{i=0}^{k-1}\left(x-[i]_q+a(q^{-i}-1)\right).
\end{equation}

This is a re-scaled version of the Al-Salam-Chihara polynomials
$Q_n(x,\alpha,\beta;q)$~\cite[p. 80--81]{KS}:
$$
C_n(x,a;q)=\left(\frac{a}{1-q}\right)^{n/2}Q_n
\left(\frac{1}{2}\sqrt{\frac{1-q}{a}}\left(x-
a-\frac{1}{1-q}\right),\frac{-1}{\sqrt{a(1-q)}}, 0;q\right).
$$
Since the generating function of the Al-Salam-Chihara polynomials is known, we derive that
$$
\sum_{n=0}^\infty C_n(x,a;q)\frac{t^n}{n!_q}=\frac{(-t;q)_\infty}{(\sqrt{a(1-q)}te^{i\theta},
\sqrt{a(1-q)}te^{-i\theta};q)_\infty},
$$
where $n!_q=[n]_q[n-1]_q\ldots [2]_q[1]_q$ and
$$
\cos\theta=\frac{1}{2}\sqrt{\frac{1-q}{a}}\left(x-a-\frac{1}{1-q}\right).
$$
We can give a combinatorial interpretation for the $q$-Charlier
polynomials from a result due to Simion and Stanton~\cite{SS}.

Consider a  subset $B$ of $[n]$ and  a permutation $\sigma$ on
$[n]\setminus B$. Then $\sigma$ consists of fixed points and
cycles of length $>1$:
$$
C=(k_0, k_1, k_2, \ldots, k_s), \quad {\text{where }}
k_s>max\{k_0,k_1,\cdots k_{s-1}\}.
$$
For any $k\in [n]\setminus B$, let  $w(k)=0$ if $k$ is
the maximum of its cycle, otherwise $k=k_j$ is on a cycle $C$ as above, then
\begin{equation*}
w(k)=k-1-|\{i: j<i<s, k_i<k_j\}|-\sum_{\textrm{cycles}\; Q,\,
\max(Q)>k_s}(\# {\text{ of points on Q less than k}}).
\end{equation*}
Let $w(B,\sigma)=\sum_{k \in [n]\setminus B} w(k)$ and let
$\cyc(\sigma)$ be the number of
cycles of $\sigma$.

\begin{exam}
Let $n=9$, $B=\{2,9\}$ and $\sigma=(6)(4\,7)(3\,5\,1\,8)$
(in cycle notation with maximum at last).
Then we have $\cyc(\sigma)=3$ and
$$
w(B,\sigma)=(3-1-1)+(5-1-1)+(1-1)+(4-1-2)=5.
$$
\end{exam}
\begin{thm}\label{thm:C_n}
We have
$$
C_n(x,a;q)=\sum_{(B, \sigma)}(-1)^{n-\cyc
(\sigma)}a^{|B|}x^{\cyc(\sigma)}q^{w(B,\sigma)}.
$$
where $B\subset [n]$ and $\sigma$ is a permutation on
$[n]\setminus B$.
\end{thm}
\begin{proof}
This is the $r=1$, $s=0$, $t=q$, $u=1$ special case of the
quadrabasic Laguerre polynomials \cite[p.313]{SS}.
\end{proof}


We now assume that each permutation $\pi$ of $[n]$ is represented as a product of disjoint
cycles, $\pi=\sigma_1\sigma_2\cdots\sigma_k$, where the cycles are written in the descending
order of their maxima and each $\sigma_i$ has its maximum at the first position.
A pair $(i,j)$, $i>j$, is called a {\em Charlier-inversion} in $\pi=\sigma_1\sigma_2\cdots\sigma_k$
if $i$ is not a maxima of any cycles of $\pi$ and $i$ appears to the left of $j$
in $\pi$. For instance, $(6,2)$, $(6,4)$, $(6,5)$, $(6,1)$, $(6,3)$,
$(2,1)$, $(4,1)$ and $(4,3)$
are all Charlier-inversions in $\pi=(8\,6\,2)(7\,4)(5\,1\,3)$. Let $\Cinv(\pi)$ denote the
number of Charlier-inversions in $\pi$.

\begin{defn}(Charlier-labeling of permutations)
A Charlier-labeling of a permutation
$\pi=\sigma_1\sigma_2\cdots\sigma_k$ is a labeling of integers and
cycles in $\pi$ satisfying the following rules:
\begin{itemize}
\item Each integer in $\pi$ is labeled $-1$.
\item Each cycle of length $1$ is labeled either $-x$ or $a$.
\item Each cycle of length $>1$ is labeled $-x$.
\end{itemize}
A permutation with a Charlier-labeling is called a
{\em Charlier-permutation.}
\end{defn}

Let $\tau$ denote a Charlier-permutation with underlying
permutation $\pi$. Identify $\Cinv(\tau)$ with $\Cinv(\pi)$.
Define the weight of $\tau$, $w(\tau)$, to be the product of
$q^{\Cinv(\tau)}$ and all the labels of integers and of cycles in
$\tau$. Since only $1$-cycles are allowed two different choices
for a label, if $\pi$ has $f$ fixed points, there are $2^f$
distinct Charlier-permutations with $\pi$ as an underlying
permutation. We represent each cycle in a permutation as a
sequence starting with the maximum, enclosed with a pair
of parentheses. The cycles in a Charlier-permutation are
represented in the same way except that 1-cycles with label $a$
are enclosed with a pair of brackets.

For each pair $(B,\sigma)$ in Theorem~1, where $B\subset [n]$ and
$\sigma$ a permutation of $[n]\setminus B$, one can associate a
Charlier-permutation $\tau$ of $[n]$ as follows: each element of $B$
gives rise a 1-cycle with brackets, each cycle $(a_1a_2\ldots a_l)$
of $\sigma$ gives rise a cycle $(a_la_{l-1}\ldots a_1)$ of $\tau$
with reverse order and the maximal element at the first position. It
is not hard to see that $w(B,\sigma)=\Cinv(\tau)$. For instance, the
Charlier-permutation corresponding to the pair $(B,\sigma)$ in the
above example is $\tau=[9](8\,1\,5\,3)(7\,4)(6)[2]$ with weight
$$
(-1)^9(-x)^3a^2q^{0+3+1+1}=a^2q^5x^3,
$$
because there are nine integers of label $-1$, three cycles of
label $-x$, two cycles of label $a$, five Charlier-inversions,
i.e. $(5,3),(5,4),(5,2),(3,2),(4,2)$.

One can restate Theorem~\ref{thm:C_n} as follows.
\begin{cor}\label{mainpolycomb}
The $q$-Charlier polynomial $C_n(x,a;q)$ is the generating function
of Charlier-permutations of $[n]$:
$$
C_n(x,a;q)=\sum_{\tau}w(\tau),
$$
where $\tau$ runs through all permutations
 of $[n]$.
\end{cor}

\section{The moments}
For the Charlier polynomials $C_n^a(x)$, the $n^{th}$ moment
$\mu_n$ is the generating function for set partitions of $\{1,2,\cdots, n\}$
according to the number of blocks (see \eqref{eq:moment}).
There is a natural $q$-analogue for the polynomials $C_n^a(x;q)$
\cite[Eq. (3.1)]{MSW}, whose $n^{th}$ moment is
$$
\mu_n=\sum_{k=1}^n S_q(n,k) a^k.
$$
Note that $S_q(n,k)$ is the most natural $q$-analogue of the Stirling numbers
of the second kind, and may also be interpreted as a generating
function for set partitions with $k$ blocks according to a
$q$-statistic. It has a remarkably simple expression as a single sum
\cite[Eq. (3.3)]{MSW}. In this section we identify an appropriate
$q$-statistic on set partitions which yields the $n^{th}$ moment
$\mu_n$ for $C_n(x,a;q)$, and give an explicit formula for it.


Recall that if $\pi$ is a partition of $M=\{1,\ldots, m\}$, then a
\emph{crossing} of $\pi$ is a quadruple $(a,b,c,d)$ of elements of
$M$ such that $a<b<c<d$, the elements $a,c$ are in some block of the
partition and $b,d$ are in another block. For two elements $e$ and
$f$ of $M$, with $e<f$, we say that $f$ \emph{follows} $e$ in $\pi$ if $e$
and $f$ belong to the same block of $\pi$, and there is no element
$g$ of this block with $e<g<f$. We define a \emph{restricted
crossing} to be a crossing $(a,b,c,d)$ such that $c$ follows $a$ and
$d$ follows $b$. Similarly a \emph{nesting} is a quadruple
$(a,b,c,d)$ of elements of $M$ such that $a<b<c<d$, the elements
$a$, $d$ are in some block of the partition and $b$, $c$ are in
another block. We define a \emph{restricted nesting} to be a nesting
$(a,b,c,d)$ such that $d$ follows $a$ and $c$ follows $b$. The
restricted crossings and nestings have a natural interpretation in
the graphic line representation of partitions. This representation
consists in drawing the $m$ points on the $x$-axis in the plane and,
if $f$ follows $e$, joining the point $e$ and $f$ by an arc above
the $x$-axis.

For instance, the graph of
$\pi=\{1,6,10\}-\{2,3,9\}-\{4,7\}-\{5,8\}$ is the following:
\begin{figure}[ht]
\begin{center}
{\setlength{\unitlength}{1mm}
\begin{picture}(50,8)(0,0)
\put(0,0){\circle*{1,3}}\put(1,-1){\makebox(-2,-4)[c]{\small 1}}
\put(5,0){\circle*{1,3}}\put(6,-1){\makebox(-2,-4)[c]{\small 2}}
\put(10,0){\circle*{1,3}}\put(11,-1){\makebox(-2,-4)[c]{\small 3}}
\put(15,0){\circle*{1,3}}\put(16,-1){\makebox(-2,-4)[c]{\small 4}}
\put(20,0){\circle*{1,3}}\put(21,-1){\makebox(-2,-4)[c]{\small 5}}
\put(25,0){\circle*{1,3}}\put(26,-1){\makebox(-2,-4)[c]{\small 6}}
\put(30,0){\circle*{1,3}}\put(31,-1){\makebox(-2,-4)[c]{\small 7}}
\put(35,0){\circle*{1,3}}\put(36,-1){\makebox(-2,-4)[c]{\small 8}}
\put(40,0){\circle*{1,3}}\put(41,-1){\makebox(-2,-4)[c]{\small 9}}
\put(45,0){\circle*{1,3}}\put(46,-1){\makebox(-2,-4)[c]{\small 10}}
\qbezier(0,0)(12.5,15)(25,0)\qbezier(25,0)(35,15)(45,0)
\qbezier(5,0)(7.5,5)(10,0)\qbezier(20,0)(27.5,10)(35,0)
\qbezier(15,0)(22.5,10)(30,0)\qbezier(10,0)(25,15)(40,0)
\end{picture}
}
\end{center}
\end{figure}


Let $\rc(\pi)$ (resp. $\rn(\pi)$) be the number of restricted
crossings (resp. restricted nestings) of a partition $\pi$.
The number of blocks of $\pi$ is denoted by $\bloc(\pi)$.
For
the above $\pi$ we have $\bloc(\pi)=4$, $\rc(\pi)=7$ and  there are $\rn(\pi)=3$ restricted nestings,
namely $(1,2,3,6)$, $(3,4,7,9)$, $(3,5,8,9)$.

We can derive the combinatorial interpretation of the moments from
the continued fraction expansion of the ordinary generating
functions of partitions with respect to the corresponding
statistics (see \cite{Bi,KZ}) and the three-term recurrence
relation \eqref{eq:three-term}.
\begin{thm} \label{mainmomcomb}
The $n^{th}$-moment of the $q$-Charlier polynomials
$C_n(x,a;q)$ is
$$
\mu_n(a):=\L_q(x^n)=\sum_{\pi\in \Pi_n}a^{\bloc (\pi)}q^{\rc
(\pi)}=\sum_{\pi\in \Pi_n}a^{\bloc (\pi)}q^{\rn (\pi)},
$$
where $\Pi_n$ denotes the set of partitions of $[n]:=\{1,\ldots,
n\}$.
\end{thm}

The first values of $\mu_n(a)$ are as follows:
$$
\mu_1(a)=a,\qquad \mu_2(a)=a+a^2,\qquad \mu_3(a)=a+3a+a^3,\qquad
\mu_4(a)=a+(6+q)a^2+6a^3+a^4.
$$

It is possible to derive an explicit formula for the moments from
the known measure for the Al-Salam-Chihara polynomials and facts
about $q$-Hermite polynomials. We do not give the details of
this calculation.

Let $\theta_0=1$, and for odd values of $m\geq 1$ let
$$
\theta_m
= \sum_{k=0}^{\lfloor m/2 \rfloor}{\binom m k}\sum_{l=0}^{\lfloor
m/2\rfloor-k}\frac{(-1)^{m-l}(a(1-q))^{k+l}}{(2\sqrt{a(1-q)})^{m}}
\frac{1-q^{m-2k}}{1-q^{m-2k-l}}{\qbinom {m-2k-l} l}_qq^{\binom l 2},
$$
while for even values of $m\geq 1$ let
$$
\theta_m
=\sum_{k=0}^{\lfloor m/2 \rfloor-1}{\binom m
k}\sum_{l=0}^{\lfloor
m/2\rfloor-k}\frac{(-1)^{m-l}(a(1-q))^{k+l}}{(2\sqrt{a(1-q)})^{m}}
\frac{1-q^{m-2k}}{1-q^{m-2k-l}}{\qbinom {m-2k-l} l}_qq^{\binom l
2}+\frac{1}{2^m}{\binom m { m/2}}.
$$

\begin{prop} The $n^{th}$-moment of the $q$-Charlier polynomials
$C_n(x,a;q)$ is given by
\begin{align*}
\mu_n(a)&=u^{-n}\sum_{m=0}^n{\binom n m}(-v)^{n-m}\theta_m,
\end{align*}
where
$$
u=\frac{1}{2}\sqrt{\frac{1-q}{a}}\quad \textrm{and}\quad
v=-\frac{a(1-q)+1}{2\sqrt{a(1-q)}}.
$$
\end{prop}

\section{The orthogonality relation and the linearization of products}

The orthogonality of the $q$-Charlier polynomials reads as
follows:
$$
\L_q(C_n(x,a;q)C_m(x,a;q))=n!_qa^n\delta_{mn}.
$$
In this section we state Anshelevich's linearization result, which
generalizes the orthogonality relation, in
Theorem~\ref{thm:Anshelevich}, and explicitly evaluate the
coefficients in Corollary~\ref{maincor}.

Set $n=n_1+n_2+\cdots n_k$. Denote by
$$
\pi_{n_1,n_2,\ldots, n_k}\in \Pi_n
$$
the partition whose blocks are intervals of consecutive integers
of lengths $n_1,n_2,\ldots, n_k$. Denote
$$
\Pi(n_1,n_2,\ldots,n_k)=\{\pi\in\Pi_n: \mbox{$\pi$ has no singleton
and $\pi\wedge\pi_{n_1,n_2,\ldots,n_k}=\hat 0$}\},
$$
the partitions \emph{without singleton} and \emph{inhomogeneous} with
respect to $\pi_{n_1,n_2,\ldots, n_k}$, that is, the collection of
all partitions which do not put together elements of the $k$
distinguished subsets in the same block. Thus
$\pi=\{1,6,10\}-\{2,3,9\}-\{4,7\}-\{5,8\}\in \Pi(2,4,4)$.


In 2005 Anshelevich~\cite{Ans} considered the re-scaled version
$C_n(x+a,a;q)$ and proved the following

\begin{thm}[Anshelevich]\label{thm:Anshelevich}
The linearization coefficients of $q$-Charlier polynomials are the
generating functions of the inhomogeneous partitions:
\begin{equation}\label{eq:ansh}
\L_q\left(C_{n_1}(x,a;q)\cdots C_{n_k}(x,a;q)\right)=
\sum_{\pi\in\Pi(n_1,n_2,\ldots,n_k)}q^{\rc(\pi)}a^{\bloc(\pi)}.
\end{equation}
\end{thm}

 For example, if $k=3$ and $n_1=n_2=2$ and $n_3=1$, then
\begin{align*}
\Pi(2,2,1)&=\{\{(1,3,5)(2,4)\},
\{(1,4,5)(2,3)\},\{(2,3,5)(1,4)\},\{(2,4,5)(1,3)\}\}.
\end{align*}
It is easy to see that the corresponding generating function in \eqref{eq:ansh}
is
$$
a^2q^2+a^2+a^2q+a^2q=a^2(1+q)^2.
$$
If $k=2$, equation~\eqref{eq:ansh} gives the orthogonality relation.
When $k=3$, there is an explicit formula for the generating function
in \eqref{eq:ansh}.
\begin{thm} \label{thm:explicit}
We have
$$
\sum_{\pi\in\Pi(n_1,n_2,n_3)}q^{\rc(\pi)}t^{\bloc(\pi)}=\sum_{l\geq0}
\frac{n_1!_qn_2!_qn_3!_q\, t^{l+n_3} q^{\binom {n_1+n_2-n_3-2l}2}}
{l!_q(n_3-n_1+l)!_q (n_3-n_2+l)!_q(n_1+n_2-n_3-2l)!_q}.
$$
\end{thm}
\begin{proof}
First we verify the $q=1$ case, and then give an argument for the $q$ case.

Let $N_1=[n_1]$,
$N_2=[n_1+n_2]\setminus [n_1]$ and $N_3=[n_1+n_2+n_3]\setminus [n_1+n_2]$.
The type of a subset $S$ of $[n_1+n_2+n_3]$ is defined to be the triple
$(|S\cap N_1|, |S\cap N_2|,|S\cap N_3|)$.

Consider the inhomogeneous partitions of the colored set
$[n_1+n_2+n_3]$ without singleton. Let $a, b,c$ and $d$ be
respectively the numbers of blocks of type : $A=(1,1,1)$,
$B=(1,1,0)$, $C=(1,0,1)$ and $D=(0,1,1)$. Then
$$
 a+b+c = n_1, \qquad
 a+b+d = n_2, \qquad
 a+c+d = n_3.
$$
Solving the equations and setting $b=l$ we get
$$
a=n_1+n_2-n_3-2l,\quad c=n_3-n_2+l,\quad d=n_3-n_1+l.
$$
The total number of blocks is equal to $a+b+c+d=n_3+l$, the power of
$t$ in Theorem~\ref{thm:explicit}.

Given an inhomogeneous partition $\pi$ with $a$ blocks of
type $A$, $b$ blocks of type $B$, $c$ blocks of
type $C$, and $d$ blocks of type $D$, the types of
elements of $[n_1]$ form a multiset permutation $w_1$ of $A^aB^bC^c$.
Similarly we may define words $w_2$ and $w_3$ of lengths $n_2$ and $n_3$
as multiset permutations of $A^aB^bD^d$ and $A^aC^cD^d$.
The number of such words $(w_1,w_2,w_3)$ is given by a product of
three trinomial coefficients. The number of ways to
choose edges to connect like types of letters is a factorial,
so there is a total of
\begin{align*}
&{\binom {n_1}{ a,b,c}}{\binom {n_2}{ a,b,d}} {\binom {n_3}{ a,c,d}}(a!)^2b!c!d!\\
&=\frac{n_1!n_2!n_3!}{l!(n_3-n_1+l)!(n_3-n_2+l)!(n_1+n_2-n_3-2l)!},
\end{align*}
inhomogeneous partitions.

We  include $q$ in the above argument by keeping track of the
possible restricted crossings of $\pi$.

If $\pi$ has words $(w_1,w_2,w_3)$, then some crossings are guaranteed
from the $w_i$, independent of how the edges are attached to the letters.

\begin{itemize}
\item any occurrence in $w_1$ of $B$ preceding $C$ or $A$ preceding
$C$ gives a crossing,
\item any occurrence in $w_2$ of $D$ preceding $B$,
$D$ preceding $A$, or $A$ preceding $B$
gives a crossing,
\item any occurrence in $w_3$ of $C$ preceding $A$
or $C$ preceding $D$ gives a crossing.
\end{itemize}
The remaining crossings are
\begin{itemize}
\item
crossings of edges of types $ABAB$ and $BABA$, where the
first two letters are in $w_1$ and the last two letters
are in $w_2$,
\item crossings of edges of types $ADAD$ and $DADA$, where the
first two letters are in $w_1$ and the last two letters
are in $w_3$,
\item crossings amongst edges of the same type.
\end{itemize}

Construct $\pi$ in the following manner. Fix a word $w_2$, the
guaranteed crossings in $w_2$ are exactly the inversions in $w_2$ if
the letters are ordered $BAD$, thus the crossing generating function
for $w_2$ is ~\cite[p. 41]{And}
$$
{\qbinom {n_2}{ a,b,d}}_q.
$$

Choose $c$ of the positions in $[n_1]$ for the locations of $C$ in $w_1$,
the $C$-inversions in $w_1$ give the crossing generating function
$$
{\qbinom {n_1} c}_q.
$$
Also choose the $c$ positions in $w_3$ for $C$, the $C$-inversions in
$w_3$ contribute
$$
{\qbinom {n_3} c}_q.
$$
Match these $2c$ positions with $c$ inhomogeneous edges, the
crossing generating function is
$$
c!_q.
$$

Connect the $a+b$ letters of $w_2$ of type $A$ or $B$
to the remaining $a+b$ positions of $w_1$ in $(a+b)!$ ways.
The crossings here have type $ABAB$, $BABA$,
and the same type $AA$, $BB$. The generating function is
$$
(a+b)!_q.
$$

Connect the $a+d$ letters of $w_2$ of type $A$ or $D$
to the remaining $a+d$ positions of $w_3$ in $(a+d)!$ ways.
The crossings here have type $ADAD$, $DADA$,
and the same type $AA$, $DD$. The generating function is
$$
(a+b)!_q.
$$

Any pair of edges, each of type $A$, always has one remaining crossing
which is not accounted for, this is
$$
q^{\binom{a}{2}}.
$$

Multiplying the above corresponding generating functions yields
the formula.
\end{proof}

\begin{cor}\label{maincor}
We have the following linearization formula:
\begin{equation}\label{eq:linear}
C_{n_1}(x,a;q)C_{n_2}(x,a;q)=\sum_{n_3}K_{n_1n_2n_3}C_{n_3}(x,a;q),
\end{equation}
where
$$
K_{n_1n_2n_3}=\sum_{l\geq 0}\frac{n_1!_qn_2!_q\, a^l
q^{\binom {n_1+n_2-n_3-2l} 2}}{l!_q(n_3-n_1+l)!_q
(n_3-n_2+l)!_q(n_1+n_2-n_3-2l)!_q}.
$$
\end{cor}

Corollary~\ref{maincor} may also be proven using the Askey-Wilson
integral, see \cite[p. 422]{I}.


\section{A Combinatorial Proof of Theorem~\ref{thm:Anshelevich}}
In this section we prove Theorem~\ref{thm:Anshelevich}, using the
combinatorial interpretation of the polynomials given in
Corollary~\ref{mainpolycomb} and the moments given in
Theorem~\ref{mainmomcomb}.

\subsection{Generalized Charlier-permutations}
We fix $\mathbf{n}=(n_1,\dots,n_k)$, where $n_i$'s are positive integers.
Let $n$ denote
$n_1+n_2+\cdots+n_k$. For $1\leq i\leq k$, let $N_i$ denote the set of all integers
$j$ such that
$n_1+\cdots+n_{i-1}<j\leq n_1+\cdots+n_{i}$, $n_0=0$. Then
$[n]=N_1\cup\cdots\cup N_k$. A {\em generalized Charlier-permutation
$\tau$ of type $\mathbf{n}$} is a sequence $(\tau_k,\tau_{k-1},\dots,\tau_1)$ where $\tau_i$
is a Charlier-permutation of $N_i$. The weight of a generalized Charlier-permutation is
the product of the weights of its Charlier-permutations.

The following are examples of generalized Charlier-permutations of
type $\mathbf{n}=(2,4,3)$:
\begin{align*}
&(9\,7)(8)\,|\,(6\,5)(4\,3)\,|\,(2)(1),\quad
(9\,7)(8)\,|\,(6\,5)(4\,3)\,|\,[2](1),\quad
(9\,7)(8)\,|\,(6\,4)(5\,3)\,|\,(2\,1),\\
&(9\,7)[8]\,|\,(6\,4)(5\,3)\,|\,(2\,1),\quad
(9\,8)[7]\,|\,(6\,4)(5\,3)\,|\,(2\,1),\quad
(9\,8)[7]\,|\,(6)(5\,4)(3)\,|\,(2\,1).
\end{align*}

\subsection{Charlier-partitions}
Combining generalized Charlier-permutations and moments discussed in the previous
sections, we want to interpret
$$\L_q\left(C_{n_1}(x,a;q)\ldots C_{n_k}(x,a;q)\right)
$$
 as the weight generating function of some objects.
 The weight of
any generalized Charlier-permutation can be regarded as a monomial
in $x$ of degree the number of cycles labeled $-x$. Applying
$\L_q$ to the monomial is equivalent to considering all possible
partitions of such cycles, where cycles are ordered as they appear
in the generalized Charlier-permutation. We call the resulting
objects {\em Charlier-partitions} of $\mathbf{n}$.  A Charlier-partition is
represented as $(\tau,\nu)$, where
$\tau=(\tau_k,\tau_{k-1},\dots,\tau_1)$ is a generalized
Charlier-permutation and $\nu$ is a partition of cycles labeled
$-x$ in $\tau$. We regard each 1-cycle with label $a$ as a block by itself in $\nu$.
The weight of $(\tau,\nu)$ is defined by
$$
w(\tau,\nu)=q^{\rc(\nu)}a^{\bloc(\nu)}\left.w(\tau)\right|_{x=1}.
$$
Then clearly we have the following identity:
\begin{equation}\label{eqn:linearization}
\L_q\left(C_{n_1}(x,a;q)\cdots C_{n_k}(x,a;q)\right)=\sum_{(\tau,\nu)}w(\tau,\nu).
\end{equation}

Given a Charlier-partition $(\tau,\nu)$ of $\mathbf{n}$ with $\tau=(\tau_k,\tau_{k-1},\dots,\tau_1)$,
we draw the corresponding diagram on the plane as follows:
\begin{itemize}
\item The $n$ integers in $\tau$ are arranged on the horizontal axis in the order they appear in $\tau$, one step apart.
\item The 1-cycles with label $a$ are framed with a box.
\item The maximum in each cycle, except that in a box, is circled, so that we can recover the cycle structure and labels.
\item If a cycle $\sigma$ follows a cycle $\sigma'$ in a block of $\nu$, then we draw an arc above the horizontal line between
the last element of $\sigma'$ and the first element, that is also
the maximum of $\sigma$, making as few crossings as possible. The
smallest number of crossings agrees with the restricted crossings in
$\nu$, $\rc(\nu)$.
\item Draw a straight edge between two adjacent elements if and only if they are in the same cycle.
\end{itemize}

\begin{exam}
Let $\mathbf{n}=(3,5,5)$.
Then  $(\tau,\nu)$  is a Charlier-partition of $\mathbf{n}$, where
$$
\tau=\left((13\;11)(12\;9)(10),(8\,4\,6)[7](5),(3\,1)(2)\right)
$$
is a generalized
Charlier-permutation  of type $\mathbf{n}$ and
$$\nu=\left\{\{(13\;11),(8\,4\,6),(3\,1)\},\{(12\;9),(5),(2)\},\{(10)\}\right\}$$
is a partition of cycles of $\tau$ with weight $-x$. The
corresponding diagram can be illustrated as follows:
$$
\xymatrix@R=5mm@C=6mm@!R@!C{
\\%
*+<3pt>[Fo]{13}\ar@{-}[r]&*+<7pt>{11}\ar@{-}@/^8mm/[rrrr]
&*+<3pt>[Fo]{12}\ar@{-}[r]&*+<7pt>{9}\ar@{-}@/^10mm/[rrrrrr]&*+<3pt>[Fo]{10}&
*+<7pt>[Fo]{8}\ar@{-}[r]&*+<7pt>{4}\ar@{-}[r]&*+<7pt>{6}\ar@{-}@/^7mm/[rrr]
&*+[F]{7}&*+<7pt>[Fo]{5}\ar@{-}@/^7mm/[rrr]&*+<7pt>[Fo]{3}\ar@{-}[r]&
*+<7pt>{1}&*+<7pt>[Fo]{2}.
}
$$
\end{exam}
\subsection{Involution} The weight function in
Equation~(\ref{eqn:linearization}) has many cancelations. We will give
a combinatorial weight-preserving sign-reversing involution
$\phi$ with fixed set $\Pi(n_1,n_2,\dots,n_k)$ defined on the set of all Charlier-partitions of type $\mathbf{n}$.

Let $(\tau,\nu)$ be a Charlier-partition of $\mathbf{n}$.
The involution $\phi$ will be defined depending on three different cases
of $(\tau,\nu)$.

\medskip
\noindent\textsc{Case 1.} If $(\tau,\nu)$ has a circled 1-cycle in a
block by itself or a boxed 1-cycle, then define $\phi(\tau,\nu)$ by
picking up the smallest 1-cycle and switching
 its box to circle or vice versa. Since a boxed 1-cycle contributes $-a$ and
a circled 1-cycle $a$, $\phi$ is weight-preserving sign-reversing in this case.

\medskip
\noindent\textsc{Case 2.}
We now assume that $(\tau,\nu)$ has no 1-cycles, boxed or
circled in a block by itself. Find the rightmost integer $\alpha$,
if it exists, in $\tau$, say in $\tau_i$,
such that it has a neighbor $\beta$ in $\tau_i$, along the
straight edge or an arc, to its right.

\noindent\textsc{Case 2.1.}
Assume that $\alpha$ and $\beta$ are in the same cycle $\sigma$ ending with $\alpha\,\beta$, i.e. $\sigma=(\cdots\alpha\,\beta)$.
Since $\alpha$ is the penultimate entry in $\sigma$, $\beta$ is not the maximum in $\sigma$.
Suppose the contribution of $\beta$ to $\Cinv(\tau_i)$ is~$j$.
Then $\tau_i$ is of the form
$$\tau_i=(\cdots)\cdots(\cdots\alpha\,\beta)(t_m)(t_{m-1})\cdots(t_{j+2})(t_{j})\cdots(t_1)$$
with
$t_1<t_2<\cdots<t_m$ and $t_{j+1}=\beta$.
Let $\tau_i'=(\cdots)\cdots(\cdots\alpha)(t_m)(t_{m-1})\cdots(t_1)$. Integers $t_m,t_{m-1},\dots,t_{j+2}$ are moved to the left by one step
and $\beta$ occupies the position of $t_{j+2}$. We make some changes on the diagram of $(\tau,\nu)$ as follows, to
obtain the diagram of the Charlier-partition $(\tau',\nu')$:

\bigskip
{\bf Algorithm: Stretch}
\begin{itemize}
\item Initially, start with the diagram of $(\tau,\nu)$ with all arcs and edges.
\item Delete the straight edge between $\alpha$ and $\beta$ in the diagram.
\item Rearrange $t_m,t_{m-1},\dots,t_1$ in descending order, leaving the arcs and edges intact in their present positions.
\item For $l$ from $m-1$ down to $m-j$, make the arc arriving from left at the position of $t_l$ to arrive at $t_{l+1}$, if it exists;
if there is no such arc at position $t_l$ and there are no arcs at position $t_{l+1}$, then make the arc arriving from right at position
$t_l$ to arrive at position $t_{l+1}$.
\item Add an arc between $\alpha$ and $t_{m-j}$.
\end{itemize}

\medskip
Let $\phi(\tau,\nu)=(\tau',\nu')$. We need to show that $\phi$ is a weight-preserving sign-reversing involution.
The involution part will be clear after the next subcase is introduced. Clearly we have $w(\tau',\nu')=-w(\tau,\nu)$ when $q=1$,
since $(\tau',\nu')$ has one more 1-cycle than $(\tau,\nu)$, contributing $-1$ to $w(\tau',\nu')$.
So it suffices to prove that the exponents of $q$ in $w(\tau,\nu)$ and $w(\tau',\nu')$ are the same.
This can be done easily by induction on $j$. The loss in Charlier inversions from $\tau$ to $\tau'$ exactly matches the gain in
restricted crossings from $\nu$ to $\nu'$ for all $j$.

The following are some examples with $\mathbf{n}=(3,6,2)$.
\smallskip
\begin{center}%\ar@{.}@/^10mm/[rrrr]^(.95){2} \ar@{.}@/^10mm/[rrrrr]^(.96){2}
$$
\xymatrix@R=15mm@C=10mm@!R@!C{
*+<3pt>[Fo]{11}\ar@{.}@/^10mm/[rrrrrr]^(.96){2}&*+<3pt>[Fo]{10}\ar@{.}@/^8mm/[rrrr]^(.95){1}&*+<7pt>[Fo]{9}\ar@{-}@/^5mm/[r]&
*+<7pt>[Fo]{8}\ar@{-}[r]^(.85){0}&{7}\ar@{-}@/^10mm/[rrrrr]&*+<7pt>[Fo]{6}&*+<7pt>[Fo]{5}\ar@{-}@/^10mm/[rrrr]&
*+<7pt>[Fo]{4}\ar@{-}@/^5mm/[r]&*+<7pt>[Fo]{3}&*+<7pt>[Fo]{2}&*+<7pt>[Fo]{1}\ar@{<.>}@/^5mm/[d]
\\
*+<3pt>[Fo]{11}\ar@{.}@/^10mm/[rrrrr]^(.95){2}&*+<3pt>[Fo]{10}\ar@{.}@/^8mm/[rrr]^(.93){1}&*+<7pt>[Fo]{9}\ar@{-}@/^5mm/[r]&
*+<7pt>[Fo]{8}\ar@{-}@/^10mm/[rrrr]^(.95){0}&*+<7pt>[Fo]{7}\ar@{-}@/^10mm/[rrrrr]&*+<7pt>[Fo]{6}&*+<7pt>[Fo]{5}\ar@{-}@/^10mm/[rrrr]&
*+<7pt>[Fo]{4}\ar@{-}@/^5mm/[r]&*+<7pt>[Fo]{3}&*+<7pt>[Fo]{2}&*+<7pt>[Fo]{1}
\\
*+<3pt>[Fo]{11}\ar@{.}@/^10mm/[rrrrrrr]^(.97){3}&*+<3pt>[Fo]{10}\ar@{.}@/^8mm/[rrrr]^(.95){1}&*+<7pt>[Fo]{9}\ar@{-}@/^5mm/[r]&
*+<7pt>[Fo]{8}\ar@{-}[r]^(.85){0}&{7}\ar@{-}@/^10mm/[rrrrr]&*+<7pt>[Fo]{6}&*+<7pt>[Fo]{5}\ar@{.}@/^10mm/[rrrr]^(.05){2}&
*+<7pt>[Fo]{4}\ar@{-}@/^5mm/[r]&*+<7pt>[Fo]{3}&*+<7pt>[Fo]{2}&*+<7pt>[Fo]{1}\ar@{<.>}@/^5mm/[d]
\\
*+<3pt>[Fo]{11}\ar@{.}@/^10mm/[rrrrrr]^(.97){3}&*+<3pt>[Fo]{10}\ar@{.}@/^8mm/[rrr]^(.93){1}&*+<7pt>[Fo]{9}\ar@{-}@/^5mm/[r]&
*+<7pt>[Fo]{8}\ar@{-}@/^10mm/[rrrr]^(.95){0}&*+<7pt>[Fo]{7}\ar@{-}@/^10mm/[rrrrr]&*+<7pt>[Fo]{6}\ar@{.}@/^10mm/[rrrrr]^(.04){2}&*+<7pt>[Fo]{5}&
*+<7pt>[Fo]{4}\ar@{-}@/^5mm/[r]&*+<7pt>[Fo]{3}&*+<7pt>[Fo]{2}&*+<7pt>[Fo]{1}
\\
*+<3pt>[Fo]{11}\ar@{-}@/^7mm/[rr]&*+<3pt>[Fo]{10}\ar@{.}@/^8mm/[rrrr]^(.95){1}&*+<7pt>[Fo]{9}\ar@{-}@/^5mm/[r]&
*+<7pt>[Fo]{8}\ar@{-}[r]^(.85){0}&{7}\ar@{-}@/^10mm/[rrrrr]&*+<7pt>[Fo]{6}&*+<7pt>[Fo]{5}\ar@{.}@/^10mm/[rrrr]^(.05){2}&
*+<7pt>[Fo]{4}\ar@{.}@/^5mm/[r]^(.2){3}&*+<7pt>[Fo]{3}&*+<7pt>[Fo]{2}&*+<7pt>[Fo]{1}\ar@{<.>}@/^5mm/[d]
\\
*+<3pt>[Fo]{11}\ar@{-}@/^7mm/[rr]&*+<3pt>[Fo]{10}\ar@{.}@/^8mm/[rrr]^(.93){1}&*+<7pt>[Fo]{9}\ar@{-}@/^5mm/[r]&
*+<7pt>[Fo]{8}\ar@{-}@/^10mm/[rrrr]^(.95){0}&*+<7pt>[Fo]{7}\ar@{-}@/^10mm/[rrrrr]&*+<7pt>[Fo]{6}\ar@{.}@/^10mm/[rrrrr]^(.04){2}&
*+<7pt>[Fo]{5}\ar@{.}@/^7mm/[rr]^(.1){3}&*+<7pt>[Fo]{4}&*+<7pt>[Fo]{3}&*+<7pt>[Fo]{2}&*+<7pt>[Fo]{1}
}
$$
\mbox{Three sets of $(\tau,\nu)$ and $(\tau',\nu')$ of type $\mathbf{n}=(3,6,2)$ with $\alpha=8$.}
\end{center}
\bigskip

\noindent\textsc{Case 2.2.} We now assume that $\alpha$ and $\beta$
are in different cycles. Clearly $\beta$ forms a 1-cycle and adjoins
$\alpha$ by an arc. Moreover, all integers to the right of $\alpha$
in $\tau_i$ form 1-cycles and are in descending order. Suppose there
are exactly $j$ integers between $\alpha$ and $\beta$. Then $\tau_i$
is of the form
$\tau_i=(\cdots)\cdots(\cdots\alpha)(t_m)(t_{m-1})\cdots(t_1)$ with
$t_1<t_2<\cdots<t_m$ and $t_{m-j}=\beta$. Let
$\tau_i'=(\cdots)\cdots(\cdots\alpha\,t_{j+1})(t_m)(t_{m-1})\cdots(t_{j+2})(t_j)\cdots(t_1)$.
Integers $t_m,t_{m-1},\dots,t_{j+2}$ are moved to the right by one
step and $t_{j+1}$ occupies the position of $t_m$. We make some
changes on the diagram of $(\tau,\nu)$ as follows, to obtain the
diagram of the Charlier-partition $(\tau',\nu')$:

\bigskip
{\bf Algorithm: Compress}
\begin{itemize}
\item Initially, start with the diagram of $(\tau,\nu)$ with all arcs and edges.
\item Delete the arc between $\alpha$ and $\beta=t_{m-j}$ in the diagram.
\item For $l$ from $m-j$ to $m-1$, make the arc arriving from left at the position of $t_{l+1}$ to arrive at $t_l$, if it exists;
if there is no such arc at position $t_{l+1}$ and there are no arcs at position $t_{l}$, then make the arc arriving from right at position
$t_{l+1}$ to arrive at position $t_l$.
\item Rearrange $t_m,t_{m-1},\dots,t_{j+1}$ as $t_{j+1},t_m,t_{m-1},\dots,t_{j+2}$.
\item Add a straight edge between $\alpha$ and $t_{j+1}$.
\end{itemize}

\medskip
We let $\phi(\tau,\nu)=(\tau',\nu')$.

If  $(\tau,\nu)$ falls on \textsc{Case 2.1} then $(\tau',\nu')$ falls on \textsc{Case 2.2} and vice versa.
The algorithms Stretch and Compress are inverses to each other. If the roles of $(\tau,\nu)$ and $(\tau',\nu')$ are exchanged
in the examples for algorithm Stretch, then they become examples of algorithm Compress.

\medskip
\noindent\textsc{Case 3.}
Assume that $(\tau,\nu)$ does not fall in Cases 1 and 2. All the cycles in $(\tau,\nu)$ are 1-cycles, every block in $\nu$ has at least two cycles,
and each block of $\nu$ has at most one element in $N_i$ for each $i=1,2,\dots,k$. So $\nu$ is a partition in $\Pi(n_1,n_2,\dots,n_k)$.
Let $\phi(\tau,\nu)=(\tau,\nu)$. The Charlier-partition $(\tau,\nu)$ becomes a fixed point of $\phi$.

Combining Cases 1, 2 and 3, the mapping $\phi$ is a weight-preserving sign-reversing involution on the
set of all Charlier-partitions of type $\mathbf{n}$ with fixed set $\Pi(n_1,n_2,\dots,n_k)$.
This constitutes a combinatorial proof of Theorem~\ref{thm:Anshelevich}.

\section{A variation}
Consider the polynomials ${\hat C}_n(x|q)$ defined by
\begin{equation}\label{eq:var}
{\hat C}_{n+1}(x|q)=(x-b[n]_q)\,{\hat C}_n(x|q)-a[n]_q{\hat
C}_{n-1}(x|q),\quad n\geq 0,
\end{equation}
where ${\hat C}_{0}(x|q)=1$ and ${\hat C}_{-1}(x|q)=0$. Then (see
\cite{Bi,KZ}) the polynomials ${\hat C}_n(x|q)$ are orthogonal with
respect to the linear functional $\hat\L_q$ defined by
$$
\hat\L_q(x^n)=\hat \mu_n=\sum_{\pi\in \Pi_n'}
q^{\rc(\pi)}a^{\bloc(\pi)}b^{n-2\bloc(\pi)},
$$
where $\Pi_n'$ is the set of partitions of $[n]$ without singleton.

These polynomials may be obtained from $C_n(x,a;q)$ as follows: let
$p_n(x)$ be the polynomial $C_n(x+a,a;q)$ with $a$ replaced by
$a/b^2$, then ${\hat C}_n(x|q)=b^np_n(x/b)$. It follows from
\eqref{eq:explicit} that
\begin{equation}\label{eq:explicit2}
{\hat C}_n(x|q)=\sum_{k=0}^n{\qbinom n
k}(-1)^{n-k}q^{k^2-kn}\left(\frac{a}{b}\right)^{n-k}
\prod_{i=0}^{k-1}\left(x+\frac{a}{b}q^{-i}-b[i]_q\right).
\end{equation}
The first values of these polynomials are
\begin{align*}
\hat C_1(x|q)&=x,\\
\hat C_2(x|q)&= {x}^{2}-bx-a,\\
\hat C_3(x|q)&={x}^{3}-b(q+2){x}^{2}+(b^{2}(1+q)-2a-aq)x+ab(1+q).
\end{align*}
Since the linearization coefficients are invariant by translation of
$x$, we have
\begin{equation}\label{eq:key}
\frac{\hat\L_q(\prod_{i=1}^k{\hat C}_{n_i}(x|q))} {\hat\L_q(({\hat
C}_{n_k}(x|q))^2)}=\left. \frac{\L_q(\prod_{i=1}^k{C}_{n_i}(x,a;q))}
{\L_q(({C}_{n_k}(x,a;q))^2)}\right|_{a\to a/b^2} \cdot
b^{n_1+n_2+\cdots n_{k-1}-n_k}.
\end{equation}
As $\hat\L_q({\hat C}_{n_k}(x|q){\hat C}_{n_k}(x|q))
=\L_q({C}_{n_k}(x,a;q){C}_{n_k}(x,a;q))=a^{n_k}n_k!_q$, we derive immediately from
\eqref{eq:key} and Theorem~6 the following
\begin{thm}[Anshelevich]\label{thm:anshelevich}
The linearization coefficients of the  polynomials $\hat C_n(x|q)$
are the generating functions of the inhomogeneous partitions:
$$
\hat\L_q\left({\hat C}_{n_1}(x|q)\cdots {\hat
C}_{n_k}(x|q)\right)=
\sum_{\pi\in\Pi(n_1,n_2,\ldots,n_k)}q^{\rc(\pi)}a^{\bloc(\pi)}b^{n_1+\cdots
+n_k-2\,\bloc(\pi)}.
$$
\end{thm}

Anshelevich~\cite{Ans} presented the above theorem as a
generalization of several other previously known results and proved
it by the same method for Theorem~6. We have just shown that
Theorem~6 and Theorem~9 are actually equivalent.

Now Corollary~8 implies the following
\begin{cor}
We have the following linearization formula:
\begin{equation}\label{eq:linearC}
{\hat C}_{n_1}(x|q)\;{\hat C}_{n_2}(x|q)=\sum_{n_3} {\hat
K}_{n_1n_2n_3}{\hat C}_{n_3}(x|q),
\end{equation}
where
$$
{\hat K}_{n_1n_2n_3}=\sum_{l\geq 0}\frac{n_1!_qn_2!_q\,
a^lb^{n_1+n_2-n_3-2l} q^{\binom {n_1+n_2-n_3-2l}
2}}{l!_q(n_3-n_1+l)!_q (n_3-n_2+l)!_q(n_1+n_2-n_3-2l)!_q}.
$$
\end{cor}
When $a=1$ and $b=0$ the polynomials ${\hat C}_{n}(x|q)$ reduce to a
family of $q$-Hermite polynomials $\tilde H_n(x|q)$ (see
\cite[(2.11)]{ISV}) and we get the corresponding combinatorial
interpretation for the linearization coefficients of the $q$-Hermite
polynomials in \cite{ISV}:
\begin{equation}\label{eq:linearH}
\hat\L_q\left({\tilde H}_{n_1}(x|q)\cdots {\tilde
H}_{n_k}(x|q)\right)= \sum_{\pi}q^{\rc(\pi)},
\end{equation}
where the summation is over all inhomogeneous 2-partitions $\pi$ of
$[n_1+\cdots +n_k]$, i.e., inhomogeneous partitions of which each
block contains only two elements.

In particular, when $a=1$ and $b=0$, identity~\eqref{eq:linearC}
reduces to
\begin{equation}
{\tilde H}_{n_1}(x|q)\;{\tilde
H}_{n_2}(x|q)=\sum_{l=0}^{\min(n_1,n_2)} {\qbinom {n_1} l}_q{\qbinom {n_2}
l}_ql!_q\;{\tilde H}_{n_1+n_2-2l}(x|q).
\end{equation}

\section{Remarks} The $q$-Charlier polynomials in \cite{MSW} have a
natural $q$-Stirling number associated with their moments, a simple
explicit formula, but a complicated and non-positive linearization formula.
In contrast, Al-Salam-Chihara $q$-Charlier polynomials have a
complicated $q$-Stirling number associated with their moments, a complicated
explicit formula, but the most natural linearization formula.

\renewcommand{\baselinestretch}{1}
\begin{thebibliography}{99}
\small \setlength{\itemsep}{-.8mm}
\bibitem{And}G. E. Andrews, The Theory of Partitions, Addison-Wesley, Reading, M.A., 1976.

\bibitem{Ans} M. Anshelevich, Linearization coefficients for orthogonal polynomials
using stochastic processes, The Annals of Probability, 2005, Vol. 33, No. 1, 114-136.

\bibitem{Bi} Ph. Biane, Some properties of crossings and partitions,
Discrete Math., 175 (1997), 41--53.

\bibitem{Chi} T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach, 1978.

\bibitem{De} A. de M\'edicis,
Aspects combinatoires des nombres de Stirling, des polyn\^omes orthogonaux de Sheffer et de leurs
$q$-analogues, ISBN 2-89276-114-X, Vol. 13, Publications du LACIM, UQAM, Montr\'eal, 1993.

\bibitem{MSW} A. de M\'edicis, D. Stanton, D. White,
The Combinatorics of $q$-Charlier Polynomials, J. Combin. Theory
Ser. A {\bf 69}, 1995, 87-114.

\bibitem{CV} M. de Saint-Catherine and G. Viennot, Combinatorial interpretation of integrals of products of Hermite, Laguerre and Tchebycheff polynomials.  Orthogonal polynomials and applications (Bar-le-Duc, 1984),  120--128, Lecture Notes in Math., 1171, Springer, Berlin, 1985.

\bibitem{Ge} I. Gessel, Generalized rook polynomials and orthogonal polynomials,
in "$q$-Series and Partitions" (D. Stanton, Ed.), IMA Volumes in Math. and Its Appl., Vol. 18, pp. 159--176,
Springer-Verlag, New York, 1989.

\bibitem{I} M. Ismail, Classical and Quantum Orthogonal
Polynomials in One Variable, Cambridge University Press, 2005.

\bibitem{ISV} M. Ismail, D. Stanton and G. Viennot, The Combinatorics of $q$-Hermite
polynomials and the Askey-Wilson integral, Europ. J. Combinatorics (1987) {\bf 8}, 379-392.

\bibitem{KZ} A. Kasraoui and J. Zeng, Distribution of crossings, nestings and
alignments of two edges in matchings and partitions, to appear in Electronic.
J. Combin. 13(1), 2006, \#R33.

\bibitem{KS}
R.~Koekoek and R.F.Swarttouw, {\em The Askey-scheme of hypergeometric
orthogonal polynomials and its $q$-analogue} Delft University of Technology,
Report no. 98-17 (1998).

\bibitem{SS} R. Simion and D. Stanton, Octabasic Laguerre polynomials and
permutation statistics, J. Comp. Appl. Math. 68 (1996), 297--329.

\bibitem{Ze} J. Zeng, Lin\'earisation de produits de polyn\^omes de Meixner, Krawtchouk, et
Charlier, SIAM J. Math. Anal., Vol. 21, No. 5, pp. 1349--1368, 1990.
\end{thebibliography}
\end{document}
