A COMBINATORIAL PROOF OF A RESULT OF HETYEI AND REINER ON FOATA-STREHL TYPE PERMUTATION TREES

MIKLÓS BÓNA

Abstract. We give a combinatorial proof of the known [4] result that there are exactly n!/3 permutations of length n in the minmax tree representation of which the ith node is a leaf. We also prove the new result that the number of n-permutations in which this node has one child is n!/3 as well, implying that the same holds for those in which this node has two children.

1. Background and definitions

In [4] the authors gave a new proof for a theorem of Purtill [5] by introducing a new ℤ_{2}^{n−1}-action on the symmetric group S_{n}. This had the flavor of a ℤ_{2}^{n}-action defined and succesfully used by Foata and Strehl [2] [3], but it proved to have a more symmetric structure. In order to define their new group action, Hetyei and Reiner studied a binary tree representation of the permutation p = (p_{1}, p_{2}, ⋯, p_{n}) called minimum-maximum trees or, in the rest of this paper, minmax trees. These are defined as follows.

Definition 1. Let p be a permutation of length n and let p = u m v where m is the leftmost of the minimum and maximum letters of p, u is the subword preceding m and v is the subword following m. The minmax tree T_{p}^{m} has m as its root. The right subtree of T_{p}^{m} is obtained by applying the definition recursively to v. Similarly, the left subtree of T_{p}^{m} is obtained by applying the definition recursively to u.

So every node of T_{p}^{m} which is not a leaf is either a minimum node or a maximum node. Useful information can be read off these trees, for example, it can be shown that p is an André-permutation if and only if all these nodes are minimum nodes.

The minmax tree of the permutation p = 3 6 7 1 5 2 10 4 9 8 is shown on Figure 1.

This paper was written while the author was a one-term visitor at Mathematical Sciences Research Institute in Spring 1997. This visit was supported by an MIT Applied Mathematics Fellowship.

[figure: 3; 1; 2; 5; 6; 7; 10; 4; 9; 8; Figure 1: T_{p}^{m} for p = 3 6 7 1 5 2 10 4 9 8.]

If a = a_{1}, a_{2}, ⋯, a_{k} is a subword of the n-permutation p, then the pattern of a is the unique k-permutation for which the pairwise comparisons between the ith and jth entries are the same as those for a. For example, the pattern of the subword 3 6 7 1 is 2 3 4 1, while the paattern of the subword 4 9 8 is 1 3 2.

The group action defined by Hetyei and Reiner is as follows: Let 1 ≤ i ≤ n. Then ψ_{i}(T_{p}^{m}) is obtained from T_{p}^{m} by changing only the subtree whose root is the entry p_{i}. If p_{i} was a minimum node, then we take the maximal entry among all entries of this subtree, put it into the place of p_{i} (so to the root of this subtree), and write the other entries of the subtree to the nodes of the subtree so that their pattern is the same as it was before the operation. Similarly, if p_{i} was a maximum node, then we put the minimal among the entries of its subtree to the place of p_{i}, then we write the other entries in the subtree to the nodes so that their pattern is unchanged.

Figure 2 shows the image of our previuos example p, under the operator ψ_{7}.

[figure: 3; 1; 2; 5; 6; 7; 4; 8; 10; 9; Figure 2: ψ_{7}(T_{p}^{m}) for p = 3 6 7 1 5 2 10 4 9 8.]

It is clear that ψ_{i}(T_{p}^{m}) = T_{p}^{m} if and only if p_{i} is a leaf in T_{p}^{m}. Hetyei and Reiner proved that any for any i ≤ n − 2, p_{i} is a leaf in exactly n!/3 permutations of length n (in the rest of this paper, n-permutations), thus ψ_{i} fixes n!/3 n-permutations. This is a little surprising: it is not even intuitively obvius why this number should be independent from i, and indeed, in the original group action of Foata and Strehl, it was not. Hetyei and Reiner used exponential generating functions and partial differential equations to get this result, however they noted that such a simple formula would deserve a combinatorial proof.

Present paper provides such a proof. We also prove the new result that the number of permutations in which p_{i} has 1 child as well as the number of n-permutations in which p_{i} has two children is n!/3, too, whenever 2 ≤ i ≤ n − 2. Thus this group action has even more symmetries, which supports the inventors’ claim that it could be used in analysing random permutations.

2. The Proof of the Theorem

First we make some simple observations which will be useful later. For any i ≤ n−1, either p_{i} is an ancestor of p_{i+1}, or p_{i+1} is an ancestor of p_{i}, for otherwise these two entries would have a common ancestor, which would have an index between i and i + 1, a contradiction. So in particular, no permutation’s minmax tree can have both p_{i} and p_{i+1} as leaves. This allows the following definition.

Definition 2. Let 1 ≤ i ≤ n − 2. Then the ith local extremum of a permutation p is the entry which is closest to the root of the minmax tree of p among p_{i}, p_{i+1} and p_{i+2}. This entry will be denoted e_{i}.

Being closest to the root means having the shortest path to the root in this definition. Note that e_{i} always exists: either p_{i+1} is an ancestor of both of its neighbors and e_{i} = p_{i+1}, or only one of its neighbors, say p_{i} is an ancestor of p_{i+1} and p_{i+2} is a descendant of p_{i+1}, implying e_{i} = p_{i}, or both of its neighbors are ancestors of p_{i+1}, in which case, by the tree-property, one must be an ancestor of the other.

Lemma 1. The number of n-permutations whose minmax tree contains p_{1} as a leaf is n!/3.

Proof. By symmetry, we can suppose that the entry 1 of our permutation precedes the entry n. Indeed, the complement of p (the permutation whose ith entry is n + 1 − p_{i}) has an isomorphic minmax tree to T_{p}^{m}.

First we consider the case when the entry 1 is among the first three elements, so in particular, e_{1} = 1. This gives rise to three subcases:

• If p_{1} = 1, then p_{1} is the root of the minmax tree.

• If p_{2} = 1, then p_{2} is the root, and p_{1} is a leaf.

• If p_{3} = 1, then p_{3} is the root, its left subtree has p_{1} and p_{2} as nodes, and among these, by definition, p_{2} is a leaf, and p_{1} is not.

Clearly, these subcases are equally likely to occur, so each of them occurs with probability 1/3.

Now suppose that the entry of the permutation is not among the first 3 elements. This entry is the root of the minmax tree of the permutation, and its left subtree has at least three nodes. Let these nodes be b_{1} < b_{2} < ⋯ < b_{k}. Repeat the previous argument for this subtree, with b_{1} playing the role of 1 and get that whenever b_{1} is among the leftmost three elements of the permutation, p_{1} is a leaf with probability 1/3.

Iterate this algorithm as long as it is necessary. It will eventually stop because we either get a left subtree of size three, or a subtree whose minimal entry is among the first three ones. In every subcase, p_{1} is a leaf with probability 1/3, completing the proof of the lemma.

We will use the same methods to prove the general theorem.

Theorem 1. The number of n-permutations containing p_{i} as a leaf is n!/3, when 1 ≤ i ≤ n − 2. If i = n − 1, then p_{i} is never a leaf, whereas if i = n, then p_{i} is always a leaf.

Proof. Clearly, p_{n} is always a leaf because it cannot be the leftmost in any comparison, thus it cannot have descendants. Similarly, p_{n} is always the child of p_{n−1}, thus p_{n−1} is never a leaf.

Now let 1 ≤ i ≤ n − 2. Again, we can suppose that 1 precedes n in our permutations. First we consider the case when 1 ∈ {p_{i}, p_{i+1}, p_{i+2}}.

• If p_{i} = 1, then p_{i} is the root of the minmax tree.

• If p_{i+1} = 1, then p_{i+1} is the root, so p_{i} is the rightmost element of its left subtree, and as such, it is necessarily a leaf.

• If p_{i+2} = 1, then p_{i+2} is the root, p_{i} is the next-to-last element of the root’s left subtree, and as such, it is always an internal node (having the leaf p_{i+1} for its only child).

Again each of these subcases occurs with probability 1/3.

If 1 ∉ {p_{i}, p_{i+1}, p_{i+2}}, then we can proceed as we did in proof of Lemma 1: look for the entry 1 of the permutation, then only consider the subtree which contains the positions i, i + 1 and i + 2. If 1 was not in any of these positions, then all the three of them are in the same subtree. Iterating this algorithm we eventually reach a subtree where we can apply the above method. The structure of the other subtrees do not influence whether p_{i} is a leaf or not, so p_{i} is a leaf with probability 1/3.

Corollary 1. Let n ≥ 4 and let d_{i,j} be the number of n-permutations whose entry p_{i} has exactly j children. Then d_{i,j} = n!/3 for 2 ≤ i ≤ n − 2 and j ∈ {0, 1, 2}.

Proof. For j = 0, this is just the statement of the Theorem. For j = 2, note that a node p_{i+1} has two children if and only if it is the local extremum e_{i}, and this happens exactly in the second subcase of the proof of the theorem, thus its probability is 1/3. Similarly, for j = 1, p_{i+1} must be the last element of the left subtree of the local extremum e_{i}, thus e_{i} = p_{i+2} must hold, which is just the third subcase.

As p_{1} cannot have two children, and p_{n−1} cannot be a leaf, we also have d_{1,1} = 2n!/3 and d_{n−1,1} = 2n!/3. This latter is true since p_{n−1} has two children if and only if p_{n−2} is a leaf.

We note that there exists a natural bijection between the set of minmax trees and that of min1-min2 trees (in these trees the root is the leftmost of the minimal and the second minimal element) and thus our results hold for the min1-min2 trees as well.

Acknowledgement

I am grateful to Gábor Hetyei who introduced me into this subject.

References

[1] D. Foata and M.P. Schützenberger, Nombres d’Euler et permutations alternantes. In: J.N. Srivastava et al., A Survey of Combinatorial Theory, Amsterdam, North–Holland, 1973 (pp. 173–187).

[2] D. Foata and V. Strehl, Rearrangements of the Symmetric Group and Enumerative Properties of the Tangent and Secant Numbers Math. Z. 137 (1974), 257–264.

[3] D. Foata and V. Strehl, Euler numbers and variations of permutations. In: Colloquio Internazionale sulle Teorie Combinatorie 1973, Tome I (Atti Dei Convegni Lincei 17, 119–131), Accademia Nazionale dei Lincei 1976.

[4] G. Hetyei, E. Reiner, Permutation Trees and Variation Statistics, In: Proceedings of the 9th Conference on Formal Power Series and Algebraic Combinatorics (Vienna, 1997), to appear.

[5] M. Purtill, André permutations, lexicographic shellability, and the cd–index of a convex polytope, Trans. Amer. Math. Soc. 338 1 (1993), 77–104.

Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139