# On joint distribution of adjacencies, descents and some Mahonian statistics

Alexander Burstein<fnref n="1" />

**Abstract.** We prove several conjectures of Eriksen regarding the joint distribution on permutations of the number of adjacencies (descents with consecutive values in consecutive positions), descents and some Mahonian statistics. We also prove Eriksen’s conjecture that a certain bistatistic on Viennot’s alternative tableaux is Euler-Mahonian.

**Résumé.** Nous demontrons plusieurs conjectures d’Eriksen concernant la distribution conjointe sur les permutations du nombre de contiguités (descentes avec des valeurs consécutives en positions consécutives), les descentes et quelques statistiques mahoniennes. Nous demontrons également une conjecture d’Eriksen qui affirme qu’une certaine bistatistique sur les tableaux alternatifs de Viennot est euler-mahonienne.

**Keywords:** permutation statistic, Eulerian, Mahonian, descent, adjacency, pattern, permutation tableau

# 1 Introduction

Eriksen [3] defined a new statistic adj on permutations that has the same distribution as the number of fixed points. He also conjectured that certain Euler-Mahonian pairs of statistics together with adj have the same joint distribution on permutations. Here we prove this conjecture. This refines a result of Foata and Zeilberger [5] that proves a conjecture of Babson and Steingrímsson [1].

## 1.1 Permutation statistics

We will start with some definitions. A combinatorial statistic on a set $S$ is a map $f: S \to \mathbb{N}^m$ for some integer $m \ge 0$. The distribution of $f$ is the map $d_f: \mathbb{N}^m \to \mathbb{N}$ with $d_f(i) = |f^{-1}(i)|$ for $i \in \mathbb{N}^m$, where $|f^{-1}(i)|$ is the number of objects $s \in S$ such that $f(s) = i$.

Let $\mathfrak{S}_n$ be the set of permutations of $[n] = \{1, \dots, n\}$. A descent of a permutation $\pi \in \mathfrak{S}_n$ is a position $i < n$ such that $\pi(i) > \pi(i + 1)$. Then $\pi(i)$ and $\pi(i + 1)$ are called descent top and descent bottom, respectively. A non-descent position is called an ascent. Ascent tops and ascent bottoms are defined similarly. An adjacency is a descent such that $\pi(i) - \pi(i + 1) = 1$. Where the context is unambiguous, we will also refer to the sequence of descent top and descent bottom as the descent, and do likewise for adjacencies.

Let des $\pi$ be the number of descents of $\pi$, and let adj $\pi$ be the number of adjacencies of $\pi 0$, i.e. a permutation of $[0, n] = \{0, 1, \dots, n\}$ obtained by appending 0 to the end of $\pi$. Eriksen proved that adj has the same distribution as fix, the number of fixed points, i.e. positions $i$ such that $\pi(i) = i$.

<footnote n="1">¹Department of Mathematics, Howard University, Washington, DC 20059 USA</footnote>
A statistic is *Eulerian* if its distribution is the same as that of the descent statistic, *des*. One well known Eulerian statistic is *exc*, the number of *excedances*, i.e. $exc \pi$ is the number of positions $i$ of $\pi$ such that $\pi(i) > i$. Another “almost” Eulerian statistic *wex*, the number of *weak excedances* (i.e. *wex* $\pi$ is the number of positions $i$ of $\pi$ such that $\pi(i) \ge i$) has the same distribution as *des* + 1. Eriksen [3] has also proved that the bistatistic (*adj*, *des* + 1) has the same distribution on permutations as (*fix*, *wex*).

An *inversion* of $\pi$ is a pair of positions $(i, j)$, such that $i < j$ and $\pi(i) > \pi(j)$. Let $inv \pi$ be the number of inversions of $\pi$. A statistic is *Mahonian* if it has the same distribution as $inv$. The first Mahonian statistic other than $inv$ was discovered by MacMahon himself and is the *major index maj*, the sum of positions of descents of a permutation. Other Mahonian statistics include, e.g., Denert's statistic *den* (see [1, 2]).

## 1.2 Permutation patterns

A *pattern* is an order-isomorphism type of a string over a totally ordered alphabet. An *occurrence* (or *instance*) of a pattern $\tau$ in a permutation $\pi$ is a subsequence of $\pi$ that is order-isomorphic to $\tau$. A *generalized pattern*, first defined in [1], is a pattern where some consecutive entries must be adjacent in all occurrences of the pattern as well. Consecutive entries of the pattern that need not be adjacent in the containing permutation are separated by a hyphen.

**Example 1.1** An occurrence of the generalized pattern 2-31 in a permutation $\pi$ is a subsequence $(\pi(i), \pi(j), \pi(j+1))$ of $\pi$ such that $i < j$ and $\pi(j+1) < \pi(i) < \pi(j)$.

Given a pattern $\tau$ and a permutation $\pi$, we denote by $(\tau)\pi$ the number of occurrences of the pattern $\tau$ in $\pi$. Thus, $(\tau)$ is a pattern occurrence statistic. Babson and Steingrímsson [1] showed that many Mahonian statistics can be expressed as sums of pattern occurrence statistics. For example,

$$ 
\begin{align} 
\mathit{inv} &= (2-1) = (21) + (3-12) + (3-21) + (2-31) = (21) + (31-2) + (32-1) + (23-1), \nonumber \\ 
\mathit{maj} &= (21) + (1-32) + (2-31) + (3-21), \tag{1.1} \\ 
\mathit{mak} &= (21) + (1-32) + (2-31) + (32-1), \nonumber \\ 
\mathit{stat} &= (21) + (13-2) + (21-3) + (32-1) \nonumber 
\end{align} 
$$

are Mahonian statistics. In fact, the last line is the definition [1] of the *stat* statistic.

We also need to define some permutation symmetries. *Reversal*, *r*, and *complement*, *c*, are the operations of reading a permutation back-to-front and upside-down, respectively. In other words, for $\pi \in \mathfrak{S}_n$, $\pi^r(i) = \pi(n+1-i)$ and $\pi^c(i) = n+1-\pi(i)$. Note that the composition $rc = cr$ is equivalent to rotating the permutation diagram by 180°. It is well known (and easily seen) that for any permutation $\pi$ and pattern $\tau$, we have $(\tau^r)\pi^r = (\tau^c)\pi^c = (\tau^{rc})\pi^{rc} = (\tau)\pi$.

## 2 Main result

Eriksen [3] conjectured that $(\mathit{adj}, \mathit{des}, \mathit{stat})$ and $(\mathit{adj}, \mathit{des}, \mathit{maj})$ are equidistributed on permutations. This (up to permutation reversal) is a refinement of a result of Foata and Zeilberger [5, Theorem 3] who use *q*-enumeration and generating functions and an almost completely automated proof via Maple packages *ROTA* and *PERCY*. In this paper, we produce a “handmade” bijective proof of Eriksen’s conjecture. A
possible redeeming feature of this approach is that the bijection is a nice and simple involution yielding a slightly better result than may have been expected.

Let $F \pi = \pi(1)$ be the first (leftmost) letter of $\pi$. Then the following result holds.

**Theorem 2.1** *Statistics (adj, des, F, maj, stat) and (adj, des, F, stat, maj) have the same joint distribution on $\mathfrak{S}_n$ for all $n$.*

Eriksen's conjecture is an immediate corollary of Theorem 2.1.

**Corollary 2.2** *Statistics (adj, des, stat) and (adj, des, maj) have the same joint distribution on $\mathfrak{S}_n$ for all $n$.*

To prove Theorem 2.1, we will define a map on permutations and prove that it preserves the values of adj, des and F and switches the values of maj and stat.

Given a permutation $\pi \in \mathfrak{S}_n$ with $\pi(1) = k$, define the permutation $\pi' \in \mathfrak{S}_n$ as follows: $\pi'(1) = \pi(1) = k$, and for $i \in [2, n]$,

$$ \pi'(i) = \begin{cases} k - \pi(n+2-i), & \text{if } \pi(n+2-i) < k, \\ n+k+1-\pi(n+2-i), & \text{if } \pi(n+2-i) > k. \end{cases} $$

This is better visualized as follows. Let $\pi_b$ (resp. $\pi_t$) be the subsequence of $\pi$ consisting of values that are lesser (resp. greater) than $k$. Then we can represent $\pi$ and $\pi'$ graphically as

$$ \pi = k \frac{\pi_t}{\pi_b} \quad \text{and} \quad \pi' = k \left( \frac{\pi_t^c}{\pi_b^c} \right)^r. $$

In other words, we take the complements of $\pi_t$ and $\pi_b$ separately, but then take the reversal of the whole $\pi$ except the first letter. Note that this implies that

$$ \pi_b' = \pi_b^{rc}, \quad \pi_t' = \pi_t^{rc}, $$

and the operation $rc$ takes descents to descents and adjacencies to adjacencies. Note also that the map $p: \pi \mapsto \pi'$ (where $p$ stands for “prime”) is an involution on the set of permutations in $\mathfrak{S}_n$ that start with $k$, i.e. $(\pi')' = \pi$. Hence, $p$ is a bijection on $\mathfrak{S}_n$.

We can also describe the bijection $p$ as follows. Insert bars between adjacent elements of $\pi_t$ and $\pi_b$ that are not adjacent in $\pi$. Also insert a bar at the start (resp. end) of the one of two sequences $\pi_t$ and $\pi_b$ not containing $\pi(2)$ (resp. $\pi(n)$). Let $\bar{\pi}_t$ and $\bar{\pi}_b$ be the resulting top and bottom sequences with bars, and write

$$ \pi = k \frac{\bar{\pi}_t}{\bar{\pi}_b}. $$

Then

$$ \pi' = k \frac{(\bar{\pi}_t)^{rc}}{(\bar{\pi}_b)^{rc}}. $$

In other words, we rotate (separately) the permutation diagrams of $\bar{\pi}_t$ and $\bar{\pi}_b$ by 180° with bars.
**Example 2.3** Let $\pi = 543617982 = 5\frac{|6|798|}{43|1|2}$. Then $\pi' = 5\frac{|768|9|}{3|4|21} = 537684921$.

We claim that the following is true:

$$
\begin{align*}
\operatorname{adj} \pi' &= \operatorname{adj} \pi \\
\operatorname{des} \pi' &= \operatorname{des} \pi \\
F \pi' &= F \pi \tag{2.1} \\
\operatorname{maj} \pi' &= \operatorname{stat} \pi \\
\operatorname{stat} \pi' &= \operatorname{maj} \pi
\end{align*}
$$

Obviously, the first letter is preserved under this map, so the third equation is certainly true. To prove
the fourth equation, we will show that

$$
\mathrm{maj} \pi + \mathrm{stat} \pi = (n+1) \mathrm{des} \pi - (k-1) = \mathrm{maj} \pi + \mathrm{maj} \pi' \quad (2.2)
$$

for all $\pi \in \mathfrak{S}_n$. Finally, the fifth equation follows from the fourth equation and the fact that the map $p: \pi \mapsto \pi'$ is an involution.

**Example 2.4** Take $\pi = 543617982$ and $\pi' = 537684921$ from Example 2.3. Then $n = 9$, $k = F\pi = F\pi' = 5$, $\mathrm{adj}\,\pi = \mathrm{adj}\,\pi' = 3$ (recall that we actually count adjacencies in $\pi 0 = 5436179820$ and $\pi' 0 = 5376849210$), $\mathrm{des}\,\pi = \mathrm{des}\,\pi' = 5$, $\mathrm{maj}\,\pi = \mathrm{stat}\,\pi' = 22$, $\mathrm{stat}\,\pi = \mathrm{maj}\,\pi' = 24$, and $(n+1)\mathrm{des}\,\pi - (k-1) = 46 = 22+24$.

**Lemma 2.5** $\mathrm{adj} \pi' = \mathrm{adj} \pi$.

**Proof:** No descent of $\pi 0$ that starts in $\pi_t$ and ends in $\pi_b 0$ can be an adjacency since the values of the descent top and descent bottom in this case differ by at least 2. Therefore, adjacencies of $\pi 0$ can be of four types:

• both top and bottom are in $\pi_t$,

- both top and bottom are in $\pi_b$,

- $k(k-1)$, if $\pi(2) = \pi_b(1) = k-1$,

- 10, if $\pi(n) = \pi_b(|\pi_b|) = 1$.

If both entries are in $\pi_t$ or in $\pi_b$, then these adjacencies are mapped to adjacencies in $\pi_t^{rc} = \pi_t'$ or $\pi_b^{rc} = \pi_b'$, respectively. If $\pi(2) = k-1$, then $\pi'(n) = 1$, so $\pi 0$ contains the adjacency $k(k-1)$ if and only if $\pi' 0$ contains the adjacency 10. Likewise, if $\pi(n) = 1$, then $\pi'(2) = k-1$, so $\pi 0$ contains the adjacency 10 if and only if $\pi' 0$ contains the adjacency $k(k-1)$. Thus, all adjacencies of $\pi 0$ map to adjacencies in $\pi' 0$, and vice versa, so $\mathrm{adj}\,\pi = \mathrm{adj}\,\pi'$. $\square$

**Lemma 2.6** $\mathrm{des} \pi' = \mathrm{des} \pi$.
**Proof:** As in the previous lemma, note that descents where both top and bottom are in $\pi_t$ or in $\pi_b$ map to descents in $\pi'$ where both entries are in $\pi_t^{rc} = \pi'_t$ and $\pi_b^{rc} = \pi'_b$, respectively. Thus, we only need to look at descents of $\pi$ and $\pi'$ that start at or above $k$ (i.e. in $k\pi_t$ or $k\pi'_t$, respectively) and end below $k$ (i.e. in $\pi_b$ or $\pi'_b$, respectively). The number of such descents equals the number of blocks in the bottom part $\pi_b$ of $\pi$, which is the same as the number of blocks in the bottom part $\pi'_b$ of $\pi'$.

This implies that $des \pi' = des \pi$ as desired. $\square$

For the next lemma, we will need a bit of notation. Given a pattern $\tau$, let $\tau_{i_1, i_2, \dots, i_h}$ denote the pattern $\tau$ with distinguished entries $i_1 < i_2 < \dots < i_h$. Usually, we will write $\tau$ with distinguished entries itali-cized. Now given a list of letters $j_1 < j_2 < \dots < j_h$ and a permutation $\pi$, let $(\tau_{i_1, i_2, \dots, i_h})(j_1, j_2, \dots, j_h)$ be the permutation statistic of the number of occurrences of $\tau$ where each entry $i_s$ in $\tau$ corresponds to the entry $j_s$ in the containing permutation, for $s = 1, 2, \dots, h$. For example, $(2-3I)(a, b)\pi$ counts all occurrences of 2-31 in $\pi$ where $a$ and $b$ in $\pi$ correspond to 1 and 3 in 2-31, respectively.

**Lemma 2.7** $maj \pi + stat \pi = (n+1) des \pi - (k-1)$.

**Proof:** From Equation (1.1), it follows that

$$maj + stat = (21) + (21) + (3-21) + (21-3) + (1-32) + (32-1) + (2-31) + (13-2).$$

Let $ba, b > a$, be a descent of $\pi$ (in other words, $b$ is the descent top and $a$ is the descent bottom here). Then

$$(21)(a, b) + (21)(a, b)$$

counts the entries $a$ and $b$ themselves,

$$(3-21)(a, b) + (21-3)(a, b)$$

counts all entries greater than $b$ (split into those to the left or to the right of the descent $ba$),

$$(1-32)(a, b) + (32-1)(a, b)$$

counts all entries less than $a$ (split into the same two groups), and

$$(2-3I)(a, b) + (3I-2)(a, b)$$

counts all entries between $a$ and $b$ (split likewise). This implies that

$$((21) + (21) + (3-21) + (21-3) + (1-32) + (32-1) + (2-31) + (31-2))(a, b)\pi = |\pi| = n$$

for any permutation $\pi$ of size $n$ and any descent $ba$ of $\pi$. Summing over all descents of $\pi$, we get

$$((21) + (21) + (3-21) + (21-3) + (1-32) + (32-1) + (2-31))\pi = n des \pi - (31-2)\pi,$$

so that

$$maj \pi + stat \pi = n des \pi + (13-2)\pi - (31-2)\pi.$$
Now for each $c \in [n]$, lets us count $(13-2)(c)\pi - (31-2)(c)\pi$. Recall that $\pi(1) = k$. We claim that the following is true:

$$ (13-2)(c)\pi - (31-2)(c)\pi = \begin{cases} 0, & \text{if } c = k, \\ 0, & \text{if } c > k \text{ is an ascent top,} \\ 1, & \text{if } c > k \text{ is an descent bottom,} \\ -1, & \text{if } c < k \text{ is an ascent top,} \\ 0, & \text{if } c < k \text{ is an descent bottom.} \end{cases} $$

Let us call instances of $(13-2)(c)$ and $(31-2)(c)$ left ascents *across* $c$ and left descents *across* $c$, respectively. Since the first line is obvious, assume $c \neq k$ and let $d$ be the entry immediately preceding $c$ in $\pi$.

If $c > k$ is an ascent top, then $c > d$ as well, so $k$ and $d$ are on the same side of $c$ (on the value axis of the permutation diagram), and hence, from $k$ to $d$, the number of ascents across $c$ is equal to the number of descents across $c$, so their difference is 0. The same result is obtained when $c < k$ is a descent bottom, i.e. when $c < d$ as well, and hence $k$ and $d$ are again on the same side of $c$. If $c > k$ is a descent bottom, then $k < c < d$, so $k$ is below $c$ and $d$ is above $c$. Hence, from $k$ to $d$, there are 1 more ascents across $c$ than descents across $c$. Finally, if $c < k$ is an ascent top, then $k > c > d$, so $k$ is above $c$ and $d$ is below $c$. Hence, from $k$ to $d$, there are 1 more descents across $c$ than ascents across $c$.

Therefore, summing over all entries $c \in \pi$, we get

$$ \begin{aligned} (13-2)\pi - (31-2)\pi &= |\{\text{descent bottoms} > k\}| - |\{\text{ascent tops} < k\}| \\ &= (|\{\text{descent bottoms} > k\}| + |\{\text{descent bottoms} < k\}|) \\ &\quad - (|\{\text{ascent tops} < k\}| + |\{\text{descent bottoms} < k\}|) \\ &= |\{\text{all descent bottoms}\}| - |\{\text{all entries} < k\}| \\ &= \text{des } \pi - |\pi_{\text{b}}| = \text{des } \pi - (k-1). \end{aligned} \quad (2.3) $$

We will explain the passage from the second to the third equality in some detail. For the first parenthesis, note that $k$ cannot be a descent bottom and that every descent bottom corresponds to a unique descent. For the second parenthesis, note that every entry less than $k$ must be at the end of an ascent or descent.

Thus,

$$ \text{maj } \pi + \text{stat } \pi = n \text{ des } \pi + \text{des } \pi - (k-1) = (n+1) \text{ des } \pi - (k-1). $$

This ends the proof.

<figure><img src="image_1.png" /></figure>

**Remark 2.8** The Equation (2.3) can also be proved as follows. Note that $\text{des} = (21)$ and $k-1 = F\pi - 1 = [2-1)$, where the initial bracket means that the first letter of the pattern must also be the first letter in the permutation. In our case, $[2-1)$ counts all inversions starting from the leftmost letter of $\pi$, i.e. all letters less than $\pi(1) = k$. We can write

$$ (2-1) = [2-1] + (32-1) + (23-1) + (13-2), \quad (2.4) $$

since the first letter in an inversion is either the initial letter in the permutation (the first summand on the right) or preceded by another letter (the other three summands). On the other hand,

$$ (2-1) = (21) + (32-1) + (23-1) + (31-2), \quad (2.5) $$
since the first letter in an inversion is immediately followed either by the second letter in that inversion (the first summand on the right) or by some other letter (the other three summands). Comparing Equations (2.4) and (2.5), we obtain

$$ (13-2) - (31-2) = (21) - [2-1] = \text{des} - (\mathbf{F} - 1). \qquad (2.6) $$

**Lemma 2.9** maj $\pi + \text{maj } \pi' = (n+1)\text{des } \pi - (k-1)$.

**Proof:** Suppose that $i$ is a descent of $\pi$ and that $\pi(i)$ and $\pi(i+1)$ are both in $\pi_t$ or both in $\pi_b$. Then the map $p: \pi \mapsto \pi'$ takes this descent to the descent at position $n+1-i$ since $\pi'(n+1-i) > \pi'(n+2-i)$ and these values are also both in $\pi_t$ or both in $\pi_b$. Therefore, each descent of $\pi$ within $\pi_t$ or within $\pi_b$ and its corresponding descent in $\pi'$ within $\pi'_t$ or $\pi'_b$ contributes

$$ i + (n + 1 - i) = n + 1 $$

to the sum $\text{maj } \pi + \text{maj } \pi'$.

Now consider descents in $\pi$ and $\pi'$ from not below $k$ to below $k$. Suppose that $\pi_b = \pi_b^{(1)} \pi_b^{(2)} \dots \pi_b^{(m)}$, where each $\pi_b^{(s)}$ is a maximal block of consecutive entries of $\pi$ that are in $\pi_b$. Suppose also that $\pi_b^{(s)}$ starts at position $j_s + 1$ for some $j_s \le n-1$. Then $\pi_b^{(s)}$ ends at position $j_s + |\pi_b^{(s)}|$. Therefore, we can partition the descents of $\pi$ and $\pi'$ from not below $k$ to below $k$ into pairs, where the descent from $k\pi_t$ to $\pi_b^{(s)}$ at position $j_s$ corresponds to the descent from $k\pi'_t$ to $(\pi_b^{(s)})^{\text{rc}}$ at position

$$ (n + 2) - (j_s + |\pi_b^{(s)}| + 1) = (n + 1) - (j_s + |\pi_b^{(s)}|). $$

Therefore, each such pair (for $s = 1, \dots, m$) together contributes

$$ j_s + \left( (n + 1) - (j_s + |\pi_b^{(s)}|) \right) = (n + 1) - |\pi_b^{(s)}| $$

to the sum $\text{maj } \pi + \text{maj } \pi'$. Summing over all $\pi_b^{(s)}$ for $s = 1, \dots, m$, we get that the descents in $\pi$ and $\pi'$ from not below $k$ to below $k$ together contribute

$$ (n + 1)|\{\text{descents from } k\pi_t \text{ to } \pi_b\}| - \sum_{s=1}^{m} |\pi_b^{(s)}| = (n + 1)|\{\text{descents from } k\pi_t \text{ to } \pi_b\}| - |\pi_b| $$

to $\text{maj } \pi + \text{maj } \pi'$. Thus, all descents in $\pi$ and $\pi'$ together sum to

$$ (n + 1)|\{\text{descents of } \pi \text{ in } \pi_t\}| + (n + 1)|\{\text{descents of } \pi \text{ in } \pi_b\}| + (n + 1)|\{\text{descents from } k\pi_t \text{ to } \pi_b\}| - |\pi_b| \\ = (n + 1)|\{\text{all descents of } \pi\}| - |\pi_b| = (n + 1) \text{ des } \pi - (k - 1), $$

in other words,

$$ \text{maj } \pi + \text{maj } \pi' = (n + 1) \text{ des } \pi - (k - 1). $$

This ends the proof.

<figure><img src="image_2.png" /></figure>

Thus, we proved all the equalities in Equation (2.1). This ends the proof of Theorem 2.1.
### 3 Distribution of $(adj, des + 1)$

In [3], Eriksen gives a proof of equidistribution of $(adj, des + 1)$ and $(fix, wex)$ on $\mathfrak{S}_n$ using two bijections from permutations to permutation tableaux. Here we give a direct bijection on permutations that maps the former bistatistic to the latter. This bijection is different [4] from the composition of Eriksen's two bijections. In fact, letting $\mathfrak{S}_n^0 = \{\pi 0 | \pi \in \mathfrak{S}_n\}$, we get $des \pi 0 = des \pi + 1$, $fix \pi 0 = fix \pi$, $wex \pi 0 = wex \pi$, so $(adj, des)$ and $(fix, wex)$ are equidistributed on $\mathfrak{S}_n^0$.

Given a permutation $\pi \in \mathfrak{S}_n$, for each entry $m \in [n]$ of $\pi$, define $\ell(m)$ to be the leftmost entry of $\pi 0$ to the right of $m$ that is less than $m$. Note that $\ell(m) + 1 \le m$ for all $m \in [n]$. Then $\pi$ is mapped to

$$ \tilde{\pi} = (1 \ \ell(1) + 1)(2 \ \ell(2) + 1)\dots(n-1 \ \ell(n-1) + 1)(n \ \ell(n) + 1). \quad (3.1) $$

The map $t: \pi \mapsto \tilde{\pi}$ is obviously a bijection since $\tilde{\pi}$ in (3.1) is the product of transpositions required to make entries $n, n-1, \dots, 2, 1$ of $\tilde{\pi}$ fixed points in order of decreasing magnitude (i.e., first, $n$ is moved from position $\ell(n) + 1$ to position $n$, then $n-1$ is moved from position $\ell(n-1) + 1$ to position $n-1$, and so on). Moreover, the inverse map $t^{-1}: \tilde{\pi} \mapsto \pi$ amounts to starting with the string 0, then inserting the entries 1, 2, \dots, $n$ in increasing order so that each $i$ is inserted immediately to the left of $\ell(i)$, then deleting the 0.

**Example 3.1** Let $\pi = 543617982$, then $\pi 0 = 5436179820$, so

$$ \tilde{\pi} = (11)(21)(32)(44)(55)(62)(73)(83)(99) = 268453179. $$

Note that $adj \pi = 3 = fix \tilde{\pi}$ and $des \pi + 1 = des(\pi 0) = 6 = wex \tilde{\pi}$.

**Proposition 3.2** The map $t: \pi \mapsto \tilde{\pi}$ is a bijection on $S_n$ such that $(adj, des + 1)\pi = (fix, wex)\tilde{\pi}$.

**Proof:** Suppose that, scanning the cycles of $\tilde{\pi}$ in formula (3.1) from right to left, we see that the element $j$ occurs first as $\ell(i)+1$ for some $i$. Then $j \le i$ and $i$ does not occur to the left of the cycle $(ij) = (i \ell(i)+1)$ in (3.1). Therefore, $\tilde{\pi}(j) = i \ge j$, i.e. $j$ is a weak excedance of $\tilde{\pi}$. But such a situation arises exactly when $i$ is to the left of $j-1 = \ell(i)$, and between $i$ and $j-1$ there is no element less than $j-1$ (by definition of $\ell(i)$) and no element greater than $j-1$ (or $j$ would occur in a transposition earlier to the right in (3.1)), i.e. exactly when $\pi 0$ contains a descent from $i$ to $j-1$.

On the other hand, suppose the above situation does not occur. Then $j$ first occurs as the greater entry of the transposition $(j \ell(j) + 1)$ in (3.1), and $\ell(j) + 1 < j$. Then $j$ is first mapped to $\ell(j) + 1 < j$ by $(j \ell(j) + 1)$, and since there are no elements greater than $j$ to the left of $(j \ell(j) + 1)$ in (3.1), it follows that $\tilde{\pi}(j) < j$.

Thus, $j$ is a weak excedance of $\tilde{\pi}$ exactly when $j-1$ is a descent bottom of $\pi 0$. Moreover, $j$ is fixed point of $\tilde{\pi}$ exactly when $\pi 0$ contains a descent from $j$ to $j-1$, i.e. when $j$ is an adjacency of $\pi 0$. $\square$

### 4 Euler-Mahonian statistics on permutation tableaux

Here we will give a simple proof of another conjecture of Eriksen [3]: that a certain bistatistic on permutation tableaux is Euler-Mahonian, i.e. has the same distribution as $(des, maj)$.

A Ferrers diagram of a partition is a left-justified column of nonincreasing rows of identical squares (cells), where some rows may be of length 0. A permutation tableau $\mathcal{T}$ (see [7]) is a $(0, 1)$-filling of a Ferrers diagram that satisfies the following properties:
(1-hinge) every cell that has a 1 to its left in the same row and a 1 above it in the same column must also contain a 1 (such a 1 is called an induced 1),

(column) every column contains at least one 1.

Permutation tableaux of semiperimeter $n$ are in bijection with permutations of length $n$ (see [7]). Note that there is no corresponding restrictions on rows, i.e. a row may contain all 0s.

A 0 in a permutation tableau is called a *restricted zero* if there is a 1 above it in the same column. Note that all cells to the left of a restricted 0 in a permutation tableau must also be filled with 0s.

Viennot [8] considered so-called *alternative tableaux*, that are closely related to the regular permutation tableaux. An alternative tableau $\bar{T}$ is obtained from an regular permutation tableau $T$ by replacing the top 1 in each column with a blue dot, the rightmost restricted 0 (if any) in each row with a red dot, then removing all nontop 1s from their cells and deleting the top row except for its bottom boundary (so that we know the length of the deleted top row).

This operation is a bijection. Indeed, given an alternative tableau $\mathcal{A}$, we can recover the permutation tableau $\hat{\mathcal{A}} = \mathcal{T}$ such that $\bar{\mathcal{T}} = \mathcal{A}$ by adjoining back the top row, inserting blue dots in those columns of the top row which had no blue dots in $\bar{\mathcal{T}}$, filling all red dot cells, cells to the left of red dots and cells above the blue dots with 0s, and filling the remaining cells with 1s.

The alternative tableaux have an advantage over the original permutation tableaux in that they are closed under the involution that consists of transposition and switching the colors of red and blue dots.

Eriksen [3] conjectured that the following statistic on alternative tableaux,

$$ \text{Astat} = \binom{\text{rows} + 1}{2} + \text{red dots} + \text{blue dots} + \text{cells to the left of red dots} + \text{cells above blue dots}, $$

is Mahonian and, in fact, that (rows, Astat) is Euler-Mahonian. Here we prove this conjecture.

**Theorem 4.1** *The bistatistic (rows, Astat) on alternative tableaux is Euler-Mahonian.*

**Proof:** Let $\mathcal{A}$ be an alternative tableau, and let $\mathcal{T} = \hat{\mathcal{A}}$ be its corresponding permutation tableau. Then the 0s of $\mathcal{T}$ that are not in the top row are exactly in the cells that either contain the red dots or are to the left of the red dots or are above the blue dots in $\mathcal{A}$. On the other hand, the 0s in the top row of $\mathcal{T}$ are exactly in the columns that contain the blue dots of $\mathcal{T}$. Note also that $\text{rows}(\mathcal{T}) = \text{rows}(\mathcal{A}) + 1$. Thus,

$$ \text{Astat}(\mathcal{A}) = \binom{\text{rows}(\mathcal{T})}{2} + \text{zeros}(\mathcal{T}). $$

Steingrímsson and Williams [7] give a bijection from permutation tableaux to permutations that converts tableau statistics to pattern statistics. If a permutation tableau $\mathcal{T}$ corresponds to a permutation $\pi$ via that bijection $(\Psi^{-1} \circ \Phi)$ in the notation of [7]), then the following holds

$$ \text{des } \pi = \text{rows}(\mathcal{T}) - 1 = \text{rows}(\mathcal{A}), $$

$$ [(31-2) + (21-3) + (3-21)]\pi - \binom{\text{des } \pi}{2} = \text{zeros}(\mathcal{T}). $$
Thus,

$$
\begin{align*}
\text{Astat}(\mathcal{A}) &= \binom{\text{des } \pi + 1}{2} + [(31-2) + (21-3) + (3-21)]\pi - \binom{\text{des } \pi}{2} \\
&= \text{des } \pi + [(31-2) + (21-3) + (3-21)]\pi \\
&= [(21) + (31-2) + (21-3) + (3-21)]\pi \\
&= [(21) + (2-31) + (1-32) + (32-1)]\pi^{\text{rc}} \\
&= \text{mak } \pi^{\text{rc}} = \text{mak}^{\text{rc}}(\pi),
\end{align*}
$$

and mak is a Mahonian statistic (e.g., see [2]). Moreover, des πrc = des π, and (des, mak) is Euler-Mahonian [6], and thus, (rows, Astat) is Euler-Mahonian as well. □

5 Further questions

In the earlier sections we have proved that the bistatistics (des, mak) (or, more specifically, (des, mak)rc)
on permutations and (rows, Astat) on permutation tableaux are equidistributed. Steingrímsson and
Williams [7] show that the bistatistics (fix, wex) on permutations and (rows-with-no-1s, rows) on per-
mutation tableaux are equidistributed. Furthermore, Eriksen [3] gives a direct bijection that shows equidis-
tribution of (adj, des + 1) and (rows-with-no-1s, rows).

However, the triples of statistics (adj, des, mak) (or (adj, des + 1, mak), or (adj, des, mak)rc) and
(rows-with-no-1s, rows, Astat) are not equidistributed. This leads us to ask if there are more or less
natural statistics on permutations or permutation tableaux that fill the position of the question mark, for
example, in the following equidistributions, among others:

(adj, des, mak) ~ (rows-with-no-1s, rows, ?)

(adj, des, mak) ~ (?, rows, Astat)

(adj, des, ?) ~ (rows-with-no-1s, rows, Astat)

(?, des, mak) ~ (rows-with-no-1s, rows, Astat)

References

[1] E. Babson, E. Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin. B44b (2000), 18 pp.

[2] R.J. Clarke, E. Steingrímsson, J. Zeng, New Euler-Mahonian statistics on permutations and words, *Adv. Appl. Math.* **18** (1997), 237–270.

[3] N. Eriksen, Pattern and position based permutation statistics, in preparation, available online at http://www.math.chalmers.se/~ner/artiklar/bpMahonianPP.pdf.

[4] N. Eriksen, personal communication.

[5] D. Foata, D. Zeilberger, Babson-Steingrímsson statistics are indeed Mahonian (and sometimes even Euler-Mahonian), *Adv. Appl. Math.* **27** (2001), 390–404.
[6] D. Foata, D. Zeilberger, Denert's permutation statistic is indeed Euler-Mahonian, *Studies in Appl. Math.* **83** (1990), 31–59.

[7] E. Steingrímsson, L.K. Williams, Permutation tableaux and permutation patterns, *J. Combin. Th. Ser. A* **114** (2007), no. 2, 211–234.

[8] X. Viennot, Alternative tableaux, permutations and partially asymmetric exclusion process. Talk given at the Isaac Newton Institute, Cambridge, available online at http://www.newton.ac.uk/programmes/CSM/seminars/042314001.html.