Séminaire Lotharingien de Combinatoire 48 (2002), Article B48b

ℙ-Species and the q-Mehler Formula

Hung Quang Ngo^{∗}

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.

1 Introduction

The Hermite polynomials are well-studied and have applications in diverse areas of Mathematics [2, 7]. 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 [17,20]. Foata [10] discovered a combinatorial proof of the Mehler formula, which was later extended to show the Kibble-Slepian formula combinatorially by Foata and Garcia [12].

A q-analogue of the Hermite polynomials, called the q-Hermite polynomials, was introduced by Rogers [19], who used them to prove Rogers-Ramanujan identities. Up to rescaling, there are other variants of the q-Hermite polynomials [1, 8, 9, 15]. 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., [4, 8, 15]), of which the one in [15] 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:

∗Computer Science and Engineering Department, 201 Bell Hall, State University of New York at Buffalo, Amherst, NY 14260, U.S.A. hungngo@cse.buffalo.edu

(a)_{n} = (a; q)_{n} := (1 − a)(1 − aq) … (1 − aq^{n−1})
[0]_{q} := 0
[n]_{q} := 1 + q + ⋯ + q^{n−1}, n ≥ 1
\left[{n \atop k}\right]_{q} := \frac{(q)_{n}}{(q)_{n−k}(q)_{k}} = \frac{(1 − q^{n}) … (1 − q^{n−k+1})}{(1 − q^{k}) … (1 − q)}, 0 ≤ k ≤ n.

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

2 Preliminaries

2.1 The Mehler formula and its extensions

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

H_{n}(x) := (−1)^{n}e^{x^{2}} \frac{d^{n}e^{−x^{2}}}{dx^{n}} ,  (1)

∑_{n=0}^{∞} H_{n}(x)\frac{r^{n}}{n!} = e^{2xr−r^{2}}.  (2)

To interpret the Hermite polynomials combinatorially, another variant of the Hermite polynomials, denoted by H̃_{n}(x), was introduced. The definition of the H̃_{n}(x), their generating function and its bilinear extension are as follows, respectively:

H̃_{n}(x) := \frac{H_{n}(x/\sqrt{2})}{2^{n/2}},  (3)
∑_{n=0}^{∞} H̃_{n}(x)\frac{t^{n}}{n!} = e^{xt−t^{2}/2},  (4)

∑_{n=0}^{∞} H̃_{n}(x)H̃_{n}(y)\frac{t^{n}}{n!} = \frac{1}{\sqrt{1 − t^{2}}} exp (\frac{2txy − t^{2}(x^{2} + y^{2})}{2(1 − t^{2})}) .  (5)

Identity (5) is the celebrated Mehler’s formula, which was shown combinatorially by Foata [10]. For a discussion of this proof and its relation to other combinatorial results on orthogonal polynomials, the reader is referred to Stanton [21].

Carlitz [5, 6] found several multilinear extensions. Kibble [17], and later independently Slepian [20] found an extension, known as the Kibble-Slepian formula, whose specializations include all other extensions. Louck [18] proposed another extension which was proved combinatorially to be equivalent to the Kibble-Slepian formula by Foata [11].

To describe the Kibble-Slepian formula, let us first introduce some notation. For each integer n ≥ 2, define a symmetric n × n matrix R by

(R)_{ij} = \begin{cases}r_{ij} & if i ≠ j, \\ 1 & otherwise, \end{cases}

where {r_{ij}}_{i,j≥1} is an infinite sequence of indeterminates. Let z = (z_{1}, …, z_{n})^{T} be a vector of n indeterminates. Let N be the set of all symmetric matrices N = (ν_{ij}) (1 ≤ i, j ≤ n) of order n such that ν_{ii} = 0 for all i ≤ n, and that ν_{ij} is a non-negative integer for all i ≠ j. Also, for a fixed N ∈ N, let the ith row sum of N be

s_{i} = ν_{i1} + ν_{i2} + ⋯ + ν_{in}.

The Kibble-Slepian formula reads

∑_{N∈N} H̃_{s_{1}}(z_{1}) … H̃_{s_{n}}(z_{n})\frac{∏_{i<j} r_{ij}^{ν_{ij}}}{∏_{i<j} ν_{ij}!} = \frac{1}{\sqrt{det R}} exp (\frac{1}{2}(z^{T} z − z^{T} R^{−1}z)) .  (6)

Foata and Garsia [12] extended Foata’s proof [10] of the Mehler formula to give a combinatorial proof of the Kibble-Slepian formula. The left hand side of (6) was interpreted as the exponential generating function of the so-called n-involutionary graphs, while the right hand side could be written as the exponential of the series

\frac{1}{2} ln \frac{1}{det R} + \frac{1}{2} ∑_{i,j}(δ_{ij} − (R^{−1})_{ij})z_{i}z_{j}.  (7)

They showed that expression (7) is the generating function for the “connected components” of the n-involutionary graphs. Consequently, the exponential formula applies, proving (6).

2.2 The q-Mehler formula and its extensions

A q-analogue of the Hermite polynomials called the q-Hermite polynomials, obtained from the so-called Rogers-Szegő polynomials [4, 9, 15, 19] can be defined by their generating function H(x, t | q) as follows:

H(x, t | q) := ∑_{n=0}^{∞} H_{n}(x | q)\frac{t^{n}}{(q)_{n}} = ∏_{k=0}^{∞} \frac{1}{(1 − 2xtq^{k} + t^{2}q^{2k})}, |t| < 1.  (8)

To get the corresponding q-version H̃_{n}(x | q) of H̃_{n}(x), we also normalize the H_{n}(x | q). Define

H̃_{n}(x | q) := \frac{H_{n}(\frac{x}{2} \sqrt{1 − q} | q)}{(1 − q)^{n/2}},  (9)

with the new three term recurrence:

H̃_{n+1}(x | q) = xH̃_{n}(x | q) − (1 + q + ⋯ + q^{n−1})H̃_{n−1}(x | q).  (10)

This recurrence relation yields a combinatorial interpretation for H̃_{n}(x | q) [15]. The interpretation gives H̃_{n}(x | q) as a q-analogue of the matching polynomials H̃_{n}(x). Notice that each matching α ∈ M_{n} can be viewed as an involution on [1, n]. Define a new statistic on α as follows:

s(α) := ∑_{e∈α} s(e),

where the sum goes over all edges e of α, and if e = (i, j), i < j, then

s(e) := |{k | i < k < j, and α(k) < j}| .

Pictorially, imagine putting n points 1, …, n in this order on a horizontal line, then drawing all edges of α 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′ ∈ α, both of whose end-points are on the left of j (see Figure 1). Let |α| denote the number of edges in the matching α, and let F (α) = n − 2|α| be the number of fixed points of α. It follows that

1  i  j  n k α(k) 1  i  j  n k  α(k) 1  i  j  n k  eee e′ e′

Figure 1: Illustration of s(e), where e = (i, j), i < j.

H̃_{n}(x | q) = ∑_{α∈M_{n}} w̃(α),  (11)

where

w̃(α) = (−1)^{|α|}x^{F (α)}q^{s(α)}.  (12)

On the same line of reasoning as in the previous section, one would hope that (11) 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 [4, 15]. In terms of H_{n}(x | q), it reads

∑_{n=0}^{∞} H_{n}(x | q)H_{n}(y | q)\frac{t^{n}}{(q)_{n}} =

\frac{(t^{2})_{∞}}{∏_{k=0}^{∞} (1 − 4tq^{k}xy + 2t^{2}q^{2k}(−1 + 2x^{2} + 2y^{2}) − 4t^{3}q^{3k}xy + t^{4}q^{4k})}. (13)

On the other hand, let h_{n}(x | q) be the generating function for the number of subspaces of 𝔽_{q}^{n}: h_{n}(x | q) = ∑_{k=0}^{n} \left[{n \atop k}\right]x^{k}, then

∑_{n=0}^{∞} h_{n}(x | q)h_{n}(y | q)\frac{t^{n}}{(q; q)_{n}} = \frac{(xyt^{2})_{∞}}{(t)_{∞}(xt)_{∞}(yt)_{∞}(xyt)_{∞}} .  (14)

It is this form of the q-Mehler formula which has the only known combinatorial proof [15] using the vector space interpretation. However, it does not seem to be possible to extend this proof along Foata and Garsia’s [12] 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 [13], 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 [16], and Ismail and Stanton [14]. 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.

2.3 A q-exponential formula

Gessel [13] 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:

Df(t) = \frac{f(t) − f(qt)}{(1 − q)t}.  (15)

Suppose f is a function with f(0) = 0 and q-exponential form

f(t) = ∑_{n=0}^{∞} f_{n} \frac{t^{n}}{n!_{q}} .  (16)

Let g = e[f] be the q-analogue of the function e^{f}, namely

g(t) = ∑_{n=0}^{∞} g_{n} \frac{t^{n}}{n!_{q}} ,  (17)

where the coefficients g_{n} are defined recursively by

g_{n+1} = \begin{cases}1 & if n = 0, \\ ∑_{k=0}^{n} \left[{n \atop k}\right]g_{n−k}f_{k+1} & if n ≥ 1. \end{cases}  (18)

Then, we can write g(t) as an infinite product:

g(t) = ∏_{n=0}^{∞} \frac{1}{(1 − (1 − q)q^{n}t · Df(q^{n}t))}.  (19)

3 Main Results

3.1 Main theorem and 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 H̄_{n}(x | q). The new variant is just a rescaling of the old H̃_{n}(x | q), and can also be defined combinatorially. The q-Mehler formula for the H̄_{n}(x | q) is then obtained by generalizing Gessel’s result summarized in Section 2.3.

Specifically, define

H̄_{n}(x | q) := i^{n}q^{\frac{n}{2}} H̃_{n} (\frac{−ix}{\sqrt{q}} | q) .  (20)

Then, these new q-Hermite polynomials can be combinatorially defined as follows.

Proposition 3.1. Let w̄ be a weight function on matchings defined by

w̄(α) := x^{F (α)}q^{|α|+s(α)}.  (21)

Then,

H̄_{n}(x | q) = ∑_{α∈M_{n}} w̄(α).  (22)

Proof. Recall the combinatorial interpretation (11) of the H̃_{n}(x | q), we get

H̄_{n}(x | q) = i^{n}q^{n/2}H̃_{n} (\frac{−ix}{\sqrt{q}} | q)

= i^{n}q^{\frac{n}{2}} ∑_{α∈M_{n}}(−1)^{|α|}q^{s(α)} (\frac{−ix}{\sqrt{q}})^{F (α)}
= ∑_{α∈M_{n}} (i^{n}(−1)^{|α|}(−i)^{F (α)}) x^{F (α)}q^{\frac{n}{2} − \frac{F (α)}{2} +s(α)}
= ∑_{α∈M_{n}} x^{F (α)}q^{|α|+s(α)}.

The following is the main theorem of the paper.

Theorem 3.2. The polynomials H̄_{n}(x | q) satisfy the following Mehler-type identity:

∑_{n=0}^{∞} H̄_{n}(x | q)H̄_{n}(y | q)\frac{t^{n}}{n!_{q}} =

\frac{(q^{2}t^{2})_{∞}}{∏_{k=0}^{∞} [(1 − t^{2}q^{2k+2})^{2} − t(1 − q)q^{k}((1 + t^{2}q^{2k+2})xy + tq^{k+1}(x^{2} + y^{2}))]}. (23)

Note that (23) is the same as (13) and (14), up to a change of variables.

Theorem 3.2 shall be shown in several steps. Notice that the right hand side of (23) looks similar to the right hand side of (19). 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 F of new species (Section 3.3) called ℙ-species (Section 3.2). Another ℙ-species G defined from F is enumerated by a sequence g_{n} which satisfes relation (18). The ℙ-species basically gives a combinatorial interpretation of relation (18). The last step is to bijectively show that g_{n} = H̄_{n}(x | q)H̄_{n}(y | q) (Section 3.4). The species 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 3.2 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.

3.2 Weighted ℙ-species

In this section, we generalize Theorem 5.2 in [13] by introducing a new kind of species [3], which then gives a combinatorial interpretation of identity (18).

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 β = i_{1} … i_{n} where {i_{1}, …, i_{n}} = N could be thought of as a permutation on N written in one line notation, i.e. β ∈ Sym(N). The set N is called the content of β, and is denoted by cont(β). For any σ ∈ Sym(N), we use I(σ) to denote the number of inversions in σ. 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) | i > j, i ∈ X, j ∈ Y }|.

Let 𝕂 ⊆ ℂ be an integral domain and 𝔸 = 𝕂[[q, t_{1}, t_{2}, …]] be a ring of formal power series or of polynomials over 𝕂 on the variables q, t_{1}, . . .. An 𝔸-weighted set is a pair (A, w) where A is a set and w : A → 𝔸 is a function associating a weight w(a) to each element a ∈ A. An 𝔸-weighted set (A, w) is said to be summable if for each monomial μ = q^{n_{0}}t_{1}^{n_{1}}t_{2}^{n_{2}} …, the number of elements a ∈ A whose weight w(a) contributes a non-zero coefficient to μ is finite. We are now ready to describe the new species.

Definition 3.3. An 𝔸-weighted ℙ-species is a rule F which

(i) to each totally ordered set N, and each permutation σ ∈ Sym(N), associates an 𝔸weighted set (F[N, σ], w),

(ii) to each increasing bijection γ : N_{1} ⟶ N_{2}, and each permutation σ ∈ S_{|N_{1}|} (= S_{|N_{2}|}), associates a weight-preserving bijection

F[γ, σ] : (F[N_{1}, σ_{1}], w) ⟶ (F[N_{2}, σ_{2}], w),

where σ_{1} ∈ Sym(N_{1}) and σ_{2} ∈ Sym(N_{2}) are derived from σ in the natural way.

Moreover, these functions F[γ, σ] must also satisfy the functorial properties:

F[Id_{N}, σ] = Id_{F[N,σ]},  (24)
F[β ∘ γ, σ] = F[β, σ] ∘ F[γ, σ].  (25)

Basically, the functorial properties say that the weighted sets (F[N, σ], w) depend only on the fact that N is totally ordered and on N’s cardinality. When |N| = n we shall use F[n, σ] to denote F[N, σ], and F[n] to denote ⋃_{σ∈S_{n}} F[n, σ].

Definition 3.4. Let F be an 𝔸-weighted ℙ-species with weight function w. The ℙ-generating series of F is the q-exponential formal power series F_{w}(t | q) with coefficients in 𝔸 defined by

F_{w}(t | q) := ∑_{n≥0} |F[n]|_{w} \frac{t^{n}}{n!_{q}} ,  (26)

where the q-inventory |F[n]|_{w} is defined by

|F[n]|_{w} := ∑_{σ∈S_{n}} ∑_{a∈F[n,σ]} w(a)q^{I(σ)}.  (27)

Theorem 5.2 of [13] 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.

Definition 3.5. Given σ ∈ S_{n}, a permutation partition π of σ is a sequence of non empty words π = (σ_{1}, …, σ_{k}) such that

σ = σ_{1}σ_{2} … σ_{k}

in one line notation, and that the largest elements of σ_{1}, …, σ_{k} form an increasing sequence. We shall write π ⊢ σ for “π is a permutation partition of σ.”

We are now ready to define a ℙ-species whose “connected components” are structures of another ℙ-species.

Definition 3.6. Let F_{v} be a weighted ℙ-species with weight function v. Define the ℙ-species G_{w} = E(F)_{w} with weight function w as follows. For each totally ordered set N and σ ∈ Sym(N), define

G[N, σ] := ⋃_{π⊢σ} F[N_{1}, σ_{1}] × ⋯ × F[N_{k}, σ_{k}],  (28)

where π = (σ_{1}, …, σ_{k}), and N_{i} = cont(σ_{i}), for all i = 1, …, k. Moreover, for each

G = (F_{1}, …, F_{k}) ∈ F[N_{1}, σ_{1}] × ⋯ × F[N_{k}, σ_{k}]

we associate

w(G) = v(F_{1}) … v(F_{k}).  (29)

This is the analogue of the multiplicative property in Theorem 5.2 of [13]. The fact that E(F)_{w} is a ℙ-species is easy to verify. At last, the promised generalization of Theorem 5.2 in [13] can now be stated:

Theorem 3.7. Let F_{v} be a ℙ-species of structures with weight function v. Let G_{w} be the ℙspecies E(F)_{w} defined as above. Define a sequence {g_{n}}_{n=0}^{∞} by g_{0} = 1 and

g_{n} = |G[n]|_{w}, n ≥ 1.

Let {f_{n}}_{n=0}^{∞} be the sequence defined by f_{0} = 0, and

f_{k+1} = |F[k + 1]|_{v}, for k ≥ 0.

Then,

1 + ∑_{n=1}^{∞} g_{n} \frac{t^{n}}{n!_{q}} = e [∑_{n=1}^{∞} f_{n} \frac{t^{n}}{n!_{q}} ] = ∏_{n=0}^{∞} \frac{1}{(1 − (1 − q)q^{n}t · DF_{v}(q^{n}t))}.  (30)

namely

G_{w}(t | q) = e[F_{v}(t | q)].  (31)

Proof. We only need to verify that the sequences g_{n} and f_{n} satisfy relation (18). Recall that each G ∈ G[n + 1] is a sequence of structures of F: G = (F_{1}, …, F_{m}). Let σ_{1}, …, σ_{m} be the corresponding permutations (or words) underlying F_{1}, …, F_{m}. Let N_{i} = cont(σ_{i}), for each i = 1, …, m. Notice that n + 1 ∈ N_{m}. Suppose |F_{m}| = k + 1, k ≥ 0. Let V := N_{m}, K := V − {n + 1}, and V̄ := [1, n + 1] − V. Note that I(V̄ , V) = I(V̄ , K) since n + 1 ∈ V. Furthermore, let G′ ∈ G[V̄] be the structure of species G obtained from G by removing F_{m}. For each structure C of a P-species, we use σ(C) to denote the underlying permutation of C.

It is clear that

I(σ(G)) = I(V̄ , K) + I(σ(G′)) + I(σ(F_{m})),

and that

w(G) = w(G′)v(F_{m}).

In order to form a G ∈ G[n + 1], we can first pick a k-subset K of [1, n] (0 ≤ k ≤ n), then form V = K ∪ {n + 1}, and finally concatenate any pair of G′ ∈ G[V̄] and F_{m} ∈ F[V]. Consequently,

g_{n+1} = ∑_{G∈G[n+1]} w(G)q^{I(σ(G))}

= ∑_{k=0}^{n} ∑_{K,|K|=k} ∑_{G′∈G[V̄]} ∑_{F_{m}∈F[V]} q^{I(V̄ ,K)} × w(G′)q^{I(σ(G′))} × v(F_{m})q^{I(σ(F_{m}))}

= ∑_{k=0}^{n} ∑_{K,|K|=k} ∑_{G′∈G_{n−k}} ∑_{F_{m}∈F_{k+1}} q^{I(V̄ ,K)} × w(G′)q^{I(σ(G′))} × v(F_{m})q^{I(σ(F_{m}))}

= ∑_{k=0}^{n} ( ∑_{K,|K|=k} q^{I([n]−K,K)}) ( ∑_{G′∈G_{n−k}} w(G′)q^{I(σ(G′))}) ( ∑_{F_{m}∈F_{k+1}} v(F_{m})q^{I(σ(F))})

= ∑_{k=0}^{n} \left[{n \atop k}\right]g_{n−k}f_{k+1}.

Example 3.8. Theorem 3.7 implies Theorem 5.2 in [13] and thus all its consequences as derived by Gessel.

Example 3.9. Take v ≡ 1 so that w ≡ 1 in Theorem 3.7, we obtain

1 + ∑_{n=1}^{∞} g_{n} \frac{t^{n}}{n!_{q}} = \frac{(t; q)_{∞}(tq; q)_{∞}}{∏_{n=0}^{∞}(1 − 2tq^{n} + t^{2}q^{2n+1})},  (32)

where,

g_{n} = ∑_{σ∈S_{n}} |{π | π ⊢ σ}|q^{I(σ)}.

In fact, when q → 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 → 1 the right hand side of (32) goes to exp(t/(1 − t)). Thus, we could have proven easily identity (32) combinatorially when q = 1.

Following Gessel’s line of derivation we can generalize the previous example as follows.

Corollary 3.10. Let π = (σ_{1}, …, σ_{k}) be any permutation partition of σ ∈ S_{n}. Let b_{i}(π) be the number of words of size i of π. Define a weight function w for π by w(π) = ∏_{i} x_{i}^{b_{i}(π)}, and let

g_{n} = ∑_{σ∈S_{n}} ∑_{π⊢σ} w(π)q^{I(σ)}.  (33)

Then,

G_{w}(t | q) = ∏_{n=0}^{∞} \frac{1}{(1 − (1 − q)q^{n}tX(q^{n}t))},  (34)

where

X(t) = ∑_{n=0}^{∞} x_{n+1}[n + 1]_{q}t^{n}.

Example 3.11. Write π ⊢_{k} σ if π ⊢ σ and all words of π are of size at most k. Set X(t) = x + (1 + q)t, so that

w(π) = \begin{cases}x^{b_{1}(π)} & if π ⊢_{2} σ \\ 0 & otherwise, \end{cases}

and hence

g_{n}(x | q) = ∑_{σ∈S_{n}} ∑_{π⊢_{2}σ} x^{b_{1}(π)}q^{I(σ)}.

Corollary 3.10 gives

G_{w}(x, t | q) = ∑_{n=0}^{∞} g_{n}(x | q)\frac{t^{n}}{n!_{q}} = ∏_{n=0}^{∞} \frac{1}{1 − (1 − q)q^{n}tX(q^{n}t)}

= ∏_{k=0}^{∞} \frac{1}{1 − 2uzq^{k} + z^{2}q^{2k}} ,  (35)

where u = \frac{−it}{2} \sqrt{\frac{1−q}{1+q}} and z = it\sqrt{1 − q^{2}}. We now get

g_{n}(x | q) = i^{n}(1 + q)^{n/2}H̃_{n} ( \frac{−ix}{\sqrt{1 + q}} | q) .  (36)

Thus,

∑_{σ∈S_{n}} ∑_{π⊢_{2}σ} x^{b_{1}(π)}q^{I(σ)} = ∑_{α∈M_{n}}(1 + q)^{|α|}q^{s(α)}x^{F (α)},  (37)

an interesting combinatorial identity.

3.3 A q-analogue of the bicolored n-involutionary graphs

The previous section gives a combinatorial view of identity (18). As outlined at the end of section 3.1, the next step in the proof of Theorem 3.2 is to find a ℙ-species F_{v} whose ℙ-generating series f(t) = F_{v}(t | q) is such that the right hand side of (19) is the same as that of (23). The ℙ-species G_{w} = E(F)_{w} is a q-analogue of the bicolored n-involutionary graphs. We actually will start defining G first.

Definition 3.12. A graph G = (N, E) is called an ordered bicolored n-involutionary graph if G satisfies the following conditions:

1. G has n vertices labeled by n distinct positive integers in N.

2. G has no multiple edges, but can have loops.

3. 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 π(G) = π_{1}π_{2} … π_{n} ∈ Sym(N).

4. Each edge of G is colored either red or blue.

5. Each vertex of G is incident to exactly 2 edges of different colors.

6. A non-loop edge of G can only connect some π_{i} to π_{i+1} unless it completes a cycle of G.

7. Let C_{1}, …, 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 π(G) must satisfy the condition that L(C_{1}) < ⋯ < L(C_{m}).

8. For each connected component C, the vertex numbered L(C) has to be on the left of the blue edge incident to it.

9. 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 2. In the figure, the bold lines represent blue edges and the thin lines represent red edges.

x  y  Blue Red L(C) y  y L(C) L(C)  y  x x x  L(C) L(C)

Figure 2: Possible connected component types of an ordered bicolored n-involutionary graph.

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

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

Definition 3.13. A weight function w defined on G_{N} with values over some commutative algebra over the rationals is said to be multiplicative if it satisfies the following conditions:

(i) w(G) = w(red(G)).

(ii) If γ_{1}, …, γ_{k} are the connected components of G (which are ordered bicolored involutionary graphs themselves), then w(G) = w(γ_{1}) … w(γ_{k}).

The following theorem is obviously a very special case of Theorem 3.7 applied to the ordered bicolored involutionary graphs.

Theorem 3.14. Supposed w is a multiplicative function on G_{n}. For n ≥ 0, define a sequence {g_{n}}_{n=0}^{∞}

g_{n} = ∑_{G∈G_{n}} w(G)q^{I(π(G))}.

Let {f_{n}}_{n=0}^{∞} be the sequence defined by f_{0} = 0, and

f_{k+1} = ∑_{C∈C_{k+1}} w(C)q^{I(π(C))}

for k ≥ 0. Then,

∑_{n=0}^{∞} g_{n} \frac{t^{n}}{n!_{q}} = e [∑_{n=1}^{∞} f_{n} \frac{t^{n}}{n!_{q}} ] .

Definition 3.15. Let G be a graph in 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 θ on each edge e of G as follows:

θ(e) = \begin{cases}q & if e is a non-loop red edge, \\ q & if e is non-loop, blue and to the left of L(C(e)), \\ 1 & if e is non-loop, blue and to the right of L(C(e)), \\ y & if e is a red loop, \\ x & if e is a blue loop. \end{cases}

Let θ be a weight function defined on G_{N} by:

θ(G) = ∏_{e∈E(G)} θ(e),

then obviously θ is multiplicative.

We call an ordered bicolored n-involutionary graphs with the weight θ associated a bicolored (q, n)-involutionary graph. Figure 3 shows an example of such a graph. In the figure, the largest

3  ^{1}  ^{10} ^{8}^{9}  ^{7}^{5}  ^{4}  ^{12}  ^{11}  ^{15}^{13}  ^{2}^{x} ^{q}  ^{1} ^{q}  ^{q}^{1} ^{q}  ^{1}  ^{6}  ^{14}^{y}^{x}  ^{y}  ^{x}  ^{y}^{q}  ^{q}  ^{1}  ^{q}  ^{1}^{π = (3, 9, 5, 1, 10, 8, 4, 7, 6, 12, 14, 11, 13, 15, 2)}  ^{I(π) = 33} θ(G)q^{I(π)} = q^{7}x^{3}y^{3} × q^{33}

Figure 3: An example of a bicolored (q, n)-involutionary graph.

vertex number L(C) in each component C has been put in bold face.

Lemma 3.16. Let θ be the function defined above, and {f_{n}}_{n=0}^{∞} be a sequence defined by f_{0} = 0 and

f_{n} = ∑_{C∈C_{n}} θ(C)q^{I(π(C))}, when n ≥ 1.

Moreover, let

f(t | q) := ∑_{n=0}^{∞} f_{n} \frac{t^{n}}{n!_{q}} .

Then,

Df(t | q) = \frac{(1 − t^{2}q^{2})tq^{2} + (1 + t^{2}q^{2})xy + tq(x^{2} + y^{2})}{(1 − t^{2}q^{2})(1 − t^{2}q^{3})}.  (38)

Proof. Firstly, we claim that

f_{2k+1} = ([k] + [k + 1])q^{2k}(2k)!_{q}xy.

To see this, let us consider Figure 2. The components in C_{2k+1} can only be the paths which start and end with different colored loops, and have largest vertex number 2k + 1. Summing θ(C)q^{I(π(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,

f(t | q) = ∑_{n=0}^{∞} f_{n} \frac{t^{n}}{n!_{q}}

= ∑_{k=0}^{∞}([k] + [k + 1])q^{2k}(2k)!_{q}xy \frac{t^{2k+1}}{(2k + 1)!_{q}}

+ ∑_{k=0}^{∞} (q^{3k+2}(2k + 1)!_{q} + [k + 1]q^{2k+1}(2k + 1)!_{q}(x^{2} + y^{2})) \frac{t^{2k+2}}{(2k + 2)!_{q}} .

Hence,

Df(t | q) = ∑_{k=0}^{∞}([k] + [k + 1])q^{2k}xyt^{2k} + ∑_{k=0}^{∞} q^{3k+2}t^{2k+1}

+ ∑_{k=0}^{∞}[k + 1]q^{2k+1}(x^{2} + y^{2})t^{2k+1}. (39)

Now, we calculate each term of (39) separately as follows:

\begin{aligned}xy ∑_{k=0}^{∞}([k] + [k + 1])q^{2k}t^{2k} & = xy(1 + t^{2}q^{2}) ∑_{k=0}^{∞}[k + 1]q^{2k}t^{2k} \\ & = xy(1 + t^{2}q^{2}) ∑_{k=0}^{∞} (∑_{j=0}^{k} q^{2(k−j)+3j}) t^{2k} \\ & = xy(1 + t^{2}q^{2}) ∑_{i=0}^{∞} t^{2i}q^{2i} ∑_{j=0}^{∞} t^{2j}q^{3j} \\ & = \frac{(1 + t^{2}q^{2})xy}{(1 − t^{2}q^{2})(1 − t^{2}q^{3})}. \end{aligned}  (40)

Similarly,

∑_{k=0}^{∞} q^{3k+2}t^{2k+1} = \frac{tq^{2}}{1 − t^{2}q^{3}} ,  (41)

and

\begin{aligned}(x^{2} + y^{2}) ∑_{k=0}^{∞}[k + 1]q^{2k+1}t^{2k+1} & = (x^{2} + y^{2})tq ∑_{k=0}^{∞} (∑_{j=0}^{k} q^{2k+j}) t^{2k} \\ & = (x^{2} + y^{2})tq ∑_{k=0}^{∞} (∑_{j=0}^{k} q^{2(k−j)+3j}) t^{2(k−j)+2j} \\ & = (x^{2} + y^{2})tq ∑_{i=0}^{∞} t^{2i}q^{2i} ∑_{j=0}^{∞} t^{2j}q^{3j} \\ & = \frac{tq(x^{2} + y^{2})}{(1 − t^{2}q^{2})(1 − t^{2}q^{3})}. \end{aligned} (42)

Combining (40), (41) and (42) yields (38).

Corollary 3.17. Let θ be the function defined above, and {g_{n}}_{n=0}^{∞} be a sequence defined by

g_{n} = ∑_{G∈G_{n}} θ(G)q^{I(π(G))}.  (43)

Then,

g(t | q) = \frac{(q^{2}t^{2})_{∞}}{∏_{k=0}^{∞} [(1 − t^{2}q^{2k+2})^{2} − t(1 − q)q^{k}((1 + t^{2}q^{2k+2})xy + tq^{k+1}(x^{2} + y^{2}))]},

where

g(t | q) = ∑_{n=0}^{∞} g_{n} \frac{t^{n}}{n!_{q}} .

Proof. This is straightforward from Theorem 3.14, Lemma 3.16 and equation (19).

3.4 A bijection

This section completes the last step of the proof of Theorem 3.2. We are left to demonstrate that H̄_{n}(x | q)H̄_{n}(y | q) = g_{n}. We shall show this relation combinatorially as formally put in the following theorem.

Theorem 3.18. Let H̄_{n} be defined combinatorially by equation (22), and g_{n} by equation (43). Then,

H̄_{n}(x | q)H̄_{n}(y | q) = g_{n}.

Proof. We want to find a weight-preserving bijection φ which maps a pair (α, α′) ∈ M_{n+1} × M_{n+1} to a graph G ∈ G_{n+1}. Let (α, α′) be a pair of matchings in M_{n+1} ×M_{n+1}, where the fixed points of α are weighted by x and of α′ by y. As before, we view the vertices 1, …, n + 1 of α and α′ 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}, …, p_{a} (a ≤ n + 1) be the sequence of vertices of α starting from the right which are not left end-points of α’s edges. Similarly, let p′_{1}, …, p′_{a′} be the corresponding sequence for α′. Notice that p_{1} = p′_{1} = n + 1. Let e_{1}, …, e_{|α|} (respectively e′_{1}, …, e′_{|α′|}) be the set of edges of α (respectively α′) 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 α and α′ seen so far. Then, remove certain points and edges from α and α′ to get β and β′ 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.

1. At some k + 1, all of p_{i} and p′_{i}, 1 ≤ i ≤ k + 1, are right end-points of edges in α and α′ respectively, and j = k + 1 is the least integer such that s(e_{j}) = 0.

2. We meet a fixed point p_{m+1} of α and then a fixed point p_{k+1} of α′ where m ≤ k. For this case to be disjoint from case 1, it is necessary that all edges e of α whose right end-points are on the right of p_{m+1} have s(e) > 0.

3. We meet a fixed point p′_{m+1} of α′ strictly before a fixed point p_{k+1} of α.

4. Two fixed points of α are met before any fixed points of α′.

5. Two fixed points of α′ are met before any fixed points of α.

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.

Case 1. There exists a k, 0 ≤ k ≤ \frac{(n−1)}{2}, such that

(i) j = k + 1 is the smallest integer where s(e_{j}) = 0. (i.e. s(e_{j}) > 0 for all j ≤ k.)

(ii) For all j = 1, …, k + 1, e_{j} has right end-point p_{j} and e′_{j} has right end-point p′_{j}.

The situation is depicted in Figure 4. Let β (respectively β′) be the matching obtained

n + 1  i_{1} i_{2} i_{2k+1}i_{2k} e_{1} e′_{1} e_{k} e_{k+1} e′_{k+1} e′_{k}  φ p_{1} p_{k} p_{k+1}  p′_{1} p′_{k+1} p′_{k}  0 ≤ k ≤ \frac{n−1}{2}

Figure 4: Illustration of case 1.

by removing e_{1}, …, e_{k+1} and their end-points (respectively e′_{1}, …, e′_{k+1} and their endpoints) from α (respectively α′). We shall construct G = φ(α, α′) such that the last connected component of G is a cycle C = (n + 1, i_{2k+1}, …, i_{1}), and that φ(β, β′) forms the rest of the components of G. Let R = {i_{2k+1}, …, 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 σ = i_{2k+1} … i_{1} ∈ Sym(R), where R = {i_{2k+1}, …, 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}, …, e_{k+1} to the weight of α plus the contribution w′_{E} of e′_{1}, …, e′_{k+1} to the weight of α′. 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 α and α′. Let U = [1, n] − R, and I(U, R) be the number of inversions created by pairs of numbers in U × R, namely the number of pairs (u, r) ∈ U × 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

w_{C} = q^{I(U,R)+I(σ)+2k+1} · q^{k+1},  (44)
w_{E} = q^{k+1} · q^{∑_{j=1}^{k+1} s(e_{j})},  (45)
w′_{E} = q^{k+1} · q^{∑_{j=1}^{k+1} s(e′_{j})}.  (46)

Hence, we need to pick σ such that

I(U, R) + I(σ) = ∑_{j=1}^{k+1} s(e_{j}) + ∑_{j=1}^{k+1} s(e′_{j}) − k.  (47)

Observe that

s(e_{k+1}) = 0,  (48)
1 ≤ s(e_{j}) ≤ n + 1 − 2j, ∀j = 1, …, k,  (49)
0 ≤ s(e′_{j}) ≤ n + 1 − 2j, ∀j = 1, …, k + 1.  (50)

Now, define a function f on {1, …, 2k + 1} by

f(t) = \begin{cases}n − t + 2 − s(e_{j}) & if t = 2j, j = 1, …, k, \\ n − t + 1 − s(e′_{j}) & if t = 2j − 1, j = 1, …, k + 1. \end{cases}

Then, recursively determine i_{1}, …, i_{2k+1}, element by element starting from i_{1}, working toward i_{2k+1} as follows:

i_{t} = the f(t)th smallest number in [1, n] − {i_{1}, …, i_{t−1}}.  (51)

It is easy to check that 1 ≤ f(t) ≤ n − (t − 1) for all t = 1, …, 2k + 1 so that i_{t} is well defined. Moreover,

I(U, R) + I(σ) = ∑_{t=1}^{2k+1} |{j | j preceeds i_{t}, j > i_{t}, j ≠ n + 1}|

= ∑_{t=1}^{2k+1}(n − (t − 1) − f(t))

= ∑_{j=1}^{k}(n − (2j − 1) − f(2j)) + ∑_{j=1}^{k+1}(n − (2j − 2) − f(2j − 1))

= ∑_{j=1}^{k+1} s(e_{j}) + ∑_{j=1}^{k+1} s(e′_{j}) − k,

which is exactly (47).

Case 2. There exists a k, 0 ≤ k ≤ \frac{n}{2}, and an m, 0 ≤ m ≤ k such that (i) For all j = 1, …, 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, …, k + 1, p_{j} is the right end-point of e_{j−1}.

(ii) For all j = 1, …, k, p′_{j} is the right end-point of e′_{j}. And, p′_{k+1} is a fixed point weighted by y.

The situation is depicted in Figure 5. This time, the last component C of G starts with

x i_{1} i_{2} i_{2m} n + 1 i_{2m+1} yi_{2k} e′_{1} e_{1} e_{m} e_{m+1} e_{k} e′_{k}  e′_{m+1} e′_{m} x y  0 ≤ k ≤ \frac{n}{2} , 0 ≤ m ≤ k φ

Figure 5: Illustration of case 2.

a red loop and ends with a blue loop. The point n + 1 is the (2m + 1)st point from the right. Let σ, R, U be defined as in the previous case, then the corresponding w_{C}, w_{E} and w′_{E} are as follows:

w_{C} = q^{I(U,R)+I(σ)+2m} · q^{2k−m} · xy,  (52)
w_{E} = q^{k} · q^{∑_{j=1}^{k} s(e_{j})} · x,  (53)
w′_{E} = q^{k} · q^{∑_{j=1}^{k} s(e′_{j})} · y.  (54)

Hence, we need to pick σ so that

I(U, R) + I(σ) = ∑_{j=1}^{k} s(e_{j}) + ∑_{j=1}^{k} s(e′_{j}) − m.  (55)

For t = 1, …, 2k, the corresponding f(t) is:

f(t) = \begin{cases}n − t + 2 − s(e_{j}) & if t = 2j, j = 1, …, m, \\ n − t + 1 − s(e_{j}) & if t = 2j, j = m + 1, …, k, \\ n − t + 1 − s(e′_{j}) & if t = 2j − 1, j = 1, …, k. \end{cases}  (56)

As in the previous case, i_{t} is defined by (51). To show that i_{t} is well defined and that they satisfy (55), we only need to observe that

1 ≤ s(e_{j}) ≤ n + 1 − 2j, j = 1, …, m,  (57)
0 ≤ s(e_{j}) ≤ n + 1 − (2j + 1), j = m + 1, …, k,  (58)
0 ≤ s(e′_{j}) ≤ n + 1 − 2j, j = 1, …, k.  (59)

Case 3. There exists a k, 1 ≤ k ≤ \frac{n}{2}, and an m, 0 ≤ m ≤ k − 1, such that

(i) For all j = 1, …, k, p_{j} is the right end-point of e_{j}, and p_{k+1} is a fixed point weighted x.

(ii) For all j = 1, …, m, s(e_{j}) > 0.

e_{1} e_{k}  e_{m+1} e_{m} x  e′_{1} e′_{m} e′_{m+1} e′_{k}  y  1 ≤ k ≤ ^{\frac{n}{2}} , 0 ≤ m ≤ k − 1 φ  y i_{1} i_{2} n + 1 xi_{2k}  i_{2m+1} i_{2m+2}

Figure 6: Illustration of case 3.

(iii) For all j = 1, …, 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, …, k + 1 p_{j} is the right end-point of e′_{j−1}. The situation is depicted in Figure 6. In this case, we have

w_{C} = q^{I(U,R)+I(σ)+2m+1} · q^{2k−(m+1)} · xy,  (60)
w_{E} = q^{k} · q^{∑_{j=1}^{k} s(e_{j})} · x,  (61)
w′_{E} = q^{k} · q^{∑_{j=1}^{k} s(e′_{j})} · y.  (62)

Hence, we need to pick σ so that

I(U, R) + I(σ) = ∑_{j=1}^{k} s(e_{j}) + ∑_{j=1}^{k} s(e′_{j}) − m.  (63)

For t = 1, …, 2k, the corresponding f(t) is:

f(t) = \begin{cases}n − t + 2 − s(e_{j}) & if t = 2j, j = 1, …, m, \\ n − t + 1 − s(e′_{j}) & if t = 2j, j = m + 1, …, k, \\ n − t + 1 − s(e′_{j}) & if t = 2j − 1, j = 1, …, m, \\ n − t + 1 − s(e_{j}) & if t = 2j − 1, j = m + 1, …, k. \end{cases}  (64)

As in the previous case, i_{t} is defined by (51). To show that i_{t} is well defined and that they satisfy (63), we only need to observe that

1 ≤ s(e_{j}) ≤ n + 1 − 2j, j = 1, …, m,  (65)
0 ≤ s(e_{j}) ≤ n + 1 − 2j, j = m + 1, …, k,  (66)
0 ≤ s(e′_{j}) ≤ n + 1 − 2j, j = 1, …, m,  (67)
0 ≤ s(e′_{j}) ≤ n + 1 − (2j + 1), j = m + 1, …, k.  (68)

Case 4. There exists a k, 0 ≤ k ≤ \frac{(n−1)}{2}, and an m, 0 ≤ m ≤ k, such that

(i) For all j = 1, …, 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, …, k + 1, p_{j} is the right end-point of e_{j−1}.

(ii) For all j = 1, …, k + 1, p′_{j} is the right end-point of e′_{j}. The situation is depicted in Figure 7. In this case, we have

w_{C} = q^{I(U,R)+I(σ)+2m} · q^{2k+1−m} · x^{2},  (69)
w_{E} = q^{k} · q^{∑_{j=1}^{k} s(e_{j})} · x^{2},  (70)
w′_{E} = q^{k+1} · q^{∑_{j=1}^{k+1} s(e′_{j})}.  (71)

e_{1} e_{m} e_{m+1} e_{k}  e′_{1} e′_{k+1}  x x  x  x i_{1} i_{2k} i_{2k+1}  n + 1  i_{2} i_{2m} 0 ≤ k ≤ \frac{n−1}{2} , 0 ≤ m ≤ k φ

Figure 7: Illustration of case 4.

Hence, we need to pick σ so that

I(U, R) + I(σ) = ∑_{j=1}^{k} s(e_{j}) + ∑_{j=1}^{k+1} s(e′_{j}) − m.  (72)

For t = 1, …, 2k + 1, the corresponding f(t) is:

f(t) = \begin{cases}n − t + 2 − s(e_{j}) & if t = 2j, j = 1, …, m, \\ n − t + 1 − s(e_{j}) & if t = 2j, j = m + 1, …, k, \\ n − t + 1 − s(e′_{j}) & if t = 2j − 1, j = 1, …, k + 1. \end{cases}  (73)

As in the previous case, i_{t} is defined by (51). To show that i_{t} is well defined and that they satisfy (72), we only need to observe that

1 ≤ s(e_{j}) ≤ n + 1 − 2j, j = 1, …, m,  (74)
0 ≤ s(e_{j}) ≤ n + 1 − (2j + 1), j = m + 1, …, k,  (75)
0 ≤ s(e′_{j}) ≤ n + 1 − 2j, j = 1, …, k + 1.  (76)

Case 5. There exists a k, 0 ≤ k ≤ \frac{(n−1)}{2}, and an m, 0 ≤ m ≤ k, such that

(i) For all j = 1, …, 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, …, k + 1, p′_{j} is the right end-point of e′_{j−1}.

(ii) For all j = 1, …, k + 1, p_{j} is the right end-point of e_{j}. (iii) For all j = 1, …, m, s(e_{j}) > 0.

The situation is depicted in Figure 8. In this case, we have

y y  e_{1} e_{k+1}  e′_{1} e′_{m} e′_{m+1} e′_{k}  y  y i_{1} i_{2k} i_{2k+1}  n + 1 0 ≤ k ≤ ^{\frac{n−1}{2}} , 0 ≤ m ≤ k φ  i_{2m+1}

Figure 8: Illustration of case 5.

w_{C} = q^{I(U,R)+I(σ)+2m+1} · q^{2k+1−(m+1)} · y^{2},  (77)
w_{E} = q^{k+1} · q^{∑_{j=1}^{k+1} s(e_{j})},  (78)
w′_{E} = q^{k} · q^{∑_{j=1}^{k} s(e′_{j})} · y^{2}.  (79)

Hence, we need to pick σ so that

I(U, R) + I(σ) = ∑_{j=1}^{k+1} s(e_{j}) + ∑_{j=1}^{k} s(e′_{j}) − m.  (80)

For t = 1, …, 2k + 1, the corresponding f(t) is:

f(t) = \begin{cases}n − t + 2 − s(e_{j}) & if t = 2j, j = 1, …, m, \\ n − t + 1 − s(e′_{j}) & if t = 2j, j = m + 1, …, k, \\ n − t + 1 − s(e′_{j}) & if t = 2j − 1, j = 1, …, m, \\ n − t + 1 − s(e_{j}) & if t = 2j − 1, j = m + 1, …, k + 1. \end{cases}  (81)

As in the previous case, i_{t} is defined by (51). To show that i_{t} is well defined and that they satisfy (80), we only need to observe that

1 ≤ s(e_{j}) ≤ n + 1 − 2j, j = 1, …, m,  (82)
0 ≤ s(e_{j}) ≤ n + 1 − 2j, j = m + 1, …, k + 1,  (83)
0 ≤ s(e′_{j}) ≤ n + 1 − 2j, j = 1, …, m,  (84)
0 ≤ s(e′_{j}) ≤ n + 1 − (2j + 1), j = m + 1, …, k.  (85)

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épartement de mathématique, Université Louis Pasteur, France, for various detailed comments which have greatly improved the presentation of this paper.

References

[1] W. A. Al-Salam and L. Carlitz, Some orthogonal q-polynomials, Math. Nachr., 30 (1965), pp. 47–61.

[2] G. E. Andrews, R. Askey, and R. Roy, Special functions, Cambridge University Press, Cambridge, 1999.

[3] F. Bergeron, G. Labelle, and P. Leroux, Combinatorial species and tree-like structures, Cambridge University Press, Cambridge, 1998. Translated from the 1994 French original by Margaret Readdy, with a foreword by Gian-Carlo Rota.

[4] D. M. Bressoud, A simple proof of Mehler’s formula for q-Hermite polynomials, Indiana Univ. Math. J., 29 (1980), pp. 577–580.

[5] L. Carlitz, An extension of Mehler’s formula, Boll. Un. Mat. Ital. (4), 3 (1970), pp. 43– 46.

[6] L. Carlitz, Some extensions of the Mehler formula, Collect. Math., 21 (1970), pp. 117– 130.

[7] T. S. Chihara, An introduction to orthogonal polynomials, Gordon and Breach Science Publishers, New York, 1978. Mathematics and its Applications, Vol. 13.

[8] J. Cigler, Elementare q-Identitäten, Sém. Lothar. Combin., 5 (1981), Art. B05a, 29 pp. (electronic).

[9] J. Désarménien, Les q-analogues des polynômes d’Hermite, Sém. Lothar. Combin., 6 (1982), Art. B06b, 12 pp. (electronic).

[10] D. Foata, A combinatorial proof of the Mehler formula, J. Combinatorial Theory Ser. A, 24 (1978), pp. 367–376.

[11] , Some Hermite polynomial identities and their combinatorics, Adv. in Appl. Math., 2 (1981), pp. 250–259.

[12] D. Foata and A. M. Garsia, A combinatorial approach to the Mehler formulas for Hermite 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.

[13] I. M. Gessel, A q-analog of the exponential formula, Discrete Math., 40 (1982), pp. 69– 80.

[14] M. E. H. Ismail and D. Stanton, On the Askey-Wilson and Rogers polynomials, Canad. J. Math., 40 (1988), pp. 1025–1045.

[15] M. E. H. Ismail, D. Stanton, and G. Viennot, The combinatorics of q-Hermite polynomials and the Askey-Wilson integral, European J. Combin., 8 (1987), pp. 379–392.

[16] B. K. Karande and N. K. Thakare, On certain q-orthogonal polynomials, Indian J. Pure Appl. Math., 7 (1976), pp. 728–736.

[17] W. F. Kibble, An extension of a theorem of Mehler’s on Hermite polynomials, Proc. Cambridge Philos. Soc., 41 (1945), pp. 12–15.

[18] J. D. Louck, Extension of the Kibble-Slepian formula for Hermite polynomials using boson operator methods, Adv. in Appl. Math., 2 (1981), pp. 239–249.

[19] L. J. Rogers, On a three-fold symmetry in the elements of Heine’s series, Proc. London Math. Soc., 24 (1893), pp. 337–352.

[20] D. Slepian, On the symmetrized Kronecker power of a matrix and extensions of Mehler’s formula for Hermite polynomials, SIAM J. Math. Anal., 3 (1972), pp. 606–616.

[21] D. Stanton, Orthogonal polynomials and combinatorics, in Special Functions 2000: Current Perspective and future directions, Kluwer, 2000, pp. 389–410.