Séminaire Lotharingien de Combinatoire 54 (2006), Article B54i

THE COMBINATORICS OF THE AL-SALAM-CHIHARA q-CHARLIER POLYNOMIALS

DONGSU KIM, DENNIS STANTON, AND JIANG ZENG

Dedicated to Xavier Viennot on the occasion of his sixtieth birthday

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.

1. Introduction

The classical Charlier polynomials C_{n}^{a}(x) have been studied combinatorially by several authors [5, 8, 14]. Recall [4] that these polynomials are defined by

C_{n}^{a}(x) = ∑_{k=0}^{n} \binom{n}{k}(−a)^{n−k}x(x − 1) ⋯ (x − (k − 1))  (1.1)

and satisfy the three term-recurrence relation

C_{n+1}^{a}(x) = (x − a − n) C_{n}^{a}(x) − an C_{n−1}^{a}(x), n ≥ 0,  (1.2)

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 [6]. 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+⋯+q^{n−1}, C_{0}^{a}(x; q) = 1, C_{−1}^{a}(x; q) = 0. The explicit formula analogous to (1.1) is given by

C_{n}^{a}(x; q) = ∑_{k=0}^{n} [\begin{matrix}n \\ k \end{matrix}]_{q}(−a)^{n−k}q^{\binom{n−k}{2}} ∏_{i=0}^{k−1}(x − [i]_{q}).

The linearization coefficients for the Charlier polynomials are given by quotients of factorials (see (1.5)). The combinatorial study of the q-analogues C_{n}^{a}(x; q) in [6] 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 [6, Theorem 3]).

The first author was partially supported by KRF grant R05-2004-000-11511-0.

The second author was partially supported by NSF grant DMS-0503660.

Anshelevich [2] has recently considered a q-analogue of the three-term recurrence (1.2) 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 [7, 10].

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 3 and Theorem 4. The explicit linearization coefficients are given in §4 in Corollary 8. We then give the killing involution in §5. We present a variation Ĉ_{n}(x|q) of the polynomials C_{n}(x, a; q) in §6, which has the advantage to include the q-Hermite polynomials in [10] as a special case.

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

The generating function is

∑_{n=0}^{∞} C_{n}^{a}(x)\frac{t^{n}}{n!} = e^{−at}(1 + at)^{x}.  (1.3)

The moment sequence μ_{n} is given by the following formula:

μ_{n} = L(x^{n}) = ∑_{x=0}^{∞} x^{n}e^{−a} \frac{a^{x}}{x!} = ∑_{k=1}^{n} S(n, k)a^{k},  (1.4)

where S(n, k) denotes the Stirling number of the second kind. The orthogonality reads:

L(C_{m}^{a}(x)C_{n}^{a}(x)) = ∑_{k=0}^{∞} C_{m}^{a}(k)C_{n}^{a}(k)\frac{e^{−a}a^{k}}{k!} = n!a^{n}δ_{mn}.

The linearization coefficient c_{n_{1}n_{2}}^{n_{3}} is defined by:

C_{n_{1}}^{a}(x)C_{n_{2}}^{a}(x) = ∑_{n_{3}} c_{n_{1}n_{2}}^{n_{3}}C_{n_{3}}^{a}(x).

By orthogonality we have c_{n_{1}n_{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 (1.3) and (1.4) that

∑_{n_{1},...,n_{k}=0}^{∞} L(C_{n_{1}}^{a}(x) … C_{n_{k}}^{a}(x))\frac{t_{1}^{n_{1}}}{n_{1}!} … \frac{t_{k}^{n_{k}}}{n_{k}!} = e^{a(e_{2}(t_{1},...,t_{k})+...+e_{k}(t_{1},...,t_{k}))},

where e_{i} is the elementary symmetric function of degree i. It follows that

L(C_{n_{1}}^{a}(x)C_{n_{2}}^{a}(x)C_{n_{3}}^{a}(x)) = ∑_{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)!}. (1.5)

THE COMBINATORICS OF THE AL-SALAM-CHIHARA q-CHARLIER POLYNOMIALS 3

In the general case the above generating function implies that L(C_{n_{1}}^{a}(x) … C_{n_{k}}^{a}(x)) (k ≥ 1) is a polynomial in a with positive integer coefficients; a combinatorial interpretation of this coefficient has been given [8, 14].

2. The new q-Charlier polynomials

We define the new q-Charlier polynomials C_{n}(x, a; q) by

C_{n+1}(x, a; q) = (x − a − [n]_{q}) C_{n}(x, a; q) − a[n]_{q} C_{n−1}(x, a; q).  (2.1)

The first values of these polynomials are

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}.

The explicit formula which is analogous to (1.1) is

C_{n}(x, a; q) = ∑_{k=0}^{n} [\begin{matrix}n \\ k \end{matrix}]_{q}q^{k(k−n)}(−a)^{n−k} ∏_{i=0}^{k−1} (x − [i]_{q} + a(q^{−i} − 1)) .  (2.2)

This is a re-scaled version of the Al-Salam-Chihara polynomials Q_{n}(x, α, β; q) [12, p. 80–81]:

C_{n}(x, a; q) = (\frac{a}{1 − q} )^{n/2} Q_{n} (\frac{1}{2}\sqrt{\frac{1 − q}{a}} (x − a − \frac{1}{1 − q} ) , \frac{−1}{\sqrt{a(1 − q)}}, 0; q) .

Since the generating function of the Al-Salam-Chihara polynomials is known, we derive that

∑_{n=0}^{∞} C_{n}(x, a; q)\frac{t^{n}}{n!_{q}} = \frac{(−t; q)_{∞}}{(\sqrt{a(1 − q)}te^{iθ}, \sqrt{a(1 − q)}te^{−iθ}; q)_{∞}} ,

where n!_{q} = [n]_{q}[n − 1]_{q} … [2]_{q}[1]_{q} and

cos θ = \frac{1}{2}\sqrt{\frac{1 − q}{a}} (x − a − \frac{1}{1 − q} ) .

We can give a combinatorial interpretation for the q-Charlier polynomials from a result due to Simion and Stanton [13].

Consider a subset B of [n] and a permutation σ on [n] \ B. Then σ consists of fixed points and cycles of length > 1:

C = (k_{0}, k_{1}, k_{2}, …, k_{s}), where k_{s} > max{k_{0}, k_{1}, ⋯ k_{s−1}}.

For any k ∈ [n] \ 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

w(k) = k − 1 − |{i : j < i < s, k_{i} < k_{j}}| − ∑_{cycles Q, max(Q)>k_{s}}(# of points on Q less than k).

Let w(B, σ) = ∑_{k∈[n]\B} w(k) and let cyc(σ) be the number of cycles of σ.

Example 1. Let n = 9, B = {2, 9} and σ = (6)(4 7)(3 5 1 8) (in cycle notation with maximum at last). Then we have cyc(σ) = 3 and

w(B, σ) = (3 − 1 − 1) + (5 − 1 − 1) + (1 − 1) + (4 − 1 − 2) = 5.

Theorem 1. We have

C_{n}(x, a; q) = ∑_{(B,σ)}(−1)^{n−cyc(σ)}a^{|B|}x^{cyc(σ)}q^{w(B,σ)}.

where B ⊂ [n] and σ is a permutation on [n] \ B.

Proof. This is the r = 1, s = 0, t = q, u = 1 special case of the quadrabasic Laguerre polynomials [13, p.313]. □

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

Definition 2. (Charlier-labeling of permutations) A Charlier-labeling of a permutation π = σ_{1}σ_{2} ⋯ σ_{k} is a labeling of integers and cycles in π satisfying the following rules:

• Each integer in π is labeled −1.

• Each cycle of length 1 is labeled either −x or a.

• Each cycle of length > 1 is labeled −x. A permutation with a Charlier-labeling is called a Charlier-permutation.

Let τ denote a Charlier-permutation with underlying permutation π. Identify Cinv(τ) with Cinv(π). Define the weight of τ, w(τ), to be the product of q^{Cinv(τ)} and all the labels of integers and of cycles in τ. Since only 1-cycles are allowed two different choices for a label, if π has f fixed points, there are 2^{f} distinct Charlier-permutations with π 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 Charlierpermutation are represented in the same way except that 1-cycles with label a are enclosed with a pair of brackets.

For each pair (B, σ) in Theorem 1, where B ⊂ [n] and σ a permutation of [n] \ B, one can associate a Charlier-permutation τ of [n] as follows: each element of B gives rise a 1-cycle with brackets, each cycle (a_{1}a_{2} … a_{l}) of σ gives rise a cycle (a_{l}a_{l−1} … a_{1}) of τ with reverse order and the maximal element at the first position. It is not hard to see that w(B, σ) = Cinv(τ). For instance, the Charlier-permutation corresponding to the pair (B, σ) in the above example is τ = [9](8 1 5 3)(7 4)(6)[2] with weight

(−1)^{9}(−x)^{3}a^{2}q^{0+3+1+1} = a^{2}q^{5}x^{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 1 as follows.

Corollary 3. The q-Charlier polynomial C_{n}(x, a; q) is the generating function of Charlierpermutations of [n]:

C_{n}(x, a; q) = ∑_{τ} w(τ),

where τ runs through all permutations of [n].

3. The moments

For the Charlier polynomials C_{n}^{a}(x), the n^{th} moment μ_{n} is the generating function for set partitions of {1, 2, ⋯, n} according to the number of blocks (see (1.4)). There is a natural q-analogue for the polynomials C_{n}^{a}(x; q) [6, Eq. (3.1)], whose n^{th} moment is

μ_{n} = ∑_{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 [6, Eq. (3.3)]. In this section we identify an appropriate q-statistic on set partitions which yields the n^{th} moment μ_{n} for C_{n}(x, a; q), and give an explicit formula for it.

Recall that if π is a partition of M = {1, …, m}, then a crossing of π 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 follows e in π if e and f belong to the same block of π, and there is no element g of this block with e < g < f. We define a restricted crossing to be a crossing (a, b, c, d) such that c follows a and d follows b. Similarly a 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 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 π = {1, 6, 10} − {2, 3, 9} − {4, 7} − {5, 8} is the following:

[figure: 1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

Let rc(π) (resp. rn(π)) be the number of restricted crossings (resp. restricted nestings) of a partition π. The number of blocks of π is denoted by block(π). For the above π we have block(π) = 4, rc(π) = 7 and there are rn(π) = 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 [3, 11]) and the three-term recurrence relation (2.1).

Theorem 4. The n^{th}-moment of the q-Charlier polynomials C_{n}(x, a; q) is

μ_{n}(a) := L_{q}(x^{n}) = ∑_{π∈Π_{n}} a^{block(π)}q^{rc(π)} = ∑_{π∈Π_{n}} a^{block(π)}q^{rn(π)},

where Π_{n} denotes the set of partitions of [n] := {1, …, n}.

The first values of μ_{n}(a) are as follows:

μ_{1}(a) = a,  μ_{2}(a) = a+a^{2},  μ_{3}(a) = a+3a+a^{3},  μ_{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 θ_{0} = 1, and for odd values of m ≥ 1 let

θ_{m} = ∑_{k=0}^{⌊m/2⌋} \binom{m}{k} ∑_{l=0}^{⌊m/2⌋−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}} [\begin{matrix}m − 2k − l \\ l \end{matrix}]_{q}q^{\binom{l}{2}},

while for even values of m ≥ 1 let

θ_{m} = ∑_{k=0}^{⌊m/2⌋−1} \binom{m}{k} ∑_{l=0}^{⌊m/2⌋−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}} [\begin{matrix}m − 2k − l \\ l \end{matrix}]_{q}q^{\binom{l}{2}}+\frac{1}{2^{m}} \binom{m}{m/2}.

Proposition 5. The n^{th}-moment of the q-Charlier polynomials C_{n}(x, a; q) is given by

μ_{n}(a) = u^{−n} ∑_{m=0}^{n} \binom{n}{m}(−v)^{n−m}θ_{m},

where

u = \frac{1}{2}\sqrt{\frac{1 − q}{a}} and v = −\frac{a(1 − q) + 1}{2\sqrt{a(1 − q)}}.

4. 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!_{q}a^{n}δ_{mn}.

In this section we state Anshelevich’s linearization result, which generalizes the orthogonality relation, in Theorem 6, and explicitly evaluate the coefficients in Corollary 8.

Set n = n_{1} + n_{2} + ⋯ n_{k}. Denote by

π_{n_{1},n_{2},...,n_{k}} ∈ Π_{n}

the partition whose blocks are intervals of consecutive integers of lengths n_{1}, n_{2}, …, n_{k}. Denote

Π(n_{1}, n_{2}, …, n_{k}) = {π ∈ Π_{n} : π has no singleton and π ∧ π_{n_{1},n_{2},...,n_{k}} = ˆ0},

the partitions without singleton and inhomogeneous with respect to π_{n_{1},n_{2},...,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 π = {1, 6, 10} − {2, 3, 9} − {4, 7} − {5, 8} ∈ Π(2, 4, 4).

In 2005 Anshelevich [2] considered the re-scaled version C_{n}(x + a, a; q) and proved the following

Theorem 6 (Anshelevich). The linearization coefficients of q-Charlier polynomials are the generating functions of the inhomogeneous partitions:

L_{q} (C_{n_{1}}(x, a; q) ⋯ C_{n_{k}}(x, a; q)) = ∑_{π∈Π(n_{1},n_{2},...,n_{k})} q^{rc(π)}a^{block(π)}.  (4.1)

For example, if k = 3 and n_{1} = n_{2} = 2 and n_{3} = 1, then

Π(2, 2, 1) = {{(1, 3, 5)(2, 4)}, {(1, 4, 5)(2, 3)}, {(2, 3, 5)(1, 4)}, {(2, 4, 5)(1, 3)}}.

It is easy to see that the corresponding generating function in (4.1) is

a^{2}q^{2} + a^{2} + a^{2}q + a^{2}q = a^{2}(1 + q)^{2}.

If k = 2, equation (4.1) gives the orthogonality relation. When k = 3, there is an explicit formula for the generating function in (4.1).

Theorem 7. We have

∑_{π∈Π(n_{1},n_{2},n_{3})} q^{rc(π)}t^{block(π)} = ∑_{l≥0} \frac{n_{1}!_{q}n_{2}!_{q}n_{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}} .

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}] \ [n_{1}] and N_{3} = [n_{1} + n_{2} + n_{3}] \ [n_{1} + n_{2}]. The type of a subset S of [n_{1} + n_{2} + n_{3}] is defined to be the triple (|S ∩ N_{1}|, |S ∩ N_{2}|, |S ∩ 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},  a + b + d = n_{2},  a + c + d = n_{3}.

Solving the equations and setting b = l we get

a = n_{1} + n_{2} − n_{3} − 2l, c = n_{3} − n_{2} + l, 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 7.

Given an inhomogeneous partition π 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^{a}B^{b}C^{c}. Similarly we may define words w_{2} and w_{3} of lengths n_{2} and n_{3} as multiset permutations of A^{a}B^{b}D^{d} and A^{a}C^{c}D^{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

\binom{n_{1}}{a, b, c}\binom{n_{2}}{a, b, d}\binom{n_{3}}{a, c, d}(a!)^{2}b!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)!},

inhomogeneous partitions.

We include q in the above argument by keeping track of the possible restricted crossings of π.

If π 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.

• any occurrence in w_{1} of B preceding C or A preceding C gives a crossing,

• any occurrence in w_{2} of D preceding B, D preceding A, or A preceding B gives a crossing,

• any occurrence in w_{3} of C preceding A or C preceding D gives a crossing. The remaining crossings are

• 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},

• 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},

• crossings amongst edges of the same type. Construct π 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 [1, p. 41]

[\begin{matrix}n_{2} \\ a, b, d \end{matrix}]_{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

[\begin{matrix}n_{1} \\ c \end{matrix}]_{q}.

Also choose the c positions in w_{3} for C, the C-inversions in w_{3} contribute

[\begin{matrix}n_{3} \\ c \end{matrix}]_{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. □

Corollary 8. We have the following linearization formula:

C_{n_{1}}(x, a; q)C_{n_{2}}(x, a; q) = ∑_{n_{3}} K_{n_{1}n_{2}n_{3}}C_{n_{3}}(x, a; q),  (4.2)

where

K_{n_{1}n_{2}n_{3}} = ∑_{l≥0} \frac{n_{1}!_{q}n_{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}} .

Corollary 8 may also be proven using the Askey-Wilson integral, see [9, p. 422].

5. A Combinatorial Proof of Theorem 6

In this section we prove Theorem 6, using the combinatorial interpretation of the polynomials given in Corollary 3 and the moments given in Theorem 4.

5.1. Generalized Charlier-permutations. We fix n = (n_{1}, …, n_{k}), where n_{i}’s are positive integers. Let n denote n_{1} + n_{2} + ⋯ + n_{k}. For 1 ≤ i ≤ k, let N_{i} denote the set of all integers j such that n_{1}+⋯+n_{i−1} < j ≤ n_{1}+⋯+n_{i}, n_{0} = 0. Then [n] = N_{1}∪⋯∪N_{k}. A generalized Charlier-permutation τ of type n is a sequence (τ_{k}, τ_{k−1}, …, τ_{1}) where τ_{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 n = (2, 4, 3):

(9 7)(8) | (6 5)(4 3) | (2)(1), (9 7)(8) | (6 5)(4 3) | [2](1), (9 7)(8) | (6 4)(5 3) | (2 1), (9 7)[8] | (6 4)(5 3) | (2 1), (9 8)[7] | (6 4)(5 3) | (2 1), (9 8)[7] | (6)(5 4)(3) | (2 1).

5.2. Charlier-partitions. Combining generalized Charlier-permutations and moments discussed in the previous sections, we want to interpret

L_{q} (C_{n_{1}}(x, a; q) … C_{n_{k}}(x, a; q))

as the weight generating function of some objects. The weight of any generalized Charlierpermutation 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 Charlier-partitions of n. A Charlier-partition is represented as (τ, ν), where τ = (τ_{k}, τ_{k−1}, …, τ_{1}) is a generalized Charlier-permutation and ν is a partition of cycles labeled −x in τ. We regard each 1-cycle with label a as a block by itself in ν. The weight of (τ, ν) is defined by

w(τ, ν) = q^{rc(ν)}a^{block(ν)} w(τ)|_{x=1} .

Then clearly we have the following identity:

L_{q} (C_{n_{1}}(x, a; q) ⋯ C_{n_{k}}(x, a; q)) = ∑_{(τ,ν)} w(τ, ν).  (5.1)

Given a Charlier-partition (τ, ν) of n with τ = (τ_{k}, τ_{k−1}, …, τ_{1}), we draw the corresponding diagram on the plane as follows:

• The n integers in τ are arranged on the horizontal axis in the order they appear in τ, one step apart.

• The 1-cycles with label a are framed with a box.

• The maximum in each cycle, except that in a box, is circled, so that we can recover the cycle structure and labels.

• If a cycle σ follows a cycle σ′ in a block of ν, then we draw an arc above the horizontal line between the last element of σ′ and the first element, that is also the maximum of σ, making as few crossings as possible. The smallest number of crossings agrees with the restricted crossings in ν, rc(ν).

• Draw a straight edge between two adjacent elements if and only if they are in the same cycle.

Example 2. Let n = (3, 5, 5). Then (τ, ν) is a Charlier-partition of n, where

τ = ((13 11)(12 9)(10), (8 4 6)[7](5), (3 1)(2))

is a generalized Charlier-permutation of type n and

ν = {{(13 11), (8 4 6), (3 1)}, {(12 9), (5), (2)}, {(10)}}

is a partition of cycles of τ with weight −x. The corresponding diagram can be illustrated as follows:

[figure: 13; 11; 12; 9; 10; 8; 4; 6; 7; 5; 3; 1; 2]

5.3. Involution. The weight function in Equation (5.1) has many cancelations. We will give a combinatorial weight-preserving sign-reversing involution ϕ with fixed set Π(n_{1}, n_{2}, …, n_{k}) defined on the set of all Charlier-partitions of type n.

Let (τ, ν) be a Charlier-partition of n. The involution ϕ will be defined depending on three different cases of (τ, ν).

Case 1. If (τ, ν) has a circled 1-cycle in a block by itself or a boxed 1-cycle, then define ϕ(τ, ν) 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, ϕ is weight-preserving sign-reversing in this case.

Case 2. We now assume that (τ, ν) has no 1-cycles, boxed or circled in a block by itself. Find the rightmost integer α, if it exists, in τ, say in τ_{i}, such that it has a neighbor β in τ_{i}, along the straight edge or an arc, to its right. Case 2.1. Assume that α and β are in the same cycle σ ending with α β, i.e. σ = (⋯ α β). Since α is the penultimate entry in σ, β is not the maximum in σ. Suppose the contribution of β to Cinv(τ_{i}) is j. Then τ_{i} is of the form

τ_{i} = (⋯) ⋯ (⋯ α β)(t_{m})(t_{m−1}) ⋯ (t_{j+2})(t_{j}) ⋯ (t_{1})

with t_{1} < t_{2} < ⋯ < t_{m} and t_{j+1} = β. Let τ′_{i} = (⋯) ⋯ (⋯ α)(t_{m})(t_{m−1}) ⋯ (t_{1}). Integers t_{m}, t_{m−1}, …, t_{j+2} are moved to the left by one step and β occupies the position of t_{j+2}. We make some changes on the diagram of (τ, ν) as follows, to obtain the diagram of the Charlier-partition (τ′, ν′):

Algorithm: Stretch • Initially, start with the diagram of (τ, ν) with all arcs and edges.

• Delete the straight edge between α and β in the diagram.

• Rearrange t_{m}, t_{m−1}, …, t_{1} in descending order, leaving the arcs and edges intact in their present positions.

• 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}.

• Add an arc between α and t_{m−j}.

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

The following are some examples with n = (3, 6, 2).

[figure: 11; 2; 10; 1; 9; 8; 0; 7; 6; 5; 4; 3; 2; 1; 11; 2; 10; 1; 9; 8; 0; 7; 6; 5; 4; 3; 2; 1; 11; 3; 10; 1; 9; 8; 0; 7; 6; 5; 2; 4; 3; 2; 1; 11; 3; 10; 1; 9; 8; 0; 7; 6; 2; 5; 4; 3; 2; 1; 11; 10; 1; 9; 8; 0; 7; 6; 5; 2; 4; 3; 3; 2; 1; 11; 10; 1; 9; 8; 0; 7; 6; 2; 5; 3; 4; 3; 2; 1]

Three sets of (τ, ν) and (τ′, ν′) of type n = (3, 6, 2) with α = 8.

Case 2.2. We now assume that α and β are in different cycles. Clearly β forms a 1-cycle and adjoins α by an arc. Moreover, all integers to the right of α in τ_{i} form 1-cycles and are in descending order. Suppose there are exactly j integers between α and β. Then τ_{i} is of the form τ_{i} = (⋯) ⋯ (⋯ α)(t_{m})(t_{m−1}) ⋯ (t_{1}) with t_{1} < t_{2} < ⋯ < t_{m} and t_{m−j} = β. Let τ′_{i} = (⋯) ⋯ (⋯ α t_{j+1})(t_{m})(t_{m−1}) ⋯ (t_{j+2})(t_{j}) ⋯ (t_{1}). Integers t_{m}, t_{m−1}, …, 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 (τ, ν) as follows, to obtain the diagram of the Charlier-partition (τ′, ν′):

Algorithm: Compress • Initially, start with the diagram of (τ, ν) with all arcs and edges.

• Delete the arc between α and β = t_{m−j} in the diagram.

• 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}.

• Rearrange t_{m}, t_{m−1}, …, t_{j+1} as t_{j+1}, t_{m}, t_{m−1}, …, t_{j+2}.

• Add a straight edge between α and t_{j+1}.

We let ϕ(τ, ν) = (τ′, ν′).

If (τ, ν) falls on Case 2.1 then (τ′, ν′) falls on Case 2.2 and vice versa. The algorithms Stretch and Compress are inverses to each other. If the roles of (τ, ν) and (τ′, ν′) are exchanged in the examples for algorithm Stretch, then they become examples of algorithm Compress.

Case 3. Assume that (τ, ν) does not fall in Cases 1 and 2. All the cycles in (τ, ν) are 1-cycles, every block in ν has at least two cycles, and each block of ν has at most one element in N_{i} for each i = 1, 2, …, k. So ν is a partition in Π(n_{1}, n_{2}, …, n_{k}). Let ϕ(τ, ν) = (τ, ν). The Charlier-partition (τ, ν) becomes a fixed point of ϕ.

Combining Cases 1, 2 and 3, the mapping ϕ is a weight-preserving sign-reversing involution on the set of all Charlier-partitions of type n with fixed set Π(n_{1}, n_{2}, …, n_{k}). This constitutes a combinatorial proof of Theorem 6.

6. A variation

Consider the polynomials Ĉ_{n}(x|q) defined by

Ĉ_{n+1}(x|q) = (x − b[n]_{q}) Ĉ_{n}(x|q) − a[n]_{q}Ĉ_{n−1}(x|q), n ≥ 0,  (6.1)

where Ĉ_{0}(x|q) = 1 and Ĉ_{−1}(x|q) = 0. Then (see [3, 11]) the polynomials Ĉ_{n}(x|q) are orthogonal with respect to the linear functional L̂_{q} defined by

L̂_{q}(x^{n}) = μ̂_{n} = ∑_{π∈Π′_{n}} q^{rc(π)}a^{block(π)}b^{n−2block(π)},

where Π′_{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 Ĉ_{n}(x|q) = b^{n}p_{n}(x/b). It follows from (2.2) that

Ĉ_{n}(x|q) = ∑_{k=0}^{n} [\begin{matrix}n \\ k \end{matrix}](−1)^{n−k}q^{k^{2}−kn} (\frac{a}{b})^{n−k} ∏_{i=0}^{k−1} (x + \frac{a}{b}q^{−i} − b[i]_{q}) .  (6.2)

The first values of these polynomials are

Ĉ_{1}(x|q) = x,
Ĉ_{2}(x|q) = x^{2} − bx − a,
Ĉ_{3}(x|q) = x^{3} − b(q + 2)x^{2} + (b^{2}(1 + q) − 2a − aq)x + ab(1 + q).

Since the linearization coefficients are invariant by translation of x, we have

\frac{L̂_{q}(∏_{i=1}^{k} Ĉ_{n_{i}}(x|q))}{L̂_{q}((Ĉ_{n_{k}}(x|q))^{2})} = \frac{L_{q}(∏_{i=1}^{k} C_{n_{i}}(x, a; q))}{L_{q}((C_{n_{k}}(x, a; q))^{2})}|_{a→a/b^{2}} · b^{n_{1}+n_{2}+···n_{k−1}−n_{k}}.  (6.3)

As L̂_{q}(Ĉ_{n_{k}}(x|q)Ĉ_{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 (6.3) and Theorem 6 the following

Theorem 9 (Anshelevich). The linearization coefficients of the polynomials Ĉ_{n}(x|q) are the generating functions of the inhomogeneous partitions:

L̂_{q} (Ĉ_{n_{1}}(x|q) ⋯ Ĉ_{n_{k}}(x|q)) = ∑_{π∈Π(n_{1},n_{2},...,n_{k})} q^{rc(π)}a^{block(π)}b^{n_{1}+···+n_{k}−2 block(π)}.

Anshelevich [2] 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

Corollary 10. We have the following linearization formula:

Ĉ_{n_{1}}(x|q) Ĉ_{n_{2}}(x|q) = ∑_{n_{3}} K̂_{n_{1}n_{2}n_{3}} Ĉ_{n_{3}}(x|q),  (6.4)

where

K̂_{n_{1}n_{2}n_{3}} = ∑_{l≥0} \frac{n_{1}!_{q}n_{2}!_{q} a^{l}b^{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}} .

When a = 1 and b = 0 the polynomials Ĉ_{n}(x|q) reduce to a family of q-Hermite polynomials H̃_{n}(x|q) (see [10, (2.11)]) and we get the corresponding combinatorial interpretation for the linearization coefficients of the q-Hermite polynomials in [10]:

L̂_{q} (H̃_{n_{1}}(x|q) ⋯ H̃_{n_{k}}(x|q)) = ∑_{π} q^{rc(π)},  (6.5)

where the summation is over all inhomogeneous 2-partitions π of [n_{1} + ⋯ + n_{k}], i.e., inhomogeneous partitions of which each block contains only two elements.

In particular, when a = 1 and b = 0, identity (6.4) reduces to

H̃_{n_{1}}(x|q) H̃_{n_{2}}(x|q) = ∑_{l=0}^{min(n_{1},n_{2})} [\begin{matrix}n_{1} \\ l \end{matrix}]_{q}[\begin{matrix}n_{2} \\ l \end{matrix}]_{q}l!_{q} H̃_{n_{1}+n_{2}−2l}(x|q).  (6.6)

7. Remarks

The q-Charlier polynomials in [6] 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.

References

[1] G. E. Andrews, The Theory of Partitions, Addison-Wesley, Reading, M.A., 1976.

[2] M. Anshelevich, Linearization coefficients for orthogonal polynomials using stochastic processes, The Annals of Probability, 2005, Vol. 33, No. 1, 114-136.

[3] Ph. Biane, Some properties of crossings and partitions, Discrete Math., 175 (1997), 41–53.

[4] T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach, 1978.

[5] A. de Médicis, Aspects combinatoires des nombres de Stirling, des polynômes orthogonaux de Sheffer et de leurs q-analogues, ISBN 2-89276-114-X, Vol. 13, Publications du LACIM, UQAM, Montréal, 1993.

[6] A. de Médicis, D. Stanton, D. White, The Combinatorics of q-Charlier Polynomials, J. Combin. Theory Ser. A 69, 1995, 87-114.

[7] 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.

[8] 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.

[9] M. Ismail, Classical and Quantum Orthogonal Polynomials in One Variable, Cambridge University Press, 2005.

[10] M. Ismail, D. Stanton and G. Viennot, The Combinatorics of q-Hermite polynomials and the Askey-Wilson integral, Europ. J. Combinatorics (1987) 8, 379-392.

[11] 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.

[12] R. Koekoek and R.F.Swarttouw, The Askey-scheme of hypergeometric orthogonal polynomials and its q-analogue Delft University of Technology, Report no. 98-17 (1998).

[13] R. Simion and D. Stanton, Octabasic Laguerre polynomials and permutation statistics, J. Comp. Appl. Math. 68 (1996), 297–329.

[14] J. Zeng, Linéarisation de produits de polynômes de Meixner, Krawtchouk, et Charlier, SIAM J. Math. Anal., Vol. 21, No. 5, pp. 1349–1368, 1990.

Department of Mathematics, KAIST, Daejeon 305-701, Korea

E-mail address: dskim@math.kaist.ac.kr

School of Mathematics, University of Minnesota, Minneapolis, MN 55455

E-mail address: stanton@math.umn.edu

Institut Camille Jordan, Université Claude Bernard (Lyon I), F-69622, Villeurbanne

E-mail address: zeng@math.univ-lyon1.fr