More Statistics on Permutation Pairs ^{∗}

Jean-Marc Fedou

Laboratoire Bordelais de Recherches en Informatique Université Bordeaux I 33405 Talence, France

Don Rawlings ^{†} Mathematics Department California Polytehnic State University San Luis Obispo, Ca. 93407

Submitted: June 30, 1994; Accepted: October 21, 1994

Abstract

Two inversion formulas for enumerating words in the free monoid by θ-adjacencies are applied in counting pairs of permutations by various statistics. The generating functions obtained involve refinements of bibasic Bessel functions. We further extend the results to finite sequences of permutations.

∗This work is partially supported by EC grant CHRX-CT93-0400 and PRC Maths-Info †Financial support provided by LaBRI, Université Bordeaux I

1 Introduction

The study of statistics on permutation pairs was initiated by Carlitz, Scoville, and Vaughan [4]. Stanley [18] q-extended their work to finite sequences of permutations. In [6], we exploited the recursive technique of Carlitz et. al. to obtain some additional refinements. We also discussed numerous related distributions. Our purpose here is to further extend the study of statistics on finite permutation sequences. Our method is based on the theory of inversion presented in [7]. For clarity, we primarily focus on permutation pairs.

Let S_{n} denote the symmetric group on {1, 2, …, n}. For a permutation σ = σ(1)σ(2) ⋯ σ(n) ∈ S_{n}, the descent and rise sets are defined as

Des σ = {i : 1 ≤ i ≤ n − 1, σ(i) > σ(i + 1)} ,
Ris σ = {i : 1 ≤ i ≤ n − 1, σ(i) < σ(i + 1)} .

These sets are of course complementary relative to {1, 2, …, n − 1}. The descent and rise numbers of σ are respectively defined to be the cardinalities of Des σ and Ris σ, that is,

des σ = | Des σ| and ris σ = | Ris σ| .

Furthermore, let

maj σ = ∑_{k∈Des σ} k ,  comaj σ = ∑_{k∈Des σ}(n − k) ,
rin σ = ∑_{k∈Ris σ} k ,  corin σ = ∑_{k∈Ris σ}(n − k) .

The statistics in the first column were originally referred to as the greater and lesser indices by Major MacMahon [16]. Many authors have since adopted the term major index for the former. Being the sum of the rise indices, we will refer to rin σ as the rise index. The statistics of the second column will respectively be called the comajor and corise indices. Since Des σ and Ris σ are complementary, des σ + ris σ = n − 1, maj σ + rin σ = \binom{n}{2}, and

comaj σ + corin σ = \binom{n}{2}.

We also consider the number of common iddescents of a permutation pair; for (α, β) in the cartesian product S_{n}^{2} = S_{n} × S_{n}, let

iddes(α, β) = | Des α^{−1} ⋂ Des β^{−1}|

where σ^{−1} denotes the inverse of σ.

Our initial results involve the first two terms of a sequence {J_{ν}^{(i,j)}}_{ν≥0} of refined bibasic Bessel functions. For a positive integer n, let

(a; q)_{n} = (1 − a)(1 − aq) ⋯ (1 − aq^{n−1}) .

By convention, (a; q)_{0} = 1. The q-binomial coefficient (or Gaussian polynomial ) is defined to be

[ \begin{matrix}n \\ k \end{matrix} ]_{q} = \frac{(q; q)_{n}}{(q; q)_{k}(q; q)_{n−k}}

when 0 ≤ k ≤ n and to be 0 when k > n. The function J_{ν}^{(i,j)} is defined as

J_{ν}^{(i,j)}(z; q, p) = ∑_{n≥0}(−1)^{n}q^{\binom{n+ν}{2}} [ \begin{matrix}i + 1 \\ n + ν \end{matrix} ]_{q} [ \begin{matrix}j + n \\ n \end{matrix} ]_{p} z^{n+ν} .

A few properties of {J_{ν}^{(i,j)}}_{ν≥0} are worth immediate remark. First, J_{0}^{(i−1,j)} is a Hadamard product of the two series appearing in the q-binomial theorem and q-binomial series ([1, p. 36]):

q-Binomial Theorem (t; q)_{i} = ∑_{n≥0}(−1)^{n}q^{\binom{n}{2}} [ \begin{matrix}i \\ n \end{matrix} ]_{q} t^{n} .

q-Binomial Series For |q|, |t| < 1, 1/(t; q)_{j+1} = ∑_{n≥0} [ \begin{matrix}j + n \\ n \end{matrix} ]_{q} t^{n} .

Also note that J_{0}^{(i−1,j)}(z; q, 0) = (z; q)_{i}.

Second, for |q|, |p| < 1, special cases of the function

J_{ν}(z; q, p) = lim_{i,j→∞} J_{ν}^{(i,j)}(z; q, p) = ∑_{n≥0} \frac{(−1)^{n}q^{\binom{n+ν}{2}}z^{n+ν}}{(q; q)_{n+ν}(p; p)_{n}}

arise in a variety of other contexts. As demonstrated by Delest and Fedou [5], the coefficient of q^{m}z^{n} in the expansion of the quotient J_{1}(zq; q, q)/J_{0}(zq; q, q) is equal to the number of skew Ferrers’ diagrams (also known as parallelogram polyominoes) having n columns and area m. Also, J_{0}(−z; q, 0) is the second q-analogue of the exponential function [11, p. 9], often denoted by E_{q}(z). Finally, omitting q^{\binom{n+ν}{2}} and replacing z^{n+ν} in the series J_{ν}(z; q, q) by (z/2)^{2n+ν} gives one of the sequences of q-Bessel (or basic Bessel) functions originally studied by Jackson [15] and further explored by Ismail [14]. Thus, J_{ν}^{(i,j)}(z; q, p) is indeed a refined bibasic Bessel function.

Several theorems could be used to demonstrate our method. Our first objective will be on determining the distribution of (iddes; des, comaj, ris, corin) over unrestricted pairs in S_{n}^{2} and over restricted pairs (α, β) ∈ S_{n}^{2} with β(1) = n. In sections 3 through 7, we prove

Theorem 1 The generating functions for the sequences

A_{n}(t, x, y, q, p) = ∑_{(α,β)∈S_{n}^{2}} t^{iddes(α,β)}x^{des α}q^{comaj α}y^{ris β}p^{corin β} ,

A_{n}^{1}(t, x, y, q, p) = ∑_{{(α,β)∈S_{n}^{2} : β(1)=n}} t^{iddes(α,β)}x^{des α}q^{comaj α}y^{ris β}p^{corin β}

(1)

are

∑_{n≥0} \frac{A_{n}(t, x, y, q, p)z^{n}}{(x; q)_{n+1}(y; p)_{n+1}} = ∑_{i,j≥0} x^{i}y^{j} \frac{1 − t}{J_{0}^{(i,j)}(z(1 − t); q, p) − t} ,  (2)

∑_{n≥0} \frac{A_{n+1}^{1}(t, x, y, q, p)z^{n+1}}{(x; q)_{n+2}(y; p)_{n+1}} = ∑_{i,j≥0} x^{i}y^{j} \frac{J_{1}^{(i,j)}(z(1 − t); q, p)}{J_{0}^{(i,j)}(z(1 − t); q, p) − t} .  (3)

For comparison with previously obtained results on permutations and permutation pairs, a number of corollaries are presented in the next section.

Other closely related five-variate distributions on permutation pairs are considered in section 8. Specifically, we give the generating functions for the distribution of (iddes; des, comaj, ris, corin) over pairs (α, β) ∈ S_{n}^{2} satisfying α(1) = n and for the distributions of (iddes; des, comaj, des, comaj) and (iddes; ris, corin, ris, corin) for unrestricted and restricted pairs in S_{n}^{2}. The corresponding refined bibasic Bessel functions are variations on J_{ν}^{(i,j)}. In section 9, we give two theorems for finite sequences of permutations which contain the ones for permutation pairs as special cases.

2 Selected Corollaries

Multiplying (2) and (3) through by (1 − x)(1 − y) and then taking the limit as x, y → 1^{−} leads respectively to the following corollaries:

Corollary 1 The distribution of (iddes; comaj, corin) on S_{n}^{2} is generated by

∑_{n≥0} \frac{A_{n}(t, 1, 1, q, p)z^{n}}{(q; q)_{n}(p; p)_{n}} = \frac{1 − t}{J_{0}(z(1 − t); q; p) − t} .

Corollary 2 The distribution of (iddes; comaj, corin) on pairs (α, β) ∈ S_{n+1}^{2} satisfying the condition β(1) = n + 1 is generated by

∑_{n≥0} \frac{A_{n+1}^{1}(t, 1, 1, q, p)z^{n+1}}{(q; q)_{n+1}(p; p)_{n}} = \frac{J_{1}(z(1 − t); q, p)}{J_{0}(z(1 − t); q, p) − t} .

These corollaries are equivalent to special cases of Theorems 2 and 4 in [6]. Several equivalent distributions are discussed in section 4 of [6]. Corollary 1 is essentially due to Stanley [18].

Further replacing z by z(1−q)(1−p) in Corollary 1 and letting q, p → 1^{−} gives the initial result on permutation pairs due to Carlitz et al. [4]:

Corollary 3 The distribution of iddes over S_{n}^{2} is generated by

∑_{n≥0} \frac{A_{n}(t, 1, 1, 1, 1)z^{n}}{n!n!} = \frac{1 − t}{∑_{n≥0}(−1)^{n}z^{n}/n!n! − t} .

By appropriately selecting the values of various parameters, it is also possible to obtain generating functions for the analogues of the Eulerian polynomials of Carlitz [2, 3] and of Stanley [18] respectively defined by

C_{n}(y, p) = ∑_{σ∈S_{n}} y^{ris σ}p^{rin σ} and S_{n}(t, q) = ∑_{σ∈S_{n}} t^{des σ}q^{inv σ}

where inv σ denotes the number of inversions of σ, that is, the number of pairs (i, j) such that 1 ≤ i < j ≤ n and σ(i) > σ(j). The bijective techniques of Foata [8] may be easily adapted to show that

C_{n}(y, p) = ∑_{σ∈S_{n}} y^{ris σ}p^{corin σ} and S_{n}(t, q) = ∑_{σ∈S_{n}} t^{ides σ}q^{comaj σ}

where ides σ = des σ^{−1}. When x = 0, the only pairs contributing non-zero weight in (1) are of the form (12 … n, β). Thus, A_{n}(1, 0, y, 0, p) = C_{n}(y, p). Similarly, A_{n}(t, 1, 0, q, 0) = S_{n}(t, q). We therefore have the following immediate corollaries of (2):

Corollary 4 The distribution of (ris, corin) over S_{n} is generated by

∑_{n≥0} \frac{C_{n}(y, p)z^{n}}{(y; p)_{n+1}} = ∑_{j≥0} \frac{y^{j}}{1 − [j + 1]_{p} z}

where [j + 1]_{p} = (1 − p^{j})/(1 − p).

Corollary 5 (Stanley) The distribution of (des, inv) on S_{n} is generated by

∑_{n≥0} \frac{S_{n}(t, q)z^{n}}{(q; q)_{n}} = \frac{1 − t}{E_{q}(−z(1 − t)) − t}

where E_{q}(z) = J_{0}(−z; q, 0).

Another generating function for C_{n}(y, p) was given by Garsia [9].

3 A key partition lemma

In proving Theorem 1, we make repeated use of a result on partitions. For later purposes, we present this result in the language of the free monoid.

Let A be an alphabet, that is, a non-empty set whose elements are referred to as letters. A finite sequence (possibly empty) w = a_{1}a_{2} … a_{n} of n letters is said to be a word of length n. The length of w will be denoted by l(w). The empty word is signified by 1. The set of all words that may be formed with the letters from A along with the concatenation product is known as the free monoid generated by A and is denoted by A^{∗}. We let A^{n} signify the set of words in A^{∗} of length n.

To state the needed partition result, we select the alphabet N of nonnegative integers and let N_{r} = {0, 1, 2, …, r}. For w = a_{1}a_{2} … a_{n} ∈ N^{n}, set

∥w∥ = a_{1} + a_{2} + … + a_{n} .

For K ⊆ {1, 2, …, n − 1}, a partition belonging to the set

C_{r}^{n}(K) = {γ = γ_{1}γ_{2} … γ_{n} ∈ N_{r}^{n} : γ_{1} ≤ γ_{2} ≤ … ≤ γ_{n}, γ_{k} < γ_{k+1} if k ∈ K}

has at most n parts (each bounded by r) and is said to be compatible with K. We define the index of a set K ⊆ {1, 2, …, n − 1} to be

ind K = ∑_{k∈K}(n − k) .

For σ ∈ S_{n}, note that ind(Des σ) = comaj σ and ind(Ris σ) = corin σ. The key partition result for the coming argumentation is

Lemma 1 For K ⊆ {1, 2, …, n − 1} and r a non-negative integer,

∑_{γ∈C_{r}^{n}(K)} q^{∥γ∥} = q^{ind K} [ \begin{matrix}r − |K| + n \\ n \end{matrix} ]_{q} .

Proof. This is a trivial consequence of a well-known result in the theory of partitions. As may be referenced in [1, p. 33],

∑_{0≤λ_{1}≤λ_{2}≤...≤λ_{n}≤s} q^{∥λ∥} = [ \begin{matrix}s + n \\ n \end{matrix} ]_{q}  (4)

where λ = λ_{1}λ_{2} … λ_{n}. Suppose γ = γ_{1}γ_{2} … γ_{n} ∈ C_{r}^{n}(K). The bijection γ_{1}γ_{2} … γ_{n} → λ_{1}λ_{2} … λ_{n} defined by λ_{j} = (γ_{j} − |{i ∈ K : i < j}|) satisfies the properties that 0 ≤ λ_{1} ≤ λ_{2} ≤ … ≤ λ_{n} ≤ (r − |K|) and ∥γ∥ = ∥λ∥ + ind K. The desired result then follows from (4).

4 Words by θ-adjacencies

The essence of our proof to Theorem 1 relies on two inversion theorems that enumerate words in the free monoid by θ-adjacencies. Let θ be a binary relation on the alphabet A. A word w = a_{1}a_{2} … a_{n} ∈ A^{n} is said to have a θ-adjacency in position k if a_{k}θa_{k+1}. The set of θ-adjacencies and the number of θ-adjacencies of w = a_{1}a_{2} … a_{n} are respectively denoted by

θAdj w = {k : 1 ≤ k ≤ n − 1, a_{k}θa_{k+1}} and θadj w = |θAdj w| .

An element of the set T_{A,θ} = {w = a_{1}a_{2} … a_{l(w)} ∈ A^{∗} : a_{1}θa_{2}θ … θa_{l(w)}} is said to be a θ-chain. We let T_{A,θ}^{+} denote the set of θ-chains of positive length. In Z[t] << A >>, the algebra of formal power series on A^{∗} with coefficients from the ring of polynomials in t having integer coefficients, the following inversion formulas hold:

Theorem 2 Words by θ-adjacencies are generated by

∑_{w∈A^{∗}} t^{θadj w}w = \frac{1}{1 + ∑_{w∈T_{A,θ}^{+}} (−1)^{l(w)}(1 − t)^{l(w)−1}w} .

Theorem 3 For a non-empty set X ⊆ A, let A^{∗}X = {va ∈ A^{∗} : a ∈ X}. Then, words ending in a letter from X by θ-adjacencies are generated by

∑_{w∈A^{∗}X} t^{θadj w}w = \frac{− ∑_{w∈T_{A,θ}X} (−1)^{l(w)}(1 − t)^{l(w)−1}w}{1 + ∑_{w∈T_{A,θ}^{+}} (−1)^{l(w)}(1 − t)^{l(w)−1}w}

where T_{A,θ}X = {va ∈ T_{A,θ} : a ∈ X} and where the ratio is to be interpreted as the product of the reciprocal of its denominator (the left factor) with its numerator (the right factor).

A number of related theories of inversion [12, 13, 18, 20, 21] have been developed and applied to a wide range of combinatorial problems. Both Theorems 2 and 3 may be readily deduced from the theory of inversion presented in [7].

5 The role played by Theorems 2 and 3

To see precisely how Theorems 2 and 3 intervene in the proof of Theorem 1, we first rewrite them as

∑_{w∈A^{∗}} t^{θadj w}w = \frac{1 − t}{∑_{w∈T_{A,θ}} (−1)^{l(w)}(1 − t)^{l(w)}w − t} ,  (5)

∑_{w∈A^{∗}X} t^{θadj w}w = \frac{− ∑_{w∈T_{A,θ}X} (−1)^{l(w)}(1 − t)^{l(w)}w}{∑_{w∈T_{A,θ}} (−1)^{l(w)}(1 − t)^{l(w)}w − t} .  (6)

Next, let θ be the binary relation on N ×N consisting of the pairs (\binom{i}{j}, \binom{k}{m}) satisfying i > k and j ≥ m;

\binom{i}{j}θ\binom{k}{m} ⟺ i > k and j ≥ m .  (7)

Thus, the set of θ-adjacencies for a biword \binom{v}{w} = \binom{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{n}} ∈ (N × N)^{n} is

θAdj \binom{v}{w} = \{k : 1 ≤ k ≤ n − 1, a_{k} > a_{k+1}, b_{k} ≥ b_{k+1}\} .

Moreover, \binom{v}{w} = \binom{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{n}} ∈ (N_{i} × N_{j})^{n} is a θ-chain if and only if

i ≥ a_{1} > a_{2} > … > a_{n} and j ≥ b_{1} ≥ b_{2} ≥ … ≥ b_{n}.  (8)

As will be seen, the crucial step in establishing Theorem 1 is the evaluation of

∑_{\binom{v}{w}∈(N_{i}×N_{j})^{∗}}t^{θadj \binom{v}{w}}W \binom{v}{w} and ∑_{\binom{v}{w}∈(N_{i}×N_{j})^{∗}X_{i}}t^{θadj \binom{v}{w}}W \binom{v}{w}

where X_{i} denotes the set of biletters N_{i} × N_{0} = \{\binom{k}{0} : 0 ≤ k ≤ i\} and where W is the homomorphism on (N × N)^{∗} obtained by multiplicatively extending the weight W \binom{i}{j} = q^{i}p^{j}z defined on each \binom{i}{j} ∈ N × N. In view of (5) and (6), this can be accomplished by computing a sum of the form

∑(−1)^{l\binom{v}{w}}(1 − t)^{l\binom{v}{w}}W \binom{v}{w}  (9)

twice; once summed over the set T_{N_{i}×N_{j},θ} of θ-chains in (N_{i} × N_{j})^{∗} and once summed over the set T_{N_{i}×N_{j},θ}X_{i} of θ-chains ending in a biletter from X_{i}.

By (8), expression (9) summed over T_{N_{i}×N_{j},θ} is equal to

∑_{n≥0}(−1)^{n}(1 − t)^{n}z^{n} ∑_{i≥a_{1}>a_{2}>...>a_{n}≥0} q^{∥v∥} ∑_{j≥b_{1}≥b_{2}≥...≥b_{n}≥0} p^{∥w∥}

which, by Lemma 1, reduces to

∑_{n≥0}(−1)^{n}q^{\binom{n}{2}} [ \begin{matrix}i + 1 \\ n \end{matrix} ]_{q} [ \begin{matrix}j + n \\ n \end{matrix} ]_{p} (1 − t)^{n}z^{n} = J_{0}^{(i,j)}(z(1 − t); q, p) .

Summarizing, we have established that

∑_{\binom{v}{w}∈T_{N_{i}×N_{j} ,θ}}(−1)^{l\binom{v}{w}}(1 − t)^{l\binom{v}{w}}W \binom{v}{w} = J_{0}^{(i,j)}(z(1 − t); q, p) .

the electronic journal of combinatorics 1 (1994), #R11 9 Similarly,

∑_{\binom{v}{w}∈T_{N_{i}×N_{j} ,θ}X_{i}}(−1)^{l\binom{v}{w}}(1 − t)^{l\binom{v}{w}}W \binom{v}{w} = −J_{1}^{(i,j)}(z(1 − t); q, p) .

The last two identities together with (5) and (6) imply

∑_{\binom{v}{w}∈(N_{i}×N_{j})^{∗}}t^{θadj \binom{v}{w}}W \binom{v}{w} = \frac{1 − t}{J_{0}^{(i,j)}(z(1 − t); q, p) − t} ,  (10)
∑_{\binom{v}{w}∈(N_{i}×N_{j})^{∗}X_{i}}t^{θadj \binom{v}{w}}W \binom{v}{w} = \frac{J_{1}^{(i,j)}(z(1 − t); q, p)}{J_{0}^{(i,j)}(z(1 − t); q, p) − t} .  (11)

6 Component bijections

To connect the left-hand sides of (10) and (11) with pairs of permutations, we have the following lemma. Lemma 2 For each n ≥ 0, there is a bijection f × g from the set

\{\binom{α, γ}{β, μ} : α, β ∈ S_{n}, γ ∈ C_{i}^{n}(Des α), μ ∈ C_{j}^{n}(Ris β)\}

to the set (N_{i} × N_{j})^{n} such that, if

f × g\binom{α, γ}{β, μ} = \binom{f(α, γ)}{g(β, μ)} = \binom{v}{w},

then ∥γ∥ = ∥v∥, ∥μ∥ = ∥w∥, and

k ∈ Des α^{−1} ⋂ Des β^{−1} ⟺ k ∈ θAdj \binom{v}{w} .  (12)

Moreover, if w = b_{1}b_{2} … b_{n}, we have

β(1) = n whenever b_{n} = 0  (13)

Proof. The bijection f × g is described in terms of two component bijections f and g. The map f sends elements from the set of pairs

{(α, γ) : α ∈ S_{n}, γ ∈ C_{i}^{n}(Des α)}

to the set N_{i}^{n} by

f(α, γ) = γ_{α^{−1}(1)}γ_{α^{−1}(2)} … γ_{α^{−1}(n)} .

The inverse of f is easily described: For v = a_{1}a_{2} … a_{n} ∈ N_{i}^{n} and s ≥ 0, let P_{s}(v) = {r : a_{r} = s}. Furthermore, let ↑ P_{s}(v) denote the increasing word consisting of the integers from P_{s}(v) and ↑ v be the non-decreasing rearrangement of v. Then,

f^{−1}(v) = (↑ P_{0}(v) ↑ P_{1}(v) … ↑ P_{i}(v), ↑ v) .

As an illustration, v = 3 0 3 0 2 2 3 ∈ N_{3}^{7} is mapped to

f^{−1}(3 0 3 0 2 2 3) = (↑ {2, 4} ↑ ∅ ↑ {5, 6} ↑ {1, 3, 7}, ↑ 3 0 3 0 2 2 3)
= (2 4 5 6 1 3 7, 0 0 2 2 3 3 3) .

Note that 0 0 2 2 3 3 3 ∈ C_{3}^{7}({4}). The bijection f^{−1} was previously used by Garsia and Gessel [10] and in [17] in the study of statistics on S_{n}.

As a partial verification of (12), suppose f(α, γ) = a_{1}a_{2} … a_{n} ∈ N_{i}^{n}, that is, γ_{α^{−1}(k)} = a_{k} for 1 ≤ k ≤ n. ¿From the characterization of f^{−1} and from the observation that Des α^{−1} consists of the integers k such that (k + 1) appears to the left of k in α, we have k ∈ Des α^{−1} if and only if a_{k} > a_{k+1}. Also note that ∥γ∥ = ∥a_{1}a_{2} … a_{n}∥.

The bijection g is similarly defined from

{(β, μ) : β ∈ S_{n}, μ ∈ C_{j}^{n}(Ris β)}

to N_{j}^{n} by setting

g(β, μ) = μ_{β^{−1}(1)}μ_{β^{−1}(2)} … μ_{β^{−1}(n)} .

For w = b_{1}b_{2} … b_{n} ∈ N_{j}^{n}, let ↓ P_{s}(w) denote the decreasing word consisting of integers from the set P_{s}(w) = {r : b_{r} = s}. Then,

g^{−1}(w) = (↓ P_{0}(w) ↓ P_{1}(w) … ↓ P_{j}(w), ↑ w) .

The properties of g listed in Lemma 1 are easily verified.

7 Proof of Theorem 1

Using the q-binomial series, the left-hand side of (2) expands as

∑_{n≥0} z^{n} ∑_{i,j≥0} x^{i}y^{j} ∑_{l=0}^{i} ∑_{k=0}^{j} A_{n,l,k} [ \begin{matrix}i − l + n \\ n \end{matrix} ]_{q} [ \begin{matrix}j − k + n \\ n \end{matrix} ]_{p}

where

A_{n,l,k} = ∑ t^{iddes(α,β)}q^{comaj α}p^{corin β}

summed over pairs (α, β) ∈ S_{n}^{2} satisfying des α = l and ris β = k. Combination with Lemma 1 gives

∑_{n≥0} \frac{A_{n}(t, x, y, q, p)z^{n}}{(x; q)_{n+1}(y; p)_{n+1}} = ∑_{i,j≥0} x^{i}y^{j} ∑_{n≥0} z^{n} ∑_{(α,β)∈S_{n}^{2}} t^{iddes(α,β)} ∑ q^{∥γ∥}p^{∥μ∥}

where the last sum is over (γ, μ) ∈ C_{i}^{n}(Des α) × C_{j}^{n}(Ris β). The bijection of Lemma 2 then implies

∑_{n≥0} \frac{A_{n}(t, x, y, q, p)z^{n}}{(x; q)_{n+1}(y; p)_{n+1}} = ∑_{i,j≥0} x^{i}y^{j} ∑_{\binom{v}{w}∈(N_{i}×N_{j})^{∗}}t^{θadj \binom{v}{w}}W \binom{v}{w} .  (14)

In view of (10), the proof of (2) is complete.

To establish (3), begin by noting that (13) implies that f ×g is a bijection from

\{\binom{α, γ}{β, μ} : α, β ∈ S_{n}, β(1) = n, γ ∈ C_{i}^{n}(Des α), μ ∈ C_{j}^{n}(Ris β), μ_{1} = 0\}

to the set (N_{i} × N_{j})^{n−1}X_{i} where X_{i} = N_{i} × N_{0}. Then, by steps similar to those used in deriving (14), it may be shown that

∑_{n≥0} \frac{A_{n+1}^{1}(t, x, y, q, p)z^{n+1}}{(x; q)_{n+2}(y; p)_{n+1}} = ∑_{i,j≥0} x^{i}y^{j} ∑_{\binom{v}{w}∈(N_{i}×N_{j})^{∗}X_{i}}t^{θadj \binom{v}{w}}W \binom{v}{w} .

Together with (11), this implies (3).

8 Other distributions on permutation pairs

With the aim of presenting theorems for finite sequences of permutations, we give the generating functions for some other five-variate distributions on S_{n}^{2}. We first consider (iddes; des, comaj, ris, corin) over pairs (α, β) ∈ S_{n}^{2} with α(1) = n. Let

B_{n}^{1}(t, x, y, q, p) = ∑_{{(α,β)∈S_{n}^{2} : α(1)=n}} t^{iddes(α,β)}x^{des α}q^{comaj α}y^{ris β}p^{corin β} .

The sequence of refined bibasic Bessel functions

F_{ν}^{(i,j)}(z; q, p) = ∑_{n≥0}(−1)^{n}q^{\binom{n+ν}{2}} [ \begin{matrix}i \\ n \end{matrix} ]_{q} [ \begin{matrix}j + n + ν \\ n + ν \end{matrix} ]_{p} z^{n+ν}

plays the role of J_{ν}^{(i,j)}. Actually, F_{0}^{(i+1,j)} = J_{0}^{(i,j)}. Define θ as in (7). Since f × g is a bijection from the set

\{\binom{α, γ}{β, μ} : α, β ∈ S_{n}, α(1) = n, γ ∈ C_{i}^{n}(Des α), γ_{1} = 0, μ ∈ C_{j}^{n}(Ris β)\}

to the set ((N_{i}\{0}) × N_{j})^{n−1}Y_{j} where Y_{j} = N_{0} × N_{j}, computations similar to those of sections 5 and 7 may be used to verify

Theorem 4 The sequence {B_{n+1}^{1}}_{n≥0} is generated by

∑_{n≥0} \frac{B_{n+1}^{1}(t, x, y, q, p)z^{n+1}}{(x; q)_{n+1}(y; p)_{n+2}} = ∑_{i,j≥0} x^{i}y^{j} \frac{F_{1}^{(i,j)}(z(1 − t); q, p)}{F_{0}^{(i+1,j)}(z(1 − t); q, p) − t} .

Next, we determine the distribution of (iddes; des, comaj, des, comaj) over unrestricted and restricted permutation pairs. Define C_{n}(t, x_{1}, x_{2}, q_{1}, q_{2}) and C_{n}^{1}(t, x_{1}, x_{2}, q_{1}, q_{2}) to be

∑_{(α,β)} t^{iddes(α,β)}x_{1}^{des α}q_{1}^{comaj α}x_{2}^{des β}q_{2}^{comaj β}

summed respectively over S_{n}^{2} and over pairs in S_{n}^{2} with β(1) = n. The appropriate sequence of refined bibasic Bessel functions is

G_{ν}^{(i_{1},i_{2})}(z; q_{1}, q_{2}) = ∑_{n≥0}(−1)^{n}q\binom{n+ν}{2}_{1}q\binom{n+ν}{2}_{2} [ \begin{matrix}i_{1} + 1 \\ n + ν \end{matrix} ]_{q_{1}} [ \begin{matrix}i_{2} \\ n \end{matrix} ]_{q_{2}} z^{n+ν} .

Let ϕ be the binary relation on N ×N consisting of the pairs (\binom{i}{j}, \binom{k}{m}) such that i > k and j > m. The map f × f from

\{\binom{α, γ}{β, μ} : α, β ∈ S_{n}, γ ∈ C_{i_{1}}^{n}(Des α), μ ∈ C_{i_{2}}^{n}(Des β)\}

to the set (N_{i_{1}} × N_{i_{2}})^{n} defined by

f × f\binom{α, γ}{β, μ} = \binom{f(α, γ)}{f(β, μ)} = \binom{v}{w}

is a bijection satisfying the properties that ∥γ∥ = ∥v∥, ∥μ∥ = ∥w∥, and

k ∈ Des α^{−1} ⋂ Des β^{−1} ⟺ k ∈ ϕAdj \binom{v}{w} .

Then, proceeding as in sections 5 and 7, we have

Theorem 5 The sequences {C_{n}}_{n≥0} and {C_{n+1}^{1}}_{n≥0} are respectively generated by

∑_{n≥0} \frac{C_{n}(t, x_{1}, x_{2}, q_{1}, q_{2})z^{n}}{(x_{1}; q_{1})_{n+1}(x_{2}; q_{2})_{n+1}} = ∑_{i_{1},i_{2}≥0} x_{1}^{i_{1}}x_{2}^{i_{2}} \frac{1 − t}{G_{0}^{(i_{1},i_{2}+1)}(z(1 − t); q_{1}, q_{2}) − t} ,

∑_{n≥0} \frac{C_{n+1}^{1}(t, x_{1}, x_{2}, q_{1}, q_{2})z^{n+1}}{(x_{1}; q_{1})_{n+2}(x_{2}; q_{2})_{n+1}} = ∑_{i_{1},i_{2}≥0} x_{1}^{i_{1}}x_{2}^{i_{2}} \frac{G_{1}^{(i_{1},i_{2})}(z(1 − t); q_{1}, q_{2})}{G_{0}^{(i_{1},i_{2}+1)}(z(1 − t); q_{1}, q_{2}) − t} .

Finally, we consider the distribution of (iddes; ris, corin, ris, corin). Define D_{n}(t, y_{1}, y_{2}, p_{1}, p_{2}) and D_{n}^{1}(t, y_{1}, y_{2}, p_{1}, p_{2}) to be

∑_{(α,β)} t^{iddes(α,β)}y_{1}^{ris α}p_{1}^{corin α}y_{2}^{ris β}p_{2}^{corin β}

summed respectively over S_{n}^{2} and over pairs in S_{n}^{2} with β(1) = n. Set

H_{ν}^{(j_{1},j_{2})}(z; p_{1}, p_{2}) = ∑_{n≥0}(−1)^{n} [ \begin{matrix}j_{1} + n + ν \\ n + ν \end{matrix} ]_{p_{1}} [ \begin{matrix}j_{2} + n \\ n \end{matrix} ]_{p_{2}} z^{n+ν} .

Take δ to be the binary relation on N × N consisting of the pairs (\binom{i}{j}, \binom{k}{m}) such that i ≥ k and j ≥ m. Using the bijection g × g, we obtain Theorem 6 The sequences {D_{n}}_{n≥0} and {D_{n+1}^{1}}_{n≥0} are respectively generated by

∑_{n≥0} \frac{D_{n}(t, y_{1}, y_{2}, p_{1}, p_{2})z^{n}}{(y_{1}; p_{1})_{n+1}(y_{2}; p_{2})_{n+1}} = ∑_{j_{1},j_{2}≥0} y_{1}^{j_{1}}y_{2}^{j_{2}} \frac{1 − t}{H_{0}^{(j_{1},j_{2})}(z(1 − t); p_{1}, p_{2}) − t} ,

∑_{n≥0} \frac{D_{n+1}^{1}(t, y_{1}, y_{2}, p_{1}, p_{2})z^{n+1}}{(y_{1}; p_{1})_{n+2}(y_{2}; p_{2})_{n+1}} = ∑_{j_{1},j_{2}≥0} y_{1}^{j_{1}}y_{2}^{j_{2}} \frac{H_{1}^{(j_{1},j_{2})}(z(1 − t); p_{1}, p_{2})}{H_{0}^{(j_{1},j_{2})}(z(1 − t); p_{1}, p_{2}) − t} .

9 Permutation sequences

We now consider distributions on finite sequences of permutations. For integers r, s ≥ 0 not both zero, let i = (i_{1}, i_{2}, …, i_{r}) and j = (j_{1}, j_{2}, …, j_{s}). Select U ⊆ {1, 2, …, r} and V ⊆ {1, 2, …, s}. Further let i(U) = (i′_{1}, i′_{2}, …, i′_{r}) where i′_{l} = i_{l} if l ∉ U and i′_{l} = i_{l} + 1 if l ∈ U.

The required multibasic extension of the previously appearing sequences of refined bibasic Bessel functions is defined by

K_{ν}^{(i , j)}(z; U, V) = ∑_{n≥0}(−1)^{n} Q_{1} Q_{2} P_{1} P_{2} z^{n+ν}

where

Q_{1} = ∏_{l∉U} q\binom{n+ν}{2}_{l} [ \begin{matrix}i_{l} + 1 \\ n + ν \end{matrix} ]_{q_{l}} , Q_{2} = ∏_{l∈U} q\binom{n+ν}{2}_{l} [ \begin{matrix}i_{l} \\ n \end{matrix} ]_{q_{l}} ,

P_{1} = ∏_{m∉V} [ \begin{matrix}j_{m} + n + ν \\ n + ν \end{matrix} ]_{p_{m}} , P_{2} = ∏_{m∈V} [ \begin{matrix}j_{m} + n \\ n \end{matrix} ]_{p_{m}} .

For r = s = 1 with U = ∅ and V = {1}, note that K_{ν}^{(i , j)}(z; ∅, {1}) = J_{ν}^{(i_{1} , j_{1})}(z; q_{1}, p_{1}). For r = 2, s = 0, U = {2}, and V = ∅, we have K_{ν}^{(i , j)}(z; {2}, ∅) = G_{ν}^{(i_{1} , i_{2})}(z; q_{1}, q_{2}). Similar choices of r, s, U, and V give the other refined bibasic Bessel functions appearing in section 8.

We define the number of common iddescents of a sequence (\overline{α}; \overline{β}) = (α_{1}, α_{2}, …, α_{r}; β_{1}, β_{2}, …, β_{s}) ∈ S_{n}^{r} × S_{n}^{s} to be

iddes(\overline{α}; \overline{β}) = | ⋂_{k=1}^{r} Des α_{k}^{−1} ⋂ ⋂_{m=1}^{s} Des β_{m}^{−1} | .

Furthermore, set

x^{des \overline{α}} = x_{1}^{des α_{1}}x_{2}^{des α_{2}} … x_{r}^{des α_{r}} and y^{ris \overline{β}} = y_{1}^{ris β_{1}}y_{2}^{ris β_{2}} … y_{s}^{ris β_{s}} .

The symbols q^{comaj \overline{α}} and p^{corin \overline{β}} are to be similarly interpreted. Finally, let

M_{n}(t, U, V) = ∑ t^{iddes(\overline{α};\overline{β})}x^{des \overline{α}}q^{comaj \overline{α}}y^{ris \overline{β}}p^{corin \overline{β}}

where the sum is over all (\overline{α}, \overline{β}) ∈ S_{n}^{r} × S_{n}^{s} with α_{l}(1) = n for l ∈ U and β_{m}(1) = n for m ∈ V. Then, the map f^{(r)} × g^{(s)} consisting of r copies of the component bijection f and s copies of the component bijection g along with judicious use of the analysis of sections 5 and 7 imply our theorems on permutation sequences:

Theorem 7 The sequence {M_{n}(t, ∅, ∅)}_{n≥0} is generated by

∑_{n≥0} \frac{M_{n}(t, ∅, ∅)z^{n}}{(x; q)_{n+1}(y; p)_{n+1}} = ∑_{i,j≥0} x^{i}y^{j} \frac{(1 − t)}{K_{0}^{(i(U) , j)}(z(1 − t); U, V) − t}

where (x; q)_{n} = (x_{1}; q_{1})_{n} ⋯ (x_{r}; q_{r})_{n} and (y; p)_{n} = (y_{1}; p_{1})_{n} ⋯ (y_{s}; p_{s})_{n}.

Theorem 8 Provided that U and V are not both empty and their complements are not both empty, the sequence {M_{n+1}(t, U, V)}_{n≥0} is generated by

∑_{n≥0} \frac{M_{n+1}(t, U, V)z^{n+1}}{(x, y; q, p)_{n+2}^{c}(x, y; q, p)_{n+1}} = ∑_{i, j≥0} x^{i}y^{j} \frac{K_{1}^{(i , j)}(z(1 − t))}{K_{0}^{(i(U) , j)}(z(1 − t); U, V) − t}

where (x, y; q, p)_{n}^{c} = ∏_{l∉U}(x_{l}; q_{l})_{n} ∏_{m∉V} (y_{m}; p_{m})_{n} and (x, y; q, p)_{n} = ∏_{l∈U}(x_{l}; q_{l})_{n} ∏_{m∈V} (y_{m}; p_{m})_{n}.

Taking the limit as x, y → 1 and setting q_{i} = 1, 1 ≤ i ≤ r, in Theorem 7 gives a result equivalent to one obtained by Stanley [18].

References

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

[2] L. Carlitz, q-Bernoulli numbers and Eulerian numbers, Trans. Amer. Math. Soc. 76 (1954) 332-350.

[3] L. Carlitz, A combinatorial property of q-Eulerian numbers, Amer. Math. Monthly 82 (1975) 51-54.

[4] L. Carlitz, R. Scoville, and T. Vaughan, Enumeration of pairs of permutations, Discrete Math. 14 (1976) 215-239.

[5] M. P. Delest and J. M. Fedou, Enumeration of skew Ferrers’ diagrams, Discrete Math. 112 (1993) 65-79.

[6] J. M. Fedou and D. P. Rawlings, Statistics on pairs of permutations, Discrete Math. (to appear).

[7] J. M. Fedou and D. P. Rawlings, Adjacencies in words, Adv. in Appl. Math. (to appear).

[8] D. Foata, Distributions Eulériennes et Mahoniennes sur le groupe des permutations, Higher Combinatorics, Proceedings, ed. M. Aigner, Reidel Publ. Co., Dodrecht, Holland (1977) 27-49.

[9] A. M. Garsia, On the maj and inv q-analogues of Eulerian polynomials, J. Lin. and Multilin. Alg. 8 (1980) 21-34.

[10] A. M. Garsia and I. Gessel, Permutation statistics and partitions, Adv. in Math. 31 (1979) 288-305.

[11] G. Gasper and M. Rahman, Basic Hypergeometric Series, Cambridge Univ. Press 1990.

[12] I. M. Gessel, Generating Functions and Enumeration of Sequences, Doctoral thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts 1977.

[13] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley & Sons 1983.

[14] M. E. H. Ismail, The zeros of basic Bessel functions, …, J. Math. Annal. and Appl. 86 (1982) 1-19.

[15] F. H. Jackson, The basic gamma function and elliptic functions, Proc. Royal Soc. A 76 (1905) 127-144.

[16] M. P. MacMahon, Combinatory Analysis, Cambridge Univ. Press 1915 (reprinted by Chelsea 1960).

[17] D. P. Rawlings, Generalized Worpitzky identities with applications to permutation enumeration Europ. J. Comb. Theory 2 (1981) 67-78.

[18] R. P. Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Comb. Theory (A) 20 (1976) 336-356.

[19] R. P. Stanley, Enumerative Combinatorics Vol. I, Wadsworth & Brooks 1986.

[20] X. G. Viennot, Heaps of pieces I: Basic definitions and combinatorial lemmas, in Combinatoire Énumérative, eds. G. Labelle and P. Leroux, Lect. Notes in Math. 1234, Springer-Verlag, Berlin 1986.

[21] D. Zeilberger, Enumeration of words by their number of mistakes, Discrete Math. 34 (1981) 89-92.