Printer Friendly

Enumeration of corners in tree-like tableaux.

In this paper, we confirm conjectures of Laborde-Zubieta on the enumeration of corners in tree-like tableaux and in symmetric tree-like tableaux. In the process, we also enumerate corners in (type B) permutation tableaux and (symmetric) alternative tableaux. The proof is based on Corteel and Nadeau's bijection between permutation tableaux and permutations. It allows us to interpret the number of corners as a statistic over permutations that is easier to count. The type B case uses the bijection of Corteel and Kim between type B permutation tableaux and signed permutations. Moreover, we give a bijection between corners and runs of size 1 in permutations, which gives an alternative proof of the enumeration of corners. Finally, we introduce conjectural polynomial analogues of these enumerations, and explain the implications on the PASEP.

Keywords: permutations, signed permutations, permutation tableaux, type B permutation tableaux, tree-like tableaux, symmetric tree-like tableaux, alternative tableaux, symmetric alternative tableaux

1 Introduction

The partially asymmetric exclusion process (PASEP) is a model from statistical mechanics, in which particles jump stochastically to the left or to the right, the probability of hopping left is q times the probability of hopping right. Moreover, particles can enter from the left with probability [alpha] and exit at the right with probability [beta]. We can describe (see Corteel and Williams (2007)) the equilibrium state of the PASEP using permutation tableaux in Postnikov (2006), alternative tableaux in Viennot (2008) or tree-like tableaux in Aval et al. (2013b). These combinatorially equivalent objects have been the focus of intense research in the recent years. For example, the reader can be referred to Burstein (2007), Corteel and Nadeau (2009), Laborde-Zubieta (2015), Nadeau (2011) and references therein for more information. One of the main reasons being that they are in bijection with permutations. For each of these three tableaux, a type B version was also defined, e.g., see Aval et al. (2013b), Nadeau (2011), Steingrimsson and Williams (2007), and the previous bijections with permutations were extended to bijections with signed permutations.

Laborde-Zubieta (2015) showed that the corners in tree-like tableaux are interpreted in the PASEP as the locations where a jump of particle is possible. He started with the enumeration of occupied corners and obtained the following results.

Proposition 1.1 (Laborde-Zubieta, 2015, Theorem 3.2) The number of occupied corners in the set of tree-like tableaux of size n is n!.

Proposition 1.2 (Laborde-Zubieta, 2015, Theorem 3.7) The number of occupied corners in the set of symmetric tree-like tableaux of size 2n + 1 is [2.sup.n] x n!.

Regarding the unrestricted corners, he gave the following two conjectures.

Conjecture 1.3 (Laborde-Zubieta, 2015, Conjecture 4.1) The number of corners in the set of tree-like tableaux of size n is n! X n+4/6.

Conjecture 1.4 (Laborde-Zubieta, 2015, Conjecture 4.2) The number of corners in the set of symmetric tree-like tableaux of size 2n + 1 is [2.sup.n] X n! X 4n+13/12.

In this work, we give a proof of these conjectures. For the first one, through bijections, we give relations between the number of corners in permutation tableaux, alternative tableaux and tree-like tableaux. Then, using a bijection due to Corteel and Nadeau (2009), we interpret the number of corners in permutation tableaux as a statistic in permutations. By computing this statistic in permutations of fixed size, we deduce the enumeration of corners in each of the three kind of tableaux (Theorem 4.1). The second conjecture is proven in the same way, which also gives us the enumeration of corners in type B permutation tableaux, in symmetric alternative tableaux (Theorem 4.3). It should be noted that Hitczenko and Lohss (2015) proved both conjectures in a different way, using a probabilistic approach. Additionally, we present a bijection between corners in tree-like tableaux and runs of size 1 in permutations, which answers to a question raised in Gao et al. (2015). Counting corners in tree-like tableaux gives an information about the average number of locations where a jump of particle is possible in the PASEP, if we set q = [alpha] = [beta] = 1. We give a conjectural (a, b)-analogue of this enumeration which would generalise the result to the case where only q is equal to 1. We also conjecture an x-analogue for the enumeration of corners in symmetric tree-like tableaux.

The paper is organised in the following way. In Section 2 we give several definitions, in particular we recall the definitions of the tableaux we will be considering. Section 3 presents the different bijections we need to relate corners in tree-like tableaux with permutations. In parallel, we also deal with the type B case. Then (Section 4), we prove the two conjectures and enumerate corners in the other types of tableaux. Moreover we give a bijection between corners in tree-like tableaux and runs of size 1 in permutations. Finally we give polynomial analogues of Conjecture 1.3 and Conjecture 1.4, and partially prove them.

2 Preliminaries

First of all, to be self-contained in this paper, let us recall some necessary basic notions and introduce some notations in this section.

2.1 (k, n)-diagrams

Here we mainly adopt Cho and Park's terminologies in Cho and Park (2015). For two nonnegative integers n and k with n [??] k, a (k, n)-diagram [??] (left subfigure of Figure 1) is a left-justified diagram of boxes in a k X (n - k) rectangle with [[lambda].sub.i] boxes in the i-th row, where [[lambda].sub.1] [??] [[lambda].sub.2] [??] x x x [??] [[lambda].sub.k] [??] 0. The integer n is called the length of [??], it is equal to the number of rows plus the number of columns. Note that a (k, n)-diagram may have empty rows or columns. A shifted (k, n)-diagram is a (k, n)-diagram together with a stair-shaped array of boxes added above, where the j-th column (from the left) has (n - k + 1 - j) additional boxes for j [member of] [n - k]. We denote [??] the shifted (k, n)-diagram obtained from a (k, n)-diagram [??]. In terms of the definitions in Cho and Park (2015), V is called the (k, n)-subdiagram of [??]. The length of [??] is defined to be the length of its (k, n)-subdiagram. Among the cells we added, the ones at the top of a column are called diagonals. An example of a shifted (4, 8)-diagram is shown in the middle of Figure 1, its diagonals are pointed out in the right Figure 1.

[FIGURE 1 OMITTED]

Let us now introduce some definitions and notations about those diagrams. A (k, n)-diagram [??] is uniquely determined by its South-East border, which is the lattice path starting at the North-East corner of the rectangle k X (n - k), going along [??]'s border and finishing at the South-West corner. Following the same direction, we label the steps of the South-East border with [n] = {1,..., n}. We extend the labelling to shifted (k, n)-diagrams. An example of both cases is given respectively in the left and the middle subfigures of Figure 1. The steps of the South-East border are called, border edges. We label the rows and the columns of a (k, n)-diagram with the label of their corresponding vertical and horizontal border edge respectively. Moreover, in the case of a shifted (k, n)-diagram, we label the added rows as follows: if the diagonal cell of an added row is in column i, then the row is labeled by -i. The right subfigure of Figure 1 shows an example of the labelling of the rows and columns of a shifted (k, n)-diagram. From now on, we will say row i or column j when we actually refer to the row with the label i or to the column with the label j. The cell (i, j) is the cell at the intersection of the ith row starting from top and the jth column starting from left, this notation is independent from the previous labelling of rows and columns. The cells we will be looking at are the followings.

Definition 2.1 In a (shifted) (k, n)-diagram, a corner is a cell such that its bottom and right edges are border edges.

For example, the (4, 8)-diagram in the left subfigure of Figure 1 has two corners, (1, 4) and (3, 3). Its shifted (4, 8)-diagram has also two corners, (5, 4) and (7, 3), as we can see in the middle subfigure of Figure 1. The last definition we need, about (k, n)-diagrams, is the main diagonal. As we can see in the Figure 2, it is the line going through the North-West and the South-East corners of the top left cell.

[FIGURE 2 OMITTED]

In this article we study alternative tableaux, permutation tableaux, tree-like tableaux and their corresponding type B versions. Tableaux should be understood in the following way.

Definition 2.2 Let [??] be a (shifted) (k, n)-diagram, a tableau of underlying diagram [??], is a certain filling of the cells of [??] with some symbols. The underlying diagram of T is denoted by [??](T). The previous definitions about (shifted) (k, n)-diagrams are extended to tableaux.

A corner of tableaux T is called an occupied corner if it is filled with a symbol, otherwise, a corner cell is called a non-occupied corner. Let us denote by [??] (T) the set of corners of a given tableau T and [??](X) the set corners of a given set X of tableaux, i.e.,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Similarly, denote by c(T) the number of corners of T and let c(X) = |[??](X)|.

2.2 Tableaux

In what follows, we shall introduce the main combinatorial objects of our work: permutation tableaux, alternative tableaux, tree-like tableaux and their type B versions.

2.2.1 Permutation tableaux

Permutation tableaux arose in the study of totally nonnegative Grassmannian, see Postnikov (2006). There have been a lot of work on the subject in many different directions since they were formally introduced by Steingrimsson and Williams (2007), see Burstein (2007), Corteel and Nadeau (2009), Corteel and Kim (2011) and Corteel and Williams (2007) for details.

Definition 2.3 A permutation tableau, is a (k, n)-diagram with no empty columns together with a 0,1-filling of the cells such that

(1) each column has at least one 1;

(2) there is no 0 which has a 1 above it in the same column and a 1 to the left of it in the same row.

We denote by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the set of permutation tableaux of length n. An example of permutation tableau of length 8 is given in the left subfigure of Figure 3. We need to introduced some definitions about permutation tableaux that will be needed in the description of the bijection between alternative tableaux and permutation tableaux (Section 3.2). In a permutation tableau, a topmost 1 is a highest 1 of a column. A restricted 0, is a 0 with a 1 above it in the same column. Finally, a rightmost restricted 0, is a restricted 0 with no restricted 0 to its right.

The type B version of these tableaux, were introduced by Lam and Williams (2008).

Definition 2.4 A type B permutation tableau is a shifted (k, n)-diagram [??] together with a 0, 1-filling of [??] satisfying the following conditions:

(1) each column has at least one 1;

(2) there is no 0 which has a 1 above it in the same column and a 1 to the left of it in the same row;

(3) if a 0 is in a diagonal cell, then it does not have a 1 to the left of it in the same row.

We denote by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the set of type B permutation tableaux of length n. An example of a permutation tableau of length 7 is given in right subfigure of Figure 3. We extend the definition of topmost 1, restricted 0 and rightmost restricted 0, adding that a 0 in a diagonal is restricted.

[FIGURE 3 OMITTED]

2.2.2 Alternative tableaux

Alternative tableaux, were introduced by Viennot (2008) as follows.

Definition 2.5 An alternative tableau is a (k, n)-diagram with a partial filling of the cells with left arrows "[left arrow]" and up arrows "[up arrow]", such that all cells left of a left arrow "[left arrow]", or above an up arrow "[up arrow]" are empty. In other words, all cells pointed by an arrow must be empty.

We denote by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the set of alternative tableaux of length n. An example of an alternative tableau of length 8 is given in the left subfigure of Figure 4.

The type B version of alternative tableau are called symmetric alternative tableaux, they were defined by Nadeau (2011).

Definition 2.6 A symmetric alternative tableau is an alternative tableau unchanged by the reflection with respect to its main diagonal.

The set of symmetric alternative tableaux of length 2n will be denoted [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. A symmetric alternative tableau of size 8 is given in the right subfigure of Figure 4.

[FIGURE 4 OMITTED]

2.2.3 Tree-like tableaux

The last kind of tableaux we will consider are the tree-like tableaux. They were introduced in Aval et al. (2013b). They have a nice recursive structure, given by an insertion algorithm, which simplified some of the previous main results.

Definition 2.7 A tree-like tableau is a filling of (k, n)-diagram (without empty rows or empty columns) with points inside some cells, such that the resulting diagram satisfies the following three rules,

(1) the top left cell of the diagram contains a point, called the root point;

(2) for every non-root pointed cell c, there exists either a pointed cell above c in the same column, or a pointed cell to its left in the same row, but not both;

(3) every column and every row possess at least one pointed cell.

The size of a tree-like tableau is defined to be its number of points. It is not difficult to see that the length of a tree-like tableau is equal to its size plus one. In the sequel, we denote by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the set of the tree-like tableaux of size n. An example of a tree-like tableau of size 8 is shown in the left subfigure of Figure 5.

Definition 2.8 A symmetric tree-like tableau is a tree-like tableau unchanged by the reflection with respect to its main diagonal.

The size of a symmetric tree-like tableau is necessarily odd, we denote by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the set of symmetric tree-like tableaux of size 2n + 1. An example of a symmetric tree-like tableau of size 9 is given in the right subfigure of Figure 5.

[FIGURE 5 OMITTED]

2.3 Permutations

A permutation [pi] of length n is a bijection from [n] to [n], we use the notation [[pi].sub.i] := [pi](i) for 1 [??] i [??] n. We can represent a permutation with the word [[pi].sub.1] ... [[pi].sub.n]. The group of permutations of length n is denoted by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We consider the following non usual definitions for ascents and descents given in Corteel and Nadeau (2009).

Definition 2.9 Given a permutation [pi] = [[pi].sub.1] x x x [[pi].sub.n] [member of] [??] with the convention that [[pi].sub.n+1]4 = n + 1, we say that [[pi].sub.i] is a descent if [[pi].sub.i] > [[pi].sub.i+1] and call [[pi].sub.i] an ascent if [[pi].sub.i] < [[pi].sub.i+1] for 1 [??] i [??] n.

For example, the descents of the permutation 5, 7, 6, 3, 1, 2, 8, 4 are {7, 6, 3, 8}.

A signed permutation (also called permutation of type B) [sigma] of length n is a bijection on {-n, - (n - 1),..., -1, 1..., n} satisfying [sigma](-i) = -[sigma](i) for i [member of] [n]. We also use the notation [[sigma].sub.i]: = [sigma](i) and represent a signed permutation with the word [[sigma].sub.1] ... [[sigma].sub.n]. The group of type B permutations is denoted by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Corteel and Kim (2011) gave the following definitions of an ascent and a descent of a signed permutation.

Definition 2.10 Let [sigma] = [[sigma].sub.1] [[sigma].sub.2] x x x [[sigma].sub.n] [member of] [??] with convention that [[sigma].sub.n+1] = n +1. For i [member of] [n], [[sigma].sub.4] is a signed descent if [[sigma].sub.i] < 0 or [[sigma].sub.i] > |[[sigma].sub.i+1]|, otherwise [[sigma].sub.i] is a signed ascent and satisfies 0 < [[sigma].sub.i] < |[[sigma].sub.i+1]|.

For [sigma] = 3, -1, -4, 2, 6, 5, 7 [member of] [??], the signed descents of [sigma] are { - 1, -4, 3, 6}.

3 Bijections

In this section we give bijections between the different kinds of tableaux and we deduce equalities between the number of corners in each type of tableaux.

3.1 A bijection [alpha] between tree-like tableaux and alternative tableaux compatible with the type B case

Recall that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the set of tree-like tableaux of size n and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the set of alternative tableaux of length n.

Theorem 3.1 (Aval et al. (2013b)) There is a bijection a : [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that for any [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the underlying diagram of [alpha](T) is obtained from [??] by deleting its topmost row and its leftmost column.

We give a description of the bijection a and its inverse [[alpha].sub.-1] in detail without proof. Given a tree-like tableau [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of size n, we construct [alpha](T) in two steps. First replace every non-root point p with a left arrow "[left arrow]" if there is no point to its left in the same row and an up arrow "[up arrow]" if there is no point above it in the same column. Then, simply delete the topmost row and the leftmost column. One can verify that the tableau we obtain is an alternative tableau of length n - 1. Figure 6 gives an example of the bijection.

Let T' be an alternative tableau of length n - 1 with underlying diagram [??]. Suppose [??] has k rows and n - 1 - k columns. We construct the underlying diagram [??] of [[alpha].sup.-1](T') from D' by adding a column of k cells at the left of its leftmost column, a row of n - 1 - k cells above its topmost row and a cell at its top left corner. Note that [??] is a (k, n - 1)-diagram and [??] is a (k + 1, n + 1)-diagram. Next, for any cell c = (i, j) in [??], if there is an up arrow "[up arrow]" in c and there is no arrows (both "[left arrow]" and "[up arrow]") to its left in the same row, add a point in the cell (i + 1, 1) in [??]. If there is a left arrow "[left arrow]" in c and there is no arrows above c in the same column, add a point in the cell (1, j + 1) in [??]. Then add a point in (1, 1) and (1, j + 1) or (i +1, 1) in [??] if column j or row i has no arrows in [??]. Lastly, add a point in (i + 1, j + 1) in [??] if there is an arrow in (i, j) in [??], the resulting tableau is a tree-like tableau of size n, denoted by T = [[alpha].sup.-1](T').

On the basis of the bijection, we can conclude the following result.

Corollary 3.2 The number of corners in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] satisfy the relation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: The underlying diagram of [alpha](T) is obtained from [??](T) by removing the topmost row and the leftmost column. Hence, the bijection [alpha] doesn't create any new corner, but it removes the corners at the right of the topmost row (corners of type 1) or the corners at the bottom of the leftmost column (corners of type 2). Corners of type 1 in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are in easy bijection with tree-like tableaux of size n - 1, which are counted by (n - 1)!. To a corner of type 1 c in a tree-like tableau T of size n, we associate the tree-like tableau obtained from T by removing c. With a similar argument, we can also prove that corners of type 2 in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are counted by (n - 1)!.

Furthermore, the bijection a can be restricted to symmetric tree-like tableaux and symmetric alternative tableaux. As an example, see Figure 6.

Theorem 3.3 If [alpha] is restricted to the set of symmetric tree-like tableaux [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then it is also a bijection between the set of symmetric tree-like tableaux [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the set of symmetric alternative tableaux [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[FIGURE 6 OMITTED]

With Theorem 3.3, it is natural to deduce the following corollary.

Corollary 3.4 The number of corners in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is equal to the number of corners in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] plus [2.sup.n](n - 1)!, i.e.,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: As in Corollary 3.2, the bijection a doesn't create any new corner, but it removes the corners at the right of the topmost row (type 1) and the corners at the bottom of the leftmost column (type 2). A symmetric tree-like tableau has a corner of type 1 if and only if it has a corner of type 2. Hence we will enumerate pairs of corners of type 1 and 2 belonging to the same symmetric tree-like tableaux of size n. Such pairs are in easy bijection with symmetric tree-like tableaux of size n - 1, which are counted by [2.sup.n-1](n - 1)!. The bijection simply consists in removing the two corners.

3.2 A bijection [gamma] between alternative tableaux and permutation tableaux

In this subsection, we give a simple description of the bijection [gamma], the reader can refer to Viennot (2008) for more details about its proof.

Theorem 3.5 (Viennot (2008)) There exists a bijection [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that for any permutation tableau [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the underlying diagram of alternative tableau [gamma] (PT) is obtained from [??](PT) by removing its first row.

Given a permutation tableau PT, [gamma](PT) is computed in the following way. First, change the topmost 1 in every column to "[up arrow]". Then, transform every rightmost restricted 0 to "[left arrow]". Finally, delete all other 0s and 1s, and erase the first row. See Figure 7 as an example.

Conversely, let AT be an alternative tableau of length n - 1 with underlying diagram D'. Suppose D' has k rows and n - 1 - k columns. The underlying diagram [??] of [[gamma].sup.-1](AT) is obtained by adding to D' a row of n - 1 - k cells above its first row. We change the filling, in the following way. For any cell c = (i, j) in [??], if there is an up arrow "[up arrow]" (resp. "[left arrow]") in c, add a 1 (resp. 0) in the cell (i + 1, j) in D. Then, if there is no 1 in some column j of D, we add a 1 in the cell (1, j). Lastly, fill with 0s the empty cells to the left of a 0 in the same row, or above a 1 in the same column, and then, fill the rest of empty cells with 1s.

[FIGURE 7 OMITTED]

Based on Theorem 3.5, we can deduce the following corollary.

Corollary 3.6 The number of corners in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] satisfy the relation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: The bijection [[gamma].sup.-1] doesn't form any corner, but if the step 1 is a west step, a new corner is constructed. The alternative tableau of length n - 1 such that the step 1 is a west step, are in easy bijection with alternative tableaux of length n - 2, which are counted by (n - 1)!. The bijection simply consist in removing the west step.

3.3 A bijection [zeta] between symmetric alternative tableaux and type B permutation tableaux

The alternative representation of a permutation tableau of type B was introduced by Corteel and Kim (2011).

Definition 3.7 The alternative representation of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a tableau obtained from [PT.sup.B] according to the following operations, denoted by R. First, we replace the topmost 1s with "[up arrow]"s and the rightmost restricted 0s with "[left arrow]"s and remove the remaining 0s and 1s. Second, we remove the "[up arrow]"s in the diagonal and cut off the diagonal cells as shown in Figure 8. We call the resulting tableau, denoted by R(P[T.sup.B]), the alternative representation of P[T.sup.B].

[FIGURE 8 OMITTED]

It is not difficult to see that R is a bijection, see Corteel and Kim (2011) for details. We note that the alternative representation of a type B permutation tableau can be obtained by cutting a symmetric alternative tableau across its main diagonal line. Hence we can construct a bijection [zeta] between permutation tableaux of type B and symmetric alternative tableaux via the bijection R.

Theorem 3.8 There is a bijection [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: We denote by F the reflection of an alternative representation across all its diagonal cells (or main diagonal line). It is bijection between alternative representations and symmetric alternative tableaux. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], is a bijection from P[T.sub.B.sub.n] to A[T.sup.sym.sub.2n].

As a corollary of Theorem 3.8, we have the following result.

Corollary 3.9 The number of corners in the set of symmetric alternative tableaux of length 2n is equal to twice the number of corners in the set of type B permutation tableaux of length n plus [2.sup.n-1]n!, i.e.,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: The bijection [zeta] doesn't remove any corner, but it creates new ones. Let PT be a type B permutation tableau. All the corners of PT appears twice in [zeta](PT) and if the step 1 of PT is a west step, an additional corner appears in [zeta](PT). To prove the Corollary, we just need to enumerate the number of type B permutation tableaux of size n such that step 1 is a west step, we denote [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the set of those tableaux. In fact, they are in bijection with type B permutation tableaux of size n such that step 1 is a south step [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The bijection consist simply in removing the rightmost diagonal, i.e., the cell above the step 1. Since the set of permutation tableaux of size n is the disjoint union of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], hence, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

3.4 A bijection [phi] from permutation tableaux to permutations

To begin with, it is worthy to mention that there have been several bijections from permutation tableaux to permutations up to now, see Burstein (2007); Corteel and Nadeau (2009); Corteel and Kim (2011); Steingrimsson and Williams (2007). Here we only introduce the one due to Corteel and Nadeau. We give the following theorem without describing the bijection, the reader can be referred to Corteel and Nadeau (2009) for details.

Theorem 3.10 (Corteel and Nadeau, 2009, Theorem 1. (1)) There exists a bijection [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that for any permutation tableau [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and 1 [??] i [??] n, i is a label of a column in PT if and only if i is a descent in [pi]; and i is a label of a row in PT if and only if i is an ascent in [pi], where [pi] = [phi](PT).

By Theorem 3.10, we can easily find the following result.

Corollary 3.11 For a permutation tableau [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and 1 [??] i < n, the consecutive border edges labeled with i and i + 1 in the South-East border in its underlying diagram form a corner if and only if i is an ascent and i + 1 is a descent in [pi] = [phi](PT).

Remark 3.12 It should be noted that, since ascent and descent are not defined in the usual way, the property such that i is an ascent and i + 1 is a descent, does not correspond to a peak.

3.5 A bijection [xi] between type B permutation tableaux and type B permutations

Corteel and Kim (2011) built a bijection between type B permutation tableaux and signed permutations.

Theorem 3.13 (Corteel and Kim, 2011, Proposition 4.1) There exists a bijection [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that for any [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and 1 [??] i [??] n, i is a signed descent if any only if i is a label of a column; and i is a signed ascent if any only if i is a row label.

By Theorem 3.13, we deduce the following corollary easily.

Corollary 3.14 For a signed permutation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and P[T.sup.B] = [xi]([sigma]), the consecutive border edges labeled with i and i + 1 in the underlying shifted (k, n)-diagram of P[T.sup.B] form a corner if, and only if, i is a signed ascent and i + 1 is a signed descent in [sigma].

4 Enumeration of Corners

4.1 Enumeration of Corners

In this subsection, from the enumeration of the statistics on permutations and signed permutations that arose in Corollary 3.11 and Corollary 3.14, we deduce the enumeration of corners in each kind of tableau.

Theorem 4.1 At fixed size, the number of corners in each of the three kinds of type A tableaux, is counted by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: For n = 1 , there is only one tableau for each kind, and only the tree-like tableau of size 1 has a corner.

For general n, using Corollary 3.2, Corollary 3.6 and Corollary 3.11, we just need to compute the number of i's in permutations of size n such that i is an ascent and i + 1 is a descent. Suppose [a.sub.j] ([pi]) means that i is an ascent and i + 1 is a descent in a permutation [pi] and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For 1 [??] i < n, let [A.sub.i] denote the set of permutations in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that i is an ascent and i + 1 is a descent in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and |[A.sub.j]| the cardinality of [A.sub.j]. It is clear that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

So, it is sufficient to compute |[A.sub.i]| in order to count [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For any permutation [pi] = [[pi].sub.1]... [[pi].sub.n] [member of] [A.sub.i], suppose there exist 1 [??] [t.sub.1], [t.sub.2] [??] n such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By the definition of ascents and descents, we know that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. There are three cases to consider.

Case 1: If [t.sub.2] = [t.sub.1] + 1, it means that there is a subsequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [pi]. It is easy to see that the number of such permutations is (i - 1)(n - 2)!.

Case 2: If [t.sub.1] = [t.sub.2] + 1, similarly there is a subsequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It is clear that the number of such permutations is (n - 2)! + (n - i - 1)(n - 2)! = (n - i)(n - 2)!, where (n - 2)! counts the number of permutations such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Case 3: For |[t.sub.1] - [t.sub.2]| > 1, there are two subcases to consider.

(a) if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the number of such permutations is (n - i - 1) (i - 1)(n - 2)!.

(b) if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the number of such permutations is (i - 1)(n - 2)!.

Therefore, in total there are (n - i) (i - 1) (n - 2)! such permutations in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

So, the number of corners in the set of permutation tableaux of length n [??] 2 is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This completes the proof.

As the third author gave the number of occupied corners, see Proposition 1.1, we can give an enumerative result for non-occupied corners in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Corollary 4.2 The number of non-occupied corners in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is n! X n-2/6 for n [??] 3 and zero for n = 1, 2. We also obtain analogues results with type B tableaux.

Theorem 4.3 At fixed size, the number of corners in each of the three kind of type B tableaux, is counted by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: For n = 1 , there are two tableaux for each kind. The two permutations tableaux have no corners, only one of the two alternative tableaux has a corner and the two tree-like tableaux have respectively one and two corners.

For general n, using Corollary 3.4, Corollary 3.9 and Corollary 3.14, we can compute the number of corners in each kind of type B tableaux, from the enumeration of i's in the permutation [sigma] such that i(1 [??] i < n) is a signed ascent and i + 1 is a signed descent in a. Suppose, [b.sub.i]([pi]) means that i is a signed ascent and i + 1 is a signed descent in [sigma] and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For 1 [??] i < n, let [B.sub.i] denote the set of type B permutations in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that i is a signed ascent and i + 1 is a signed descent in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and |[B.sub.i]| the cardinality of [B.sub.i]. It is clear that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

So, it is sufficient to compute |[B.sub.i]| in order to count [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For 1 [??] i < n and [sigma] = [[sigma].sub.1][[sigma].sub.2] x x x [[sigma].sub.n] [member of] [B.sub.i]. Suppose there exist 1 [??] [t.sub.1], [t.sub.2] [??] n such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It is worthy to mention that 1 [??] [t.sub.1], [t.sub.2] [??] n and [t.sub.1] [not equal to] [t.sub.2]. By the definition of [B.sub.i] we know that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a signed ascent and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a signed descent in [sigma], which implies that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So there are two cases to consider for a given integer i.

Case 1: If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we can divide it into two subcases:

Subase 1: [t.sub.2] = [t.sub.1] + 1, which means that there is a subsequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [sigma]. By the definition of signed permutations, it is not difficult to compute the number of such signed permutations is [2.sup.n-2](n - 1)!.

Subase 2: [t.sub.2] = [t.sub.1] + 1, then there are two subcases to consider.

(i) if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the number of such type B permutations is [2.sup.n-2](n-i-1)(n-1)!;

(ii) if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the number of such type B permutations is [2.sup.n-2](n - 1)!.

Hence there are [2.sup.n-2] (n - i)(n - 1)! such signed permutations in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Case 2: If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Similarly, there are three subcases to consider:

Subase 1: if [t.sub.2] = [t.sub.1] + 1, this implies that there is a subsequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] suchthat [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [sigma]. By the definition of permutations of type B, the number of such permutations is [2.sup.n-2](i - 1)(n - 2)!.

Subase 2: if [t.sub.1] = [t.sub.2] + 1. That is to say, there is a subsequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [sigma]. Analogously, the number of such permutations is [2.sup.n-2](n - 2)! + [2.sup.n-2](n - i - 1)(n - 2)!, where [2.sup.n-2] (n - 2)! counts the number of permutations such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus such type B permutations are counted by [2.sup.n-2](n - i)(n - 2)!.

Subase 3: if |[t.sub.1] - [t.sub.2]| > 1, there are two subcases to consider:

(i) if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the number of such permutations is [2.sup.n-2](n - i - 1)(i - 1)(n - 2)!.

(ii) if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the number of such permutations is [2.sup.n-2](i - 1)(n - 2)!. In total, there are [2.sup.n-2](n - i)(i - 1)(n - 2)! such type B permutations.

All in all, the number of elements in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This completes the proof.

By Proposition 1.2 and Theorem 4.3, we can enumerate the non-occupied corners in symmetric tree-like tableaux of size 2n + 1.

Corollary 4.4 The number of non-occupied corners in symmetric tree-like tableaux [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of size 2n + 1 is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

4.2 Bijection between corners and runs of size 1

In this subsection, we give an alternative proof of the enumeration of corners, by constructing a bijection between corners in tree-like tableaux and ascending runs of size 1 in permutations. This answers to a question raised in Gao et al. (2015). Ascending run is also called increasing run, which was first studied deeply by Gessel (1977). Recently, Zhuang studied further on runs and generalized Gessel's results to allow for a much wider variety of restrictions on increasing run lengths, for more details, see Zhuang (2016). There is a closed formula counting the number of ascending runs of size r in permutations of size n (Sloane et al., 2011, A122843), for 0 < r < n we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

In particular, for r = 1, we get the sequence enumerating corners in tree-like tableaux.

An ascending run of length r of a permutation [sigma] = [[sigma].sub.1] x x x [[sigma].sub.n], is a sequence ([[sigma].sub.m],..., [[sigma].sub.m+r-1]) such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with the convention that [[sigma].sub.0] = n + 1 and [[sigma].sub.n+1] = 0. In particular, [sigma] has a run of size 1 means that there exists i [member of] [n] such that [[sigma].sub.i-1] > [[sigma].sub.i] > [[sigma].sub.i+1].

In order to build the bijection, we need a preliminary result about non-ambiguous trees due to Aval et al. (2014). They correspond to rectangular shaped tree-like tableaux. The height (resp. width) of a non-ambiguous tree is its number of row (resp. column) minus 1. We have the following result about these objects (it is a reformulation of Proposition 1.16 in Aval et al. (2015)).

Proposition 4.5 Non-ambiguous trees of height h and width w are in bijection with permutations [sigma] of {1, 2,..., w, 0, 1,..., h}, finishing by a pointed element and such that if two consecutive elements [[sigma].sub.i] and [[sigma].sub.i+1] are both pointed or not pointed, then [[sigma].sub.i] < [[sigma].sub.i+1].

Proof: The initial result is that, non-ambiguous trees of height h and width w are in bijection with pairs (u, v) of 2-colored words, with blue letters on [w] and red letters on [h], where each letter appear exactly once (in u or in v), letters in blocks of the same colors are decreasing, u (resp. v) ends by a red (resp. blue) letter.

In order to obtain the Proposition 4.5, we turn pairs (u, v) into the desired permutations [sigma]. Let us consider a non-ambiguous tree nat and its corresponding pair (u, v). We start by constructing a pair (u', v') by replacing the blue (resp. red) letters i of u and v by the uncolored (resp. uncolored pointed) letters w - i + 1 (resp. h - i + 1). The permutation [sigma] corresponding to nat is v'0u'.

The bijection between corners and ascending runs of size 1 is decomposed into two steps: Lemma 4.6 and Lemma 4.7.

Lemma 4.6 For n [??] 1, there is a bijection between corners in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and triplets ([T.sub.l], [T.sub.r], nat) such that

* [T.sub.l] is a tree-like tableau of size [n.sub.l],

* [T.sub.r] is a tree-like tableau of size [n.sub.r],

* [n.sub.l] + [n.sub.r] + 1 = n,

* nat is a non-ambiguous tree of height left([T.sub.r]) + 1 and width top([T.sub.l]) + 1.

Proof: The proof is based on the l-cut procedure defined in Aval et al. (2014). Let T be in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and c one of its corners. We start by cutting T along the lines corresponding to the bottom and the right edges of c, as shown in Figure 9a. We denote by L the bottom part, M the middle part and R the right part. In order to obtain [T.sub.l] we add to L a first row whose length is equal to the number of columns of M minus 1. There is exactly one way to add dots in this first row for [T.sub.l] to be a tree-like tableau: we put them inside the cells corresponding to non empty columns in M. In a similar way, we obtain [T.sub.r] from R by adding a dotted first column. [T.sub.l] and [T.sub.r] are two tree-like tableaux, and the sum of their length is equal to the length of T, hence [n.sub.l] + [n.sub.r] + 1 = n. Finally, removing the empty rows and columns of M we obtain nat. This procedure is illustrated in Figure 9b. It should be clear that the construction can be reversed and that [T.sub.l], [T.sub.r] and nat verifies the desired conditions.

Lemma 4.7 The triplets ([T.sub.l], [T.sub.r], nat) satisfying all the conditions in Lemma 4.6 are in bijection with runs of size 1 in permutations of size n.

Proof: The idea of the proof is the following: from a triplet ([T.sub.l], [T.sub.r], nat) we construct a permutation [sigma] of size n which have a run of size 1 ([[sigma].sub.k]) such that [[sigma].sub.k] = [n.sub.l] + 1 for some k. [T.sub.l] gives the ordering of the values smaller than [[sigma].sub.k], [T.sub.r] the ordering of the values bigger than [[sigma].sub.k], and nat tells us how we mix them and where we put [[sigma].sub.k].

Tree-like tableaux of size n with k points in the first column are in bijection with permutations of size n with exactly k cycles. Indeed, by Proposition 1.3 in Aval et al. (2013b), they are in bijection with permutation tableaux of size n with k unrestricted rows. Moreover, by Theorem 1 in Corteel and Nadeau (2009), they are in bijection with permutations of size n with k right-to-left minimum. Finally, the statistic of right-to-left minimum is equi-distributed with the statistic left-to-right maximum, which is itself equidistributed with the statistic of the number of cycles as shown by the "transformation fondamentale" of Foata-Schutzenberger (Proposition 1.3.1 in Stanley (2012) or Section 1.3 in Foata and Schutzenberger (1970)). Using an axial symmetry with respect to the main diagonal of the underlying diagram of T, we deduce the same result for tree-like tableaux of size n with k points in the first row. We denote by h and w the height and the width of nat respectively. Let l[sigma] (resp. r[sigma]) be the permutation associated to [T.sub.l] (resp. [T.sub.r]) by this bijection. We denote by [L.sub.1], x x x , [L.sub.w] (resp. [R.sub.1], x x x , [R.sub.h]) the disjoint cycles of l[sigma] (resp. r[sigma]), such that if i < j, then the maximum of [L.sub.i] (resp. [R.sub.i]) is smaller than the maximum of [L.sub.j] (resp.[R.sub.j]). In addition, we shift the values of the [R.sub.i] by [n.sub.l] + 1. We will write a cycle without parenthesis and with its biggest element at the first position. For example, suppose l[sigma] = (6) (7523) (9184) and r[sigma] = (423) (5) (716) (98), then [L.sub.1] = 6, [L.sub.2] = 7 5 2 3, [L.sub.3] = 9184, [R.sub.1] = 14 12 13, [R.sub.2] = 15, [R.sub.3] = 1711 16 and [R.sub.4] = 19 18. Let m be the word corresponding to nat. If 0 is not the last letter of m and if the letter after 0 is not pointed, we can uniquely represent m as

[FIGURE 9 OMITTED]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where u can be empty, and the words [b.sub.i] (resp. [a.sub.i]) consist of a non empty increasing sequence of pointed (resp. non pointed) letter. In this case, we replace m by swapping subwords [a.sub.i] and [b.sub.i] for all i (1 [??] i [??] p), i.e.,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Obviously, this operation is bijective.

We finish the general construction by substituting [n.sub.l] + 1 for 0, [L.sub.i] for i and [R.sub.i] for i. For example, if

m = 23231401

then we obtain the run of size one

15 17 11 16 7 5 2 3 9 1 8 4 14 12 13 19 18 10 6.

Another example, if

m = 14012233

then

m* = 14021233

and thus we get

6 19 18 10 7 5 2 3 14 12 13 15 9 1 8 4 17 11 16.

In order to reverse the construction from a run of size one ([[sigma].sub.k]), we use the "transformation fondamentale" in each maximal sequence of integers smaller (resp. larger) than [[sigma].sub.k]. This way, we are able to identify the [L.sub.i] (resp. [R.sub.i]), so that we can recover l[sigma], r[sigma] and nat. For example, if we consider the run

426 11 9 128 37 1 5 10,

we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

hence

l[sigma] = (3) (4 2) (6) (7 1 5), r[sigma] = (2) (3 1) (4), m* = 232301441, m = 232301144.

As a consequence of Lemma 4.6 and Lemma 4.7, we have the following theorem.

Theorem 4.8 For n [??] 1, corners in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are in bijection with runs of size 1 in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Even if we send corners to runs of size 1, the two statistics does not have the same distribution. For example, the permutation 321 have 3 runs of size 1 while a tree-like tableau of size 3 cannot have 3 corners.

From Theorem 4.8 and Equation (1) we deduce the enumeration of corners.

Corollary 4.9 The number of corners in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is n! * n+4/6 for n [??] 2 and 1 for n =1.

4.3 Polynomial analogues

In this subsection, we present two conjectures that generalise the enumeration of corners in tree-like tableaux and in symmetric tree-like tableaux, by giving polynomial analogues.

4.3.1 (a, b)-analogue of the average number of non-occupied corners in treelike tableaux

To refine the enumeration of corners, the two statistics over tree-like tableaux we consider are: top and left, that were defined in Aval et al. (2013b). They count the number of non-root points in the first row and in the first column, respectively. They are interesting statistics since they correspond to the parameters [alpha] and [beta] respectively in the PASEP.

As explained in Section 4 of Laborde-Zubieta (2015), computing the average number of corners gives us the average number of locations where a particle may jump to the left or to the right in the PASEP model, in the case [alpha] = [beta] = q = 1 and [delta] = [gamma] = 0. Computing the (a, b)-analogue of average number of corners

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where w(T) = [a.sup.top(T)][b.sup.left(T)], would extend the result to the case q = 1 and [delta] = [gamma] = 0, if we replace a by [[alpha].sub.-1] and b by [[beta].sub.1].

The (a, b)-analogue of the average number of tree-like tableaux, was computed in Aval et al. (2013b), it is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It turns out that the (a,b)-analogue of the average number of occupied corners is also [T.sub.n](a, b). In order to prove this, we just need to redo the short proof of Section 3.2 in Laborde-Zubieta (2015) via keeping track of left and top points. As a consequence of this result, computing the (a,b)-analogue for corners or for non-occupied corners, is equivalent. In this section, we focus on non-occupied corners, because their study seems easier. We denote by no[c.sub.n](a, b) the (a,b)-analogue of the average number of non-occupied corners, i.e.,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where noc(T) is the number of non-occupied corners of T. In particular, Corollary 4.2 implies that no[c.sub.n](1, 1) = n! x n-2/6. Using an implementation of tree-like tableaux in Sage Developers (2015), the following conjecture has been experimentally confirmed until n = 10.

Conjecture 4.10 For n [??] 3, the (a,b)-analogue of the enumeration of non-occupied corners is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In order to obtain the conjecture about corners, we just have to add [T.sub.n](a, b) to no[c.sub.n](a, b). So, [c.sub.n](a, b) can be rewritten as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let X(s) be the random variable counting the number of locations of a state s of size n of the PASEP, where a particle may jump to the right or to the left. We can compute the conjectural expected value of X by using the formula of Section 4 in Laborde-Zubieta (2015),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Instead of studying no[c.sub.n](a, b) as a sum over tree-like tableaux, we will study it as a sum over non-occupied corners in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let noc be a non-occupied corner of a tree-like tableau T, we define the weight of noc as

w(noc): = w(T).

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the set of non-occupied corners in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we can rewrite no[c.sub.n](a, b) as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The study of this conjecture brings a partitioning of non-occupied corners. We denote by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the set of non-occupied corners with no point above them, in the same column, except in the first row and no point at their left, in the same row, except in the first column. The set of non-occupied corners with no point above them, except in the first row, or no point at their left, except in the first column, but not both in the same time, are denoted by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] respectively. The remaining corners are regrouped in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The different types of non-occupied corners are illustrated in Figure 10.

[FIGURE 10 OMITTED]

Proposition 4.11 For n [??] 3, the (a, b)-analogue of the enumeration of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: In order to show that, we put in bijection non-occupied corners of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of this shape and the set of pairs (T, i) where T is a tree-like tableau of size n - 2 and i is an interstice between two consecutive border edges of T. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and T' be its tree-like tableau of size n. Let j be the integer such that noc is the cell at the intersection of row j and column j + 1. We obtain a tree-like tableau T of size n - 2 by removing the row j and the column j + 1. The North-West corner i of noc corresponds to an interstice between two consecutive border edges of T, we associate to noc the pair (T, i). Conversely, let us consider a pair (T, i). We construct a tree-like tableau T' as follows, we add to T a row and a column ending a common cell c with i as its North-West corner, and we had a point to the left-most (resp. highest) cell of the new row (resp. column). In particular, c is in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The bijection is illustrated in Figure 11a.

[FIGURE 11 OMITTED]

For each tree-like tableau T of size n - 2, there are n - 2 choices of interstice i, in addition, the weight of noc is equal to ab x w(T). As a result,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We are also able to give an (a, b)-analogue of the enumeration of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In order to do that, we need an (a, b)-analogue of the enumeration of tree-like tableaux of size n with a fixed number of rows k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

From Proposition 3.4 of Aval et al. (2013b), we already know that [A.sub.1,1](n, k) is the Eulerian number and satisfies

[A.sub.1,1](n + 1, k) = k[A.sub.1,1](n, k) + (n + 2 - k)[A.sub.1,1](n, k - 1).

In the general case, the linear recurrence satisfied by [A.sub.a,b](n, k) is

[A.sub.a,b](n + 1, k) = (a - 1 + k)[A.sub.a,b](n, k) + (b + n +1 - k)[A.sub.a,b](n, k - 1).

As in Aval et al. (2013b), we consider the Eulerian polynomial:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Lemma 4.12 For n [??] 2,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: The first identity is a consequence of the definition of [A.sub.n](t). For the second one, we deduce from (2) that [A.sub.n](t) satisfies the recurrence relation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with initial condition [A.sub.1](t) = t. Hence, by differentiating and evaluating at t = 1, we get the following recurrence relation for [A'.sub.n] (1)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For n [??] 3, dividing by [T.sub.n-1] (a, b), we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [A'.sub.2] (1) = a + 2b, for n [??] 2,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We can now prove the following result,

Proposition 4.13 For n [??] 3, the (a, b)-analogue of the enumeration of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and the (a, b)-analogue of the enumeration of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: In order to compute [f.sub.n](a, b) we put in bijection elements of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with pairs (T, r) where T is a tree-like tableaux of size n - 1 and r is a row of T, different from the first one. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and T' its tree-like tableau of size n. Let j be the integer such that noc is the cell at the intersection of row j and column j + 1. We obtain T by removing the column j + 1, r corresponds to the row j. It should be clear that this operation is revertible. The bijection is illustrated in Figure 11b. Using the previous notations, w(noc) = a x w(T). As a result,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The axial symmetry with respect to the main diagonal of the underlying diagram gives a bijection between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], a top point becomes a left point and conversely. Hence, [g.sub.n](a, b) can be deduced from [f.sub.n](a, b) by the identity [g.sub.n](a, b) = [f.sub.n](b, a). Since [T.sub.n-2](a, b) is a symmetric polynomial, [g.sub.n](a, b) = b(n-2/2) x [T.sub.n-2](a, b).

To prove the conjecture, we miss the (a, b)-analogue of the enumeration of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The main issue is how to link these non-occupied corners with tree-like tableaux of smaller size.

4.3.2 A conjectural x-analogue for symmetric tree-like tableaux

In the case of symmetric tree-like tableaux, top and left are always equal, moreover, there is always a non-root point in the first row and in the first column, therefore we will consider left* (T) = left(T) - 1. It gives a nice x-analogue of the enumeration of symmetric tree-like tableaux. Indeed, Section 2.4 in Aval et al. (2013b) tells us that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(We believe that there is a mistake in Section 2.4 of Aval et al. (2013b), we should take the definition

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

in order to get,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It turns out that in the case of the enumeration of corners in symmetric tree-like tableaux, the x-analogue might be nice as well. As in the non-symmetric case, the x-analogue of the enumeration of occupied corners is equal to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus conjecturing an x-analogue for non-occupied corners and unrestricted corner is equivalent. A computer exploration using Sage Developers (2015), gives us the following expression:

Conjecture 4.14 The x-analogue of the enumeration of non-occupied corners in symmetric tree-like tableaux is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using Sage Developers (2015), we can confirm this x-analogue until n = 7:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In the non-symmetric case, we were only able to prove the coefficients of [x.sup.2]. It also corresponds to the empty corners such that the only point above them is in the first row and only point to their left is in the first column.

5 Conclusion and Remarks

We computed the number of corners in (type B) permutation tableaux, (symmetric) alternative tableaux and (symmetric) tree-like tableaux, by interpreting the number of corners as a statistic on (signed) permutations. Moreover, we gave a bijection between corners in tree-like tableaux and ascending runs of size one in permutations. Finally, we partially proved a conjectural (a,b)-analogue and x-analogue of the enumeration of corners, in tree-like tableaux and symmetric tree-like tableaux respectively.

It is worthy noting that the number of non-occupied corners in tree-like tableaux of size n + 1 occurs in (Sloane et al., 2011, A005990), which enumerates the total positive displacement of all letters in all permutations on [n], i.e,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

the number of double descents in all permutations of [n - 1] and also the sum of the excedances of all permutations of [n]. We say that i is a double descent of a permutation [pi] = [[pi].sub.1][[pi].sub.2] x x x [[pi].sub.n] if [[pi].sub.i] > [[pi].sub.i+1] > [[pi].sub.i+2], with 1 [??] i [??] n - 2 and an excedance if [[pi].sub.i] > i, with 1 [??] i [??] n - 1. Besides, they are also related to coefficients of Gandhi polynomials, see Tuenter (2002). To find the relationship between both of them is also an interesting problem.

Acknowledgements

The authors would like to thank the anonymous referees for their valuable suggestions and comments that have helped a lot to improve the quality and presentation of the paper.

A part of this research was driven by computer exploration using the open-source software Sage Sage Developers (2015) and its algebraic combinatorics features developed by the Sage--Combinat due to Sage-Combinat community (2008).

References

J.-C. Aval, A. Boussicault, and S. Dasse-Hartaut. Dyck tableaux. Theoret. Comput. Sci., 502:195-209, 2013a. doi: 10.1016/j.tcs.2011.11.038. URL http://dx.doi.org/10.1016/j.tcs.2011.11.038.

J.-C. Aval, A. Boussicault, and P. Nadeau. Tree-like tableaux. Electron. J. Combin., 20(4):Paper34, 24pp, 2013b.

J.-C. Aval, A. Boussicault, M. Bouvel, and M. Silimbani. Combinatorics of non-ambiguous trees. Adv. in Appl. Math., 56:78-108, 2014. doi: 10.1016/j.aam.2013.11.004. URL http://dx.doi.org/10.1016/j.aam.2013.11.004.

J.-C. Aval, A. Boussicault, B. Delcroix-Oger, F. Hivert, and P. Laborde-Zubieta. Non-ambiguous trees: new results and generalisation. arXiv preprint arXiv:1511.09455, 2015.

A. Burstein. On some properties of permutation tableaux. Ann. Comb., 11(3-4):355-368, 2007. doi: 10.1007/s00026-007-0323-0. URL http://dx.doi.org/10.1007/s00026-007-0323-0.

S. Cho and K. Park. Permutation statistics and weak Bruhat order in permutation tableaux of type B. European J. Combin., 47:23-39, 2015. doi: 10.1016/j.ejc.2015.01.006. URL http://dx.doi.org/10.1016/j.ejc.2015.01.0 06.

S. Corteel and J. S. Kim. Combinatorics on permutation tableaux of type A and type B. European J. Combin., 32(4):563-579, 2011. doi: 10.1016/j.ejc.2011.01.003. URL http://dx.doi.org/101016/j.ejc.2011.01.003.

S. Corteel and P. Nadeau. Bijections for permutation tableaux. European J. Combin., 30(1):295-310, 2009. doi: 10.1016/j.ejc.2007.12.007. URL http://dx.doi.org/10.1016/j.ejc.2007.12.007.

S. Corteel and L. K. Williams. Tableaux combinatorics for the asymmetric exclusion process. Adv. in Appl. Math., 39(3):293-310, 2007. doi: 10.1016/j.aam.2006.08.002. URL http://dx.doi.org/10.1016/j.aam.2006.08.002.

D. Foata and M.-P. Schutzenberger. Theorie geometrique des polynomes euleriens. Lecture Notes in Mathematics, Vol. 138. Springer-Verlag, Berlin-New York, 1970.

A. L. Gao, E. X. Gao, and B. Y. Sun. Zubieta's conjecture on the enumeration of corners in treelike tableaux. arXiv preprint arXiv:1511.05434, 2015. URL http://arxiv.org/abs/1511.05434v1

I. M. Gessel. Generating functions and enumeration of sequences. PhD thesis, Massachusetts Institute of Technology, 1977.

P. Hitczenko and A. Lohss. Corners in tree-like tableaux. arXiv preprint arXiv:1511.04989, 2015. URL http://arxiv.org/abs/1511.0498 9v1

P. Laborde-Zubieta. Occupied corners in tree-like tableaux. Sem. Lothar. Combin., 74:Art. B74b, 14pp, 2015.

T. Lam and L. Williams. Total positivity for cominuscule Grassmannians. New York J. Math., 14:53-99, 2008. URL http://nyjm.albany.edu:8000/j/2008/14_53.html.

P. Nadeau. The structure of alternative tableaux. J. Combin. Theory Ser. A, 118(5):1638-1660, 2011. ISSN 0097-3165. doi: 10.1016/j.jcta.2011.01.012. URL http://dx.doi.org/10.1016/j.jcta.2011.01.012.

A. Postnikov. Total positivity, grassmannians, and networks. arXiv preprint math/0609764, 2006. URL http://arxiv.org/abs/math/060 9764

Sage-Combinat community. Sage-combinat: enhancing sage as a toolbox for computer exploration in algebraic combinatorics, 2008. URL http://combinat.sagemath.org.

Sage Developers. Sagemath mathematics software (Version 6.10.beta1), 2015. URL http://www.sagemath.org.

N. J. Sloane et al. The on-line encyclopedia of integer sequences, 2011. URL http://oeis.org.

R. P. Stanley. Enumerative combinatorics. Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 2012.

E. Steingrimsson and L. K. Williams. Permutation tableaux and permutation patterns. J. Combin. Theory Ser. A, 114(2):211-234, 2007. doi: 10.1016/j.jcta.2006.04.001. URL http://dx.doi.org/10.1016/j.jcta.2006.04.001.

H. J. H. Tuenter. Walking into an absolute sum. Fibonacci Quart., 40(2):175-180, 2002.

X. G. Viennot. Alternative tableaux, permutations and partially asymmetric exclusion process. In I. N. I. for Mathematical Science, editor, Worshop "Statistical Mechanics and Quantum-Field Theory Methods in Combinatorial Enumeration", Isaac Newton Institiute for Mathematical Science, pages http://www.newton.ac.uk/webseminars/pg+ws/2008/csm/csmw04/0423/viennot/, Cambridge, United Kingdom, Apr. 2008. URL https://hal.archives-ouvertes.fr/hal-00385528.

Y. Zhuang. Counting permutations by runs. J. Combin. Theory Ser. A, 142:147-176, 2016. doi: 10.1016/j.jcta.2016.04.002. URL http://dx.doi.org/10.1016/j.jcta.2016.04.002.

Alice L.L. Gao (1)

Emily X.L. Gao (1)

Patxi Laborde-Zubieta (2)

Brian Y. Sun (3[dagger])

(1) Center for Combinatorics, LPMC-TJKLC Nankai University, Tianjin 300071, P. R. China

(2) LaBRI - University of Bordeaux, 351, cours de la Libration F-33405 Talence cedex, France

(3) College of Mathematics and System Science, Xinjiang University, Urumqi, Xinjiang 830046, P. R. China

received 12th Mar. 2016, revised 2nd Oct. 2016, accepted 9th Nov. 2016.

(*) This work was partially supported by the 973 Project, the PCSIRT Project of the Ministry of Education and the National Science Foundation of China and the Scientific Research Program of the Higher Education Institution of Xinjiang Uygur Autonomous Region (No. XJEDU2016S032)

([dagger]) Corresponding author. Email: brianys1984@126.com.
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Gao, Alice L.L.; Gao, Emily X.L.; Laborde-Zubieta, Patxi; Sun, Brian Y.
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Date:Nov 1, 2016
Words:11184
Previous Article:Most complex regular ideal languages.
Next Article:Matchings of quadratic size extend to long cycles in hypercubes.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters