Statistics on staircase tableaux, eulerian and mahonian statistics

Sylvie Corteel and Sandrine Dasse-Hartaut†

LIAFA, CNRS et Université Paris-Diderot, Paris, France

**Abstract.** We give a simple bijection between some staircase tableaux and tables of inversion. Some nice properties of the bijection allows us to define some $q$-Eulerian polynomials related to the staircase tableaux. We also give a combinatorial interpretation of these $q$-Eulerian polynomials in terms of permutations.

**Résumé.** Nous proposons une bijection simple entre certains tableaux escalier et les tables d'inversion. Cette bijection nous permet de montrer que les statistiques Euleriennes et Mahoniennes sont naturelles sur les tableaux escalier. Nous définissons des polynômes $q$-Eulériens et en donnons une interprétation combinatoire.

**Keywords:** staircase tableaux, bijection, permutations

# 1 Introduction

Staircase tableaux are new combinatorial objects defined by S. Corteel and L. Williams (10). They are related to the asymmetric exclusion process on a one-dimensional lattice with open boundaries (ASEP) and were also used to give a combinatorial formula for the moments of the Askey-Wilson polynomials defined in (1; 11). Those results are presented in (10; 7). The staircase tableaux are generalizations of the permutation tableaux (6; 16) coming from work and alternative tableaux (13; 17).

**Definition 1** (10) A staircase tableau of size $n$ is a Young diagram of shape $(n, n-1, ..., 1)$ such that boxes are empty or filled with $\alpha, \beta, \gamma, \delta$ and that

* the boxes along the diagonal are not empty

* a box in the same row and on the left of a $\beta$ or a $\delta$ is empty

* a box in the same column and above a $\alpha$ or a $\gamma$ is empty

**Definition 2** (10) The weight $\text{wt}(\mathcal{T})$ of a staircase tableau $\mathcal{T}$ is a monomial in $\alpha, \beta, \gamma, \delta, q$, and $u$, which we obtain as follows. Every blank box of $\mathcal{T}$ is assigned a $q$ or $u$, based on the label of the closest labeled box to its right in the same row and the label of the closest labeled box below it in the same column, such that:

<footnote>†Both authors are partially supported by the ANR grant ANR-08-JCJC-0011 and the second author was supported by the ANR grant BLAN07-2-195422 from March to September 2010.
corteel@liafa.jussieu.fr, dasse@liafa.jussieu.fr</footnote>
<figure><img src="image_1.png" /></figure>

<figure><img src="image_2.png" /><figcaption>Fig. 1: A staircase tableau of size 7 and its weight</figcaption></figure>

* every blank box which sees a $\beta$ to its right gets assigned a $u$;

* every blank box which sees a $\delta$ to its right gets assigned a $q$;

* every blank box which sees an $\alpha$ or $\gamma$ to its right, and an $\alpha$ or $\delta$ below it, gets assigned a $u$;

* every blank box which sees an $\alpha$ or $\gamma$ to its right, and a $\beta$ or $\gamma$ below it, gets assigned a $q$.

After assigning a $q$ or $u$ to each blank box in this way, the weight of $\mathcal{T}$ is then defined as the product of all labels in all boxes.

The tableau on Figure 1 has weight $\alpha^3\beta^2\gamma^3\delta^3q^9u^8$.

**Remark.** The weight of a staircase tableau always has degree $n(n+1)/2$. For convenience, we will sometimes set $u = 1$, since this results in no loss of information.

**Definition 3** The generating polynomial of staircase tableaux of size $n$ is

$$Z_n(\alpha, \beta, \gamma, \delta, q, u) = \sum_{T \text{ of size } n} \mathrm{wt}(T).$$

When $q = u = 1$, this generating polynomial is simple (10):

$$Z_n(\alpha, \beta, \gamma, \delta, 1, 1) = \prod_{i=0}^{n-1} (\alpha + \beta + \gamma + \delta + i(\alpha + \gamma)(\beta + \delta)). \quad (1)$$

In (7), the authors give an explicit formula for $Z_n(\alpha, \beta, \gamma, \delta, q, 1)$. It is very complicated and is derived from a formula of the moments of the Askey-Wilson polynomials. In this paper, we show that there are other special cases of $Z_n$ that have a very nice form. In particular, we show that

**Theorem 1**

$$Z_n(0, \beta, \gamma, 0, q, u) = \prod_{i=0}^{n-1} (\beta u^i + \beta \gamma (u^{i-1}q + \dots + u q^{i-1}) + \gamma q^i).$$

Notice that as the definition of the tableaux implies that $Z_n(\alpha, \beta, \gamma, \delta, 1, 1) = Z_n(0, \beta+\delta, \alpha+\gamma, 0, 1, 1)$, our result is a refinement of (1).

We will prove the results in two ways: a bijection and an inductive argument. We will see that both of these arguments are quite simple. This gives the simplest argument that there exist $4^n n!$ staircase tableaux
of size $n$ (10; 7). We will study $(\beta/\gamma)$-tableaux that are staircase tableaux which do not contain any $\alpha$ or $\delta$. We show that our very simple bijection can be generalized to any family of staircase tableaux.

We continue the study of the $(\beta/\gamma)$-tableaux. When those tableaux have exactly $n$ entries equal to $\gamma$, there exist exactly $n!$ such tableaux. In (7), it is shown that they are in bijection with permutation tableaux (16) or alternative tableaux (13; 17). We will show that the bijection allows us in this case to understand the statistic "number of $\beta$s on the diagonal" which is known to be related to the eulerian numbers (16; 18). Thanks to this we will introduce some new $q$-Eulerian polynomials and will give some combinatorial interpretation in terms of permutations.

We start in this paper by studying $Z_n(\alpha, \beta, \gamma, \delta, 1, 1)$ and some simple consequences and symmetries on staircase tableaux. We then study the $(\beta/\gamma)$-staircase tableaux and define the $q$-Eulerian polynomials. We show how the same type of arguments can be extended for type B staircase tableaux. We end this extended abstract with some concluding remarks and open problems.

## 2 Warm up on staircase tableaux

We first recall some simple recurrence to compute $Z_n(\alpha, \beta, \gamma, \delta, 1, 1)$ given in (7). Thanks to the definition of staircase tableaux, it is direct to see that

$$Z_n(\alpha, \beta, \gamma, \delta, 1, 1) = Z_n(\alpha + \gamma, \beta + \delta, 0, 0, 1, 1)$$

We then just need to count tableaux with $\alpha$s and $\beta$s as done for permutation tableaux in (6). As in (10), we say that a line is indexed by $\alpha$ if the leftmost entry of the line is $\alpha$. Let $Z_{n,k}(\alpha, \beta)$ be the number of tableaux counted by $Z_n(\alpha, \beta, 0, 0, 1, 1)$ with $k$ rows indexed by $\alpha$. Then if we add a new column to a staircase tableau, we see that:

$$Z_{n,k}(\alpha, \beta) = \sum_{\ell \ge k-1} \alpha \beta^{\ell-k+1} \binom{\ell}{k-1} Z_{n-1, \ell}(\alpha, \beta) + \sum_{\ell \ge k} \beta^{\ell-k+1} \binom{\ell}{k} Z_{n-1, \ell}(\alpha, \beta).$$

for $n > 0$ and $i \le n$. The initial conditions are $Z_{0,0} = 1$ and $Z_{n,k} = 0$ if $k < 0$ or $n < 0$ or $k > n$. This implies that $Z_n(\alpha, \beta, x) = \sum_k Z_{n,k}(\alpha, \beta)x^k$ follows the recurrence for $n > 0$

$$Z_n(\alpha, \beta, x) = (\alpha x + \beta) Z_{n-1}(\alpha, \beta, x + \beta)$$

and with the initial condition $Z_0(\alpha, \beta, x) = 1$. The solution is $Z_n(\alpha, \beta, x) = \prod_{i=0}^{n-1} (\alpha x + \beta + i\alpha\beta)$ and therefore $Z_n(\alpha, \beta, 0, 0, 1, 1) = \prod_{i=0}^{n-1} (\alpha + \beta + i\alpha\beta)$.

This implies the following known results (7):

1. The number of staircase tableaux of size $n$ with $\alpha$s and $\beta$s is $(n+1)!.

2. The number of staircase tableaux of size $n$ is $4^n$!

3. The number of staircase tableaux of size $n$ with $\alpha$s and $\beta$s and $\gamma$s is $(2n+1)!!$.

We get some other simple results.

**Lemma 1** 1. The number of staircase tableaux of size $n$ with a maximum number of $\alpha, \beta, \gamma$ or $\delta$ is $4^n(n-1)!$.
2. The number of staircase tableaux of size $n$ with a minimum number of $\alpha, \beta, \gamma$ or $\delta$ is $4^n$.

From the definition of the weight of the tableaux, we also get:

**Lemma 2** 1. The number of tableaux of size $n$ with $\alpha$s and $\beta$s and a minimum (resp. maximum) number of us is $3 \times 4^{\frac{n-1}{2}}$ (resp. $n$).

2. The number of tableaux of size $n$ a minimum number of us is $\binom{n}{2}$.

We can also define three involutions on tableaux. The proof that they are involutions follows directly from the definition of the tableaux.

**Involution 1.** Let $\phi$ be the involution on the staircase tableaux that takes a tableau $T$, exchanges $\alpha$s and $\beta$s, and exchanges $\gamma$s and $\delta$s, and conjugates the tableau. We can check that the tableau obtained is a staircase tableau, and that the number of $\alpha$ in $T$ is the number of $\beta$ in $\phi(T)$ and so on. This implies that:

$$Z_n(\alpha, \beta, \gamma, \delta, 1, 1) = Z_n(\beta, \alpha, \delta, \gamma, 1, 1).$$

An example is given on Figure 2.

<figure><img src="image_3.png" /><figcaption>**Fig. 2:** Example of the involution 1</figcaption></figure>

**Involution 2.** We can also use the involution $\psi$ that exchanges $\alpha$s with $\delta$s, and $\beta$s with $\gamma$s and conjugates the obtained tableau. This gives :

$$Z_n(\alpha, \beta, \gamma, \delta, 1, 1) = Z_n(\delta, \gamma, \beta, \alpha, 1, 1).$$

**Involution 3.** Finally if we exchange $\alpha$s and $\gamma$s and $\beta$s and $\delta$s, we get

$$Z_n(\alpha, \beta, \gamma, \delta, q, u) = Z_n(\gamma, \delta, \alpha, \beta, \alpha, u, q).$$

**Open problem** Find a combinatorial proof of the fact that :

$$Z_n(\alpha, \beta, \gamma, \delta, q, u) = Z_n(\beta, \alpha, \delta, \gamma, q, u).$$

By a combinatorial proof, we mean a natural involution on the tableaux.
# 3 A bijection from tableaux to inversion table

## 3.1 Tableaux with $n$ entries equal to $\gamma$ and $\beta$s

We first recall that $(\beta/\gamma)$-tableaux are staircase tableaux with no $\alpha$ or $\delta$. We start by enumerating the $(\beta/\gamma)$-tableaux of size $n$ that contain exactly $n$ entries equal to $\gamma$. Let $\tilde{Z}_n(\beta, \gamma, q)$ be their generating polynomial. We will show that:

**Proposition 1** $\tilde{Z}_n(\beta, \gamma, q) = \gamma^n \prod_{i=0}^{n-1} (\beta(1+q+\dots+q^{i-1})+q^i)$.

We define a bijection from those tableaux of size $n$ to permutations of $S_n$ via tables of inversion $T = [T[1], \dots, T[n]]$ with $T[i] < i$ for $1 \le i \le n$.

**A bijection from tableaux to permutations.** There is one $\gamma$ in each column, so we can number them: the leftmost $\gamma$ will be designed by $\gamma_1$, the following by $\gamma_2$ and so on, until $\gamma_n$. Then, for each $\gamma_i$, we count the number $t_i$ of cells that do not contain a Greek letter to the immediate left of $\gamma_i$. We can construct a table of inversion $T$ with $T[i] = t_i$.

<figure><img src="image_4.png" /><figcaption>**Fig. 3:** A $(\beta/\gamma)$-staircase tableau</figcaption></figure>

For example from the tableau on Figure 3, we obtain the table $T = (0, 1, 2, 1, 2, 2, 1)$. Then we can use any bijection from inversion table to permutations and obtain a permutation. For example if $T[i]$ corresponds to the number of elements $j < i$ such that $\sigma^{-1}(i) < \sigma^{-1}(j)$, we obtain the permutation (3,2,5,6,4,7,1).

**Inverse of the bijection.** We have an inversion table $T$ of size $n$, we construct a staircase tableau of size $n$ using the following algorithm:

* Put $\gamma$ in the last column and first row, and mark $T[n]$ cells to its left (with $q$).

* For $i = n-1$ to 1

- Look at the topmost cell in the $i$th column which is not occupied and put a $\gamma$ in it.

- Mark the $T[i]$ cells to its left (with $q$)

- Fill all the empty cells under it with $\beta$

- Mark all the cells to the left of the $\beta$s (with $u$)

We have exactly one $\gamma$ in each column. Each $\beta$ has no Greek letter to its left and each $\gamma$ has no Greek letter above itself. We have a staircase tableau, and it is obvious that the table of inversion obtained from
this staircase tableau is exactly $T$. Therefore we defined a bijection. Moreover all the cells directly to the left of a $\gamma$ get a weight $q$. Therefore

**Proposition 2** The number of $(\beta/\gamma)$-staircase tableaux of size $n$ with $n$ entries equal to $\gamma$, $a$ entries equal to $q$, $b$ rows indexed by $\gamma$ is equal to the number of permutations of $\{1, \dots, n\}$ with $a$ inversions and $b$ left-to-right minima.

Using well known results on enumeration of permutations (see for example (15) Chapter 1), we get a proof of Proposition 1.

## 3.2 Generalization of the bijection

Now we can generalize the previous bijection to staircase tableaux. Start with a staircase tableau of size $n$ and number the columns from 1 to $n$ from left to right. Then for each column $i$, we look at the topmost Greek letter in column $i$ and count the number of cells $j$ directly to its left that does not contain any Greek letter. If this letter, say $x$, is topmost and leftmost, we record $T[i] = j_x$. Otherwise let $y$ be the first Greek letter to the left of $x$ and let $z$ be the first Greek letter under $y$. Then $T[i] = j_{x,z}$.

For example, using the tableau of Figure 1, we obtain $T = (0_{\gamma}, 1_{\beta}, 2_{\alpha}, 1_{\alpha,\beta}, 2_{\alpha,\delta}, 2_{\gamma,\delta}, 1_{\gamma,\delta})$.

For the general case, this is a bijection from staircase tableaux of size $n$ and colored tables of inversion $T$ such that $T[i] = (i-1)_x$ with $x \in \{\alpha, \beta, \gamma, \delta\}$ or $T[i] = j_{x,y}$ with $0 \le j < i-1$ and $x \in \{\alpha, \gamma\}$ and $y \in \{\beta, \delta\}$.

This implies equation (1), that is:

$$Z_n(\alpha, \beta, \gamma, \delta, 1, 1) = \prod_{i=0}^{n-1} (\alpha + \beta + \gamma + \delta + i(\alpha + \gamma)(\beta + \delta)).$$

For the $(\beta/\gamma)$-tableaux, this is a bijection from $(\beta/\gamma)$-staircase tableaux of size $n$ and colored tables of inversion $T$ such that $T[i] = (i-1)_x$ with $x \in \{\beta, \gamma\}$ or $T[i] = j_{\gamma,\beta}$ with $0 \le j < i-1$. The number of $q$ of the tableau is equal to the sum of the $T[i]$ (except the ones that are equal to $i_{\beta}$). This implies that

$$Z_n(0, \beta, \gamma, 0, q, 1) = \prod_{i=0}^{n-1} (\beta + \beta\gamma(q + \dots + q^{i-1}) + \gamma q^i).$$

This is Theorem 1.

**Remark.** As in the previous section, we could have proven this by recurrence. Let $Z_{n,k}(\beta, \gamma, q)$ be the number of tableaux counted by $Z_n(0, \beta, \gamma, 0, q, 1)$ with $k$ rows indexed by $\gamma$. We look at how many ways we can add a column to a tableau of size $n-1$. We get:

$$Z_{n,k}(\beta, \gamma, q) = \sum_{\ell \ge k-1} \gamma \beta^{\ell-k+1} q^{k-1} \binom{\ell}{k-1} Z_{n-1,\ell}(\beta, \gamma, q) + \sum_{\ell \ge k} \beta^{\ell-k+1} q^k \binom{\ell}{k} Z_{n-1,\ell}(\beta, \gamma, q).$$

for $n > 0$ and $k \le n$. The initial condition are $Z_{0,0} = 1$ and $Z_{n,k} = 0$ if $k < 0$ or $n < 0$ or $k > n$. Let $Z_n(\beta, \gamma, q, x) = \sum_k Z_{n,k}(\beta, \gamma, q)x^k$. The recurrence implies that $Z_0(\beta, \gamma, q, x) = 1$ and for $n > 0$

$$Z_n(\beta, \gamma, q, x) = (\gamma x + \beta) Z_{n-1}(\beta, \gamma, q, xq + \beta)$$
The solution is

$$Z_n(\beta, \gamma, q, x) = \prod_{i=0}^{n-1} (\beta + \beta\gamma(q + \dots + q^{i-1}) + \gamma x q^i).$$

$$\text{Therefore } Z_n(0, \beta, \gamma, 0, q, 1) = \prod_{i=0}^{n-1} (\beta + \beta\gamma(q + \dots + q^{i-1}) + \gamma q^i).$$

# 4 q-Eulerian polynomials

## 4.1 Entries equal to $\beta$ on the diagonal

Again we number the columns of the tableau from left to right. In this section we use some properties of the bijection defined in Section 3.1. We need the following simple lemma.

**Lemma 3** Given a $(\beta/\gamma)$-tableau of size $n$ with $n$ entries equal to $\gamma$, there is a $\beta$ on the diagonal in column $i$ if and only if there is at least one $\gamma$ in column $j > i$ that has $j - i - 1$ entries equal to $q$ to its immediate left.

**Proof:** Direct from the definition of the tableau and the fact that those tableaux have exactly one $\gamma$ in each column. $\square$

We use the bijection of Section 3.1. We now transform the table of inversion $T = [T[1], \dots, T[n]]$ obtained from the $(\beta/\gamma)$-tableau into the table $[0 - T[1], 1 - T[2], \dots, n - 1 - T[n]]$. We still obtain a table of inversion. Moreover the distinct positive values of the table of inversion now correspond to the diagonal entries filled with $\beta$. We skip the proof of this claim. Therefore

**Proposition 3** There exists a bijection between

* $(\beta/\gamma)$-tableaux of size $n$ with $n$ entries equal to $\gamma$, entries equal to $\beta$ in diagonals $\{i_1, \dots, i_k\}$ and $a$ entries equal to $q$

* table of inversion $T = [T[1], \dots, T[n]]$ such that

- for $1 \le j \le k$, there exists at least one $\ell$ such that $T[\ell] = i_j$

- $\sum_{i=1}^{n} T[i] = \binom{n}{2} - a$.

For fixed $n$ and $k$, let $\mathcal{Z}_{n,k}(\beta, \gamma, q)$ be the generating polynomial of $(\beta/\gamma)$-tableaux of size $n$ with $n$ entries equal to $\gamma$ and $k$ entries equal to $\beta$ on the diagonal.

**Lemma 4** The number $\mathcal{Z}_{n,k}(1, 1, 1)$ is equal to the Eulerian numbers $E_{n,k+1}$.

**Proof:** This is direct as these staircase tableaux of size $n$ are in bijection with permutation tableaux of length $n$. This bijection is such that the entries equal to $\beta$ on the diagonal are in one-to-one correspondence with the columns of the permutation tableau. See (10) for the bijection from staircase tableaux to permutation tableaux. See (6; 16) for the bijection from permutation tableaux to permutations. $\square$

We now interpret $\mathcal{Z}_{n,k}(\beta, \gamma, q)$ in terms of permutations.
## 4.2 Permutations with $k$ descents

We have seen that staircase tableaux with $k$ entries equal to $\beta$ on the diagonal are in bijection with tables of inversion with $k$ different positive values. We construct here a bijection between these tables of inversion and permutations with $k$ descents.

### 4.2.1 From permutations with $k$ descents to the tables of inversion with $(k+1)$ distinct values (including 0)

Let $\sigma$ be a permutation with $k$ descents. We construct a table of inversion $T$ from $\sigma$. For $i$ from 1 to $n$, let $j$ be the first element to the right of $i$ satisfying $j < i$. If such a $j$ does not exist, set $T[i] = 0$ and $T[i] = j$ otherwise.

It is easy to check that for all $i$, $T[i] < i$. Moreover all the values of the table are either 0 or the values of the end of the descents of $\sigma$. Finally, for all descent in $\sigma$ of index $i$, $\sigma_{i+1}$ is in at least one index in $T$. Then the table has $k+1$ distinct values.

For example, let $\sigma = (5, 8, 2, 1, 6, 7, 3, 4, 9)$. We obtain $T = [0, 1, 0, 0, 2, 3, 3, 2, 0]$. The permutation $\sigma$ has three descents that end in 1, 2 and 3, and the table has four distinct values 0, 1, 2 and 3.

### 4.2.2 From tables of inversion to permutations

We start a table $T$ of inversions with $k+1$ distincts values. We create $\sigma$ by inserting successively the letters $i = 1, 2, \dots, n$. If $T[i] > 0$ then we insert $i$ directly before $T[i]$ and add $i$ at the end otherwise.

For example, if we have the table $T = [0, 0, 1, 0, 4, 1, 0]$, we get the permutation $\sigma = (3, 6, 1, 2, 5, 4, 7)$ which has two descents. This is clearly the reverse map of the previous subsection.

We now can interpret $\mathcal{Z}_{n,k}(\beta, \gamma, q)$ in terms of permutations. Given a permutation $\sigma$ of $S_n$, we suppose that $\sigma(n+1) = 0$. Let $M(\sigma, i)$ be $j$ if $j$ is the first element to the right of $i$ such that $j < i$. Let

$$M(i) = \min\{j \mid j < i \text{ and } \sigma^{-1}(j) > \sigma^{-1}(i)\}$$

$$M(\sigma) = \sum_{i} M(\sigma, i).$$

Let $\text{RLmin}(\sigma)$ be the number of right-to-left minima of $\sigma$. For example, if $\sigma = (3, 6, 1, 2, 5, 4, 7)$ then $M(\sigma, 3) = M(\sigma, 6) = 1$, $M(\sigma) = 6$ and $\text{RLmin}(\sigma) = 4$. Let $S_{n,k}$ be the set of permutations in $S_n$ with $k$ descents. Thanks to the previous bijection, we get that

**Proposition 4**

$$\mathcal{Z}_{n,k}(\beta, \gamma, q) = \gamma^n \beta^n q^{\binom{n}{2}} \sum_{\sigma \in S_{n,k}} q^{-M(\sigma)} \beta^{-\text{RLmin}(\sigma)}.$$

But also we get a refinement. Let $I = \{i_1, \dots, i_k\}$, let $Z_{n,I}(\beta, \gamma, q)$ be the generating polynomial of the $(\beta/\gamma)$-tableaux of size $n$ with $n$ entries equal to $\gamma$ and where entries equal to $\beta$ on the diagonals are indexed by $I$. Let $S_n(I)$ be the set of permutations of $S_n$ such that $\sigma(j-1) > \sigma(j)$ if and only if $\sigma(j) \in I$. Then

**Proposition 5**

$$Z_{n,I}(\beta, \gamma, q) = q^{\binom{n}{2}} \beta^n \gamma^n \sum_{\sigma \in S_n(I)} q^{-M(\sigma)} \beta^{-\text{RLmin}(\sigma)}.$$

**Remark.** The case $\beta = q = 1$ was already known for permutation tableaux (6; 18).
# 5 Type B tableaux

In this section, we study some type B staircase tableaux. They are the analogue of the type B permutation and alternative tableaux (12; 4; 5).

**Definition 4** A type B staircase tableau of size $n$ is a staircase tableau of size $2n$ that is invariant under the involution 2 from Section 2.

As the tableau is symmetric, we only keep half of it. A type B staircase tableau of size $n$ is therefore of shape $(1, 2, \dots, n, n, n-1, \dots, 1)$. We number the rows from top to bottom and the columns from left to right. We denote by sign-diagonal the cells $(i, i)$, for $1 \le i \le n$. As in Section 1, we define the generating polynomial $Z_n^{(B)}(\alpha, \beta, \gamma, \delta, q, u)$. We only look at the case $u = q = 1$.

We first investigate tableaux with only $\beta$s and $\gamma$s. We can construct a bijection from those tableaux the signed permutations, using the idea of the bijection between staircase tableaux and permutations:

* When column $i$ does not contain a $\gamma$, we add a $\gamma$ in cell $(i, i)$.

* We number the $\gamma$s from left to right.

* We create two tables, the table of inversion $T$ and the table of sign $\theta$

* For each $i$, $T[i]$ is the number of cells with no Greek letter immediately to the left of $\gamma_i$ (in the column $i$). The sign of $i$ is $\ominus$ if $\gamma_i$ is in the sign-diagonal and $\oplus$ otherwise.

For example, starting from the tableau on Figure 4, we obtain the signed permutation given by the tables $T = [0, 0, 2, 1, 2]$ and $\theta = [\ominus, \oplus, \oplus, \ominus, \ominus]$.

<figure><img src="image_5.png" /><figcaption>Fig. 4: A type B staircase tableau and the tableau when $\gamma$s are inserted on the sign-diagonal</figcaption></figure>

Therefore

**Proposition 6** The previous algorithm defines a bijection between type B staircase tableaux of size $n$ with $\gamma$s and $\beta$s and signed permutations of $\{1, \dots, n\}$. This bijection implies that

$$Z_n^{(B)}(0, \beta, \gamma, 0, 1, 1) = (\gamma + \beta)^n \prod_{i=0}^{n-1} (1 + \beta i).$$
**Proof:** We obviously have a function that transforms a tableau into a signed permutation. To see that it is a bijection, we just have to notice that there is two choices for $\gamma_n$, and that knowing $\theta(n)$ allows us to know in which of these two cells is the $\gamma$ of column $n$. Then for each $i$, if we know where are all the $\gamma_j$ for $j > i$, we have two choices : $\gamma_i$ may be on the left of a $\gamma_j$ or on the diagonal or on the sign diagonal. The latter case corresponds to $\theta[i] = \ominus$. The others are identical to the construction between staircase tableaux and permutations. There is no other choice since for each $\gamma$ on the column $i$ that is not on the sign-diagonal the row $i$ has to be empty (recall that the whole tableau is invariant under the involution 2 from Section 2). $\square$

Again, it is easy to see that:

$$Z_n^{(B)}(\alpha, \beta, \gamma, \delta) = Z_n^{(B)}(0, \beta + \delta, \gamma + \alpha, 0). \qquad (2)$$

And we obtain the following corollary

**Corollary 1** There exist $4^n(2n - 1)!!$ staircase tableaux of type B and size n.

# 6 Conclusion

In this paper, we give a very simple bijection between $(\beta/\gamma)$-staircase tableaux and permutations. This bijection is such that the number of $q$ in the tableaux is related to the number of inversions of the permutation. Thanks to this construction, we get some possibly new $q$-Eulerian polynomials. This work opens a set of natural open questions.

1. Is there a natural partially ordered set on $(\beta/\gamma)$-staircase tableaux that is isomorphic to the (weak) Bruhat order?

2. Can we compute these $q$-Eulerian polynomials as done in (18) for the permutation tableaux?

3. Can we compute the generating polynomial of $(\beta/\gamma)$-staircase tableaux when the diagonal is fixed as done in (18; 14) for the permutation tableaux?

Our goal in this study of the staircase tableaux is to understand the $q$-statistics in the general staircase tableaux. We know that this is related to crossings or 31-2 patterns in permutations for the case with only $\alpha$s and $\beta$s (3; 6; 16), to inversions in permutation for the case with only $\beta$s and $\gamma$s and to f-crossings in matchings (7) for the case with only $\alpha$s, $\beta$s and $\gamma$s. Similar results hold also for the type B analogue (12; 5; 4). The general case is still open for now.

# References

[1] R. Askey and J. Wilson, Some basic hypergeometric orthogonal polynomials that generalize Jacobi polynomials, Mem. Amer. Math. Soc. 54 (1985), no. 319.

[2] A. Burstein, On some properties of permutation tableaux, Ann. Combin. 11 (2007) no. 3-4, 355-368.

[3] S. Corteel, Crossings and alignments of permutations, Adv. Appl. Math. 38 (2007), no 2, 149-163.

[4] S. Corteel, M. Josuat-Vergès and J.S. Kim, Enumeration of type B Le-diagrams and permutation tableaux, in preparation (2011).
[5] S. Corteel, M. Josuat-Vergès and L.K. Williams, The matrix ansatz, permutation tableaux and permutations, to appear in Adv. Appl. Math, to appear (2012).

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

[7] S. Corteel, R. Stanley, D. Stanton, L. Williams, Formulae for Askey-Wilson moments and enumeration of staircase tableaux, Trans. Amer. Math. Soc., to appear (2011).

[8] S. Corteel, L. Williams, Tableaux combinatorics for the asymmetric exclusion process, Adv. Appl. Math. 39 (2007), 293-310.

[9] S. Corteel, L. Williams, A Markov chain on permutations which projects to the asymmetric exclusion process, Int. Math. Res. Not. (2007), article ID mm055.

[10] S. Corteel and L. Williams, Staircase tableaux, the asymmetric exclusion process, and Askey-Wilson polynomials. Proc. Natl. Acad. Sci. USA 107 (2010), no. 15, 6726-6730. Long version to appear in Duke Math J. (2011).

[11] R. Koekoek, P. Lesky, and R. Swarttouw, Hypergeometric orthogonal polynomials and their $q$-analogues, with a foreword by T. Koornwinder, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2010

[12] T. Lam and L.K. Williams, Total positivity for cominuscule Grassmannians. New York J. Math. 14 (2008), 53-99.

[13] P. Nadeau, The structure of alternative tableaux, J. Comb. Theory, Ser. A 118(5): 1638-1660 (2011).

[14] J.-C. Novelli, J.-Y. Thibon and L.K. Williams, Combinatorial Hopf algebras, noncommutative Hall-Littlewood functions, and permutation tableaux. Adv. Math. 224 (2010), no. 4, 1311-1348,

[15] R.P. Stanley, Enumerative combinatorics. Vol. 1. With a foreword by Gian-Carlo Rota. Corrected reprint of the 1986 original. Cambridge Studies in Advanced Mathematics, 49. Cambridge University Press, Cambridge, 1997.

[16] E. Steingrímsson, L. Williams, Permutation tableaux and permutation patterns, Journ. Comb. Th. A, **114** (2007), 211-234.

[17] X. Viennot, slides and video from the talk "Alternative tableaux, permutations, and partially asymmetric exclusion process," at the Isaac Newton Institute, April 23, 2008, http://www.newton.ac.uk/webseminars/pg+ws/2008/csm/csmw04/0423/viennot/.

[18] L. Williams, Enumeration of totally positive Grassmann cells. Adv. Math. 190 (2005), no. 2, 319-342.