Alignments, crossings, cycles, inversions, and
weak Bruhat order in permutation tableaux of
type B †‡

Soojin Cho<fnref n="1" />§ and Kyoungsuk Park<fnref n="2" />¶

**Abstract.** Alignments, crossings and inversions of signed permutations are realized in the corresponding permutation tableaux of type *B*, and the cycles of signed permutations are understood in the corresponding bare tableaux of type *B*. We find the relation between the number of alignments, crossings and other statistics of signed permutations, and also characterize the covering relation in weak Bruhat order on Coxeter system of type *B* in terms of permutation tableaux of type *B*.

**Résumé.** De nombreuses statistiques importantes des permutations signées sont réalisées dans les tableaux de permutations ou "bare" tableaux de type *B* correspondants : les alignements, croisements et inversions des permutations signées sont réalisés dans les tableaux de permutations de type *B* correspondants, et les cycles des permutations signées sont comprises dans les "bare" tableaux de type *B* correspondants. Cela nous mène à relier le nombre d'alignements et de croisements avec d'autres statistiques des permutations signées, et aussi de caractériser la relation de couverture dans l'ordre de Bruhat faible sur des systèmes de Coxeter de type *B* en termes de tableaux de permutations de type *B*.

**Keywords:** permutation tableaux of type *B*, alignment, crossing, inversion, Bruhat order, Coxeter group of type *B*, signed permutation

# 1 Introduction

There have been a great deal of work on *permutation tableaux* since they were introduced [SW07], in many different directions([Nad11, Bur07, CW07b, CW07a, CN09, CL11, CSSW12, CK11, CJVK13]). Permutation tableaux are in bijection with permutations and therefore provide another point of view to look at permutations in various types. Some statistics on (signed) permutations are very well understood

<footnote n="1">¹Department of Mathematics, Ajou University, Korea</footnote>

<footnote n="2">²Department of Mathematics, Ajou University, Korea</footnote>

<footnote>†This is an extended abstract of the full research paper [CP15].</footnote>

<footnote>‡This research was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education(NRF2011-0012398).</footnote>

<footnote>§Email: chosj@ajou.ac.kr.</footnote>

<footnote>¶Email: bluemk00@ajou.ac.kr.</footnote>
in permutation tableaux (of type *B*), and statistics naturally defined on permutation tableaux make it
possible to develop further combinatorial theories on Coxeter groups.

The inversion number of a signed permutation gives the length when we consider the signed permu-
tation as an element in the corresponding Coxeter group of type B, and hence it plays an essential role
to understand the Bruhat order on the Coxeter groups. However, there is no known way to understand
inversions directly in the permutation tableaux. In the present article, we realize the inversion number and
the covering relation in weak Bruhat order on Coxeter groups of type B, directly from the permutation
tableaux of type B (Theorem 15, Theorem 13). Inversion numbers are closely related to alignments and
crossings, which are relatively new statistics introduced by S. Corteel in [Cor07] for (signed) permuta-
tions, and we start our work by closely looking at the alignments and crossings in permutation tableaux
of type B. We prove an equation that writes the sum of alignments and crossings in terms of weak ex-
cedances and negatives in Theorem 7, which resolves a problem (open problem 3) posed by Corteel et
al. in [CJVK13]. We also show that the number of cycles of a signed permutation counts the number of
certain 1's in the corresponding bare tableau of type B. We make a remark that our works on permutation
statistics have been known for the cases of type A (see Proposition 3), and we extend the results to cases
of type B. The work on weak Bruhat order in permutation tableaux is new in both types A and B.

The present article is organized as follows: In Section 2 we introduce necessary notions and known
results on signed permutations and permutation tableaux of type B. Alignments and crossings of signed
permutations are understood in permutation tableaux of type B in Section 3, and the number of cycles of
a signed permutation is realized in the corresponding bare tableau of type B in Section 4. In Section 5,
we understand the inversion numbers and hence the weak Bruhat order in terms of permutation tableaux
of type B.

## 2 Preliminaries

A signed permutation σ of length n is a permutation on [±n] = {±1, ..., ±n} satisfying σ(−i) = −σ(i) for i ∈ [n] = {1, ..., n}. The group of signed permutations is denoted by $\mathfrak{S}_n^B$, and the subgroup of (ordinary) permutations in $\mathfrak{S}_n^B$ is denoted by $\mathfrak{S}_n$. One line notation σ = σ₁, ..., σn of σ ∈ $\mathfrak{S}_n^B$ means that σ(i) = σᵢ for i ∈ [n]. In cycle notation we write σ = (a₁,₁, ..., a₁,k₁) ... (aₘ,₁, ..., aₘ,kₘ) where {|a₁,₁|, ..., |a₁,k₁|}, ..., {|aₘ,₁|, ..., |aₘ,kₘ|} are mutually disjoint subsets of [n], to mean that σ(|aᵢ,ⱼ|) = aᵢ,ⱼ+1 with the convention aᵢ,ₖᵢ₊₁ = aᵢ,₁ for each i. If $\sum_j k_i = n$ then the given cycle notation is called the full cycle notation. Note that a single cycle (a) ∈ $\mathfrak{S}_n^B$ is the signed permutation σ such that σ(|a|) = a fixing all other elements. Hence, if a > 0 then (a) is the identity permutation and we usually omit (a). For example, τ = −1, 2, 3 ∈ $\mathfrak{S}_3^B$ is the signed permutation such that τ(1) = −1, τ(2) = 2, and τ(3) = 3, and (−1) is a cycle notation and (−1)(2)(3) is the full cycle notation of τ.

We give definitions of some statistics on signed permutations. Let $\sigma \in \mathfrak{S}_n^B$. $i \in [n]$ is a weak excedance of $\sigma$ if $\sigma(i) \ge i$ and the number of weak excedances of $\sigma$ is denoted by wex($\sigma$). $i \in [n]$ is a drop of $\sigma$ if $\sigma(i) < i$ and the number of drops of $\sigma$ is denoted by drop($\sigma$). Note that wex($\sigma$) + drop($\sigma$) = n for all $\sigma \in \mathfrak{S}_n^B$. The number of negative integers in the one line notation of $\sigma$ is denoted by neg($\sigma$) and the number of cycles in the full cycle notation of $\sigma$ is denoted by cyc($\sigma$).

Corteel introduced alignments and crossings on permutations in [Cor07], and they were also defined for
signed permutations in [CJVK13]. We use the same definition of crossings and redefine alignments for
signed permutations. Our definition of alignments is consistent with the one in [Cor07] for permutations
in $\mathfrak{S}_n$.
**Definition 1** Let $\sigma \in \mathfrak{S}_n^B$ and $i, j \in [n]$.

• $(i, j) \in A_{nest}$ if $-i < -j < -\sigma(j) < -\sigma(i)$, $-i < j \le \sigma(j) < -\sigma(i)$, or $i < j \le \sigma(j) < \sigma(i)$.

• $(i, j) \in A_{EN}(\sigma)$ if $-i < 0 < -\sigma(i) < \sigma(j) < j$ or $i \le \sigma(i) < \sigma(j) < j$.

• $(i, j) \in A_{NE}(\sigma)$ if $\sigma(i) < i < j \le \sigma(j)$.

• $(i, j) \in C(\sigma)$ if $i < j \le \sigma(i) < \sigma(j)$, $-i < -j < -\sigma(i) < -\sigma(j)$, or $-i < j \le -\sigma(i) < \sigma(j)$.

We let $\text{al}_{nest}(\sigma) = |A_{nest}(\sigma)|$, $\text{al}_{EN}(\sigma) = |A_{EN}(\sigma)|$, and $\text{al}_{NE}(\sigma) = |A_{NE}(\sigma)|$. We also let $\text{al}(\sigma) = \text{al}_{nest}(\sigma) + \text{al}_{EN}(\sigma) + \text{al}_{NE}(\sigma)$ be the number of alignments of $\sigma$ and $\text{cr}(\sigma) = |C(\sigma)|$ be the number of crossings of $\sigma$.

For positive integers $k \le n$, a $(k, n)$-diagram is a left-justified diagram of boxes in a $k \times (n-k)$ rectangle with $\lambda_i$ boxes in the $i$th row, where $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_k \ge 0$. A shifted $(k, n)$-diagram is a $(k, n)$-diagram together with the stair shaped array of boxes added above, where the $j$th column (from the left) has $(n-k-j+1)$ additional boxes for $j \in [n-k]$. We call the (unique) $(k, n)$-diagram in a shifted $(k, n)$-diagram the $(k, n)$-subdiagram, and the $(n-k)$ topmost boxes in a shifted $(k, n)$-diagram diagonals. See Figure 1.

We label the rows and columns of a $(k, n)$-diagram as follows: From the northeast corner to the southwest corner, follow the southeast border edges of the diagram and give labels 1, 2, . . . , $n$ in order. If a south edge earned the label $i$ then we label the corresponding column with $i$, and if an east edge earned the label $j$ then we label the corresponding row with $j$. We put the labels on the left of each row and on the top of each column. For a shifted $(k, n)$-diagram, label the rows and columns of the $(k, n)$-subdiagram with the numbers in $[n]$ first. Then label the remaining rows as follows; if the diagonal in a row is in the column labeled $i$, then we label the row with $-i$. We usually put the label on the left of each row and omit the column labels. We use row $i$, $i \in [\pm n]$, to denote the row labeled by $i$ and col $j$ for the column labeled by $j$. See Figure 1.

<figure><img src="image_1.png" /><figcaption>**Fig. 1:** A (4, 9)-diagram and a shifted (4, 9)-diagram with labelings.</figcaption></figure>

A permutation tableau of type B is a (0, 1)-filling of a shifted $(k, n)$-diagram that satisfies the following conditions:

(1) Every column has at least one 1.

(2) (⊠-condition or 1-hinge condition) A box with a 1 above it in the same column and a 1 to the left in the same row has a 1.
(3) If a diagonal has a 0, then there is no 1 in the same row.

A bare tableau of type B is a (0, 1)-filling of a shifted $(k, n)$-diagram that satisfies the previous conditions (1) and (3), and the following condition instead of (2):

(2') (0-hinge condition) A box with a 1 above it in the same column and a 1 to the left in the same row has a 0.

Permutation tableaux (or bare tableaux) of type A are permutation tableaux (or bare tableaux, respectively) of type B such that the diagonals are filled with all 0's. The length of any filling of a (shifted) $(k, n)$-diagram is $n$. The set of permutation tableaux of type B (or type A) of length $n$ is denoted by $\mathcal{PT}_n^B$ (or $\mathcal{PT}_n$, respectively) and the set of bare tableaux of type B (or type A, respectively) of length $n$ is denoted by $\mathcal{BT}_n^B$ (or $\mathcal{BT}_n$, respectively).

As in [SW07], we can represent a permutation tableau of type B in a different way; fill in the boxes outside the diagram (within the $k \times (n-k)$ rectangle) with 2's; see Figure 2. We call this representation the *extended* representation of $\mathcal{T}$.

<figure><img src="image_2.png" /><figcaption>**Fig. 2:** The permutation tableau, the bare tableau of type B, and the extended representation of the permutation tableau of type B corresponding to the signed permutation 2, 7, -5, 6, -4, 1, 8, -3.</figcaption></figure>

E. Steingrímsson and L. Williams defined a bijective zigzag map $\Phi: \mathcal{PT}_n \to \mathfrak{S}_n$ in [SW07] and it was extended to $\zeta: \mathcal{PT}_n^B \to \mathfrak{S}_n^B$ by Corteel and J. Kim in [CK11]. A bijective zigzag map $\Phi_{bare}: \mathcal{BT}_n \to \mathfrak{S}_n$ was defined ([Bur07, Nad11, CK11]) and it can be naturally extended to a bijection $\zeta_{bare}: \mathcal{BT}_n^B \to \mathfrak{S}_n^B$. For a permutation tableau $\mathcal{T}$ of type B, a zigzag path from $row j$ (or $col i$) in $\mathcal{T}$, is the path starting from the left of $row j$ (or the top of $col i$, respectively), moving east (or south, respectively) until it meets the right of a row or the bottom of a column where it changes the direction to either south or east whenever it meets a 1. Then the zigzag map $\zeta: \mathcal{PT}_n^B \to \mathfrak{S}_n^B$ is defined as follows: For $\mathcal{T} \in \mathcal{PT}_n^B$ and $i \in [n]$,

(1) if $i$ is the label of a row of $\mathcal{T}$, then $\zeta(\mathcal{T})(i)$ is the label of the row or the column that the zigzag path from $row i$ ends,

(2) if $-i$ is the label of a row of $\mathcal{T}$ and $row(-i)$ has 0 in its diagonal, then $\zeta(\mathcal{T})(-i)$ is the label of the row or the column that the zigzag path from $col i$ ends, and

(3) if $-i$ is the label of a row of $\mathcal{T}$ and $row(-i)$ has 1 in its diagonal, then $\zeta(\mathcal{T})(-i)$ is the label of the row or the column that the zigzag path from $row(-i)$ ends.

The zigzag map $\zeta_{bare}: \mathcal{BT}_n^B \to \mathfrak{S}_n^B$ is defined in the same way. Zigzag maps $\zeta$ and $\zeta_{bare}$ are described in Figure 3.
<figure><img src="image_3.png" /><figcaption>**Fig. 3:** Zigzag maps in permutation tableaux of type B.</figcaption></figure>

**Definition 2** Let $T \in \mathcal{PT}_n^B$. There are three types of zeros in $T$. Note that there are two zigzag paths passing through a given 0, one passing vertically and the other passing horizontally.

* A 0 in $T$ is of type EE if two zigzag paths passing through the 0 are both from rows of $T$. The number of 0's of type EE in $T$ is denoted by $\text{zero}_{EE}(T)$.

* A 0 in $T$ is of type NN if two zigzag paths passing through the 0 are both from columns of $T$. The number of 0's of type NN in $T$ is denoted by $\text{zero}_{NN}(T)$.

* A 0 in $T$ is of type EN if it is not in a zero row labeled by a negative integer and a zigzag path passing through the 0 is from a row and the other is from a column of $T$. The number of 0's of type EN in $T$ is denoted by $\text{zero}_{EN}(T)$.

A 0 in $T$ is non-typed if it is not given a type of EE, NN, or EN. The number of typed 0's in $T$ is denoted by $\text{zero}(T) = \text{zero}_{EE}(T) + \text{zero}_{NN}(T) + \text{zero}_{EN}(T)$, and the numbers of 1's and 2's in the extended representation of $T$ are denoted by $\text{one}(T)$ and $\text{two}(T)$, respectively.

Note that a 0 in a zero row labeled by a negative integer is either of type EE or non-typed, and non-typed 0's appear only in zero rows labeled by a negative integer. The definition of $\text{zero}(T)$ is consistent with the one for permutation tableaux of type A, which is given in [SW07]. It is easy to see that the number of non-typed 0's in the zero row $\text{row}(-i)$, $i \in [n]$, is the number of zero rows above $\text{row}(-i)$, including $\text{row}(-i)$ itself. We use EE, NN, or EN to denote 0's of corresponding types in permutation tableaux for convenience.

We introduce some statistics on permutation tableaux or bare tableaux of type B. Let $T$ be a permutation tableau or a bare tableau of type B. A 1 is a *doubly essential one of T* if it is both the topmost 1 in its column and the leftmost 1 in its row, and the number of doubly essential ones of $T$ is denoted by $\text{dess}(T)$. A 1 is a *superfluous one of T* if it is not the topmost 1 in its column, and the number of superfluous ones of $T$ is denoted by $\text{so}(T)$. The number of rows of $T$ with 'positive labels', is denoted by $\text{row}(T)$ and the number of zero rows (filled with all 0's) of $T$ with 'positive labels' is denoted by $\text{zerorow}(T)$. It is easy to see that each zero row of $T \in \mathcal{PT}_n^B$ (or $T \in \mathcal{BT}_n^B$) with positive label is corresponding to a fixed point of $\zeta(T)$ (or $\zeta_{bare}(T)$, respectively).

Certain statistics on permutation tableaux and bare tableaux (of type B) correspond to statistics on (signed) permutations through the zigzag maps $\zeta$ and $\zeta_{bare}$:

**Proposition 3 ([SW07, Bur07])** 1. For $T \in \mathcal{PT}_n$, $\text{wex}(\zeta(T)) = \text{row}(T)$, $\text{cr}(\zeta(T)) = \text{so}(T)$, $\text{al}_{nest}(\zeta(T)) + \text{al}_{EN}(\zeta(T)) = \text{zero}(T)$, and $\text{al}_{NE}(\zeta(T)) = \text{two}(T)$,

2. For $T_0 \in \mathcal{BT}_n$, $\text{cyc}(\zeta_{bare}(T_0)) = \text{dess}(T_0) + \text{zerorow}(T_0)$.
**Proposition 4 ([CK11, CJVK13])** For $\mathcal{T} \in \mathcal{PT}_n^B$, $\mathrm{wex}(\zeta(\mathcal{T})) = \mathrm{row}(\mathcal{T})$, and $\mathrm{cr}(\zeta(\mathcal{T})) = \mathrm{so}(\mathcal{T})$.

We show that $\mathrm{al}_{nest}(\zeta(\mathcal{T})) + \mathrm{al}_{EN}(\zeta(\mathcal{T})) = \mathrm{zero}(\mathcal{T})$ and $\mathrm{al}_{NE}(\zeta(\mathcal{T})) = \mathrm{two}(\mathcal{T})$ also hold for a permutation tableau $\mathcal{T}$ of type $B$ in Section 3. Further, we prove that $\mathrm{cyc}(\zeta_{bare}(\mathcal{T}_0)) = \mathrm{dess}(\mathcal{T}_0) + \mathrm{zerorow}(\mathcal{T}_0)$ also holds for a bare tableau $\mathcal{T}_0$ of type $B$ in Section 4. The following lemma is clear from the definition of $\zeta$ and $\zeta_{bare}$, and Proposition 4.

**Lemma 5** Let $\mathcal{T} = \zeta^{-1}(\sigma)$ or $\mathcal{T} = \zeta_{bare}^{-1}(\sigma)$ for $\sigma \in \mathfrak{S}_n^B$. Then for $i \in [n]$, $i$ is a weak excedance of $\sigma$ if and only if $i$ is a row label of $\mathcal{T}$, $i$ is a drop of $\sigma$ if and only if $(-i)$ is a row label of $\mathcal{T}$, and $\sigma(i) < 0$ if and only if $(-i)$ is a row label of $\mathcal{T}$ and the diagonal of $\mathrm{row}(-i)$ is filled with a 1.

## 3 Alignments and crossings in permutation tableaux of type $B$

In this section, we understand the alignments and crossings of signed permutations in their corresponding permutation tableaux of type $B$. We remark that two zigzag paths in a permutation tableau of type $B$ crossing at a 0 never cross again at another 0 due to the $\downarrow$-condition. The following proposition refines and generalizes the result in [SW07] (see Theorem 14) to type $B$.

**Proposition 6** Let $\mathcal{T} \in \mathcal{PT}_n^B$. Then,

$$ \mathrm{al}_{nest}(\zeta(\mathcal{T})) = \mathrm{zero}_{EE}(\mathcal{T}) + \mathrm{zero}_{NN}(\mathcal{T}), $$

$$ \mathrm{al}_{EN}(\zeta(\mathcal{T})) = \mathrm{zero}_{EN}(\mathcal{T}), \text{ and } \mathrm{al}_{NE}(\zeta(\mathcal{T})) = \mathrm{two}(\mathcal{T}). $$

**Proof (sketch):** For each inequality of the definition of alignments, we consider two zigzag paths from columns or rows in a (or an extended) permutation tableau. Then, two paths cross at unique 0 in each case. $\square$

We prove a theorem for the sum of alignments and crossings of a signed permutation, which extends the result on permutations by Corteel in [Cor07].

**Theorem 7** Let $\sigma \in \mathfrak{S}_n^B$. Then,

$$ \mathrm{al}(\sigma) + \mathrm{cr}(\sigma) = (n - \mathrm{wex}(\sigma))(\mathrm{wex}(\sigma) - 1 + \mathrm{neg}(\sigma)) - \binom{\mathrm{neg}(\sigma)}{2}. \quad (8) $$

**Proof (sketch):** In the extended representation of $\mathcal{T}$, there are $n + (n - 1) + \cdots + (n - \mathrm{col}(\mathcal{T}) + 1)$ boxes and this is equal to $\mathrm{zero}(\mathcal{T}) + \mathrm{two}(\mathcal{T}) + \mathrm{one}(\mathcal{T})$ plus the number of non-typed zeros in $\mathcal{T}$. It is not hard to see that there are $1 + \cdots + (\mathrm{col}(\mathcal{T}) - \mathrm{diag}(\mathcal{T}))$ non-typed 0's and the number of superfluous 1's is $\mathrm{col}(\mathcal{T})$. Then, we can obtain the equation of the theorem. $\square$

Since $\mathrm{neg}(\sigma) = 0$ for $\sigma \in \mathfrak{S}_n$, the equation 8 becomes $\mathrm{al}(\sigma) + \mathrm{cr}(\sigma) = (n - \mathrm{wex}(\sigma))(\mathrm{wex}(\sigma) - 1)$ which is Proposition 5 in [SW07]. A similar equation in Theorem 7 is proved by Corteel et al. (Proposition 4.3 in [CJVK13]) using pignose diagram, and it is posed as an open problem to give a proof of the proposition using permutation tableaux of type $B$. Our proof of Theorem 7 refines the equation and resolves the problem of Corteel et al. in [CJVK13].
**Example 9** Let $\mathcal{T} = \zeta^{-1}(\sigma)$ for $\sigma = -2, -4, 5, 3, 1 \in \mathfrak{S}_5^B$. We have $\mathrm{al}_{\mathrm{nest}}(\sigma) = 2$, $\mathrm{al}_{\mathrm{EN}}(\sigma) = 1$, $\mathrm{al}_{\mathrm{NE}}(\sigma) = 2$, and $\mathrm{cr}(\sigma) = 2$. The extended representation of $\mathcal{T}$ is in Figure 4 and we have $\mathrm{zero}_{\mathrm{EE}}(\mathcal{T}) = 1$, $\mathrm{zero}_{\mathrm{NN}}(\mathcal{T}) = 1$, $\mathrm{zero}_{\mathrm{EN}}(\mathcal{T}) = 1$, and two($\mathcal{T}$) = 2. Hence, $\mathrm{al}_{\mathrm{nest}}(\sigma) = \mathrm{zero}_{\mathrm{EE}}(\mathcal{T}) + \mathrm{zero}_{\mathrm{NN}}(\mathcal{T}) = 2$, $\mathrm{al}_{\mathrm{EN}}(\sigma) = \mathrm{zero}_{\mathrm{EN}}(\mathcal{T}) = 1$, and $\mathrm{al}_{\mathrm{NE}}(\sigma) = \mathrm{two}(\mathcal{T}) = 2$. Moreover, since $\mathrm{wex}(\sigma) = 1$ and $\mathrm{neg}(\sigma) = 2$, we can check that $\mathrm{al}(\sigma) + \mathrm{cr}(\sigma) = (5-1)(1-1+2) - \binom{2}{2} = 7$.

<figure><img src="image_4.png" /><figcaption>Fig. 4: The extended representation of $\mathcal{T} = \zeta^{-1}(\sigma)$ where $\sigma = -2, -4, 5, 3, 1$.</figcaption></figure>

# 4 Signed permutations and bare tableaux of type B

In this section, we prove a theorem on the number of cycles of signed permutations, which extends a theorem by A. Burstein (Theorem 4.2 in [Bur07]).

**Theorem 10** Let $\mathcal{T} \in \mathcal{B}\mathcal{T}_n^B$, then

$$ \mathrm{cyc}(\zeta_{\mathrm{bare}}(\mathcal{T})) = \mathrm{dess}(\mathcal{T}) + \mathrm{zerorow}(\mathcal{T}). $$

**Proof (sketch):** Let $\sigma = \zeta_{\mathrm{bare}}(\mathcal{T})$. We draw a forest of (binary) trees inside $\mathcal{T}$; 1's become vertices and two 1's are connected by an edge if they are adjacent vertices in a same row or in a same column, as it was done in [ABN11]. Each positively labeled zero row in $\mathcal{T}$ is bijectively corresponding to an identity cycle $(i)$. Moreover, each (connected) tree has a unique doubly essential 1 of $\mathcal{T}$, and we can show that each tree is bijectively corresponding to a non-identity cycle in the full cycle notation of $\sigma$. $\square$

**Example 11** For $\mathcal{T} \in \mathcal{B}\mathcal{T}_5^B$ in Figure 5, we have $\mathrm{dess}(\mathcal{T}) = 2$ and $\mathrm{zerorow}(\mathcal{T}) = 1$. The corresponding signed permutation of $\mathcal{T}$ is $\sigma = (1)(-2, 5, 4)(-3)$ in the full cycle notation, hence, $\mathrm{cyc}(\sigma) = 3$.

<figure><img src="image_5.png" /><figcaption>Fig. 5: The bare tableau $\mathcal{T}$ corresponding to $\sigma = (1)(-2, 5, 4)(-3)$.</figcaption></figure>

# 5 Weak Bruhat order on Coxeter system of type B

In this section, we consider the weak Bruhat order on Coxeter system of type B in terms of permutation tableaux of type B. The group $\mathfrak{S}_n^B$ with generators $s_0, s_1, \dots, s_{n-1}$ forms the Coxeter system of type B, where $s_0 = (-1)$, $s_i = (i, i+1)$ for $i \in [n-1]$ in cycle notation. The length of $\sigma \in \mathfrak{S}_n^B$, denoted by $\ell(\sigma)$, is defined as the minimum of $k$ such that $\sigma = s_{a_1} \dots s_{a_k}$. A pair $(i, j) \in [n] \times [n]$ is called an
inversion of $\sigma$, if $i < j$ and $\sigma(i) > \sigma(j)$, or $i \le j$ and $\sigma(-i) > \sigma(j)$. The number of inversions of $\sigma$ is denoted by $\text{inv}(\sigma)$ and it is well known that $\ell(\sigma) = \text{inv}(\sigma)$. (See Proposition 8.1.1 in [BB05].) The covering relation in weak Bruhat order on $\mathfrak{S}_n^B$ is defined as follows; for $\sigma, \sigma' \in \mathfrak{S}_n^B$, $\sigma'$ covers $\sigma$, denoted by $\sigma \prec \sigma'$, if $\sigma' = \sigma s_i$ for some $i \in \{0, 1, \dots, n-1\}$ and $\ell(\sigma') = \ell(\sigma) + 1$.

Our main goal is to illustrate the covering relations in weak Bruhat order on $\mathfrak{S}_n^B$ in terms of permutation tableaux of type B: Suppose that $\sigma \prec \sigma'$ in $\mathfrak{S}_n^B$ and let $\mathcal{T} = \zeta^{-1}(\sigma)$ and $\mathcal{T}' = \zeta^{-1}(\sigma')$. Then $\sigma' = \sigma s_i$ for some $i \in \{0, 1, \dots, n-1\}$ and $\ell(\sigma') = \ell(\sigma) + 1$. We will describe how $\mathcal{T}$ and $\mathcal{T}'$ are related.

(WB1): If $s_i = s_0$, then $\sigma'(1)$ is negative and $\mathcal{T}'$ is easily obtained by adding one diagonal with 1; see Figure 6.

If $s_i \neq s_0$, then we have following five cases to consider.

(WB2): $\sigma(i) < i$ and $\sigma(i+1) \ge i+1$: See Figure 6.

(WB3): $\sigma(i) = i$ and $\sigma(i+1) \ge i+1$: See Figure 6.

<figure><img src="image_6.png" /><figcaption>Fig. 6: (WB1), (WB2), and (WB3).</figcaption></figure>

(WB4): $\sigma(i) > i$ and $\sigma(i+1) > i+1$: We consider two types for (WB4). See Figure 7.

<figure><img src="image_7.png" /><figcaption>Fig. 7: (WB4-1) and (WB4-2).</figcaption></figure>

(WB5): $0 < \sigma(i) < i$ and $0 < \sigma(i+1) < i+1$: We consider two types for (WB5). See Figure 8.

(WB6): $\sigma(i) < 0 < i$ and $\sigma(i+1) < i+1$: We have two types for (WB6) depending on the sign of $\sigma(i+1)$. See Figure 9.

**Remark 12** In cases (WB5-1), (WB5-2), and (WB6-2), it is possible for us to have a zero column col i, and hence a zero row row $(-i)$ as a result. In this case, delete col i and row $(-i)$ and insert the new zero row row i instead in the resulting permutation tableau. For example, consider $\sigma = -4, 1, 2, -3 \in \mathfrak{S}_4^B$ and $\sigma' = \sigma s_2 \succ \sigma$. This is case (WB5-1), and col 2 in $\mathcal{T}'$ is a zero column and row $(-2)$ is a zero row. Thus we insert row 2 with all 0's, while deleting col 2 and row $(-2)$ to make $\mathcal{T}'$ a permutation tableau; see Figure 10.
<figure><img src="image_8.png" /><figcaption>Fig. 8: (WB5-1) and (WB5-2).</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 9: (WB6-1) and (WB6-2).</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 10: Modify $T'$ by deleting col2 and row(-2), and inserting a zero row with labeling 2.</figcaption></figure>

From the arguments that we have developed above, we can classify the covering relations in weak Bruhat order on $S_n^B$ in terms of permutation tableaux of type B and also can prove a theorem on the inversion number of signed permutations. We considered all possible cases in which $\sigma \prec \sigma'$ holds, and we can conclude as follows:

**Theorem 13** For $T, T' \in \mathcal{PT}_n^B$, and corresponding signed permutations $\sigma = \zeta(T), \sigma' = \zeta(T')$, $\sigma'$ covers $\sigma$ in weak Bruhat order if and only if $T$ and $T'$ are in one of the relations; (WB1), (WB2), (WB3), (WB4-1), (WB4-2), (WB5-1), (WB5-2), (WB6-1), and (WB6-2) with some modification of zero column as in Remark 12.

**Example 14** Let $\sigma = -2, -4, 5, 3, 1 \in S_5^B$ and $T = \zeta^{-1}(\sigma)$ as in Example 9. We also let $\sigma_i = \sigma s_i$ and $T_i = \zeta^{-1}(\sigma_i)$ for $i \in \{0, 1, 2, 3, 4\}$. Since the pair $(2, 3)$ is not an inversion of $\sigma$, and the pairs $(1, 2), (3, 4), (4, 5)$ are inversions of $\sigma$, $\sigma \prec \sigma_2$ and $\sigma_j \prec \sigma$ for $j = 0, 1, 3, 4$. The covering relations in weak Bruhat order of the corresponding permutation tableaux of type B are shown in Figure 11.

From Theorem 13 and induction on length of a signed permutation, we have following theorem.

**Theorem 15** Let $\sigma \in S_n^B$ and $T = \zeta^{-1}(\sigma) \in \mathcal{PT}_n^B$, then

$$ \ell(\sigma) = \mathrm{inv}(\sigma) = 2\{\mathrm{zero}_{EE}(T) + \mathrm{zero}_{NN}(T)\} + \mathrm{one}(T). \quad (16) $$
<figure><img src="image_11.png" /><figcaption>Fig. 11: All covering relations in weak Bruhat order including $\mathcal{T}$.</figcaption></figure>

Rewriting the equation 16 in terms of permutation statistics by using Proposition 6 and Proposition 4, we have the following equation which is proved in [SZ10] for type A.

**Corollary 17** Let $\sigma \in \mathcal{S}_n^B$, then

$$ \ell(\sigma) = \mathrm{inv}(\sigma) = 2 \mathrm{al}_{\mathrm{nest}}(\sigma) + \mathrm{cr}(\sigma) + n - \mathrm{wex}(\sigma). $$

## References

[ABN11] Jean-Christophe Aval, Adrien Boussicault, and Philippe Nadeau. Tree-like tableaux. In 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), Discrete Math. Theor. Comput. Sci. Proc., AO, pages 63–74. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2011.

[BB05] Anders Björner and Francesco Brenti. Combinatorics of Coxeter groups, volume 231 of Graduate Texts in Mathematics. Springer, New York, 2005.

[Bur07] Alexander Burstein. On some properties of permutation tableaux. Ann. Comb., 11(3-4):355–368, 2007.

[CJVK13] Sylvie Corteel, Matthieu Josuat-Vergès, and Jang Soo Kim. Crossings of signed permutations and $q$-Eulerian numbers of type B. J. Comb., 4(2):191–228, 2013.

[CK11] Sylvie Corteel and Jangsoo Kim. Combinatorics of permutation tableaux of type A and type B. European J. Combin., 32:563–579, 2011.

[CL11] William Y. C. Chen and Lewis H. Liu. Permutation tableaux and the dashed permutation pattern 32–1. Electron. J. Combin., 18(1):Paper 111, 11, 2011.

[CN09] Sylvie Corteel and Philippe Nadeau. Bijections for permutation tableaux. European J. Combin., 30(1):295–310, 2009.

[Cor07] Sylvie Corteel. Crossings and alignments of permutations. Adv. in Appl. Math., 38(2):149–163, 2007.
[CP15] Soojin Cho and Kyoungsuk Park. Permutation statistics and weak Bruhat order in permutation tableaux of type B. *European J. Combin.*, 47:23–39, 2015.

[CSSW12] Sylvie Corteel, Richard P. Stanley, Dannis Stanton, and Lauren K. Williams. Formulae for Askey-Wilson moments and enumeration of staircase tableaux. *Trans. Amer. Math. Soc.*, 364(11):6009–6037, 2012.

[CW07a] Sylvie Corteel and Lauren K. Williams. A Markov chain on permutations which projects to the PASEP. *Int. Math. Res. Not.* IMRN, (17):Art. ID rnm055, 27, 2007.

[CW07b] Sylvie Corteel and Lauren K. Williams. Tableaux combinatorics for the asymmetric exclusion process. *Adv. in Appl. Math.*, 39(3):293–310, 2007.

[Nad11] Philippe Nadeau. The structure of alternative tableaux. *J. Combin. Theory Ser. A*, 118(5):1638–1660, 2011.

[SW07] Einar Steingrímsson and Lauren K. Williams. Permutation tableaux and permutation patterns. *J. Combin. Theory Ser. A*, 114(2):211–234, 2007.

[SZ10] Heesung Shin and Jiang Zeng. The *q*-tangent and *q*-secant numbers via continued fractions. *European J. Combin.*, 31(7):1689–1705, 2010.