\documentstyle[12pt]{article} \begin{document} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 1 (1994), \#Xnn\hfill} \thispagestyle{empty} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 1 (1994), \#R11\hfill} \thispagestyle{empty} \pagebreak \begin{titlepage} \title{More Statistics on Permutation Pairs \thanks{This work is partially supported by EC grant CHRX-CT93-0400 and PRC Maths-Info} } \author{Jean-Marc Fedou \\ Laboratoire Bordelais de Recherches en Informatique \\ Universit\'{e} Bordeaux I \\ 33405 Talence, France \and Don Rawlings \thanks{Financial support provided by LaBRI, Universit\'{e} Bordeaux I} \\ Mathematics Department \\ California Polytehnic State University \\ San Luis Obispo, Ca. 93407 \date{ Submitted: June 30, 1994; Accepted: October 21, 1994}} \maketitle \begin{abstract} \noindent Two inversion formulas for enumerating words in the free monoid by $\theta$-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. \end{abstract} \end{titlepage} \section{Introduction} The study of statistics on permutation pairs was initiated by Carlitz, Scoville, and Vaughan \cite{CSV}. Stanley \cite{St} $q$-extended their work to finite sequences of permutations. In \cite{FR2}, 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 \cite{FR3}. For clarity, we primarily focus on permutation pairs. Let $S_n$ denote the symmetric group on $\{1,2, \ldots ,n \}$. For a permutation $\sigma = \sigma(1)\sigma(2) \cdots \sigma(n) \in S_n$, the {\em descent} and {\em rise} sets are defined as \def\Des{\mathop{\rm Des}\nolimits} \def\Ris{\mathop{\rm Ris}\nolimits} \def\des{\mathop{\rm des}\nolimits} \def\ris{\mathop{\rm ris}\nolimits} \def\maj{\mathop{\rm maj}\nolimits} \def\comaj{\mathop{\rm comaj}\nolimits} \def\rin{\mathop{\rm rin}\nolimits} \def\iddes{\mathop{\rm iddes}\nolimits} \def\corin{\mathop{\rm corin}\nolimits} \begin{eqnarray*} \Des \sigma = \{i: 1 \leq i \leq n-1,\: \sigma(i) > \sigma(i+1)\} \; , \\*[.3cm] \Ris \sigma = \{i: 1 \leq i \leq n-1,\: \sigma(i) < \sigma(i+1)\} \; . \nonumber \end{eqnarray*} These sets are of course complementary relative to $\{1,2, \ldots ,n-1\}$. The {\em descent} and {\em rise numbers} of $\sigma$ are respectively defined to be the cardinalities of $\Des \sigma$ and $\Ris \sigma$, that is, \begin{eqnarray} \des \sigma = |\Des \sigma| & {\rm and} & \ris \sigma = |\Ris \sigma| \; . \nonumber \end{eqnarray} Furthermore, let \begin{eqnarray} \begin{array}{llll} \displaystyle \maj \sigma=\sum_{k \in \Des \sigma} k \;, & & & \displaystyle \comaj \sigma=\sum_{k \in \Des \sigma} (n-k) \;, \nonumber \\*[.5cm] \displaystyle \rin \sigma=\sum_{k \in \Ris \sigma} k \;, & & & \displaystyle \corin\, \sigma=\sum_{k \in \Ris \sigma} (n-k) \;. \nonumber \end{array} \end{eqnarray} The statistics in the first column were originally referred to as the {\em greater} and {\em lesser indices} by Major MacMahon \cite{Mac}. Many authors have since adopted the term {\em major index} for the former. Being the sum of the rise indices, we will refer to $\rin \sigma$ as the {\em rise index}. The statistics of the second column will respectively be called the {\em comajor} and {\em corise indices}. Since $\Des \sigma$ and $\Ris \sigma$ are complementary, $\des \sigma+\ris \sigma=n-1$, $\maj \sigma + \rin \sigma = {n \choose 2}$, and $\comaj \sigma + \corin \sigma = {n \choose 2}$. We also consider the {\em number of common iddescents} of a permutation pair; for $(\alpha,\beta)$ in the cartesian product $S^2_n=S_n \times S_n$, let \begin{eqnarray} \iddes (\alpha,\beta) = | \Des \alpha^{-1} \; \bigcap \; \Des \beta^{-1} | \nonumber \end{eqnarray} where $\sigma^{-1}$ denotes the inverse of $\sigma$. \pagebreak Our initial results involve the first two terms of a sequence $\{J_\nu^{(i,j)}\}_{\nu \geq 0}$ of {\em refined bibasic Bessel functions}. For a positive integer $n$, let \[ (a;q)_n = (1-a)(1-aq) \cdots (1-aq^{n-1}) \;. \] By convention, $(a;q)_0=1$. The {\em $q$-binomial coefficient} (or {\em Gaussian polynomial}\,) is defined to be \[ \left[ \! \begin{array}{c} n\\ k \end{array} \! \right]_q = \frac{(q;q)_n}{(q;q)_k(q;q)_{n-k}} \;\; \] when $0 \leq k \leq n$ and to be 0 when $k>n$. The function $J_\nu^{(i,j)}$ is defined as \begin{eqnarray} J_\nu^{(i,j)}(z;q,p)=\sum_{n \geq 0} (-1)^n q^{{n+\nu \choose 2}} \left[ \! \begin{array}{c} i+1\\ n+\nu \end{array} \! \right]_q \left[ \! \begin{array}{c} j+n\\ n \end{array} \! \right]_p z^{n+\nu} \;. \nonumber \end{eqnarray} A few properties of $\{J_\nu^{(i,j)}\}_{\nu \geq 0}$ are worth immediate remark. First, $J_0^{(i-1,j)}$ is a Hadamard product of the two series appearing in the {\em q-binomial theorem} and {\em q-binomial series} (\cite[p.\ 36]{andrews}): \begin{description} \item[q-Binomial Theorem] $\; (t;q)_i=\sum_{n \geq 0} (-1)^n q^{{n \choose 2}} \left[ \! \begin{array}{c} i\\ n \end{array} \! \right]_q t^n \;\; . $ \item[q-Binomial Series] For $|q|,|t|<1$, $\; 1/(t;q)_{j+1}=\sum_{n \geq 0} \left[ \! \begin{array}{c} j+n\\ n \end{array} \! \right]_q t^n \;\; . $ \end{description} 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_\nu(z;q,p) = \lim_{i,j \rightarrow \infty} J_\nu^{(i,j)}(z;q,p) = \sum_{n \geq 0} \frac{(-1)^nq^{{n+\nu \choose 2}}z^{n+\nu}}{(q;q)_{n+\nu}(p;p)_{n}} \] arise in a variety of other contexts. As demonstrated by Delest and Fedou \cite{DF}, the coefficient of $q^mz^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 \cite[p.\ 9]{GR}, often denoted by $E_q(z)$. Finally, omitting $q^{{n+\nu \choose 2}}$ and replacing $z^{n+\nu}$ in the series $J_\nu(z;q,q)$ by $(z/2)^{2n+\nu}$ gives one of the sequences of {\em q-Bessel} (or {\em basic Bessel}\/) functions originally studied by Jackson \cite{J} and further explored by Ismail \cite{I}. Thus, $J^{(i,j)}_\nu(z;q,p)$ is indeed a refined {\em 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 $(\alpha,\beta) \in S_n^2$ with $\beta(1)=n$. In sections 3 through 7, we prove \newtheorem{theorem}{Theorem} \newtheorem{corollary}{Corollary} \begin{theorem} The generating functions for the sequences \begin{eqnarray} \begin{array}{c} A_n(t,x,y,q,p)=\displaystyle \sum_{(\alpha,\beta) \in {S_n^2}} t^{\iddes(\alpha, \beta)} x^{\des \alpha} q^{\comaj \alpha} y^{\ris \beta} p^{\corin \beta} \; , \\*[.7cm] A^1_n(t,x,y,q,p)=\displaystyle \sum_{\{(\alpha,\beta) \in {S_n^2} \; : \; \beta(1)=n\}} t^{\iddes(\alpha, \beta)} x^{\des \alpha} q^{\comaj \alpha} y^{\ris \beta} p^{\corin \beta} \end{array} \end{eqnarray} are \begin{eqnarray} \sum_{n \geq 0} \frac{A_n(t,x,y,q,p)z^n}{(x;q)_{n+1}(y;p)_{n+1}}= \sum_{i,j \geq 0} x^iy^j \, \frac{1-t}{J_0^{(i,j)}(z(1-t);q,p)-t} \;\; , \\*[.4cm] \sum_{n \geq 0} \frac{A^1_{n+1}(t,x,y,q,p)z^{n+1}}{(x;q)_{n+2}(y;p)_{n+1}}= \sum_{i,j \geq 0} x^iy^j \,\frac{J_1^{(i,j)}(z(1-t);q,p)}{J_0^{(i,j)}(z(1-t);q,p)-t} \;\;.\end{eqnarray} \end{theorem} 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 $(\alpha,\beta) \in S_n^2$ satisfying $\alpha(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_\nu^{(i,j)}$. In section 9, we give two theorems for finite sequences of permutations which contain the ones for permutation pairs as special cases. \section{Selected Corollaries} Multiplying (2) and (3) through by $(1-x)(1-y)$ and then taking the limit as $x,y \rightarrow 1^-$ leads respectively to the following corollaries: \begin{corollary} The distribution of $(\iddes;\comaj,\corin)$ on $S_n^2$ is generated by \begin{eqnarray*} \sum_{n \geq 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} \;\;.\end{eqnarray*} \end{corollary} \begin{corollary} The distribution of $(\iddes;\comaj,\corin)$ on pairs $(\alpha,\beta) \in S_{n+1}^{2}$ satisfying the condition $\beta(1)=n+1$ is generated by \begin{eqnarray*} \sum_{n \geq 0} \frac{A^1_{n+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} \;\;. \end{eqnarray*} \end{corollary} These corollaries are equivalent to special cases of Theorems 2 and 4 in \cite{FR2}. Several equivalent distributions are discussed in section 4 of \cite{FR2}. Corollary 1 is essentially due to Stanley \cite{St}. Further replacing $z$ by $z(1-q)(1-p)$ in Corollary 1 and letting $q,p \rightarrow 1^-$ gives the initial result on permutation pairs due to Carlitz et al.\ \cite{CSV}: \begin{corollary} The distribution of $\iddes$ over $S^2_n$ is generated by \begin{eqnarray*} \sum_{n \geq 0} \frac{A_n(t,1,1,1,1)z^n}{n!n!}= \frac{1-t}{\sum_{n \geq 0} (-1)^nz^n/n!n! \;\; -\;\; t} \;\;.\end{eqnarray*} \end{corollary} By appropriately selecting the values of various parameters, it is also possible to obtain generating functions for the analogues of the {\em Eulerian polynomials} of Carlitz \cite{C1,C2} and of Stanley \cite{St} respectively defined by \[ C_n(y,p)=\sum_{\sigma \in S_n} y^{\ris \sigma} p^{\rin \sigma} \;\; {\rm and} \;\; S_n(t,q)=\sum_{\sigma \in S_n} t^{\des \sigma}q^{{\rm inv}\, \sigma} \] where ${\rm inv}\, \sigma$ denotes the number of inversions of $\sigma$, that is, the number of pairs $(i,j)$ such that $1 \leq i\sigma(j)$. The bijective techniques of Foata \cite{Fo1} may be easily adapted to show that \[ C_n(y,p)=\sum_{\sigma \in S_n} y^{\ris \sigma} p^{\corin \sigma} \;\; {\rm and} \;\; S_n(t,q)=\sum_{\sigma \in S_n} t^{{\rm ides}\, \sigma}q^{\comaj \sigma} \] where ${\rm ides}\, \sigma=\des \sigma^{-1}$. When $x=0$, the only pairs contributing non-zero weight in (1) are of the form $(12 \ldots n,\beta)$. 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): \begin{corollary} The distribution of $(\ris, \corin)$ over $S_n$ is generated by \begin{eqnarray*} \sum_{n \geq 0} \frac{C_n(y,p)z^n}{(y;p)_{n+1}}=\sum_{j \geq 0} \frac{y^j}{1-[j+1]_p \, z} \end{eqnarray*} where $[j+1]_p=(1-p^j)/(1-p)$. \end{corollary} \begin{corollary}[Stanley] The distribution of $(\des, {\rm inv})$ on $S_n$ is generated by \begin{eqnarray*} \sum_{n \geq 0} \frac{S_n(t,q)z^n}{(q;q)_{n}}= \frac{1-t}{E_q(-z(1-t))-t} \end{eqnarray*} where $E_q(z)=J_0(-z;q,0)$. \end{corollary} Another generating function for $C_n(y,p)$ was given by Garsia \cite{G}. \section{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 {\em free monoid}. Let ${\cal A}$ be an {\em alphabet}, that is, a non-empty set whose elements are referred to as {\em letters}. A finite sequence (possibly empty) $w=a_1a_2 \ldots a_n$ of $n$ letters is said to be a {\em word} of {\em 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 ${\cal A}$ along with the concatenation product is known as the {\em free monoid} generated by ${\cal A}$ and is denoted by ${\cal A^*}$. We let ${\cal A}^n$ signify the set of words in ${\cal A^*}$ of length $n$. To state the needed partition result, we select the alphabet $N$ of non-negative integers and let ${ N_{{ r}}}=\{0,1,2, \ldots, r \}$. For $w=a_1a_2 \ldots a_{n} \in { N^n}$, set \[ \|w\|=a_1 + a_2 + \ldots + a_{n} \; .\] For $K \subseteq \{1,2, \ldots ,n-1\}$, a partition belonging to the set \def\ind{\mathop{\rm ind}\nolimits} \[ {\cal C}^n_r(K)=\{ \gamma = \gamma_1 \gamma_2 \ldots \gamma_n \in N^{n}_{r}: \gamma_1 \leq \gamma_2 \leq \ldots \leq \gamma_n, \; \gamma_k < \gamma_{k+1} \; {\rm if} \; k \in K\} \] has at most $n$ parts (each bounded by $r$) and is said to be {\em compatible with $K$}. \pagebreak We define the {\em index} of a set $K \subseteq \{1,2, \ldots ,n-1\}$ to be \[\ind K= \sum_{k \in K} (n-k) \;\;. \] For $\sigma \in S_n$, note that $\ind(\Des \sigma)= \comaj \sigma$ and $\ind(\Ris \sigma)= \corin \sigma$. The key partition result for the coming argumentation is \newtheorem{lemma}{Lemma} \begin{lemma} For $K \subseteq \{1,2, \ldots ,n-1\}$ and $r$ a non-negative integer, \begin{eqnarray*} \sum_{\gamma \in {\cal C}^{n}_{r}(K)} q^{\| \gamma \|}=q^{\ind K} \left[ \! \begin{array}{c} r-|K|+n\\ n \end{array} \! \right]_q \;\; . \end{eqnarray*} \end{lemma} {\em Proof.}\/ This is a trivial consequence of a well-known result in the theory of partitions. As may be referenced in \cite[p. 33]{andrews}, \begin{eqnarray} \sum_{0 \leq \lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n \leq s} q^{\| \lambda \|}= \left[ \! \begin{array}{c} s+n\\ n \end{array} \! \right]_q \end{eqnarray} where $ \lambda = \lambda_1 \lambda_2 \ldots \lambda_n$. Suppose $\gamma= \gamma_1 \gamma_2 \ldots \gamma_n \in {\cal C}^{n}_{r}(K)$. The bijection $\gamma_1 \gamma_2 \ldots \gamma_n \rightarrow \lambda_1 \lambda_2 \ldots \lambda_n$ defined by $\lambda_j=(\gamma_j-|\{i \in K: i < j\}|)$ satisfies the properties that $0 \leq \lambda _1 \leq \lambda_2 \leq \ldots \leq \lambda_n \leq (r-|K|)$ and $\| \gamma \| = \| \lambda \| + \ind K$. The desired result then follows from (4). \def\Adj{\mathop{\rm Adj}\nolimits} \def\adj{\mathop{\rm adj}\nolimits} \section{Words by $\theta$-adjacencies} The essence of our proof to Theorem 1 relies on two inversion theorems that enumerate words in the free monoid by $\theta$-{\em adjacencies}. Let $\theta$ be a binary relation on the alphabet ${\cal A}$. A word $w=a_1a_2 \ldots a_n \in {\cal A}^n$ is said to have a {\em $\theta$-adjacency} in position $k$ if $a_k \theta a_{k+1}$. The {\em set of $\theta$-adjacencies} and the {\em number of $\theta$-adjacencies} of $w=a_1a_2 \ldots a_n$ are respectively denoted by \[ \theta\!\Adj w = \{k: 1 \leq k \leq n-1,\, a_k \theta a_{k+1}\} \; \; {\rm and } \;\; \theta\! \adj w = |\theta \! \Adj w| \;\; . \] An element of the set ${\cal T}_{{\cal A}, \theta}=\{w=a_1a_2 \ldots a_{l(w)} \in {\cal A^*}: a_1 \theta a_2 \theta \ldots \theta a_{l(w)} \}$ is said to be a $\theta$-{\em chain}. We let ${\cal T}_{{\cal A},\theta}^+$ denote the set of $\theta$-chains of positive length. In $Z[t]<<{\cal A}>>$, the algebra of formal power series on ${\cal A^*}$ with coefficients from the ring of polynomials in $t$ having integer coefficients, the following inversion formulas hold: \begin{theorem} Words by $\theta$-adjacencies are generated by \begin{eqnarray*} \sum_{w \in {\cal A^*}} t^{\theta\! \adj w} w = \frac{1}{ 1 + \sum_{w \in {\cal T}_{{\cal A},\theta}^+} \, (-1)^{l(w)}(1-t)^{l(w)-1}w } \;\; . \end{eqnarray*} \end{theorem} \begin{theorem} For a non-empty set $X \subseteq {\cal A}$, let ${\cal A^*}X=\{ va \in {\cal A^*}: a \in X \}$. Then, words ending in a letter from $X$ by $\theta$-adjacencies are generated by \begin{eqnarray*} \sum_{w \in {\cal A^*}X} t^{\theta\! \adj w} w = \frac{- \sum_{w \in {\cal T}_{{\cal A}, \theta}X} \, (-1)^{l(w)}(1-t)^{l(w)-1}w } { 1 + \sum_{w \in {\cal T}_{{\cal A},\theta}^+} \, (-1)^{l(w)}(1-t)^{l(w)-1} w} \;\; \end{eqnarray*} where ${\cal T}_{{\cal A}, \theta}X=\{ va \in {\cal T}_{{\cal A}, \theta}: a \in 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). \end{theorem} A number of related theories of inversion \cite{Ge,GJ,St,XV1,Z} 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 \cite{FR3}. \section{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 \begin{eqnarray} \sum_{w \in {\cal A^*}} t^{\theta\! \adj w} w = \frac{1-t}{\sum_{w \in {\cal T}_{{\cal A}, \theta}} \, (-1)^{l(w)}(1-t)^{l(w)}w \; - \; t }\;\; , \\*[.4cm] \sum_{w \in {\cal A^*}X} t^{\theta\! \adj w} w = \frac{- \sum_{w \in {\cal T}_{{\cal A}, \theta}X} \, (-1)^{l(w)}(1-t)^{l(w)}w}{\sum_{w \in {\cal T}_{{\cal A}, \theta}} \, (-1)^{l(w)}(1-t)^{l(w)} w \; - \; t} \;\; . \end{eqnarray} Next, let $\theta$ be the binary relation on ${ N} \times { N}$ consisting of the pairs $ \left( {i \choose j},{k \choose m} \right)$ satisfying $i > k$ and $j \geq m$; \begin{eqnarray} {i \choose j} \theta { k \choose m} \iff i>k \; {\rm and} \; j \geq m\;. \end{eqnarray} Thus, the set of $\theta$-adjacencies for a {\em biword} ${v \choose w}={a_1a_2 \ldots a_n \choose b_1b_2 \ldots b_n} \in ({N} \times {N})^n$ is \begin{eqnarray*} \theta \! \Adj {v \choose w}= \{ k: 1 \leq k \leq n-1,\, a_k > a_{k+1}, \, b_{k} \geq b_{k+1} \} \;. \end{eqnarray*} Moreover, ${v \choose w}={a_1a_2 \ldots a_n \choose b_1b_2 \ldots b_n} \in (N_i \times N_j)^n$ is a $\theta$-chain if and only if \begin{eqnarray}i \geq a_1 > a_2 > \ldots > a_n \; \; {\rm and} \; \; j \geq b_1 \geq b_2 \geq \ldots \geq b_n. \end{eqnarray} As will be seen, the crucial step in establishing Theorem 1 is the evaluation of \begin{eqnarray*} \sum_{ {v \choose w} \in (N_i \times N_j)^*} \! t^{\theta \! \adj {v \choose w}} W{v \choose w} \;\; {\rm and} \;\; \sum_{ {v \choose w} \in (N_i \times N_j)^*X_i} \! t^{\theta \! \adj {v \choose w}} W{v \choose w} \end{eqnarray*} where $X_i$ denotes the set of {\em biletters} $N_i \times N_0 = \{ {k \choose 0}: 0 \leq k \leq i \}$ and where $W$ is the homomorphism on ${(N \times N)^*}$ obtained by multiplicatively extending the weight $W{i \choose j}=q^ip^jz$ defined on each ${i \choose j} \in N \times N$. In view of (5) and (6), this can be accomplished by computing a sum of the form \begin{eqnarray} \sum (-1)^{l{v \choose w}}(1-t)^{l{v \choose w}} W {v \choose w} \end{eqnarray} twice; once summed over the set ${\cal T}_{{N}_i \times {N}_j,\theta }$ of $\theta$-chains in $({N}_i \times {N}_j)^*$ and once summed over the set ${\cal T}_{{N_{i}} \times N_{j},\theta }X_i$ of $\theta$-chains ending in a biletter from $X_i$. By (8), expression (9) summed over ${\cal T}_{{N}_i \times {N}_j, \theta}$ is equal to \[ \sum_{n \geq 0} (-1)^n(1-t)^nz^n \sum_{i \geq a_1 > a_2 > \ldots > a_n \geq 0} q^{\|v\|} \sum_{j \geq b_1 \geq b_2 \geq \ldots \geq b_n \geq 0} p^{\|w\|} \] which, by Lemma 1, reduces to \begin{eqnarray} \sum_{n \geq 0} (-1)^n q^{{n \choose 2}} \left[ \! \begin{array}{c} i+1\\ n \end{array} \! \right]_q \left[ \! \begin{array}{c} j+n\\ n \end{array} \! \right]_p (1-t)^n z^{n} = J_0^{(i,j)}(z(1-t);q,p)\;. \nonumber \end{eqnarray} Summarizing, we have established that \begin{eqnarray*} \sum_{ {v \choose w} \in {\cal T}_{{N}_i \times {N}_j, \theta}} (-1)^{l{v \choose w}}(1-t)^{l{v \choose w}} W {v \choose w} = J_0^{(i,j)}(z(1-t);q,p)\;. \end{eqnarray*} Similarly, \begin{eqnarray*} \sum_{ {v \choose w} \in {\cal T}_{{N_{i}} \times {N_{ j}}, \theta }X_i} (-1)^{l{v \choose w}}(1-t)^{l{v \choose w}} W {v \choose w} = - J_1^{(i,j)}(z(1-t);q,p)\;. \end{eqnarray*} The last two identities together with (5) and (6) imply \begin{eqnarray} \sum_{ {v \choose w} \in (N_i \times N_j)^*} \! t^{\theta\! \adj {v \choose w}} W{v \choose w} = \frac{1-t}{J_0^{(i,j)}(z(1-t);q,p)\; -\; t} \;\; , \end{eqnarray} \begin{eqnarray} \sum_{ {v \choose w} \in (N_i \times N_j)^*X_i} \! t^{\theta\! \adj {v \choose w}} W{v \choose w} = \frac{J_1^{(i,j)}(z(1-t);q,p)}{J_0^{(i,j)}(z(1-t);q,p)\; - \; t} \; . \end{eqnarray} \section{Component bijections} To connect the left-hand sides of (10) and (11) with pairs of permutations, we have the following lemma. \begin{lemma} For each $n \geq 0$, there is a bijection $f \times g$ from the set \[ \{ {\alpha,\gamma \choose \beta,\mu}: \alpha,\beta \in S_n, \, \gamma \in {\cal C}^n_i(\Des \alpha), \, \mu \in {\cal C}^n_{ j}(\Ris \beta) \} \] to the set $(N_i \times N_j)^n$ such that, if \[ f \times g {\alpha,\gamma \choose \beta, \mu} = {f(\alpha,\gamma) \choose g(\beta, \mu)}={v \choose w} , \] then $ \| \gamma \| = \| v \|$, $\| \mu \| = \| w \|$, and \begin{eqnarray} k \in \Des \alpha^{-1} \bigcap \Des \beta^{-1} \iff k \in \theta \! \Adj{v \choose w} \;. \end{eqnarray} Moreover, if $w=b_1b_2 \ldots b_n$, we have \begin{eqnarray} \beta (1) = n \; \; {\rm whenever} \; \; b_n=0 \end{eqnarray} \end{lemma} \noindent {\em Proof}. The bijection $f \times g$ is described in terms of two {\em component} bijections $f$ and $g$. The map $f$ sends elements from the set of pairs \[ \{ (\alpha, \gamma): \alpha \in S_n, \gamma \in {\cal C}^n_i(\Des \alpha)\} \] to the set ${N_i^n}$ by \[ f(\alpha,\gamma)=\gamma_{\alpha^{-1}(1)}\gamma_{\alpha^{-1}(2)} \ldots \gamma_{\alpha^{-1}(n)} \;\; . \] The inverse of $f$ is easily described: For $v = a_1a_2 \ldots a_n \in { N_i^n}$ and $s \geq 0$, let $P_s(v)=\{r:a_r=s\}$. Furthermore, let $\uparrow P_s(v)$ denote the increasing word consisting of the integers from $P_s(v)$ and $\uparrow v$ be the non-decreasing rearrangement of $v$. Then, \[ f^{-1}(v)= (\uparrow P_0(v) \, \uparrow P_1(v) \ldots \uparrow P_i(v), \uparrow v) \;\; .\] As an illustration, $v = 3\,0\,3\,0\,2\,2\,3 \in { N_{\rm 3}^{\rm 7}}$ is mapped to \begin{eqnarray*} f^{-1}(3\,0\,3\,0\,2\,2\,3) & = & (\uparrow \{2,4\} \, \uparrow \emptyset \, \uparrow \{5,6\} \, \uparrow \{1,3,7\} ,\uparrow 3\,0\,3\,0\,2\,2\,3) \\ & = & (2\,4\,5\,6\,1\,3\,7,0\,0\,2\,2\,3\,3\,3) \;\; . \end{eqnarray*} Note that $0\,0\,2\,2\,3\,3\,3 \in {\cal C^{\rm 7}_{\rm 3}}(\{4\})$. The bijection $f^{-1}$ was previously used by Garsia and Gessel \cite{GG} and in \cite{DPR} in the study of statistics on $S_n$. As a partial verification of (12), suppose $f(\alpha,\gamma)=a_1a_2\ldots a_n \in { N}_i^n$, that is, $\gamma_{\alpha^{-1}(k)}=a_k$ for $1 \leq k \leq n$. From the characterization of $f^{-1}$ and from the observation that $\Des \alpha^{-1}$ consists of the integers $k$ such that $(k+1)$ appears to the left of $ k$ in $\alpha$, we have $ k \in \Des \alpha^{-1}$ if and only if $a_k > a_{k+1}$. Also note that $\| \gamma \|= \|a_1a_2\ldots a_n\|$. The bijection $g$ is similarly defined from \[ \{ (\beta, \mu): \beta \in S_n, \mu \in {\cal C}^n_j (\Ris \beta)\} \;\; \] to ${ N^{n}_{j}}$ by setting \[ g(\beta,\mu)=\mu_{\beta^{-1}(1)} \mu_{\beta^{-1}(2)} \ldots \mu_{\beta^{-1}(n)} \;\; .\] For $w=b_1b_2 \ldots b_n \in { N^n_j}$, let $\downarrow P_s(w)$ denote the decreasing word consisting of integers from the set $P_s(w)=\{r: b_r=s\}$. Then, \[ g^{-1}(w)= (\downarrow P_0(w) \, \downarrow P_1(w) \ldots \downarrow P_j(w), \uparrow w) \;\; .\] The properties of $g$ listed in Lemma 1 are easily verified. \section{Proof of Theorem 1} Using the $q$-binomial series, the left-hand side of (2) expands as \[ \sum_{n \geq 0}z^{n} \sum_{i,j \geq 0} x^iy^j \sum_{l=0}^i \sum_{k=0}^j A_{n,l,k} \left[ \! \begin{array}{c} i-l +n\\ n \end{array} \! \right]_q \left[ \! \begin{array}{c} j-k +n\\ n \end{array} \! \right]_p \] where \[ A_{n,l,k}= \sum t^{\iddes(\alpha,\beta)}q^{\comaj \alpha}p^{\corin \beta} \] summed over pairs $(\alpha,\beta) \in S_n^2$ satisfying $\des \alpha = l$ and $\ris \beta =k$. Combination with Lemma 1 gives \begin{eqnarray*} \sum_{n \geq 0} \frac{A_{n}(t,x,y,q,p)z^{n}}{(x;q)_{n+1}(y;p)_{n+1}} = \sum_{i,j \geq 0} x^iy^j \sum_{n \geq 0}z^{n} \sum_{(\alpha,\beta) \in S_n^2} t^{\iddes(\alpha,\beta)} \sum q^{\|\gamma \|} p^{\| \mu \|} \end{eqnarray*} where the last sum is over $(\gamma,\mu) \in {\cal C}^n_i (\Des \alpha) \times {\cal C}^n_j(\Ris \beta)$. The bijection of Lemma 2 then implies \begin{eqnarray} \sum_{n \geq 0} \frac{A_{n}(t,x,y,q,p)z^{n}}{(x;q)_{n+1}(y;p)_{n+1}} = \sum_{i,j \geq 0} x^iy^j \sum_{ {v \choose w} \in (N_i \times N_j)^*} \! t^{\theta\! \adj {v \choose w}} W {v \choose w} \;. \end{eqnarray} In view of (10), the proof of (2) is complete. To establish (3), begin by noting that (13) implies that $f \times g$ is a bijection from \[ \{ {\alpha,\gamma \choose \beta,\mu}: \alpha,\beta \in S_{n}, \, \beta(1)=n, \, \gamma \in {\cal C}^n_i(\Des \alpha), \, \mu \in {\cal C}^n_j(\Ris \beta), \, \mu_1=0 \} \] to the set $(N_i \times N_j)^{n-1}X_i$ where $X_i=N_i \times N_0$. Then, by steps similar to those used in deriving (14), it may be shown that \begin{eqnarray*} \sum_{n \geq 0} \frac{A^1_{n+1}(t,x,y,q,p)z^{n+1}}{(x;q)_{n+2}(y;p)_{n+1}} = \sum_{i,j \geq 0} x^iy^j \sum_{ {v \choose w} \in (N_i \times N_j)^*X_i} \! t^{\theta\! \adj {v \choose w}} W{v \choose w} \;. \end{eqnarray*} Together with (11), this implies (3). \section{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 $(\alpha,\beta) \in S^2_{n}$ with $\alpha(1)=n$. Let \begin{eqnarray*} B^1_{n}(t,x,y,q,p)=\displaystyle \sum_{\{(\alpha,\beta) \in {S_{n}^2} \; : \; \alpha(1)=n\}} t^{\iddes(\alpha, \beta)} x^{\des \alpha} q^{\comaj \alpha} y^{\ris \beta} p^{\corin \beta} \;\;. \end{eqnarray*} The sequence of refined bibasic Bessel functions \begin{eqnarray} F_\nu^{(i,j)}(z;q,p)=\sum_{n \geq 0} (-1)^n q^{{n+\nu \choose 2}} \left[ \! \begin{array}{c} i\\ n \end{array} \! \right]_q \left[ \! \begin{array}{c} j+n+\nu\\ n+\nu \end{array} \! \right]_p z^{n+\nu} \nonumber \end{eqnarray} plays the role of $J_\nu^{(i,j)}$. Actually, $F_0^{(i+1,j)} = J_0^{(i,j)}$. Define $\theta$ as in (7). Since $f \times g$ is a bijection from the set \[ \{ {\alpha,\gamma \choose \beta,\mu}: \alpha,\beta \in S_{n}, \, \alpha(1)=n,\, \gamma \in {\cal C}^n_i(\Des \alpha),\, \gamma_1=0,\, \mu \in {\cal C}^n_j(\Ris \beta) \} \] to the set $(({N_{i}} \backslash \{0\}) \times {N_{ j}})^{n-1}Y_j$ where $Y_j=N_0 \times N_j$, computations similar to those of sections 5 and 7 may be used to verify \begin{theorem} The sequence $\{B^1_{n+1}\}_{n \geq 0}$ is generated by \begin{eqnarray} \sum_{n \geq 0} \frac{B^1_{n+1}(t,x,y,q,p)z^{n+1}}{(x;q)_{n+1}(y;p)_{n+2}}= \sum_{i,j \geq 0} x^iy^j \,\frac{F_1^{(i,j)}(z(1-t);q,p)}{F_0^{(i+1,j)}(z(1-t);q,p)-t} \;\;. \nonumber \end{eqnarray} \end{theorem} 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^1_n(t,x_1,x_2,q_1,q_2)$ to be \begin{eqnarray*} \displaystyle \sum_{(\alpha,\beta)} t^{\iddes(\alpha, \beta)} x_1^{\des \alpha} q_1^{\comaj \alpha} x_2^{\des \beta} q_2^{\comaj \beta} \end{eqnarray*} summed respectively over $S_n^2$ and over pairs in $S_n^2$ with $\beta(1)= n$. The appropriate sequence of refined bibasic Bessel functions is \begin{eqnarray} G_\nu^{(i_1,i_2)}(z;q_1,q_2)=\sum_{n \geq 0} (-1)^n q_1^{{n+\nu \choose 2}} q_2^{{n+\nu \choose 2}} \left[ \! \begin{array}{c} i_1 +1 \\ n+\nu \end{array} \! \right]_{q_1} \left[ \! \begin{array}{c} i_2\\ n \end{array} \! \right]_{q_2} z^{n+\nu} \;. \nonumber \end{eqnarray} Let $\phi$ be the binary relation on ${N} \times { N}$ consisting of the pairs $\left( {i \choose j},{k \choose m} \right)$ such that $i > k$ and $j > m$. The map $f \times f$ from \[ \{ {\alpha,\gamma \choose \beta,\mu}: \alpha,\beta \in S_{n} , \, \gamma \in {\cal C}^n_{i_1}(\Des \alpha), \, \mu \in {\cal C}^n_{i_2}(\Des \beta) \} \] to the set $({N_{i_1}} \times {N_{ i_2}})^{n}$ defined by \[ f \times f {\alpha,\gamma \choose \beta, \mu} = {f(\alpha,\gamma) \choose f(\beta, \mu)}={v \choose w} \] is a bijection satisfying the properties that $\| \gamma \| = \| v \|$, $\| \mu \| = \| w \|$, and \begin{eqnarray} k \in \Des \alpha^{-1} \bigcap \Des \beta^{-1} \iff k \in \phi \! \Adj{v \choose w} \;. \nonumber \end{eqnarray} Then, proceeding as in sections 5 and 7, we have \begin{theorem} The sequences $\{C_n\}_{n \geq 0}$ and $\{C^1_{n+1}\}_{n \geq 0}$ are respectively generated by \begin{eqnarray*} \sum_{n \geq 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}}= \sum_{i_1,i_2 \geq 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} \;\; , \\*[.4cm] \sum_{n \geq 0} \frac{C^1_{n+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}}= \sum_{i_1,i_2 \geq 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} \;\;.\end{eqnarray*} \end{theorem} 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^1_n(t,y_1,y_2,p_1,p_2)$ to be \begin{eqnarray*} \displaystyle \sum_{(\alpha,\beta)} t^{\iddes(\alpha, \beta)} y_1^{\ris \alpha} p_1^{\corin \alpha} y_2^{\ris \beta} p_2^{\corin \beta} \end{eqnarray*} summed respectively over $S_n^2$ and over pairs in $S_n^2$ with $\beta(1)= n$. Set \begin{eqnarray} H_\nu^{(j_1,j_2)}(z;p_1,p_2)=\sum_{n \geq 0} (-1)^n \left[ \! \begin{array}{c} j_1 + n + \nu \\ n+\nu \end{array} \! \right]_{p_1} \left[ \! \begin{array}{c} j_2 + n\\ n \end{array} \! \right]_{p_2} z^{n+\nu} \;. \nonumber \end{eqnarray} Take $\delta$ to be the binary relation on ${N} \times { N}$ consisting of the pairs $\left( {i \choose j},{k \choose m} \right)$ such that $i \geq k$ and $j \geq m$. Using the bijection $g \times g$, we obtain \begin{theorem} The sequences $\{D_n\}_{n \geq 0}$ and $\{D^1_{n+1}\}_{n \geq 0}$ are respectively generated by \begin{eqnarray*} \sum_{n \geq 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}}= \sum_{j_1,j_2 \geq 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} \;\; , \\*[.4cm] \sum_{n \geq 0} \frac{D^1_{n+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}}= \sum_{j_1,j_2 \geq 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} \;\;.\end{eqnarray*} \end{theorem} \section{Permutation sequences} We now consider distributions on finite sequences of permutations. For integers $r,s \geq 0$ not both zero, let ${\bf i}=(i_1,i_2, \ldots ,i_r)$ and ${\bf j}=(j_1,j_2, \ldots ,j_s)$. Select $U \subseteq \{1, 2, \ldots ,r\}$ and $V \subseteq \{1, 2, \ldots ,s\}$. Further let ${\bf i}(U) = ( i_1^{\prime},i_2^{\prime},\ldots , i_r^{\prime})$ where $i_l^{\prime}=i_l$ if $l \notin U$ and $i_l^{\prime} = i_l +1$ if $l \in U$. The required {\em multibasic} extension of the previously appearing sequences of refined bibasic Bessel functions is defined by \begin{eqnarray} K_\nu^{({\bf i}\,,\,{\bf j})}(z; U,V)=\sum_{n \geq 0} (-1)^n \, Q_1\, Q_2\, P_1 \, P_2 \, z^{n+\nu} \nonumber \end{eqnarray} where \begin{eqnarray*} Q_1 = \prod_{l \notin U} q_l^{{n+\nu \choose 2}} \left[ \! \begin{array}{c} i_l+1\\ n+ \nu \end{array} \! \right]_{q_l} , & \displaystyle Q_2 = \prod_{l \in U} q_l^{{n+\nu \choose 2}} \left[ \! \begin{array}{c} i_l \\ n \end{array} \! \right]_{q_l}, \\*[.4cm] P_1= \prod_{m \notin V} \left[ \! \begin{array}{c} j_m+n+ \nu \\ n+ \nu \end{array} \! \right]_{p_m} , & \displaystyle P_2 = \prod_{m \in V} \left[ \! \begin{array}{c} j_m +n \\ n \end{array} \! \right]_{p_m} \; . \end{eqnarray*} For $r=s=1$ with $U=\emptyset$ and $V=\{1\}$, note that $K_\nu^{({\bf i}\,,\,{\bf j})}(z; \emptyset,\{1\})=J_\nu^{({ i_1}\,,\,{ j_1 })}(z; q_1,p_1)$. For $r=2$, $s=0$, $U=\{2\}$, and $V= \emptyset$, we have $K_\nu^{({\bf i}\,,\,{\bf j})}(z; \{2\}, \emptyset)=G_\nu^{({ 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 {\em number of common iddescents} of a sequence $(\overline {\alpha};\overline{\beta}) = (\alpha_1, \alpha_2, \ldots , \alpha_r;\beta_1,\beta_2, \ldots , \beta_s) \in S_n^r \times S_n^s$ to be \[ \iddes (\overline{\alpha};\overline{\beta})= | \; \bigcap_{k=1}^r \Des \alpha_k^{-1} \;\; \bigcap \;\; \bigcap_{m=1}^s \Des \beta_m^{-1} \; | \;\; . \] Furthermore, set \[ {\bf x}^{\des \overline{\alpha}} = x_1^{\des \alpha_1}x_2^{\des \alpha_2} \ldots x_r^{\des \alpha_r} \;\; {\rm and} \;\; {\bf y}^{\ris {\overline \beta}} = y_1^{\ris \beta_1}y_2^{\ris \beta_2} \ldots y_s^{\ris \beta_s} \;\; . \] The symbols ${\bf q}^{\comaj \overline{\alpha}}$ and ${\bf p}^{\corin \overline{\beta}}$ are to be similarly interpreted. Finally, let \begin{eqnarray*} M_n(t,U,V)=\displaystyle \sum t^{\iddes(\overline{ \alpha};\overline{\beta})} {\bf x}^{\des \overline{\alpha}} {\bf q}^{\comaj \overline{\alpha}} {\bf y}^{\ris \overline{\beta}} {\bf p}^{\corin \overline{\beta}} \end{eqnarray*} where the sum is over all $(\overline{\alpha}, \overline{\beta}) \in S_n^r \times S_n^s$ with $\alpha_l(1)=n$ for $l \in U$ and $\beta_m(1)=n$ for $m \in V$. Then, the map $f^{(r)} \times 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: \begin{theorem} The sequence $\{M_{n}(t,\emptyset,\emptyset)\}_{n \geq 0}$ is generated by \begin{eqnarray} \sum_{n \geq 0} \frac{M_{n}(t,\emptyset,\emptyset)z^n} { ({\bf x};{\bf q})_{n+1}({\bf y};{\bf p})_{n+1}}= \sum_{{\bf i,j} \geq 0} {\bf x}^{\bf i}{\bf y}^{\bf j} \,\frac{(1-t)}{K_0^{({\bf i}(U)\,,\,{\bf j})}(z(1-t);U,V)-t} \nonumber \end{eqnarray} where $({\bf x}; {\bf q})_n=(x_1;q_1)_n \cdots (x_r;q_r)_n$ and $({\bf y}; {\bf p})_n=(y_1;p_1)_n \cdots (y_s;p_s)_n$. \end{theorem} \begin{theorem} 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 \geq 0}$ is generated by \begin{eqnarray} \sum_{n \geq 0} \frac{M_{n+1}(t,U,V)z^{n+1}} { ({\bf x},{\bf y};{\bf q},{\bf p})_{n+2}^c({\bf x},{\bf y} ;{\bf q},{\bf p})_{n+1}}= \sum_{{\bf i,\,j} \geq 0} {\bf x}^{\bf i}{\bf y}^{\bf j} \,\frac{K_1^{({\bf i}\,,\,{\bf j})}(z(1-t))}{K_0^{({\bf i}(U)\,,\,{\bf j})}(z(1-t);U,V)-t} \nonumber \end{eqnarray} where $({\bf x},{\bf y};{\bf q},{\bf p})_{n}^c=\prod_{l \notin U}(x_l;q_l)_n \prod_{m \notin V}(y_m;p_m)_n$ and \\ $({\bf x},{\bf y} ;{\bf q},{\bf p})_{n}=\prod_{l \in U}(x_l;q_l)_n \prod_{m \in V}(y_m;p_m)_n$. \end{theorem} Taking the limit as $x,y \rightarrow 1$ and setting $q_i=1$, $1 \leq i \leq r$, in Theorem 7 gives a result equivalent to one obtained by Stanley \cite{St}. \begin{thebibliography}{99} \bibitem{andrews} G.\ E.\ Andrews, {\em The Theory of Partitions}, Addison-Wesley 1976. \bibitem{C1} L.\ Carlitz, {\em q}-Bernoulli numbers and Eulerian numbers, {\em Trans. Amer. Math. Soc.} 76 (1954) 332-350. \bibitem{C2} L.\ Carlitz, A combinatorial property of {\em q}-Eulerian numbers, {\em Amer. Math. Monthly} 82 (1975) 51-54. \bibitem{CSV} L.\ Carlitz, R.\ Scoville, and T.\ Vaughan, Enumeration of pairs of permutations, {\em Discrete Math.} 14 (1976) 215-239. \bibitem{DF} M.\ P.\ Delest and J.\ M.\ Fedou, Enumeration of skew Ferrers' diagrams, {\em Discrete Math.} 112 (1993) 65-79. \bibitem{FR2} J.\ M.\ Fedou and D.\ P.\ Rawlings, Statistics on pairs of permutations, {\em Discrete Math.} (to appear). \bibitem{FR3} J.\ M.\ Fedou and D.\ P.\ Rawlings, Adjacencies in words, {\em Adv.\ in Appl.\ Math.} (to appear). \bibitem{Fo1} D.\ Foata, Distributions Eul\'{e}riennes et Mahoniennes sur le groupe des permutations, {\em Higher Combinatorics}, Proceedings, ed.\ M.\ Aigner, Reidel Publ. Co., Dodrecht, Holland (1977) 27-49. \bibitem{G} A.\ M.\ Garsia, On the {\em maj} and {\em inv} {\em q-}analogues of Eulerian polynomials, {\em J. Lin. and Multilin. Alg.} 8 (1980) 21-34. \bibitem{GG} A.\ M.\ Garsia and I.\ Gessel, Permutation statistics and partitions, {\em Adv. in Math.} 31 (1979) 288-305. \bibitem{GR} G.\ Gasper and M.\ Rahman, {\em Basic Hypergeometric Series}, Cambridge Univ. Press 1990. \bibitem{Ge} I.\ M.\ Gessel, {\em Generating Functions and Enumeration of Sequences}, Doctoral thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts 1977. \bibitem{GJ} I.\ P.\ Goulden and D.\ M.\ Jackson, {\em Combinatorial Enumeration}, John Wiley \& Sons 1983. \bibitem{I} M.\ E.\ H.\ Ismail, The zeros of basic Bessel functions, $\dots$ , {\em J. Math. Annal. and Appl.} 86 (1982) 1-19. \bibitem{J} F.\ H.\ Jackson, The basic gamma function and elliptic functions, {\em Proc. Royal Soc. A} 76 (1905) 127-144. \bibitem{Mac} M.\ P.\ MacMahon, {\em Combinatory Analysis}, Cambridge Univ.\ Press 1915 (reprinted by Chelsea 1960). \bibitem{DPR} D.\ P.\ Rawlings, Generalized Worpitzky identities with applications to permutation enumeration {\em Europ.\ J.\ Comb.\ Theory} 2 (1981) 67-78. \bibitem{St} R.\ P.\ Stanley, Binomial posets, M\"{o}bius inversion, and permutation enumeration, {\em J.\ Comb.\ Theory} (A) 20 (1976) 336-356. \bibitem{St2} R.\ P.\ Stanley, {\em Enumerative Combinatorics} Vol. I, Wadsworth \& Brooks 1986. \bibitem{XV1} X.\ G.\ Viennot, Heaps of pieces I: Basic definitions and combinatorial lemmas, in {\em Combinatoire \'{E}num\'{e}rative}, eds. G.\ Labelle and P.\ Leroux, Lect.\ Notes in Math.\ 1234, Springer-Verlag, Berlin 1986. \bibitem{Z} D.\ Zeilberger, Enumeration of words by their number of mistakes, {\em Discrete Math.} 34 (1981) 89-92. \end{thebibliography} \end{document}