# Combinatorics of the PASEP partition function

Matthieu Josuat-Vergès¹ †

¹ LRI, Bât. 490, Université Paris-sud 11, 91405 Orsay CEDEX

**Abstract.** We consider a three-parameter PASEP model on $N$ sites. A closed formula for the partition function was obtained analytically by Blythe et al. We give a new formula which generalizes the one of Blythe et al, and is proved in two combinatorial ways. Moreover the first proof can be adapted to give the moments of Al-Salam-Chihara polynomials.

**Résumé.** Nous considérons un modèle de PASEP à trois paramètres sur $N$ sites. Une formule close pour la fonction de partition a été obtenue analytiquement par Blythe et al. Nous donnons une formule qui généralise celle de Blythe et al, prouvée combinatoirement de deux manières différentes. Par ailleurs la première preuve peut être adaptée de sorte à obtenir les moments des polynômes d'Al-Salam-Chihara.

**Keywords:** asymmetric exclusion process, lattice paths, orthogonal polynomials, enumeration

## 1 Introduction

The partially asymmetric simple exclusion process (also called PASEP) is a Markov chain describing the evolution of particles in $N$ sites arranged in a line, each site being either empty or occupied by one particle. Particles may enter the leftmost site at a rate $\alpha \ge 0$, go out the rightmost site at a rate $\beta \ge 0$, hop left at a rate $q \ge 0$ and hop right at a rate $p \ge 0$ when possible. By rescaling time it is always possible to assume that the latter parameter is 1 without loss of generality. It is possible to define either a continuous-time model or a discrete-time model, but they are equivalent in the sense that their stationary distributions are the same. In this work we only study some combinatorial properties of the partition function. For precisions, background about the model, and much more, we refer to [2, 3, 4, 5, 7, 9, 18]. We refer particularly to the long survey of Blythe and Evans [2] and all references therein to give evidence that this is a widely studied model. Indeed, it is quite rich and some important features are the various phase transitions, and spontaneous symmetry breaking for example, so that it is considered to be a fundamental model of nonequilibrium statistical physics.

A method to obtain the stationary distribution and the partition function $Z_N$ of the model is the Matrix Ansatz of Derrida, Evans, Hakim and Pasquier [9]. We suppose that $D$ and $E$ are linear operators, $\langle W |$ is a vector, $|V\rangle$ is a linear form, such that:

$$DE - qED = D + E, \quad \langle W | \alpha E = \langle W |, \quad \beta D |V\rangle = |V\rangle, \quad \langle W | V\rangle = 1, \quad (1)$$

<footnote>†Partially supported by the grant ANR08-JCJC-0011.</footnote>
then the non-normalized probability of each state can be obtained by taking the product $\langle W | t_1 \dots t_N | V \rangle$ where $t_i$ is $D$ if the $i$th site is occupied and $E$ if it is empty. It follows that the normalization, or partition function, is given by $\langle W | (D + E)^N | V \rangle$. It is possible to introduce another variable $y$, which is not a parameter of the probabilistic model, but is a formal parameter such that the coefficient of $y^k$ in the partition function corresponds to the states with exactly $k$ particles (physically it could be called a *fugacity*). The partition function is then:

$$Z_N = \langle W | (yD + E)^N | V \rangle, \qquad (2)$$

which we may take as a definition on the combinatorial point of view. An interesting property is the symmetry:

$$Z_N(\alpha, \beta, y, q) = y^N Z_N(\beta, \alpha, y^{-1}, q), \qquad (3)$$

which can be seen on the physical point of view by exchanging the empty sites with occupied sites. It can also be obtained from the Matrix Ansatz by using the transposed matrices $D^*$ and $E^*$ and the transposed vectors $\langle V |$ and $|W\rangle$, which satisfies a similar Matrix Ansatz with $\alpha$ and $\beta$ exchanged.

In section 2, we will use the explicit solution of the Matrix Ansatz found by Derrida & al. [9], and it will permit to make use of weighted lattice paths as in [4].

An exact formula for $Z_N$ was given by Blythe & al. [3, Equation (57)] in the case where $y = 1$. It was obtained from the eigenvalues and eigenvectors of the operator $D + E$ as defined in (10) and (11) below. This method gives an integral form for $Z_N$, which can be simplified so as to obtain a finite sum rather than an integral. Moreover this expression for $Z_N$ was used to obtain various properties of the large system size limit, such as phases diagrams and currents. Here we generalize this result since we also have the variable $y$, and the proofs are combinatorial. This is an important result since most interesting properties of a model can be derived from the partition function. The interest of the result is also due to the plentiful combinatorial information of $Z_N$ [7], in the full version of this work we will show that it is the generating function of permutations in $S_{N+1}$ with respect to right-to-left minima, right-to-left maxima, ascents, and occurrences of the pattern 31-2 (see [6] for a close result).

**Theorem 1.1** Let $\tilde{\alpha} = (1-q)^{\frac{1}{\alpha}} - 1$ and $\tilde{\beta} = (1-q)^{\beta} - 1$. We have:

$$Z_N = \frac{1}{(1-q)^N} \sum_{n=0}^{N} R_{N,n}(y,q) B_n(\tilde{\alpha}, \tilde{\beta}, y,q), \qquad (4)$$

where

$$R_{N,n}(y,q) = \sum_{i=0}^{\lfloor \frac{N-n}{2} \rfloor} (-y)^i q^{\binom{i+1}{2}} \left[ \begin{matrix} n+i \\ i \end{matrix} \right]_q^{N-n-2i} \sum_{j=0}^{N-n-2i} y^j \left( \begin{matrix} N \\ j \end{matrix} \binom{N}{n+2i+j} - \binom{N}{j-1} \binom{N}{n+2i+j+1} \right) \qquad (5)$$

and

$$B_n(\tilde{\alpha}, \tilde{\beta}, y, q) = \sum_{k=0}^{n} \begin{bmatrix} n \\ k \end{bmatrix}_q \tilde{\alpha}^k (y\tilde{\beta})^{n-k}. \qquad (6)$$
In the case where $y = 1$, one sum can be simplified by the Vandermonde identity $\sum_j \binom{N}{j} \binom{N}{m-j} = \binom{2N}{m}$, and we recover the expression given in [3, Equation (54)] by Blythe & al:

$$R_{N,n}(1,q) = \sum_{i=0}^{\lfloor \frac{N-n}{2} \rfloor} (-1)^i \left( \binom{2N}{N-n-2i} - \binom{2N}{N-n-2i-2} \right) q^{\binom{i+1}{2}} \left[ \binom{n+i}{i} \right]_q. \quad (7)$$

In the case where $\alpha = \beta = 1$, it is known [8, 13] that:

$$Z_N = \frac{1}{(1-q)^{N+1}} \sum_{k=0}^{N+1} (-1)^k \left( \sum_{j=0}^{N+1-k} y^j \left( \binom{N+1}{j} \binom{N+1}{j+k} - \binom{N+1}{j-1} \binom{N+1}{j+k+1} \right) \right) \left( \sum_{i=0}^{k} y^i q^{i(k+1-i)} \right) \quad (8)$$

(see Remarks 2.4 and 3.3 for a comparison between this previous result and the new one in Theorem 1.1). And in the case where $y = q = 1$, from a recursive construction of permutation tableaux [6] or lattice paths combinatorics [4] it is known that:

$$Z_N = \prod_{i=0}^{N-1} \left( \frac{1}{\alpha} + \frac{1}{\beta} + i \right). \qquad (9)$$

Our first proof of (4) is a purely combinatorial enumeration of some weighted Motzkin paths defined below in (13), appearing from explicit representations of the operators $D$ and $E$ of the Matrix Ansatz. It partially relies on results of [8, 13] through Proposition 2.1 below. In contrast, our second proof does not use a particular representation of the operators $D$ and $E$, but only on the combinatorics of the normal ordering process. It also relies on previous results of [13] (through Proposition 3.1 below), but we will sketch a self-contained proof. Additionally we will show that our first proof of Theorem 1.1 can be adapted to give a formula for Al-Salam-Chihara moments [1].

## 2 A first combinatorial derivation of $Z_N$ using lattice paths

We use the solution of the Matrix Ansatz (1) given by Derrida & al. [9]. Let $\tilde{\alpha} = (1-q)^{\frac{1}{\alpha}} - 1$ and $\tilde{\beta} = (1-q)^{\frac{1}{\beta}} - 1$, their matrices are $D = (D_{i,j})_{i,j \in \mathbb{N}}$ and $E = (E_{i,j})_{i,j \in \mathbb{N}}$ with coefficients:

$$(1-q)D_{i,i} = 1 + \tilde{\beta}q^i, \quad (1-q)D_{i,i+1} = 1 - \tilde{\alpha}\tilde{\beta}q^i, \qquad (10)$$

$$(1-q)E_{i,i} = 1 + \tilde{\alpha}q^i, \quad (1-q)E_{i+1,i} = 1 - q^{i+1}, \qquad (11)$$

all other coefficients being 0, and vectors:

$$\langle W \rangle = (1, 0, 0, \dots), \quad |V\rangle = (1, 0, 0, \dots)^*, \qquad (12)$$

(i.e. $|V\rangle$ is the transpose of $\langle W \rangle$). Even if infinite-dimensional, they have the nice property of being tridiagonal and this lead to a combinatorial interpretation of $Z_N$ in terms of lattice paths [4]. Indeed, we
can see $yD + E$ as a transfer matrix for walks in the non-negative integers, and from (2) we obtain that
$(1-q)^N Z_N$ is the sum of weights of Motzkin paths of length $N$ with weights:

$$
\begin{align}
& \bullet \ 1 - q^{h+1} \text{ for a step } \nearrow \text{ starting at height } h, \notag \\
& \bullet \ (1+y) + (\tilde{\alpha} + y\tilde{\beta})q^h \text{ for a step } \rightarrow \text{ starting at height } h, \tag{13} \\
& \bullet \ y(1 - \tilde{\alpha}\tilde{\beta}q^{h-1}) \text{ for a step } \searrow \text{ starting at height } h. \notag
\end{align}
$$

$$
\bullet y(1 - \tilde{\alpha}\tilde{\beta}q^{h-1}) \text{ for a step } \searrow \text{ starting at height } h.
$$

To give a bijective proof of Theorem 1.1, we need to consider the set $\mathfrak{P}_N$ of weighted Motzkin paths of length $N$ such that:

$$
\bullet \text{ the weight of a step } \nearrow \text{ starting at height } h \text{ is } q^i - q^{i+1} \text{ for some } i \in \{0, \dots, h\},
$$

$$
\bullet \text{ the weight of a step } \rightarrow \text{ starting at height } h \text{ is either } 1+y \text{ or } (\tilde{\alpha}+y\tilde{\beta})q^h,
$$

$$
\bullet \text{ the weight of a step } \searrow \text{ starting at height } h \text{ is either } y \text{ or } -y\tilde{\alpha}\tilde{\beta}q^{h-1}.
$$

The sum of weights of elements in $\mathfrak{P}_N$ is $(1-q)^N Z_N$ because the weights sum to the ones in (13). We stress that on the combinatorial point of view, it will be important to distinguish $(h+1)$ kinds of step $\nearrow$ starting at height $h$, instead of one kind of step $\nearrow$ with weight $1-q^{h+1}$.

We will show that each element of $\mathfrak{P}_N$ bijectively corresponds to a pair of weighted Motzkin paths.
The first path (respectively, second path) belongs to a set whose generating function is $R_{N,n}(y, q)$ (respec-
tively, $B_n(\tilde{\alpha}, \tilde{\beta}, y, q)$) for some $n \in \{0, \dots, N\}$. Following this scheme, our first combinatorial proof of
(4) is a consequence of Propositions 2.1, 2.2, and 2.3 below.

Let $\mathfrak{R}_{N,n}$ be the set of weighted Motzkin paths of length $N$ such that:

$$
\bullet \text{ the weight of a step } \nearrow \text{ starting at height } h \text{ is } q^i - q^{i+1} \text{ for some } i \in \{0, \dots, h\},
$$

$$
\bullet \text{ the weight of a step } \rightarrow \text{ starting at height } h \text{ is either } 1+y \text{ or } q^h, \text{ and there are exactly } n \text{ steps } \rightarrow \\ \text{weighted by a power of } q,
$$

$$
\bullet \text{ the weight of a step } \searrow \text{ is } y,
$$

**Proposition 2.1** The sum of weights of elements in $\mathfrak{R}_{N,n}$ is $R_{N,n}(y, q)$.

This can be obtained with the methods used in [8, 13]. Some precisions are in order. In [8] and [13], we
obtained the formula (8) which is the special case $\alpha = \beta = 1$ in $Z_N$, and is the $N$th moment of $q$-Laguerre
polynomials [15] which are a rescaling of Al-Salam-Chihara polynomials. Since $Z_N$ is also very closely
related with these polynomials (see Section 4) it is not surprising that some steps are in common between
these previous results and the present ones. See also Remark 2.4 below.

Let $\mathfrak{B}_n$ be the set of weighted Motzkin paths of length $n$ such that:

$$
\bullet \text{ the weight of a step } \nearrow \text{ starting at height } h \text{ is } q^i - q^{i+1} \text{ for some } i \in \{0, \dots, h\},
$$

$$
\bullet \text{ the weight of a step } \rightarrow \text{ starting at height } h \text{ is } (\tilde{\alpha} + y\tilde{\beta})q^h,
$$

$$
\bullet \text{ the weight of a step } \searrow \text{ starting at height } h \text{ is } -y\tilde{\alpha}\tilde{\beta}q^{h-1}.
$$
**Proposition 2.2** *The sum of weights of elements in $\mathfrak{B}_n$ is $B_n(\tilde{\alpha}, \tilde{\beta}, y, q)$.*

It is a consequence of properties of the Al-Salam-Carlitz orthogonal polynomials. Indeed, a standard argument [10, 20] shows that $B_n(\tilde{\alpha}, \tilde{\beta}, y, q)$ is the $n$th moment of an orthogonal sequence whose three-term recurrence relation is derived from the weights in the Motzkin paths. These polynomials are a rescaled version of Al-Salam-Carlitz polynomials, whose moments are known [16]. The result follows.

**Proposition 2.3** *There exists a weight-preserving bijection $\Phi$ between the disjoint union of $\mathfrak{R}_{N,n} \times \mathfrak{B}_n$ over $n \in \{0, \dots, N\}$, and $\mathfrak{P}_n$ (we understand that the weight of a pair is the product of the weights of each element).*

To define the bijection, we start from a pair $(H_1, H_2) \in \mathfrak{R}_{N,n} \times \mathfrak{B}_n$ for some $n \in \{0, \dots, N\}$ and build a path $\Phi(H_1, H_2) \in \mathfrak{P}_n$. Let $i \in \{1, \dots, N\}$.

* If the $i$th step of $H_1$ is a step $\to$ weighted by a power of $q$, say the $j$th one among the $n$ such steps, then:

- the $i$th step $\Phi(H_1, H_2)$ has the same direction as the $j$th step of $H_2$,

- its weight is the product of weights of the $i$th step of $H_1$ and the $j$th step of $H_2$.

* Otherwise the $i$th step of $\Phi(H_1, H_2)$ has the same direction and same weight as the $i$th step of $H_1$.

See Figure 1 for an example, where the thick steps correspond to the ones in the first of the two cases considered above. It is immediate that the total weight of $\Phi(H_1, H_2)$ is the product of the total weights of $H_1$ and $H_2$.

<figure><img src="image_1.png" /><figcaption>**Fig. 1:** Example of paths $H_1, H_2$ and their image $\Phi(H_1, H_2)$.</figcaption></figure>

The inverse bijection is not as simple. It can be checked that $H_1$ and $H_2$ can be recovered by reading $\Phi(H_1, H_2)$ step by step from right to left.
**Remark 2.4** The decomposition $\Phi$ is the key step in our first proof of Theorem 1.1. This makes the proof quite different from the one in the case $\alpha = \beta = 1$ [8], even though we have used results from [8] to prove an intermediate step (namely Proposition 2.1). Actually, it might be possible to have a direct adaptation of the case $\alpha = \beta = 1$ [8] to prove Theorem 1.1, but it should give rise to many computational steps. In contrast our decomposition $\Phi$ explains the formula for $Z_N$ as a sum of products.

### 3 A second derivation of $Z_N$ using the Matrix Ansatz

In this section we build on our previous work [13] to give a second proof of (4). In this reference we define the operators

$$ \hat{D} = \frac{q-1}{q} D + \frac{1}{q} I \quad \text{and} \quad \hat{E} = \frac{q-1}{q} E + \frac{1}{q} I, \qquad (14) $$

where $I$ is the identity. The new relations for these operators are:

$$ \hat{D}\hat{E} - q\hat{E}\hat{D} = \frac{1-q}{q^2}, \quad \langle W | \hat{E} = -\frac{\tilde{\alpha}}{q} \langle W |, \quad \text{and} \quad \hat{D}|V\rangle = -\frac{\tilde{\beta}}{q}|V\rangle, \qquad (15) $$

where $\tilde{\alpha}$ and $\tilde{\beta}$ are defined as in the previous section. While the normal ordering problem for $D$ and $E$ leads to permutation tableaux [7], for $\hat{D}$ and $\hat{E}$ it leads to rook placements as was shown for example in [21]. The combinatorics of rook placements lead to the following proposition.

**Proposition 3.1** We have:

$$ \langle W | (qy\hat{D} + q\hat{E})^k | V \rangle = \sum_{\substack{i+j \le k \\ i+j \equiv k \mod 2}} \begin{bmatrix} i+j \\ i \end{bmatrix}_q (-\tilde{\alpha})^i (-y\tilde{\beta})^j M_{\frac{k-i-j}{2}, k} \qquad (16) $$

where

$$ M_{\ell,k} = y^{\ell} \sum_{u=0}^{\ell} (-1)^u q^{\binom{u+1}{2}} \begin{bmatrix} k-2\ell+u \\ u \end{bmatrix}_q \left( \binom{k}{\ell-u} - \binom{k}{\ell-u-1} \right). \qquad (17) $$

**Proof:** This is a consequence of results in [13] (see Section 2, Corollary 1, Proposition 12). We also give here a self-contained recursive proof. By means of the commutation relation in (15), we can write $(yq\hat{D} + q\hat{E})^k$ as a normal form:

$$ (yq\hat{D} + q\hat{E})^k = \sum_{i,j \ge 0} d_{i,j}^{(k)} (q\hat{E})^i (qy\hat{D})^j, \qquad (18) $$

where $d_{i,j}^{(k)}$ are polynomials in $y$ and $q$, and only finitely many of them are non-zero. From the commutation relation we also obtain:

$$ (qy\hat{D})^j (q\hat{E}) = q^j (q\hat{E}) (qy\hat{D})^j + y(1-q^j)(qy\hat{D})^{j-1}. \qquad (19) $$

If we multiply (18) by $yq\hat{D}+q\hat{E}$ to the right, using (19) we can get a recurrence relation for the coefficients $d_{i,j}^{(k)}$, which reads:

$$ d_{i,j}^{(k+1)} = d_{i,j-1}^{(k)} + q^j d_{i-1,j}^{(k)} + y(1-q^{j+1})d_{i,j+1}^{(k)}. \qquad (20) $$
The initial case is that $d_{i,j}^{(0)}$ is 1 if $(i, j) = (0, 0)$ and 0 otherwise. It can be directly checked that the recurrence is solved by:

$$d_{i,j}^{(k)} = \begin{bmatrix} i+j \\ i \end{bmatrix}_q M_{\frac{k-i-j}{2}, k} \qquad (21)$$

where we understand that $M_{\frac{k-i-j}{2}, k}$ is 0 when $k - i - j$ is not even. More precisely, if we let $e_{i,j}^{(k)} = \begin{bmatrix} i+j \\ i \end{bmatrix}_q M_{\frac{k-i-j}{2}, k}$ then we have:

$$e_{i,j-1}^{(k)} + q^j e_{i-1,j}^{(k)} = \begin{bmatrix} i+j \\ i \end{bmatrix}_q M_{\frac{k-i-j+1}{2}, k}, \qquad (22)$$

and also

$$y(1 - q^{j+1}) e_{i,j+1}^{(k)} = y(1 - q^{i+j+1}) \begin{bmatrix} i+j \\ i \end{bmatrix}_q M_{\frac{k-i-j-1}{2}, k}. \qquad (23)$$

So to prove $d_{i,j}^{(k)} = e_{i,j}^{(k)}$ it remains only to check that

$$M_{\frac{k-i-j+1}{2}, k} + y(1 - q^{i+j+1}) M_{\frac{k-i-j-1}{2}, k} = M_{\frac{k-i-j}{2}, k}. \qquad (24)$$

See for example [13, Proposition 12] (actually this recurrence already appeared more than fifty years ago in the work of Touchard, see loc. cit. for precisions). □

Now we can give our second proof of Theorem 1.1.

**Proof:** From (2) and (14) we have:

$$(1 - q)^N Z_N = \langle W | ((1 + y)I - qy\hat{D} - q\hat{E})^N | V \rangle = \sum_{k=0}^{N} \binom{N}{k} (1 + y)^{N-k} (-1)^k \langle W | (qy\hat{D} + q\hat{E})^k | V \rangle.$$

So, from Proposition 3.1 we have:

$$(1 - q)^N Z_N = \sum_{k=0}^{N} \sum_{\substack{i+j \le k \\ i+j \equiv k \bmod 2}} \begin{bmatrix} i+j \\ i \end{bmatrix}_q \tilde{\alpha}^i (y\tilde{\beta})^j \binom{N}{k} (1 + y)^{N-k} M_{\frac{k-i-j}{2}, k}$$

(the $(-1)^k$ cancels with a $(-1)^{i+j}$). Setting $n = i + j$, we have:

$$(1 - q)^N Z_N = \sum_{n=0}^{N} B_n(\tilde{\alpha}, \tilde{\beta}, y, q) \sum_{\substack{n \le k \le N \\ k \equiv n \bmod 2}} \binom{N}{k} (1 + y)^{N-k} M_{\frac{k-n}{2}, k}.$$

So it remains only to show that the latter sum is $R_{N,n}(y, q)$. If we change the indices so that $k$ becomes $n + 2k$, this sum is:

$$\sum_{k=0}^{\lfloor \frac{N-n}{2} \rfloor} \binom{N}{n+2k} (1+y)^{N-n-2k} y^k \sum_{i=0}^{k} (-1)^i q^{\binom{i+1}{2}} \begin{bmatrix} n+i \\ i \end{bmatrix}_q \left( \binom{n+2k}{k-i} - \binom{n+2k}{k-i-1} \right)$$
$$ = \sum_{i=0}^{\lfloor \frac{N-n}{2} \rfloor} (-y)^i q^{\binom{i+1}{2}} \begin{bmatrix} n+i \\ i \end{bmatrix}_q \sum_{k=i}^{\lfloor \frac{N-n}{2} \rfloor} y^{k-i} \binom{N}{n+2k} (1+y)^{N-n-2k} \left( \binom{n+2k}{k-i} - \binom{n+2k}{k-i-1} \right). $$

We can simplify the latter sum by Lemma 3.2 below and obtain $R_{N,n}(y, q)$. This completes the proof. □

**Lemma 3.2** For any $N, n, i \ge 0$ we have:

$$ \sum_{k=i}^{\lfloor \frac{N-n}{2} \rfloor} y^{k-i} \binom{N}{n+2k} (1+y)^{N-n-2k} \left( \binom{n+2k}{k} - \binom{n+2k}{k-1} \right) \tag{25} \\ = \sum_{j=0}^{N-n-2i} y^j \left( \binom{N}{j} \binom{N}{n+2i+j} - \binom{N}{j-1} \binom{N}{n+2i+j+1} \right). $$

**Proof:** It can be shown that the right-hand side of (25) is the number of Motzkin prefixes of length $N$, final height $n+2i$, and a weight $1+y$ on each step $\rightarrow$ and $y$ on each step $\searrow$. Similarly, $y^{k-i} \left( \binom{n+2k}{k-i} - \binom{n+2k}{k-i-1} \right)$ is the number of Dyck prefixes of length $n+2k$ and final height $n+2i$, with a weight $y$ on each step $\searrow$. From these two combinatorial interpretations it is straightforward to obtain a bijective proof of (25). Each Motzkin prefix is built from a shorter Dyck prefix with the same final height, by choosing where are the $N-n-2k$ steps $\rightarrow$. □

**Remark 3.3** All the ideas in this proof were present in [13] where we obtained the case $\alpha = \beta = 1$. The particular case was actually more difficult to prove because several $q$-binomial and binomial simplifications were needed. In particular, it is natural to ask if the formula in (8) for $Z_{N|\alpha=\beta=1}$ can be recovered from the general expression in Theorem 1.1, and the (affirmative) answer is essentially given in [13] (see also Subsection 4.2 below for a very similar simplification).

# 4 Moments of Al-Salam-Chihara polynomials

The link between the PASEP and the Al-Salam-Chihara orthogonal polynomials $Q_n(x; a, b | q)$ was described in [18]. These polynomials, denoted by $Q_n(x)$ when we do not need to precise the other parameters, are defined by the recurrence [17]:

$$ 2xQ_n(x) = Q_{n+1}(x) + (a+b)q^n Q_n(x) + (1-q^n)(1-abq^{n-1})Q_{n-1}(x) \tag{26} $$

together with $Q_{-1}(x) = 0$ and $Q_0(x) = 1$. They were introduced as the most general orthogonal sequence that is a convolution of two orthogonal sequences [1]. In terms of the Askey-Wilson polynomials $p_n(x; a, b, c, d | q)$, Al-Salam-Chihara polynomials are an important particular case since $Q_n(x; a, b | q) = p_n(x; a, b, 0, 0 | q)$ [17].
## 4.1 Closed formulas for the moments

It can be checked that the specialization $(1-q)^N Z_N|_{y=1}$ is the Nth moment of the sequence $\{Q_n(\frac{x}{2} - 1; \tilde{\alpha}, \tilde{\beta} | q)\}_{n \in \mathbb{N}}$, where $\tilde{\alpha} = (1-q)^{\frac{1}{\alpha}} - 1$ and $\tilde{\beta} = (1-q)^{\frac{1}{\beta}} - 1$ as before. There is a simple relation between the moments of an orthogonal sequence and the ones of a rescaled sequence, so that assuming $a = \tilde{\alpha}$ and $b = \tilde{\beta}$ the Nth moment $\mu_N$ of the Al-Salam-Chihara polynomials can be obtained via the relation:

$$ \mu_N = \sum_{k=0}^{N} \binom{N}{k} (-1)^{N-k} 2^{-k} (1-q)^k Z_k|_{y=1}. \qquad (27) $$

Actually, the methods of Section 2 also give a direct proof of the following.

**Theorem 4.1** The Nth moment of the Al-Salam-Chihara polynomials is:

$$ \mu_N = \frac{1}{2^N} \sum_{\substack{0 \le n \le N \\ n \equiv N \mod 2}} \left( \sum_{j=0}^{\frac{N-n}{2}} (-1)^j q^{\binom{j+1}{2}} \left[ \begin{matrix} n+j \\ j \end{matrix} \right]_q \left( \left( \frac{N}{2-n}-j \right) - \left( \frac{N}{2-n}-j-1 \right) \right) \right) \left( \sum_{k=0}^{n} \left[ \begin{matrix} n \\ k \end{matrix} \right]_q a^k b^{n-k} \right). \quad (28) $$

**Proof:** The general idea is to adapt the proof of Theorem 1.1 in Section 2. Let $\mathfrak{P}'_N \subset \mathfrak{P}_N$ be the subset of paths which contain no step $\to$ with weight $1+y$. The sum of weights of elements in $\mathfrak{P}'_N$ specialized at $y=1$, gives the Nth moment of the sequence $\{Q_n(\frac{x}{2})\}_{n \ge 0}$. This can be seen by comparing the weights in the Motzkin paths and the recurrence (26). But the Nth moment of this sequence is also $2^N \mu_N$.

From the definition of the bijection $\Phi$ in Section 2, we see that $\Phi(H_1, H_2)$ has no step $\to$ with weight $1+y$ if and only if $H_1$ has the same property. So from Proposition 2.3 the bijection $\Phi^{-1}$ gives a weight-preserving bijection between $\mathfrak{P}'_N$ and the disjoint union of $\mathfrak{R}'_{N,n} \times \mathfrak{B}_n$ over $n \in \{0, \dots, N\}$, where $\mathfrak{R}'_{N,n} \subset \mathfrak{R}_{N,n}$ is the subset of paths which contain no horizontal step with weight $1+y$. Note that $\mathfrak{R}'_{N,n}$ is empty when $n$ and $N$ do not have the same parity, because now $n$ has to be the number of steps $\to$ in a Motzkin path of length $N$. In particular we can restrict the sum over $n$ to the case $n \equiv N \mod 2$.

At this point it remains only to adapt the proof of Proposition 2.1 to compute the sum of weights of elements in $\mathfrak{R}'_{N,n}$, and obtain the sum over $j$ in (28). As in the previous case we can adapt the methods from [8]. $\square$

We have to mention that there are analytical methods to obtain the moments $\mu_N$ of these polynomials. A nice formula for the Askey-Wilson moments was given by D. Stanton [19], as a consequence of joint results with M. Ismail [12, equation (1.16)]. As a particular case they have the Al-Salam-Chihara moments:

$$ \mu_N = \frac{1}{2^N} \sum_{k=0}^{N} (ab; q)_k q^k \sum_{j=0}^{k} \frac{q^{-j^2} a^{-2j} (q^j a + q^{-j} a^{-1})^N}{(q, a^{-2}q^{-2j+1}; q)_j (q, a^2q^{1+2j}; q)_{k-j}}, \qquad (29) $$

where we use the $q$-Pochhammer symbol. The latter formula has no apparent symmetry in $a$ and $b$ and has denominators, but D. Stanton gave evidence [19] that (29) can be simplified down to (28) using binomial, $q$-binomial, and $q$-Vandermonde summation theorems. Moreover (29) is equivalent to a formula for rescaled polynomials given in [15] (Section 4, Theorem 1 and equation (29)).
## 4.2 Some particular cases of Al-Salam-Chihara moments

When $a = b = 0$ in (28) we immediately recover the known result for the continuous $q$-Hermite moments. This is 0 if $N$ is odd, and the Touchard-Riordan formula if $N$ is even. Other interesting cases are the $q$-secant numbers $E_{2n}(q)$ and $q$-tangent numbers $E_{2n+1}(q)$, defined in [11] by continued fraction expansions of the generating functions:

$$ \sum_{n \ge 0} E_{2n}(q) t^n = \frac{1}{1 - \frac{[1]_q^2 t}{1 - \frac{[2]_q^2 t}{1 - \frac{[3]_q^2 t}{\ddots}}}} \quad \text{and} \quad \sum_{n \ge 0} E_{2n+1}(q) t^n = \frac{1}{1 - \frac{[1]_q[2]_q t}{1 - \frac{[2]_q[3]_q t}{1 - \frac{[3]_q[4]_q t}{\ddots}}}} \quad (30) $$

The exponential generating function of the numbers $E_n(1)$ is the function $\tan(x) + \sec(x)$. They have the following combinatorial interpretation [11, 14]: $E_n(q)$ is the generating function counting the occurrences of the generalized pattern 31-2 in alternating permutations of size $n$. We say that $\sigma \in \mathfrak{S}_n$ is alternating when $\sigma(1) > \sigma(2) < \sigma(3) > \dots$. From (30) these numbers are particular case of Al-Salam-Chihara moments:

$$ E_{2n}(q) = \left(\frac{2}{1-q}\right)^{2n} \mu_{2n}|_{a=-b=i\sqrt{q}}, \quad \text{and} \quad E_{2n+1}(q) = \left(\frac{2}{1-q}\right)^{2n} \mu_{2n}|_{a=-b=iq} \quad (31) $$

(where $i^2 = -1$). From (28) and $q$-binomial identities it is possible to obtain the closed formulas for $E_{2n}(q)$ and $E_{2n+1}(q)$ that were given in [14], in a similar manner that (4) can be simplified into (8) when $\alpha = \beta = 1$. Indeed, from (28) we can rewrite:

$$ 2^{2n} \mu_{2n} = \sum_{m=0}^{n} \left( \binom{2n}{n-m} - \binom{2n}{n-m-1} \right) \sum_{j,k \ge 0} (-1)^j q^{\binom{j+1}{2}} \left[ \begin{matrix} 2m-j \\ j \end{matrix} \right]_q \left[ \begin{matrix} 2m-2j \\ k \end{matrix} \right]_q \left( \frac{b}{a} \right)^k a^{2m-2j} \quad (32) $$

This latter sum over $j$ and $k$ is also

$$ \sum_{j,k \ge 0} (-1)^j q^{\binom{j+1}{2}} \left[ \begin{matrix} 2m-j \\ j+k \end{matrix} \right]_q \left[ \begin{matrix} j+k \\ j \end{matrix} \right]_q \left( \frac{b}{a} \right)^k a^{2m-2j} = \sum_{\ell \ge j \ge 0} (-1)^j q^{\binom{j+1}{2}} \left[ \begin{matrix} 2m-j \\ \ell \end{matrix} \right]_q \left[ \begin{matrix} \ell \\ j \end{matrix} \right]_q \left( \frac{b}{a} \right)^{\ell-j} a^{2m-2j} \quad (33) $$

The sum over $j$ can be simplified in the case $a = -b = i\sqrt{q}$, or $a = -b = iq$, using the $q$-binomial identities already used in [13] (see Lemma 2):

$$ \sum_{j \ge 0} (-1)^j q^{\binom{j}{2}} \left[ \begin{matrix} 2m-j \\ \ell \end{matrix} \right]_q \left[ \begin{matrix} \ell \\ j \end{matrix} \right]_q = q^{\ell(2m-\ell)}, \quad (34) $$

and

$$ \sum_{j \ge 0} (-1)^j q^{\binom{j-1}{2}} \left[ \begin{matrix} 2m-j \\ \ell \end{matrix} \right]_q \left[ \begin{matrix} \ell \\ j \end{matrix} \right]_q = \frac{q^{\ell(2m-\ell)} - q^{\ell(2m-\ell)} + q^{\ell(2m-\ell+1)} - q^{\ell(2m-\ell+1)}}{q^{2m-1}(1-q)} \quad (35) $$
Omitting details, this gives a new proof of the Touchard-Riordan-like formulas for $q$-secant and $q$-tangent numbers [14]:

$$E_{2n}(q) = \frac{1}{(1-q)^{2n}} \sum_{m=0}^{n} \left( \binom{2n}{n-m} - \binom{2n}{n-m-1} \right) \sum_{\ell=0}^{2m} (-1)^{\ell+m} q^{\ell(2m-\ell)+m}, \quad (36)$$

and

$$E_{2n+1}(q) = \frac{1}{(1-q)^{2n+1}} \sum_{m=0}^{n} \left( \binom{2n+1}{n-m} - \binom{2n+1}{n-m-1} \right) \sum_{\ell=0}^{2m+1} (-1)^{\ell+m} q^{\ell(2m+2-\ell)}. \quad (37)$$

## Acknowledgements

I thank my advisor Sylvie Corteel for her help, advice, support and kindness. I thank Einar Steingrímsson, Jiang Zeng and Lauren Williams for their help.

## References

[1] W. A. Al-Salam and T. S. Chihara, Convolutions of orthonormal polynomials, SIAM J. Math. Anal. 7 (1976), 16–28.

[2] R. A. Blythe and M. R. Evans, Nonequilibrium steady states of matrix product form: A solver's guide, J. Phys. A: Math. gen. 40, 333–441.

[3] R. A. Blythe, M. R. Evans, F. Colaiori and F. H. L. Essler, Exact solution of a partially asymmetric exclusion model using a deformed oscillator algebra, J. Phys. A: Math. Gen. 33 (2000), 2313–2332.

[4] R. Brak, S. Corteel, J. Essam, R. Parviainen and A. Rechnitzer, A combinatorial derivation of the PASEP stationary state, Electron. J. Combin. 13(1) (2006), R108.

[5] S. Corteel, Crossings and alignments of permutations, Adv. in Appl. Math. 38(2) (2007), 149–163.

[6] S. Corteel, P. Nadeau, Bijections for permutation tableaux, European. J. Combin. 30(1) (2009), 295–310.

[7] S. Corteel and L. K. Williams, Tableaux combinatorics for the asymmetric exclusion process, Adv. in Appl. Math. 39(3) (2007), 293–310.

[8] S. Corteel, M. Josuat-Vergès, T. Prellberg and M. Rubey, Matrix Ansatz, lattice paths and rook placements, Proc. FPSAC 2009.

[9] B. Derrida, M. Evans, V. Hakim and V. Pasquier, Exact solution of a 1D asymmetric exclusion model using a matrix formulation, J. Phys. A: Math. Gen. 26 (1993), 1493–1517.

[10] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 41 (1982), 145–153.

[11] G.-N. Han, A. Randrianarivony, J. Zeng, Un autre $q$-analogue des nombres d'Euler, Séminaire Lotharingien de Combinatoire, B42e (1999).
[12] M. Ismail and D. Stanton, *q*-Taylor theorems, polynomial expansions, and interpolation of entire functions, J. Approx. Th. 123 (2003), 125–146.

[13] M. Josuat-Vergès, Rook placements in Young diagrams and permutation enumeration, preprint 2008, arXiv:0811.0524v2 [math.CO].

[14] M. Josuat-Vergès, *A *q*-enumeration of alternating permutations, to appear in European J. Combin.

[15] A. Kasraoui, D. Stanton and J. Zeng, The Combinatorics of Al-Salam-Chihara *q*-Laguerre polynomials, preprint 2008, arXiv:0810.3232v1 [math.CO].

[16] D. Kim, On combinatorics of Al-Salam Carlitz polynomials, European. J. Combin. 18(3) (1997), 295–302.

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

[18] T. Sasamoto, One-dimensional partially asymmetric simple exclusion process with open boundaries: orthogonal polynomials approach, J. Phys. A: Math. Gen. 32 (1999), 7109–7131.

[19] D. Stanton, personal communication.

[20] X. G. Viennot, Une théorie combinatoire des polynômes orthogonaux, Notes de cours, UQAM, Montréal 1988.

[21] A. Varvak, Rook numbers and the normal ordering problem, J. Combin. Theory Ser. A 112(2) (2005), 292–307.