Permutation Tableaux and the Dashed Permutation Pattern 32–1

William Y.C. Chen^{1} and Lewis H. Liu^{2}

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

1chen@nankai.edu.cn, ^{2}lewis@cfc.nankai.edu.cn

Abstract

We give a solution to a problem posed by Corteel and Nadeau concerning permutation tableaux of length n and the number of occurrences of the dashed pattern 32–1 in permutations on [n]. We introduce the inversion number of a permutation tableau. For a permutation tableau T and the permutation π obtained from T by the bijection of Corteel and Nadeau, we show that the inversion number of T equals the number of occurrences of the dashed pattern 32–1 in the reverse complement of π. We also show that permutation tableaux without inversions coincide with L-Bell tableaux introduced by Corteel and Nadeau.

Keywords: Permutation tableaux, dashed permutation patten AMS Classification: 05A05, 05A19

1 Introduction

Permutation tableaux were introduced by Steingrímsson and Williams [13] in the study of totally positive Grassmannian cells [11, 12, 16]. They are closely related to the PASEP (partially asymmetric exclusion process) model in statistical physics [5, 8, 9, 10, 14]. Permutation tableaux are also in one-to-one correspondence with alternative tableaux introduced by Viennot [15].

A permutation tableau is defined by a Ferrers diagram possibly with empty rows such that the cells are filled with 0’s and 1’s subject to the following conditions:

(1) Each column contains at least one 1.

(2) There does not exist a 0 with a 1 above (in the same column) and a 1 to the left (in the same row).

The length of a permutation tableau is defined as the number of rows plus the number of columns. A 0 in a permutation tableau is said to be restricted if there is a 1 above. Among the restricted 0’s in a row, the rightmost one plays a special role, which is called a rightmost restricted 0. A row is said to be unrestricted if it does not contain any restricted 0. A permutation tableau T of length n is labeled by the elements in [n] = {1, 2, …, n} in increasing order from the top right corner to the bottom left corner. The set [n] is referred to as the label set of T. We use (i, j) to denote the cell with row label i and column label j.

For example, Figure 1.1 exhibits a permutation tableau of length 11 which contains an empty row. There are two rightmost restricted 0’s at cells (5,9) and (8,10), and there are four unrestricted rows labeled by 1, 2, 7, and 11.

00010 11011 001 01 01 ^{1}^{2}^{3}^{4}^{5}^{6}^{7}^{8}^{9}^{10}^{11} Figure 1.1: Permutation tableau

It is known that the number of permutation tableaux of length n is n!. There are several bijections between permutation tableaux and permutations, see Corteel and Nadeau [7], Steingrímsson and Williams [13]. The second bijection in [13] connects the number of 0’s in a permutation tableau to the total number of occurrences of the dashed patterns 31–2, 21–3 and 3–21. This bijection also yields a relationship between the number of 1’s and the number of occurrences of the dashed pattern 2–31 in a permutation, as well as a relationship between the number of cells in the Ferrers diagram and the number of occurrences of dashed patterns 1–32 and 32–1 in a permutation. In answer to a question of Steingrímsson and Williams [13], Burstein [2] found a classification of zeros in permutation tableaux and its connection to the total number of occurrences of dashed patterns 31–2 and 21–3 , and the number of occurrences of the dashed pattern 3–21.

On the other hand, the second bijection of Corteel and Nadeau [7] implies that the number of non topmost 1’s in a permutation tableau equals the number of occurrences of the dashed pattern 31–2 in the corresponding permutation. They raised the problem of finding a statistic on permutation tableaux that has the same distribution as the number of occurrences of the dashed pattern 32-1 in permutations.

Let us recall the definition of dashed permutation patterns introduced by Babson and Steingrímsson [1]. A dashed pattern is a permutation of [k] for k ≤ n containing dashes indicating that the entries in a permutation of [n] need not occur consecutively. In this notation, a permutation pattern σ = σ_{1}σ_{2} … σ_{k} in the usual sense may be rewritten as σ = σ_{1}–σ_{2}–…–σ_{k}. For example, we say that a permutation π on [n] avoids a dashed pattern 32–1 if there are no subscripts i < k such that π_{i−1} > π_{i} > π_{k}. Claesson and Mansour [4] found explicit formulas for the number of permutations containing exactly i occurrences of a dashed pattern σ of length 3 for i = 1, 2, 3.

The main idea of this paper is to introduce the inversion number of a permutation tableau (see Definition 2.2). We show that the inversion number of a permutation tableau of length n has the same distribution as the number of occurrences of dashed pattern 32-1 in a permutation of [n]. To be more specific, for a permutation tableau T and the permutation π obtained from T by the first bijection of Corteel and Nadeau, we prove that the inversion number of T equals the number of occurrences of the dashed pattern 32–1 in the reverse complement of π. This gives a solution to the problem proposed Corteel and Nadeau [7].

This paper is ended with a connection between permutation tableaux without inversions and L-Bell tableaux introduced by Corteel and Nadeau in [7]. We show that a permutation tableau has no inversions if and only if it is an L-Bell tableau.

2 The inversion number of a permutation tableau

In this section, we define the inversion number of a permutation tableau (see Definition 2.2). We show that the inversion number of permutation tableau T equals the number of occurrences of the dashed pattern 32–1 in the reverse complement of the permutation π corresponding to T under the bijection ξ of Corteel and Nadeau.

Let π = π_{1}π_{2} … π_{n}. Denote by f_{σ}(π) the number of occurrences of dashed pattern σ in π. The reverse complement of π is denoted by

π̄ = (n + 1 − π_{n}, … n + 1 − π_{2}, n + 1 − π_{1}),

here a permutation is also written in the form of a vector.

The main result of this paper is stated as follows. Throughout this paper ξ denotes the bijection of Corteel and Nadeau. For completeness, a brief description of ξ will be given later.

Theorem 2.1. Let T be a permutation tableau. Let inv(T) be the number of inversions of T. Then we have

inv(T) = f_{32–1}(π̄).  (2.1)

Since an occurrence of the dashed pattern 32–1 in π̄ corresponds to an occurrence of the dashed pattern 3-21 in π, relation (2.1) can be restated as

inv(T) = f_{3–21}(π).  (2.2)

Corteel and Nadeau [7] have shown that a permutation tableau is uniquely determined by the topmost 1’s and the rightmost restricted 0’s. For a permutation tableau T, the alternative representation of T is defined by Corteel and Kim [6] as the diagram obtained from T by replacing the topmost 1’s with ↑’s, replacing the rightmost restricted 0’s with ←’s and leaving the remaining cells blank. In this paper, we use black dots and white dots to represent the topmost 1’s and rightmost restricted 0’s in an alternative representation, as illustrated in Figure 2.1.

Note that for each dot in an alternative representation of a permutation tableau, there is an unique path, called an alternating path, to a black dot on an unrestricted row. More precisely, an alternating paths is defined as follows. For a white dot we can find a black dot at the top as the next dot. For a black dot which is not on an unrestricted row, there is a white dot to the left as the next dot. Figure 2.1 shows two alternating paths.

For an alternative representation of a permutation tableau, we may use the row and column labels to represent an alternating path. It is evident that a black dot is determined by a column label and a white dot is determined by a row label. Hence an alternating path can be represented by an alternating sequence of row and column labels ending with a column label of a black dot on an unrestricted row.

For example, for the black dot in cell (5, 6), the alternating path can be expressed as (6, 5, 12). For the white dot in cell (7, 10), the corresponding alternating path takes the form (7, 10, 4, 11).

100000 110100 001100 00111 0001 1 ^{1}^{2}^{3}^{4}^{5}^{6}^{7}^{8}^{9}^{10}^{11}^{12}  • ∘ ∘ • ∘ • ∘ ∘ • • • ↑←  ↑ ← ↑  ^{1}^{2}^{3}^{4}^{5}^{6}^{7}^{8}^{9}^{10}^{11}^{12} Figure 2.1: Alternative representation of a permutation tableau

For two alternating paths P and Q of T, we say that P contains Q if Q is a segment of P. Assume that P and Q does not contain each other. We proceed to define the order relation on P and Q. Clearly, if P and Q intersect at some point, then they will share the same ending segment after this point. If this is the case, we will remove the common dots of P and Q, and then consider the resulting alternating paths P′ and Q′. We say that P > Q (P < Q) if one of the following four conditions holds:

(1) The paths P and Q do not intersect, and the ending dot of P is below (above) the ending dot of Q.

(2) The paths P and Q do not intersect, and the ending dot of P is to the right (to the left) of the ending dot of Q.

(3) The paths P and Q intersect, and the ending dot of P′ is below (above) the ending dot of Q′.

(4) The paths P and Q intersect, and the ending point of P′ is to the right (to the left) of the ending dot of Q′.

For any two alternating paths P and Q that do not contain each other, it can be seen that either P > Q or P < Q holds. Using this order, we can define the inversion number of an alternative representation T of a permutation tableau, which is also considered as the inversion number of the original permutation tableau.

Definition 2.2. Suppose that j is a column label of T and P_{j} is the alternating path starting with the black dot with column label j. Let k be a label of T with j < k such that k is not a label of a dot on P_{j}. In other words, P_{k} is not contained in P_{j}, where P_{k} denotes the alternating path with the dot with label k. We say that the pair of labels (j, k) is an inversion of T if P_{j} > P_{k}. The total number of inversions of T is denoted by inv(T).

Analogous to the inversion code of a permutation, for a column label j we define w_{j}(T) as the number of inversions of T that are of the form (j, k). Hence

inv(T) = ∑_{j∈C(T)} w_{j}(T),

where C(T) is the set of column labels of T.

For example, Figure 2.2 gives two permutation tableaux in the form of their alternative representations. For the alternative representation T on the left, we have C(T) = {2, 3}. Since P_{2} > P_{3}, we see that w_{2}(T) = 1, w_{3}(T) = 0, and inv(T) = 1. For the alternative representation T′ on the right, we have C(T′) = {3, 5}. Since P_{3} > P_{4} and P_{3} > P_{5}, we find w_{3}(T′) = 2, w_{5}(T′) = 0, and inv(T′) = 2.

• • 1 2 3  • ∘ • ↑  12 3 4 5 Figure 3.2: Two examples

We now proceed to present a proof of Theorem 2.1. For completeness, we give a brief description of the bijection ξ of Corteel and Nadeau from permutation tableaux to permutations.

Assume that T is the alternative representation of a permutation tableau. Let ξ(T) = π = π_{1}π_{2} … π_{n}. The bijection is a recursive procedure to construct π. Starting with the sequence of the labels of free rows in increasing order. Then successively insert the column labels of T. Let j be the maximum column label to be inserted. If the cell (i, j) is filled with a black dot, then insert j immediately to the left of i. If column j contains white dots in rows i_{1}, i_{2}, …, i_{k}, then insert i_{1}, i_{2}, …, i_{k} in increasing order to the left of j. Repeating this process, we obtain a permutation π.

For the sake of presentation, we give three lemmas that will be needed in the proof of theorem 2.1. The first lemma was established by Corteel and Nadeau [7].

Lemma 2.3. Let π = ξ(T). Then π_{i} > π_{i+1} if and only π_{i} is a column label of T.

The next lemma states that the labels representing an alternating path of T form a subsequence of ξ(T).

Lemma 2.4. Let P = p_{1}p_{2} ⋯ p_{r} be an alternating path of T starting with a dot labeled by p_{1} and ending with a black dot labeled by p_{r}. Then p_{1}p_{2} ⋯ p_{r} is a subsequence of ξ(T).

Proof. Assume that the alternating path P ends with a black dot at cell (i, p_{r}), where i is an unrestricted row label. Since the ending dot represents a topmost 1, by the construction of ξ, we see that p_{r} is inserted to the left of i. Note that the cell (p_{r−1}, p_{r}) is filled with a white dot representing a rightmost restricted 0, so p_{r−2} is inserted to the left of p_{r−1}. Since the path P is alternating with respect to black and white dots, we deduce that p_{r−3}, ⋯, p_{2}, p_{1} are inserted one by one such that p_{i} is inserted to the left of p_{i+1} for i = 1, 2, …, r − 1. It follows that p_{1}p_{2} ⋯ p_{r} is a subsequence of the permutation ξ(T). This completes the proof.

Given two labels i and j of T, the following lemma shows that the relative order of i and j in ξ(T) can be determined by the order of the alternating paths starting with the two dots labeled by i and j.

Lemma 2.5. Let P_{i} and P_{j} be two alternating paths of T starting with two dots labeled by i and j respectively. Then i is to the left of j in ξ(T) if and only if P_{i} < P_{j} or P_{j} is contained in P_{i}.

Proof. If P_{j} is contained in P_{i}, by Lemma 2.4 we see that i is to the left of j. Otherwise, let P_{i} = i_{1}i_{2} … i_{s} and P_{j} = j_{1}j_{2} … j_{t}, where i = i_{1} and j = j_{1} respectively. Assume that P_{i} and P_{j} do not intersect. We wish to prove that j_{1} is to the right of i_{s} in ξ(T), since i_{1} is to the left of i_{s} by Lemma 2.4.

If P_{i} and P_{j} intersect at some dot, let P′_{i} and P′_{j} be the alternating paths by removing the common dots of P_{i} and P_{j}. Suppose that the ending dot of P′_{i} is labeled by i_{s−m}. Then the ending dot of P′_{j} is labeled by j_{t−m}. In this case, we aim to show that j_{1} is to the right of i_{s−m} in ξ(T), since i_{1} is to the left of i_{s−m} by Lemma 2.4.

Consider the following four cases corresponding to the order on P_{i} and P_{j}. In the first two cases, P_{i} and P_{j} do not intersect, that is, i_{m} ≠ j_{r} for any m = 1, 2, …, s and r = 1, 2, …, t. Suppose that the ending black dots of P_{i} and P_{j} are in cells (r_{P_{i}}, i_{s}) and (r_{P_{j}}, j_{t}) respectively, where r_{P_{i}} and r_{P_{j}} are the labels of unrestricted rows. Case 1. r_{P_{i}} < r_{P_{j}}. First of all, r_{P_{i}} is to the left of r_{P_{j}} in ξ(T). Since both cells (r_{P_{i}}, i_{s}) and (r_{P_{j}}, j_{t}) are filled with black dots, the element i_{s} is inserted immediately to the left of r_{P_{i}}, while j_{t} is inserted immediately to the left of r_{P_{j}}. This implies that j_{t} is to the right of r_{P_{i}} in ξ(T). Hence j_{t} is to the right of i_{s}.

Since the path P_{j} alternates with black and white dots, the cell (j_{t}, j_{t−1}) is filled with a white dot. Thus j_{t−1} is inserted to the left of j_{t} but to the right of r_{P}, that is, j_{t−1} is to the right of i_{s}. Repeating the above procedure, we reach the conclusion that the label j_{r} is to the right of i_{s} for r = t, t − 1, …, 1. In particular, j_{1} is to the right of i_{s}, so that j_{1} is to the right of i_{1}. Case 2. r_{P_{i}} = r_{P_{j}} and j_{t} < i_{s}. In the implementation of the algorithm ξ, i_{s} is inserted immediately to the left of r_{P_{i}} and then j_{t} is inserted immediately to the left of r_{P_{j}} = r_{P_{i}}. Hence j_{t} is to the right of i_{s}. Inspecting the relative positions of i_{s} and j_{r} for r < t like we have done in Case 1, we infer that j_{r} is to the right of i_{s} for r = t, t − 1, …, 1. So we arrive at the assertion that j_{1} is to the right of i_{1}. Case 3. The ending point of P′_{j} is below the ending point of P′_{i}, that is, j_{t−m} > i_{s−m}. In this case, both cells (i_{s−m}, i_{s−m+1}) and (j_{t−m}, j_{t−m+1}) are filled with white dots. To construct π from T according to ξ, both elements i_{s−m} and j_{t−m} are inserted to the left of the element i_{s−m+1} = j_{t−m+1} in increasing order. Hence i_{t−m} is to the left of j_{t−m}. Considering the relative positions of i_{s−m} and j_{r} for r < t − m as in Case 1, we deduce that j_{r} is to the right of i_{s−m} for 1 ≤ r < t − m. Therefore j_{1} is to the right of i_{s−m}, and hence to the right of i_{1}. Case 4. The ending point of P′_{j} is to the right of the ending point of P′_{i}, that is, j_{t−m} < i_{s−m}. Observe that the element i_{s−m} is inserted immediately to the left of i_{s−m+1}. Then the element j_{t−m} is inserted immediately to the left of j_{t−m+1} = i_{s−m+1}. It follows that j_{t−m} is to the right of i_{s−m}. Using the same argument as in Case 1 for the elements i_{s−m} and j_{r} with r < t − m, we conclude that j_{r} is to the right of i_{s−m} for 1 ≤ r < t − m. Consequently, j_{1} is to the right of i_{s−m}, and hence to the right of i_{1}.

In summary, we see that if P_{i} < P_{j}, then i is to the left of j in ξ(T). It remains to show that if i is to the left of j in ξ(T), then we have P_{i} < P_{j} or P_{j} is contained in P_{i}. The proof is essentially the reverse procedure of the above argument, and is omitted. Proof of Theorem 2.1. Let ξ(T) = π = π_{1}π_{2} … π_{n}. Combining Lemma 2.3 and Lemma 2.5, we find that the subsequence π_{i}π_{j}π_{j+1} of π is an occurrence of the dashed pattern 3–21 if and only if (π_{j}, π_{i}) is an inversion of T. It follows that

inv(T) = f_{3–21}(π),

which is equivalent to the statement of the theorem.

Figure 3.4 gives a permutation tableau T of length 10 and its alternative representation. For this example, we see that C(T) = {5, 6, 7, 9}, w_{5}(T) = 4, w_{6}(T) = 3, w_{8}(T) = 1 and w_{9}(T) = 0. Hence we have inv(T) = 8. On the other hand,

π = ξ(T) = (9, 2, 7, 8, 1, 6, 5, 3, 4).

This gives π̄ = (6, 5, 7, 4, 9, 2, 3, 8, 1). It can be checked that the number of occurrences of the dashed pattern 32–1 in π̄ equals 8.

10011 10110 0011 0011 ^{1}^{2}^{3}^{4}^{5}^{6}^{7}  ^{8}^{8}^{9}  • • ∘ ∘ • • ↑  ^{1}^{2}^{3}^{4}^{5}^{6}^{7}^{8}^{9} Figure 3.2: A permutation tableau and its alternative representation

3 Connection with L-Bell tableaux

In this section, we show that a permutation tableau has no inversions if and only if it is an L-Bell tableau as introduced by Corteel and Nadeau [7]. Recall that an L-Bell tableau is a permutation tableau such that any topmost 1 is also a left-most 1.

It has been shown by Claesson [3] that the number of permutations of [n] avoiding the dashed pattern 32–1 is given by the n-th Bell number B_{n}. Together with Theorem 2.1 we are led to the following correspondence.

Theorem 3.1. The number of permutation tableaux T of length n such that inv(T) = 0 equals B_{n}.

On the other hand, the following relation was proved by Corteel and Nadeau [7].

Theorem 3.2. The number of L-Bell permutation tableaux of length n equals B_{n}

By the definition of an inversion of a permutation tableau, it is straightforward to check that an L-Bell tableau has no inversion. Combining Theorem 3.2 and Theorem 3.3, we obtain the following connection.

Theorem 3.3. Let T be a permutation tableau. Then inv(T) = 0 if and only if T is an L-Bell tableau.

Here we give a direct reasoning of the above theorem. Let T be an alternative representation of a permutation tableau without inversions. It can be seen that the permutation tableau corresponding to T is an L-Bell tableau if and only T satisfies the following conditions:

(1) Each row contains at most one black dot.

(2) There is no empty cell that has a black dot above and a black dot immediately to the right.

We wish to prove that if inv(T) = 0, then T satisfies the above conditions.

Assume that there is a row containing two black dots, say, at cells (i, j) and (i, k) with j < k. Then (j, k) is an inversion of T, a contradiction. Thus condition (1) holds.

For condition (2), assume to the contrary that there exists an empty cell (i, j) such that there is a black dot above and a black dot immediately to the right. Without loss of generality, we may assume that i is the minimal row label of an empty cell subject to the above assumption. Now we choose j to be the maximal column label. Assume that the black dot in row i and the black dot in column j appear at cells (i, k) and (t, j) respectively. Note that we have t < i. Since j < k and inv(T) = 0, we must have P_{j} < P_{k}. This implies that the unrestricted row containing the ending black dot of P_{j} must be above row t. Assume that this ending black dot is in column m. Then there exists a white dot in row t. Suppose that it occurs at cell (t, s). Clearly, we have s ≤ m. Moreover, we see that no cell (x, y) for x > t, y > s can be filled with a white dot. On the other hand, no cell (x, y) for x < t, j < y < s can be filled with a black dot.

By walking backwards from the ending black dot along the path P_{j}, we can find a black dot in column s on the alternating path P_{j} which is also on the alternating path P_{k}. So we deduce that the next white dot on P_{j} is below the next white dot on P_{k}, that is, P_{j} > P_{k}. But this implies that (j, k) is an inversion of T, again a contradiction. Hence the proof is complete.

Acknowledgments. This work was supported by the 973 Project, the PCSIRT Project of the Ministry of Education, and the National Science Foundation of China.

References

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

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

[3] A. Claesson, Generalized pattern avoidance, European J. Combin. 22 (2001) 961–971.

[4] A. Claesson and T. Mansour, Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations, Adv. Appl. Math. 29 (2002) 293–310.

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

[6] S. Corteel and J. S. Kim, Combinatorics on permutation tableaux of type A and type B, arXiv:1006.3812.

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

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

[9] S. Corteel and L. Williams, Tableaux combinatorics for the asymmetric exclusion process II, arXiv:0810.2916.

[10] S. Corteel and L. Williams, A Markov chain on permutations which projects to the PASEP, Int. Math. Res. Not. (2007) Art. ID rnm055.

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

[12] A. Postnikov, Total positivity, Grassmannians, and networks, arXiv:math/0609764.

[13] E. Steingrímsson and L. Williams, Permutation tableaux and permutation patterns, J. Combin. Theory, Ser. A 114 (2007) 211-234.

[14] X. Viennot, Catalan tableaux, permutation tableaux and the asymmetric exclusion process, FPSAC 2007, Tianjin, China.

[15] X. Viennot, Alternative tableaux, permutations and partially asymmetric exclusion process, Isaac Newton institute, April 2007.

[16] L. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005) 319–342.