Séminaire Lotharingien de Combinatoire 81 (2020), Article B81e

COMBINATORICS OF (q, y)-LAGUERRE POLYNOMIALS AND THEIR MOMENTS

QIONGQIONG PAN AND JIANG ZENG

To Christian Krattenthaler on the occasion of his 60th birthday

Abstract. We consider a (q, y)-analogue of Laguerre polynomials L_{n}^{(α)}(x; y | q) for integral α ≥ −1, which turns out to be a rescaled version of Al-Salam–Chihara polynomials. A combinatorial interpretation for the (q, y)-Laguerre polynomials is given using a colored version of Foata and Strehl’s Laguerre configurations with suitable statistics. When α ≥ 0, the corresponding moments are described using certain classical statistics on permutations, and the linearization coefficients are proved to be a polynomial in y and q with nonnegative integral coefficients.

1. Introduction

The monic Laguerre polynomials L_{n}^{(α)}(x) are defined by the generating function

(1 + t)^{−α−1} exp (\frac{xt}{t + 1}) = ∑_{n=0}^{∞} L_{n}^{(α)}(x)\frac{t^{n}}{n!}.  (1.1)

They are the multiple of the usual (general) Laguerre polynomials [16, pp. 241–242] by (−1)^{n}n!. We have the explicit formula

L_{n}^{(α)}(x) = ∑_{k=0}^{n}(−1)^{n−k} \frac{n!}{k!} \binom{n + α}{n − k}x^{k}  (1.2)

and the three-term recurrence relation

L_{n+1}^{(α)}(x) = (x − (2n + α + 1))L_{n}^{(α)}(x) − n(n + α)L_{n−1}^{(α)}(x).  (1.3)

The Laguerre polynomials L_{n}^{(α)}(x) are orthogonal with respect to the moments L(x^{n}) = (α+1)_{n}, where (x)_{n} = x(x+1) ⋯ (x+n−1) (n ≥ 1) is the shifted factorial with (x)_{0} = 1, and L is the linear functional defined by

L(f) = \frac{1}{Γ(α + 1)} ∫_{0}^{∞} f(x)x^{α}e^{−x}dx.  (1.4)

2010 Mathematics Subject Classification. Primary 05A18; Secondary 05A15, 05A30. Key words and phrases. Laguerre polynomials, (q, y)-Laguerre polynomials, Al-Salam–Chihara poly-

nomials, moments, linearization coefficients, moments, inversion numbers, rook polynomials, matching polynomials.

4 7 2 5 13 14 15 12 6 11 10 8 1 3 9 A

Figure 1. A Laguerre configuration (A, f) on [15] with A = [15] \ {3, 8, 9, 11}.

The linearization formula [23] reads as follows:

L(L_{n_{1}}^{(α)}(x)L_{n_{2}}^{(α)}(x)L_{n_{3}}^{(α)}(x)) = ∑_{s≥0} \frac{n_{1}! n_{2}! n_{3}! 2^{n_{1}+n_{2}+n_{3}−2s} (α + 1)_{s}}{(s − n_{1})! (s − n_{2})! (s − n_{3})! (n_{1} + n_{2} + n_{3} − 2s)!}. (1.5)

A combinatorial model for Laguerre polynomials with parameter α was first given by Foata and Strehl [7]. Recall that a Laguerre configuration on [n] := {1, …, n} is a pair (A, f), where A ⊂ [n] and f is an injection from A to [n]. A Laguerre configuration can be depicted by a digraph on [n] by drawing an edge i → j if and only if f(i) = j. Clearly, such a graph has two types of connected components called cycles and paths, see Figure 1. Let LC_{n,k} be the set of Laguerre configurations (A, f) on [n] with |A| = n−k. Then Foata and Strehl’s interpretation [7] reads

∑_{(A,f)∈LC_{n,k}}(α + 1)^{cyc(f)} = \frac{n!}{k!} \binom{n + α}{n − k},  (1.6)

where cyc(f) is the number of cycles of f.

Note that one can derive (1.6) from any of the three formulas (1.1)–(1.3), see [1, 7]. The aim of this paper is to study combinatorial aspects of more general (q, y)-Laguerre polynomials L_{n}^{(α)}(x; y | q) (n ≥ 0) defined by the three term-recurrence relation

L_{n+1}^{(α)}(x; y | q) = (x − (y[n + α + 1]_{q} + [n]_{q})) L_{n}^{(α)}(x; y | q)

− y[n]_{q}[n + α]_{q} L_{n−1}^{(α)}(x; y | q), α ≥ −1, n ≥ 1, (1.7)

with L_{0}^{(α)}(x; y | q) = 1, L_{−1}^{(α)}(x; y | q) = 0. Here and throughout this paper, we use the standard q-notations: [n]_{q} = \frac{1−q^{n}}{1−q} for n ≥ 0, the q-analogue of n-factorial n!_{q} = ∏_{i=1}^{n}[i]_{q}, and the q-binomial coefficient

[\begin{matrix}n \\ k \end{matrix}]_{q} = \frac{n!_{q}}{k!_{q} (n − k)!_{q}} for 0 ≤ k ≤ n.

COMBINATORICS OF (q, y)-LAGUERRE POLYNOMIALS 3

Clearly we have L_{n}^{(α)}(x; 1 | 1) = L_{n}^{(α)}(x). Kasraoui et al. [17] gave a combinatorial interpretation for the linearization coefficients of the polynomials L_{n}^{(0)}(x; y | q) and pointed out that a combinatorial model for L_{n}^{(0)}(x; y | q) can be derived from Simion and Stanton’s model for octabasic q-Laguerre polynomials in [22]. For k ∈ ℤ, let

ℕ_{k} := {n ∈ ℤ : n ≥ k}

and ℕ := ℕ_{1}. Recently, using the theory of q-Riordan matrices, Cheon, Jung and Kim [3] derived a combinatorial model for the q-Laguerre polynomials L_{n}^{(α)}(x; q | q) when α ∈ ℕ_{0}. It is then natural to search for a combinatorial structure unifying the above two special cases, as was alluded to at the end of [3]. Our first goal is to give such a combinatorial model for L_{n}^{(α)}(x; y | q) with variable y and integer α ∈ ℕ_{−1} by using a q-analogue of Foata and Strehl’s Laguerre configurations. Moreover, for α ∈ ℕ_{0}, the (q, y)-Laguerre polynomials L_{n}^{(α)}(x; y | q) are orthogonal polynomials. It is our second goal to give a combinatorial interpretation for the moments of (q, y)-Laguerre polynomials and prove that the linearization coefficients are polynomials in y and q with nonnegative integral coefficients. We achieve this by making use of the combinatorial theory of continued fractions.

By (1.7), the first few values of L_{n}^{(α)}(x; y | q) are

L_{1}^{(α)}(x; y | q) = x − y[α + 1]_{q},
L_{2}^{(α)}(x; y | q) = x^{2} − (y[α + 1]_{q} + y[α + 2]_{q} + 1) x + [α + 1]_{q}[α + 2]_{q}y^{2},
L_{3}^{(α)}(x; y | q) = x^{3} − (y([α + 1]_{q} + [α + 2]_{q} + [α + 3]_{q}) + 2 + q)x^{2}
+ (y^{2}([α + 1]_{q}[α + 2]_{q} + [α + 2]_{q}[α + 3]_{q} + [α + 1]_{q}[α + 3]_{q})

+ y([α + 3]_{q} + [2]_{q}[α + 1]_{q}) + [2]_{q}) x − y^{3}[α + 1]_{q}[α + 2]_{q}[α + 3]_{q}.

For convenience, we introduce the signless (q, y)-Laguerre polynomials

L_{n}^{(α)}(x; y | q) := (−1)^{n}L_{n}^{(α)}(−x; y | q) = ∑_{k=0}^{n} ℓ_{n,k}^{(α)}(y; q)x^{k}.  (1.8)

For α ∈ ℕ_{−1}, we observe that ℓ_{n,k}^{(α)}(y; q) is a polynomial in y, q with nonnegative integral coefficients, which is far from obvious from the explicit Formula (2.8). For α ∈ ℕ_{−1}, Formula (1.6) implies that ℓ_{n,k}^{(α)}(1; 1) is equal to the number of Laguerre configurations in LC_{n,k} such that each cycle carries a color ∈ [1 + α]. In particular, the number of Laguerre configurations in LC_{n,k} without cycles (i.e., consisting of only k paths) is equal to the Lah numbers [18]:

ℓ_{n,k}^{(−1)}(1; 1) = \frac{n!}{k!} \binom{n − 1}{k − 1}.

Remark 1. Two different q-analogues of Lah numbers were defined and studied by Garsia and Remmel [9] and Lindsay et al. [19], respectively. Moreover an elliptic analogue of Garsia and Remmel’s q-Lah numbers was constructed by Schlosser and Yoo [21].

The organization of this paper is as follows. In Section 2 we identify the (q, y)-Laguerre polynomials as a rescaled version of Al-Salam–Chihara polynomials and derive several expansion formulas for (q, y)-Laguerre polynomials. In Section 3 we present a combinatorial interpretation for the (q, y)-Laguerre polynomials in terms of α-Laguerre configurations, which are in essence the product structure of “cycles” and “paths”. In Section 4 we give a combinatorial interpretation for the moments of (q, y)-Laguerre polynomials and prove that the linearization coefficients are polynomials in y and q with nonnegative integral coefficients. As the Laguerre polynomials play an important role in the theory of rook polynomials, we translate our α-Laguerre configurations in terms of rook placements in Section 5 and set up the connection between our α-Laguerre configurations and the matching model of complete bipartite graphs K_{n,n+α} (see Godsil and Gutman [12]).

2. A detour to Al-Salam–Chihara polynomials

The q-Pochhammer symbol or q-shifted factorial (a; q)_{n} is defined by

(a; q)_{n} = \begin{cases}∏_{i=0}^{n−1}(1 − aq^{i}) & for n ∈ ℤ^{+} ∪ \{∞\}, \\ 1 & for n = 0. \end{cases}

The Al-Salam–Chihara polynomials Q_{n}(x) := Q_{n}(x; a, b | q) are defined by the generating function (see [16, Chapter 14])

∑_{n=0}^{∞} Q_{n}(x; a, b | q)\frac{t^{n}}{(q; q)_{n}} = \frac{(at, bt; q)_{∞}}{(te^{iθ}, te^{−iθ}; q)_{∞}} ,  (2.1)

with (a, b; q)_{∞} = (a; q)_{∞}(b; q)_{∞}, and they satisfy the recurrence relation (op. cit.)

\begin{cases}Q_{−1}(x) = 0, Q_{0}(x) = 1, \\ Q_{n+1}(x) = (2x − (a + b)q^{n})Q_{n}(x) − (1 − q^{n})(1 − abq^{n−1})Q_{n−1}(x), n ≥ 0. \end{cases}  (2.2)

We have the explicit formula

Q_{n}(x; a, b | q) = \frac{(ab; q)_{n}}{a^{n}} ∑_{k=0}^{n} \frac{(q^{−n}; q)_{k} (au; q)_{k} (au^{−1}; q)_{k}}{(ab; q)_{k}(q; q)_{k}} q^{k},  (2.3)

where x = \frac{u+u^{−1}}{2} or x = cos θ if u = e^{iθ}.

Comparing (1.7) with (2.2) and using (1.8), we see that our polynomials L_{n}^{(α)}(x; y | q) are a rescaled version of the Al-Salam–Chihara polynomials:

L_{n}^{(α)}(x; y | q) = (\frac{\sqrt{y}}{1 − q} )^{n} Q_{n} (\frac{(1 − q)x + y + 1}{2\sqrt{y}}; \frac{1}{\sqrt{y}} , \sqrt{y}q^{α+1} | q) .  (2.4)

COMBINATORICS OF (q, y)-LAGUERRE POLYNOMIALS 5

The Al-Salam–Chihara polynomials (see [16, pp. 455–456] and [14]) are orthogonal with respect to the linear functional L̂_{q} defined by

L̂_{q}(f) = \frac{(q, ab; q)_{∞}}{2π} ∫_{−1}^{+1} \frac{f(x)dx}{\sqrt{1 − x^{2}}} ∏_{k=0}^{∞} \frac{1 − 2(2x^{2} − 1)q^{k} + q^{2k}}{[1 − 2xaq^{k} + a^{2}q^{2k}][1 − 2xbq^{k} + b^{2}q^{2k}]}. (2.5)

Hence, for α ∈ ℕ_{0}, the polynomials L_{n}^{(α)}(x; y | q) are orthogonal with respect to the linear functional L_{q} given by

L_{q}(f) = \frac{(q, q^{α+1}; q)_{∞}}{2π} \frac{1 − q}{2\sqrt{y}} ∫_{B_{−}}^{B_{+}} \frac{f(x)dx}{\sqrt{1 − v(x)^{2}}}

× ∏_{k=0}^{∞} \frac{[1 − 2(2v(x)^{2} − 1)q^{k} + q^{2k}]}{[1 − 2v(x)q^{k}/\sqrt{y} + q^{2k}/y][1 − 2v(x)q^{k+α+1}\sqrt{y} + q^{2k+2α+2}y]}, (2.6)

where B_{±} = \frac{(1±\sqrt{y})^{2}}{1−q} and

v(x) = \frac{1}{2\sqrt{y}} ((q − 1)x + (y + 1)).  (2.7)

Now, by (2.4), we may derive an explicit formula from (2.3), namely

L_{n}^{(α)}(x; y | q) = ∑_{k=0}^{n} \frac{n!_{q}}{k!_{q}} [\begin{matrix}n + α \\ k + α \end{matrix}]_{q} q^{k(k−n)}y^{n−k} ∏_{j=0}^{k−1} (x + (1 − yq^{−j})[j]_{q}) ,  (2.8)

and, from (2.1), the generating function

L^{(α)}(x; y; t | q) := ∑_{n≥0} L_{n}^{(α)}(x; y | q)\frac{t^{n}}{n!_{q}}
= \frac{(t; q)_{∞} (ytq^{α+1}; q)_{∞}}{∏_{k=0}^{∞} [1 − ((1 − q)x + y + 1)tq^{k} + yt^{2}q^{2k}]},  (2.9)

which can be written as

L^{(α)}(x; y; t | q) = L^{(α)}(0; y; t | q) · L^{(−1)}(x; y; t | q).  (2.10)

Define the “vertical generating function”

L_{k}^{(α)}(y; t | q) := [x^{k}]L^{(α)}(x; y; t | q) = ∑_{n≥k} ℓ_{n,k}^{(α)}(y, q)\frac{t^{n}}{n!_{q}} ,  (2.11)

and the q-derivative operator D_{q} for f(t) ∈ R[[t]] by

D_{q}(f(t)) = \frac{f(t) − f(qt)}{(1 − q)t},

where R = ℂ[[x, y, q, …]]. Thus D_{q}(1) = 0 and D_{q}(t^{n}) = [n]_{q}t^{n−1} for n > 0.

6 QIONGQIONG PAN AND JIANG ZENG

It follows from (2.9) that

D_{q}L^{(−1)}(x; y; t | q) = \frac{x}{(1 − t)(1 − yt)}L^{(−1)}(x; y; t | q),  (2.12)

which in particular gives

D_{q}L_{1}^{(−1)}(y; t | q) = [x]D_{q}L^{(−1)}(x; y; t | q)

= \frac{1}{(1 − t)(1 − ty)}

= ∑_{n≥0} n!_{q} [n + 1]_{y} \frac{t^{n}}{n!_{q}} .  (2.13)

So we can rewrite (2.12) as

D_{q}L^{(−1)}(x; y; t | q) = x · D_{q}L_{1}^{(−1)}(y; t | q) · L^{(−1)}(x; y; t | q),  (2.14)

which is equivalent to the following result. Proposition 2. For n ∈ ℕ, we have

L_{n+1}^{(−1)}(x; y | q) = x ∑_{k=0}^{n} [\begin{matrix}n \\ k \end{matrix}]_{q} k!_{q} [k + 1]_{y} L_{n−k}^{(−1)}(x; y | q).  (2.15)

Now, applying the q-binomial formula (see [10, Chapter 1])

∑_{n≥0} \frac{(a; q)_{n}}{(q; q)_{n}} z^{n} = \frac{(az; q)_{∞}}{(z; q)_{∞}}

with a = q^{α+1} and z = yt, we have

L^{(α)}(0; y; t | q) = \frac{(ytq^{α+1}; q)_{∞}}{(yt; q)_{∞}} = ∑_{n≥0} ( ∏_{k=1}^{n}[α + k]_{q})\frac{(yt)^{n}}{n!_{q}} .  (2.16)

Substitution of the latter into (2.10) gives the following result. Proposition 3. For n ∈ ℕ, we have

L_{n}^{(α)}(x; y | q) = ∑_{k=0}^{n} [\begin{matrix}n \\ k \end{matrix}]_{q} ( ∏_{j=1}^{k}[α + j]_{q})y^{k}L_{n−k}^{(−1)}(x; y | q).  (2.17)

Remark 4. (1) More generally we can prove the following connection formula for α ≥ β ≥ −1:

L_{n}^{(α)}(x; y | q) = ∑_{k=0}^{n} [\begin{matrix}n \\ k \end{matrix}]_{q} ( ∏_{j=0}^{k−1}[α − β + j]_{q})(yq^{β+1})^{k}L_{n−k}^{(β)}(x; y | q).  (2.18)

(2) For q → 1, Identity (2.9) reduces to

∑_{n≥0} L_{n}^{(α)}(x; y | 1)\frac{t^{n}}{n!} = (1 − yt)^{−(α+1)} (1 − \frac{(1 − y)t}{1 − yt})^{−x/(1−y)} .

Comparing with the generating function of the Meixner polynomials (see [16, Equation (1.9.11)])

∑_{n=0}^{∞} \frac{(β)_{n}}{n!} M_{n}(x; β, c)t^{n} = (1 − t)^{−x−β}(1 − t/c)^{x},

we derive

L_{n}^{(α)}(x; y | 1) = y^{n}(α + 1)_{n}M_{n} (\frac{−x}{1 − y}; α + 1, y) .

Hence the (q, y)-Laguerre polynomials L_{n}^{(α)}(x; y | q) are a q-analogue of rescaled Meixner polynomials.

3. Combinatorial interpretation of (q, y)-Laguerre polynomials

The reader is referred to [1, 6, 13] for the general combinatorial theory of exponential generating functions for labeled structures. For our purpose we need only a q-version of this theory for special labeled structures. A labeled structure on a (finite) set A ⊂ ℕ is a graph with vertex set A. Consider a family of labeled F-structures F = ⋃_{n=0}^{∞} F_{n}, where F_{n} consists of the F-structures on [n]. If A = {a_{1}, …, a_{n}} ⊂ ℕ, where a_{1} < ⋯ < a_{n}, an F-structure on A is obtained by replacing i by a_{i} for i = 1, …, n in the elements of F_{n}. Let F[A] denote the set of F-structures on A and associate a weight u(f) to each object f ∈ F. For the set of weighted F-structures F_{u} (where the valuation u may involve the parameter q), the q-generating function is defined as

F_{u}(t) = ∑_{f∈F} u(f)\frac{t^{|f|}}{|f|!_{q}} ,

where |f| = n if f ∈ F[n]. If F_{u} and G_{v} are two weighted structures, we denote by (F · G)_{w}[n] the set of pairs (f, g) ∈ F[S] × G[T] with weight

w(f, g) = u(f) · v(g) · q^{inv(S,T)},

where (S, T) is an ordered bipartition of [n] and inv(S, T) is the number of pairs (i, j) ∈ S × T such that i > j. Recall (see [13, p. 98]) that

∑_{(S,T)} q^{inv(S,T)} = [\begin{matrix}n \\ k \end{matrix}]_{q} ,

where the sum is over all ordered bipartitions (S, T) of [n] with |S| = k. It is folklore and immediately checked that

(F · G)_{w}(t) = F_{u}(t) · G_{v}(t).  (3.1)

We need some further definitions.

(a) For a permutation σ of a set A ⊂ ℕ, let the word σ̂ denote its linear representation in the usual sense, i.e., σ̂ = σ(i_{1}) … σ(i_{n}) if A = {i_{1}, …, i_{n}} with i_{1} < ⋯ < i_{n}.

(b) A list of (nonnegative) integers, taken as a word over ℕ, is strict if no element occurs more than once. For a strict list ρ let rl(ρ) be the number of elements that come after the maximum element.

(c) For a set λ of k non-empty and disjoint strict lists of integers, order these lists according to their minimum element (increasing). This gives a list of k words (λ_{1}, …, λ_{k}), which will be identified with λ. Then \underline{λ} = λ_{1} … λ_{k} denotes the concatenation of these lists.

Two particular structures will be used to interpret the (q, y)-Laguerre polynomials.

(d) The structures S^{(α)} consist of permutations σ, where each cycle carries a color ∈ {0, 1, 2, …, α}. Write σ as a product of unicolored permutations, σ = σ_{0} ·σ_{1} ⋯ σ_{α}, where σ_{i} is the product of cycles with color i. Now consider the concatenation

\underline{σ} = σ̂_{0} · σ̂_{1} ⋯ σ̂_{α}

and the word with letters from {0, 1} given by

\underline{\underline{σ}} = 0^{|σ̂_{0}|}10^{|σ̂_{1}|}1 ⋯ 10^{|σ̂_{α}|}.

Define the valuation u on S^{(α)} by

u(σ) = y^{|\underline{σ}|}q^{inv(\underline{σ})+inv(\underline{\underline{σ}})}.

(e) The structures Lin^{(k)} consist of sets λ = (λ_{1}, …, λ_{k}) of k nonempty and disjoint strict lists (cf. (c)). Define the valuation v on Lin^{(k)} by

v(λ) = y^{rl(λ)}q^{inv(\underline{λ})−rl(λ)},

where rl(λ) = ∑_{i=1}^{k} rl(λ_{i}).

Let LC_{n,k}^{(α)} := S^{(α)} · Lin^{(k)}[n]. For any α-Laguerre configuration (σ, λ) ∈ S^{(α)}[A] × Lin^{(k)}[B] with A ∩ B = ∅ and A ∪ B = [n], in order to invoke the folklore statement (3.1), one should use as valuation

w(σ, λ) = u(λ) · v(λ) · q^{inv(A,B)}
= y^{|\underline{σ}|}q^{inv(\underline{σ})+inv(\underline{\underline{σ}})}y^{rl(λ)}q^{inv(\underline{λ})−rl(λ)}q^{inv(A,B)}
= y^{|\underline{σ}|+rl(λ)}q^{inv(\underline{σ})+inv(\underline{\underline{σ}})+inv(\underline{λ})−rl(λ)}q^{inv(A,B)}
= y^{|\underline{σ}|+rl(λ)}q^{inv(\underline{σ}.\underline{λ})−rl(λ)+inv(\underline{\underline{σ}})}.  (3.2)

\begin{matrix}4 \\ 7 \\ 0 \\ 2 \\ 5 \\ 13 \\ 1 \\ 14 \\ 1 \\ 15 \\ 0 \\ 12 \\ 6 \\ 11 \\ 10 \\ 8 \\ 1 \\ 3 \\ 9 \\ σ \\ λ \end{matrix}

Figure 2. A 1-Laguerre configuration (σ, λ) ∈ LC_{15,4}^{(1)}, which is the Laguerre configuration in Figure 1 of which each cycle gets a color 0 or 1.

The essential point is inv(\underline{σ}) + inv(\underline{λ}) + inv(A, B) = inv(\underline{σ}.\underline{λ}). This describes the weighted configurations (LC_{n,k}^{(α)})_{w}. An element of (LC_{n,k}^{(α)})_{w} is called an α-Laguerre configuration on [n], see Figure 2. Lemma 5. For α ∈ ℕ, we have

S_{u}^{(α)}(t) = L^{(α)}(0; y; t | q).

Proof. Let P(n, α) be the set of words of length n+α with n 0’s and α 1’s, i.e., lattice paths from (0, 0) to (n, α). For σ ∈ S^{(α)}[n], the word \underline{σ} can be seen as the linear representation of an (ordinary) permutation σ̃ ∈ S^{(0)}[n], whereas \underline{\underline{σ}} ∈ P(n, α). The mapping

S^{(α)}[n] → S^{(0)}[n] × P(n, α)
σ ↦ (σ̃, \underline{\underline{σ}})

is a bijection, and from summing both contributions separately, one obtains

∑_{σ∈S^{(α)}[n]} q^{inv(\underline{σ})+inv(\underline{\underline{σ}})} = ∑_{σ∈S^{(0)}[n]} q^{inv(\underline{σ})} ∑_{\underline{\underline{σ}}∈P (n,α)} q^{inv(\underline{\underline{σ}})}

= n!_{q} [\begin{matrix}n + α \\ α \end{matrix}]_{q} ,

which is ∏_{i=1}^{n}[α + i]_{q}. So we get

S_{u}^{(α)}(t) = ∑_{n≥0} ( ∏_{i=1}^{n}[α + i]_{q})(yt)^{n}.

The result then follows from (2.16). □ Lemma 6. For integers k ≥ 1, we have

Lin_{v}^{(k)}(t) = L_{k}^{(−1)}(y; t | q).

Proof. We proceed by induction on k ≥ 1.

• The case k = 1. For a single list λ = \underline{λ} ∈ Lin^{(1)}[n + 1], let j_{λ} be the position of the maximum element, let λ′ = \underline{λ}′ ∈ Lin^{(1)}[n] be the list obtained by deleting this maximum element. Then

Lin^{(1)}[n + 1] → Lin^{(1)}[n] × [n + 1]
λ ↦ (λ′, j_{λ})

is a bijection such that inv(\underline{λ}) = inv(\underline{λ}′) + rl(λ). Furthermore, we have

∑_{λ∈Lin^{(1)}[n+1]} y^{rl(λ)}q^{inv(\underline{λ})−rl(λ)} = ∑_{λ′∈Lin^{(1)}[n]} q^{inv(\underline{λ′})} ∑_{j∈[n+1]} y^{n+1−j},

and thus

∑_{λ∈Lin^{(1)}[n+1]} v(λ) = n!_{q} [n + 1]_{y},

which, in view of (2.13), gives

D_{q}Lin_{v}^{(1)}(t) = D_{q}L_{1}^{(−1)}(y; t | q),

and by q-integration

Lin_{v}^{(1)}(t) = L_{1}^{(−1)}(y; t | q)

because the series on both sides have a zero constant term.

• The case k > 1. Assuming that Lin_{v}^{(k)}(t) = L_{k}^{(−1)}(y; t | q) has already been proved for k ≥ 1, the goal is to show

Lin_{v}^{(k+1)}(t) = L_{k+1}^{(−1)}(y; t | q).

Comparing the coefficients of x^{k+1} on both sides of Equation (2.14), we obtain

D_{q}L_{k+1}^{(−1)}(y; t | q) = D_{q}L_{1}^{(−1)}(y; t | q) · L_{k}^{(−1)}(y; t | q).

If we can show that similarly

D_{q}Lin_{v}^{(k+1)}(t) = D_{q}Lin_{v}^{(1)}(t) · Lin_{v}^{(k)}(t),  (3.3)

then we would be done. Again, the final integration step poses no problem because in both Lin_{v}^{(k+1)}(t) and L_{k+1}^{(−1)}(y; t | q) the first k + 1 coefficients vanish. Recall that a configuration λ ∈ Lin^{(k+1)}[n] consists of a list of k+1 disjoint strict lists, written as a list λ = (λ_{0}, λ_{1}, …, λ_{k}), with λ_{i} ∈ Lin^{(1)}[A_{i}], where

⨄_{i=0}^{k} A_{i} = [n] and min A_{i−1} < min A_{i}, 1 ≤ i ≤ k.

We have a bijection

Lin^{(k+1)}[A] → Lin^{(1)}[A_{0}] × Lin^{(k)}[A′]
λ ↦ (λ_{0}, λ′),

where λ′ = (λ_{1}, …, λ_{k}) and A′ = ⋃_{i=1}^{k} A_{i}, which also satisfies the requirement for applying the folklore statement (3.1):

v(λ) = v(λ_{0}) · v(λ′) · q^{inv(A_{0},A′)}.

All this holds only if for the bipartition A = A_{0} ⊎A′ it is guaranteed that min A_{0} < min A′. This is where the derivative D_{q} comes into play. Differentiation for a collection of structures means that the minimum element of the underlying set of a structure is tagged and no longer counted in the w-valuation of the base set. In the present situation, this implies that only structures are considered where tagging the minimum element of λ means the same as tagging the minimum element of λ_{0}. This shows that (3.3) holds. □

Theorem 7. For integers α ≥ −1, we have

ℓ_{n,k}^{(α)}(y; q) = ∑_{(σ;λ)∈LC_{n,k}^{(α)}} y^{|\underline{σ}|+rl(λ)}q^{inv(\underline{σ}.\underline{λ})−rl(λ)+inv(\underline{\underline{σ}})}.

Proof. From (2.10) we infer

L_{k}^{(α)}(y; t | q) = L^{(α)}(0; y; t | q)L_{k}^{(−1)}(y; t | q),

and the result follows from Lemmas 1 and 2. □

Here we give an example to illustrate the α-Laguerre configurations.

Example 8. Consider the 1-Laguerre configuration (σ; λ) ∈ LC_{15,4}^{(1)} in Figure 2. We have

σ = σ_{0} · σ_{1} with σ_{0} = (15)(7 4), σ_{1} = (14)(13 5 2);
λ = (λ_{1}, λ_{2}, λ_{3}, λ_{4}) with λ_{1} = 1 3, λ_{2} = 12 6 11, λ_{3} = 10 8, λ_{4} = 9.

Thus,

\underline{σ} = σ̂_{0} · σ̂_{1} = 7 4 15 · 13 2 5 14,
\underline{\underline{σ}} = 0^{3} 1 0^{4};
\underline{λ} = 1 3 · 12 6 11 · 10 8 · 9.

We have |\underline{σ}| = 7, rl(λ) = 3, inv(\underline{\underline{σ}}) = 4, and inv(\underline{σ} · \underline{λ}) = 52.

Remark 9. Our model of α-Laguerre configurations is simpler than the model in [3]. Actually, the α-Laguerre configurations are essentially the Laguerre configurations of which each cycle has a color in {0, …, α}. A linear order of paths and colored cycles is needed only for the valuation w in (3.2).

4. Moments of (q, y)-Laguerre polynomials

For α ∈ ℕ_{0}, by (2.6) the moments of the (q, y)-Laguerre polynomials are defined by

μ_{n}^{(α)}(q, y) := L_{q}(x^{n}).  (4.1)

According to the theory of orthogonal polynomials (see [4]) and the three-term recurrence relation (1.7), we have the orthogonality relation

L_{q}(L_{n}^{(α)}(x; y | q)L_{m}^{(α)}(x; y | q)) = y^{n}n!_{q}( ∏_{j=1}^{n}[α + j]_{q})δ_{n m}.  (4.2)

Moreover, we have the following continued fraction expansion:

∑_{n≥0} μ_{n}^{(α)}(q, y)t^{n} = \frac{1}{1 − b_{0}t − \frac{λ_{1}t^{2}}{1 − b_{1}t − \frac{λ_{2}t^{2}}{...}}} ,  (4.3)

where b_{n} = y[n + α + 1]_{q} + [n]_{q} and λ_{n} = y[n]_{q}[n + α]_{q}.

Let 𝔖_{n} be the set of permutations of {1, 2, …, n}. For σ ∈ 𝔖_{n}, we define three statistics, namely:

• the number of weak excedances, wex(σ), given by

wex(σ) = |{i ∈ [n] : σ(i) ≥ i}|;

• the number of records (or left-to-right maxima), rec(σ), given by

rec(σ) = |{i ∈ [n] : σ(i) > σ(j) for all j < i}|;

• the number of crossings, cros(σ), given by

cros(σ) = |{(i, j) ∈ [n] × [n] : i < j ≤ σ(i) < σ(j) or σ(j) < σ(i) < j < i}|.

Theorem 10. Let β = [α + 1]_{q}. Then

μ_{n}^{(α)}(y, q) = ∑_{σ∈𝔖_{n}} β^{rec(σ)}y^{wex(σ)}q^{cros(σ)}.  (4.4)

The first values of the moments are as follows:

μ_{1}^{(α)}(y, q) = yβ,
μ_{2}^{(α)}(y, q) = yβ + y^{2}β^{2},
μ_{3}^{(α)}(y, q) = yβ + β(1 + (2 + q)β)y^{2} + y^{3}β^{3}.

Due to the contraction formula [13, p. 292], we can rewrite (4.3) as

∑_{n≥0} μ_{n}^{(α)}(q, y)t^{n} = \frac{1}{1 − \frac{γ_{1}t}{1 − \frac{γ_{2}t}{...}}} ,  (4.5)

where γ_{2n} = [n]_{q} and γ_{2n+1} = y[n + α]_{q} = y([n]_{q} + [α + 1]_{q}q^{n}) for n ≥ 0.

Recall that a Dyck path of length 2n is a sequence of points (ω_{0}, …, ω_{2n}) in ℕ_{0} × ℕ_{0} satisfying ω_{0} = (0, 0), ω_{2n} = (2n, 0) and ω_{i+1} − ω_{i} = (1, 1) or (1, −1) for i = 0, …, 2n − 1. Clearly we can also identify a Dyck path with its sequence of steps (or Dyck word) s = s_{1} … s_{2n} on the alphabet {u, d}, and we use |s|_{u} and |s|_{d} to denote the number of u’s and d’s, respectively, in s. So, for a Dyck word s, we have |s|_{u} = |s|_{d} = n and |s_{1} … s_{k}|_{u} ≥ |s_{1} … s_{k}|_{d} for k ∈ [2n]. The height h_{k} of step s_{k} is defined to be h_{1} = 0 and

h_{k} = |s_{1} … s_{k−1}|_{u} − |s_{1} … s_{k−1}|_{d} for k = 2, …, 2n.

A Laguerre history of length 2n is a pair (s, ξ), where s is a Dyck word of length 2n and ξ = (ξ_{1}, …, ξ_{2n}) is a sequence of integers such that ξ_{i} = 1 if s_{i} = u and 1 ≤ ξ_{i} ≤ ⌈h_{i}/2⌉ if s_{i} = d. Let LH_{n} be the set of Laguerre histories of length 2n. We essentially use Biane’s bijection [2] to construct a bijection Φ from 𝔖_{n} to LH_{n}.

Proof of Theorem 10. We identify a permutation σ ∈ 𝔖_{n} with the bipartite graph G on {1, …, n; 1′, …, n′} with an edge (i, j′) if and only if σ(i) = j. We display the vertices on two rows called top row and bottom row as follows:

(\begin{matrix}1 & 2 & ⋯ & n \\ 1′ & 2′ & ⋯ & n′ \end{matrix}) ,

and we read the graph column by column from left to right and from top to bottom. In other words, the order of vertices is v_{1} = 1, v_{2} = 1′, …, v_{2n−1} = n, v_{2n} = n′.

For k = 1, …, 2n, the k-th restriction of G is the graph G_{k} on {v_{1}, v_{2}, …, v_{k}} with edge (v_{i}, v_{j}) in G_{k} if and only if i, j ∈ [k], so isolated vertices may exist in G_{k}.

For i = 1, …, n, the Dyck path s = s_{1} … s_{2n} is defined as follows:

• if σ^{−1}(i) > i < σ(i) (i.e., i is a cycle valley), then s_{2i−1}s_{2i} = uu;

• if σ^{−1}(i) < i < σ(i) (i.e., i is a cycle double ascent), then s_{2i−1}s_{2i} = ud;

• if σ^{−1}(i) > i > σ(i) (i.e., i is a cycle double descent), then s_{2i−1}s_{2i} = du;

• if σ^{−1}(i) < i > σ(i) (i.e., i is a cycle peak), then s_{2i−1}s_{2i} = dd;

• if σ^{−1}(i) = i = σ(i) (i.e., i is a fixed point), then s_{2i−1}s_{2i} = ud. It is easy to see that

• s is a Dyck path;

• the height h_{i} is the number of isolated vertices in G_{i−1} for i ∈ [2n] with G_{i−1} = ∅; thus h_{2i−1} (respectively h_{2i}) is even (respectively odd) for i = 1, …, n and there are ⌈h_{i}/2⌉ isolated vertices in the top row.

Next, the sequence ξ = (ξ_{1}, …, ξ_{2n}) is defined as follows:

• s_{i} = u then ξ_{i} = 1;
• s_{i} = d, then

– if σ(i) < i (i.e., i is a cycle double descent or cycle peak), then h_{2i−1} > 0; let ξ_{i} = m if σ(2i) is the m-th isolated vertex in the bottom row of G_{2i−2} from right-to-left (1 ≤ m ≤ ⌈h_{2i}/2⌉); clearly the value i will contribute m − 1 crossings l < k < i < j such that l = σ(i), k = σ(j);

– if σ^{(−1)}(i) ≤ i (i.e., i is a cycle double ascent, cycle peak or fixed point), then h_{2i} > 0; let ξ_{i} = m if σ^{(−1)}(i) is the m-th isolated vertex in the top row of G_{2i−2} from right-to-left, so 1 ≤ m ≤ ⌈h_{2i}/2⌉; clearly the value i will contribute m − 1 crossings l < k < i < j such that l = σ^{−1)}(i), k = σ(j), and i is a record if and only if m = ⌈h_{2i}/2⌉.

Let Φ(σ) = (s, ξ). Then

wex(σ) = |{i ∈ [n] : s_{2i} = d}|,
rec(σ) = |{i ∈ [n] : s_{2i} = d, ξ_{2i} = ⌈h_{2i}/2⌉}|,
cros(σ) = ∑_{i:s_{i}=d}(ξ_{i} − 1).

Therefore,

∑_{σ∈𝔖_{n}} β^{rec(σ)}y^{wex(σ)}q^{cros(σ)} = ∑_{(s,ξ)∈LH_{n}} ∏_{i:s_{i}=d} q^{ξ_{i}−1} ∏_{i:s_{2i}=d} yβ^{χ(ξ_{2i}=⌈h_{2i}/2⌉)}
= ∑_{s∈Dyck_{n}} ∏_{i:s_{i}=d} w(s_{i}),  (4.6)

where Dyck_{n} denotes the set of Dyck paths of semilength n, and the weight of each down step s_{i} = d is defined by

w(s_{i}) = \begin{cases}1 + q + ⋯ + q^{k−1}, & if h_{i} = 2k, \\ y(1 + q + ⋯ + q^{k−1} + βq^{k}), & if h_{i} = 2k + 1. \end{cases}

A folklore theorem [5] implies that the generating function of (4.6) has the continued fraction expansion (4.5), and we are done. □

Example 11. If σ = 4 1 2 7 9 6 5 8 3 ∈ 𝔖_{9}, then the Laguerre history Φ(σ) = (s, ξ) is given by

(\begin{matrix}s \\ ξ \end{matrix}) = (\begin{matrix}u u & d u & d u & u d & u u & u d & d d & u d & d d \\ 1 1 & 1 1 & 1 1 & 1 2 & 1 1 & 1 1 & 1 2 & 1 1 & 1 1 \end{matrix}) .

Theorem 12. Let α ∈ ℕ_{0}. For nonnegative integers n_{1}, …, n_{k}, the linearization coefficient

L_{q} (∏_{k=1}^{m} L_{n_{k}}^{(α)}(x; y | q))  (4.7)

is a polynomial in ℕ[y, q].

Proof. In view of the orthogonality (4.2), it suffices to prove the m = 3 case. Indeed, we can derive the following explicit formula from [17, Theorem 1]:

L_{q}(L_{n_{1}}^{(α)}(x; y | q)L_{n_{2}}^{(α)}(x; y | q)L_{n_{3}}^{(α)}(x; y | q))

= n_{1}!_{q} n_{2}!_{q} n_{3}!_{q} ∑_{s≥max(n_{1},n_{2},n_{3})} y^{s} [\begin{matrix}s \\ n_{1} + n_{2} + n_{3} − 2s, s − n_{3}, s − n_{2}, s − n_{1} \end{matrix}]_{q}

× [\begin{matrix}α + s \\ s \end{matrix}]_{q} ∑_{k≥0} [\begin{matrix}n_{1} + n_{2} + n_{3} − 2s \\ k \end{matrix}]_{q} y^{k}q^{\binom{k+1}{2}+\binom{n_{1}+n_{2}+n_{3}−2s−k}{2}+kα}, (4.8)

where the q-multinomial coefficients

[\begin{matrix}a + b + c + d \\ a, b, c, d \end{matrix}]_{q} = \frac{(a + b + c + d)!_{q}}{a!_{q} b!_{q} c!_{q} d!_{q}}

are known to be polynomials in ℕ[q] for integral a, b, c, d ≥ 0, see [13]. Hence, the righthand side of (4.8) is a polynomial in ℕ[y, q], and we are done. □

For arbitrary α, a combinatorial interpretation of (4.7) was given by Foata and Zeilberger [8] with y = q = 1, and generalized by the second author [23] to q = 1 (see also [24]), while for α = 0 a combinatorial interpretation of (4.7) was given by Kasraoui et al. [17]. Thus, the following problem suggests itself.

Problem. What is the combinatorial interpretation of (4.7) for α ∈ ℕ_{0} unifying the two special cases with α = 0 or q = 1?

5. Connection with rook polynomials and matching polynomials

In this section we show how the model of α-Laguerre configurations is connected with the models of non-attacking rook placements and matchings of complete bipartite graphs.

5.1. Interpretation in rook polynomials. An m by n board B is a subset of an m×n grid of cells (or squares). A rook is a chessboard piece which takes on rows and columns. If r_{k} is the number of ways of putting k non-attacking rooks on this board, then the ordinary rook polynomial is defined by

R_{m,n}(x) = ∑_{k} r_{k}x^{k}.

Thus, the Laguerre polynomials (1.2) can be written as

L_{n}^{(α)}(x) = (−1)^{n}n! R_{n,n+α}(−x^{−1}).  (5.1)

A k-rook placement on a board B is a subset C ⊂ B of k cells such that no two cells are in the same row or column of B. We refer the reader to Riordan’s classical book [20, Chapters 7 and 8] for many problems formulated in terms of configurations of nonattacking rooks on “chessboards” of various shapes.

\begin{matrix}× \\ × \\ × \end{matrix}

Figure 3. The Ferrers board of shape μ = (4, 4, 3, 3, 1) and a placement C of three non-attacking rooks with inv(C) = 3.

We label the rows of the grid from top to bottom and the columns from left to right in the same way as referring to the entries of an m×n matrix. Recall that an integer partition is a sequence of positive integers μ := (μ_{1}, μ_{2}, …, μ_{l}) such that μ_{1} ≥ μ_{2} ≥ ⋯ ≥ μ_{l} > 0. We also use the notation μ = (n_{1}^{m_{1}}, …, n_{k}^{m_{k}}) to denote the partition with m_{i} parts equal to n_{i} for i = 1, …, k. For convenience, we shall identify μ with its Ferrers board B_{μ}, which is defined as the subset {(i, j) : 1 ≤ i ≤ μ_{j}, 1 ≤ j ≤ l} of ℕ × ℕ. For a placement C of rooks on B_{μ}, the inversion number inv(C) is defined as follows: for each rook (cell) in C cross out all the cells which are below or to the right of the rook; then inv(C) is the number of squares of F_{μ} that are not crossed out. An example is shown in Figure 3.

Definition 13. For integers n, k ≥ 0 and α ≥ −1, let m = (m_{0}, …, m_{α}) and n = (n_{1}, …, n_{k}) be nonnegative integer sequences such that m_{0}+m_{1}+⋯+m_{α}+n_{1}+⋯+n_{k} = n with m_{i} ≥ 0 and n_{j} ≥ 1. We define B_{n,k}^{(α)}(m; n) as the set of n × n squares of color shape B := (B^{(1)}; B^{(2)}) with

B^{(1)} :=(n^{m_{0}}, …, n^{m_{α}}),  (5.2a)
B^{(2)} :=(n^{n_{1}}, …, n^{n_{k}}).  (5.2b)

By convention, if α = −1 (respectively k = 0), then B^{(1)} = ∅ (respectively B^{(2)} = ∅). Let

cw(B) = ∑_{i=0}^{α} m_{i} and cd(B) = ∑_{i=0}^{α} i · m_{i}.

Let BC_{n,k}^{(α)}(m; n) denote the set of all ordered pairs R = (B, C), where B ∈ B_{n,k}^{(α)}(m; n) and C is an n-rook placement on B such that

min(C ∩ B_{1}^{(2)}) < min(C ∩ B_{2}^{(2)}) < ⋯ < min(C ∩ B_{k}^{(2)}),  (5.3)

where min(C ∩ B_{1}^{(2)}) is the minimum row index of cells in C ∩ B_{1}^{(2)}. For each block B_{i}^{(2)} = (n^{n_{i}}), we define ind(C ∩ B_{i}^{(2)}) as the number of rooks in C ∩ B_{i}^{(2)} whose column indices are greater than the column index of the rook which has the maximum row index in B_{i}^{(2)}, and let ind(R) = ∑_{i=1}^{k} ind(C ∩ B_{i}^{(2)}). Let

BC_{n,k}^{(α)} = ⋃_{m,n} BC_{n,k}^{(α)}(m; n)  with  ∑_{i=0}^{α} m_{i} + ∑_{j=1}^{k} n_{j} = n.

\begin{matrix}15 \\ 14 \\ 13 \\ 12 \\ 11 \\ 10 \\ 9 \\ 8 \\ 7 \\ 6 \\ 5 \\ 4 \\ 3 \\ 2 \\ 1 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \\ 13 \\ 14 \\ 15 \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \\ × \end{matrix}

Figure 4. The colored rook configuration R corresponding to the 1-Laguerre configuration in Figure 2 with (m; n) = ((3, 4); (2, 3, 2, 1)).

An element R = (B, C) ∈ BC_{n,h}^{(α)} is called a colored rook configuration.

Remark 14. One can imagine that each column of a board in BC_{n,k}^{(α)}(m; n) is colored with colors in {0, 1, …, α + k} from left to right as follows: the first m_{0} columns get color 0, the next m_{1} columns get color 1, …, the last n_{k} columns get color α + k.

Theorem 15. The coefficient ℓ_{n,k}^{(α)}(y; q) in (1.8) is the following generating polynomial of colored rook configurations in BC_{n,k}^{(α)}:

ℓ_{n,k}^{(α)}(y; q) = ∑_{R=(B,C)∈BC_{n,k}^{(α)}} y^{cw(B)+ind(R)}q^{inv(C)+cd(B)−ind(R)}.

Proof. Let LC_{n,k}^{(α)}(m; n) be the set of ρ := (σ_{0}, …, σ_{α}; λ_{1}, …, λ_{k}) ∈ LC_{n,k}^{(α)} such that |ρ| = (|σ_{0}|, …, |σ_{α}|; |λ_{1}|, …, |λ_{k}|) = (m; n). We define the map ϕ : LC_{n,k}^{(α)}(m; n) ⟶ BC_{n,k}^{(α)}(m; n) by ϕ(ρ) = (B, C) for ρ = (σ_{0}, …, σ_{α}; λ_{1}, …, λ_{k}) ∈ LC_{n,k}^{(α)}(m; n) as follows:

(i) The colored board B = (B^{(1)}, B^{(2)}) is given by

B^{(1)} = (n^{|σ_{0}|}, …, n^{|σ_{α}|}) and B^{(2)} = (n^{|λ_{1}|}, n^{|λ_{2}|}, …, n^{|λ_{k}|}).

(ii) If w := σ̂_{0}σ̂_{1} ⋯ σ̂_{α}λ_{1}λ_{2} ⋯ λ_{k} = w_{1} … w_{n}, which is a permutation of [n], let C = {(j, w_{j}) : j ∈ [n]}.

It is clear that ϕ(ρ) ∈ BC_{n,k}^{(α)}, and the procedure is reversible. Hence ϕ is a bijection. It is easy to verify that inv(C) = inv(ρ), ind(B_{i}^{(2)}) = rl(λ_{i}), and cd(B) = ∑_{i=0}^{α} i|σ_{i}|, which implies that

|\underline{σ}| + rl(λ) = cw(B) + ind(R);
inv(\underline{σ}.\underline{λ}) − rl(λ) + inv(\underline{\underline{σ}}) = inv(C) + cd(B) − ind(R).

The result then follows from Theorem 7. □

Example 16. Let ρ = ((7 4)(15), (13 2 5)(14); 1 3, 12 6 11, 10 8, 9) ∈ LC_{15,4}^{(1)}. Then ϕ maps ρ to the placement of 15 rooks on the board B = (15^{7}; 15^{2}, 10^{3}, 8^{2}, 7) shown in Figure 4. We find cw(B) = 1, cd(B) = 4; inv(C) = 52 and ind(R) = 3.

5.2. Interpretation in matching polynomials. Recall that a matching of a graph G is a set of edges without common vertices. For any graph G with n vertices, the matching polynomial of G is defined by

m(G, x) = ∑_{k=0}^{⌊n/2⌋}(−1)^{k}m_{k}x^{n−2k},

where m_{k} is the number of k-edge matchings of G. Let K_{n,m} denote the set of complete bipartite graphs on the two disjoint sets A = [n] and B = {1′, …, m′}, that is, there is an edge (a, b) if and only if a ∈ A and b ∈ B. From the explicit formula (1.2) it is quite easy to derive the connection formula

m(K_{n,n+α}, x) = x^{α}L_{n}^{(α)}(x^{2}),  α ≥ −1.  (5.4)

Godsil and Gutman [12] proved (5.4) by showing that the matching polynomials satisfy the same three-term recurrence relation (1.3). Here we give a simple bijection between our α-Laguerre configuration model and the above matching model of complete bipartite graphs. Let M_{n,m}^{n−k} be the set of matchings of K_{n,m} with n − k edges.

Proposition 17. For integers n, k ≥ 1 and α ≥ −1, there exists an explicit bijection ϕ : LC_{n,k}^{(α)} ⟶ M_{n,n+α}^{n−k}.

Proof. We construct such a bijection ϕ. Let ρ = (σ_{0}, σ_{1}, …, σ_{α}; λ_{1}, λ_{2}, …, λ_{k}) ∈ LC_{n,k}^{(α)} be an α-Laguerre configuration. We define a matching γ of K_{n,n+α} such that (a, b′) ∈ A × B is an edge in γ if and only if (a, b) satisfies one of the following three conditions:

(1) σ_{0}(a) = b, i.e., the image of a is b through the action of permutation σ_{0};

(2) a and b are consecutive letters in the word σ̂_{1}(n + 1)σ̂_{2}(n + 2) … σ̂_{α}(n + α);

(3) a and b are consecutive letters in the word λ_{j} for some j ∈ [k]. By convention, if α = −1 (respectively α = 0) there are no words of types (1) and (2) (respectively type (2)). Since σ_{0}σ_{1} … σ_{α}λ_{1} … λ_{k} is a permutation of [n], it is clear that there are n − k such edges (a, b′). The above procedure is obviously reversible. □

12345678910 11 12 13 14 15 1′ 2′ 3′ 4′ 5′ 6′ 7′ 8′ 9′ 10′ 11′ 12′ 13′ 14′ 15′ 16′

Figure 5. The matching corresponding to the 1-Laguerre configuration in Figure 2

Example 18. For the 1-Laguerre configuration

ρ = ((7 4)(15), (13 2 5)(14); 1 3, 12 6 11, 10 8, 9) ∈ LC_{15,4}^{(1)}

in Example 8, the corresponding matching γ of K_{15,16}^{11} is shown in Figure 5.

Remark 19. We leave it to the interested reader to find the (q, y)-version of the above matching polynomials for (q, y)-Laguerre polynomials L_{n}^{(α)}(x; y | q).

Acknowledgement

We thank the anonymous reviewers for their careful reading of our manuscript and their many helpful comments and suggestions.

References

[1] F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures. Encyclopedia of Mathematics and its Applications, vol. 67. Cambridge University Press, Cambridge, 1998.

[2] P. Biane, Permutations suivant le type d’excédance et le nombre d’inversions et interprétation combinatoire d’une fraction continue de Heine. European J. Combin. 14 (1993), no. 4, 277–284.

[3] G.-S. Cheon, J.-H. Jung and S.-R. Kim, New q-Laguerre polynomials having factorized permutation interpretations. J. Math. Anal. Appl. 470 (2019), 118–134.

[4] T. Chihara, An Introduction to Orthogonal Polynomials. Gordon and Breach, New York, London, Paris, 1978.

[5] P. Flajolet, Combinatorial aspects of continued fractions. Discrete Math. 32 (1980), no. 2, 125– 161.

[6] P. Flajolet and R. Sedgewick, Analytic Combinatorics. Cambridge University Press, Cambridge, 2009.

[7] D. Foata and V. Strehl, Combinatorics of Laguerre polynomials. In: “Enumeration and design” (Waterloo, Ont., 1982), Academic Press, Toronto, 1984, pp. 123–140.

[8] D. Foata and D. Zeilberger, Laguerre polynomials, weighted derangements, and positivity. SIAM J. Discrete Math. 1 (1988), no. 4, 425–433.

[9] A. M. Garsia and J. Remmel, A combinatorial interpretation of q-derangement and q-Laguerre numbers. European J. Combin. 1 (1980), 47–59.

[10] G. Gasper and M. Rahman, Basic Hypergeometric Series. 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 96, Cambridge University Press, Cambridge, 2004.

[11] I. M. Gessel, Generalized rook polynomials and orthogonal polynomials. In: D. Stanton, ed., q-Series and Partitions (Springer, Berlin, 1989), pp. 154–176.

[12] C. D. Godsil and I. Gutman, On the theory of the matching polynomial. J. Graph Theory 5 (1981), no. 2, 137–144.

[13] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Inc., New York, 1983.

[14] M. E. H. Ismail, Classical and Quantum Orthogonal Polynomials in One Variable. Cambridge University Press, Cambridge, 2009.

[15] M. E. H. Ismail, A. Kasraoui and J. Zeng, Separation of variables and combinatorics of linearization coefficients of orthogonal polynomials. J. Combin. Theory Ser. A 120 (2013), no. 3, 561–599.

[16] R. Koekoek, P. A. Lesky and R. F. Swarttouw, Hypergeometric Orthogonal Polynomials and Their q-Analogues. Springer Monographs in Mathematics, Springer, 2010.

[17] A. Kasraoui, D. Stanton and J. Zeng, The combinatorics of Al-Salam–Chihara (q, y)-Laguerre polynomials. Adv. Appl. Math. 47 (2011), no. 2, 216–239.

[18] I. Lah, Eine neue Art von Zahlen, ihre Eigenschaften und Anwendung in der mathematischen Statistik. Mitteilungsbl. Math. Statist. 7 (1955), 203–212.

[19] J. Lindsay, T. Mansour and M. Shattuck, A new combinatorial interpretation of a q–analogue of the Lah numbers. J. Combin. 2 (2011), no. 2, 245–264.

[20] J. Riordan, An Introduction to Combinatorial Analysis. Reprint of the 1958 original [Wiley, New York]. Dover Publications, Inc., Mineola, NY, 2002.

[21] M. J. Schlosser and M. Yoo, Elliptic rook and file numbers. Electron. J. Combin. 24 (2017), no. 1, Paper 1.31, 47 pp.

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

[23] J. Zeng, Weighted derangements and the linearization coefficients of orthogonal Sheffer polynomials. Proc. London Math. Soc. (3) 65 (1992), 1–22.

[24] J. Zeng, Combinatorics of orthogonal polynomials and their moments. Lecture Notes at OPSF Summer School, Univ. Maryland, College Park, MD, July 11–July 15, 2016.

Univ Lyon, Université Lyon1, UMR 5208 du CNRS, Institut Camille Jordan, F-69622, Villeurbanne Cedex, France

Email address: qpan@math.univ-lyon1.fr

Univ Lyon, Université Lyon1, UMR 5208 du CNRS, Institut Camille Jordan, F-69622, Villeurbanne Cedex, France

Email address: zeng@math.univ-lyon1.fr