Permutation Trees and Variation Statistics

Gábor Hetyei^{∗}and Ethan Reiner^{†}^{‡} LaCIM, Départment de mathématiques Université du Québec à Montréal C.P. 8888, succ. Centre-Ville Montréal (Québec) CANADA H3C 3P8

Submitted to the European Journal of Combinatorics

Abstract In this paper we exploit binary tree representations of permutations to give a combinatorial

proof of Purtill’s result [?] that

∑_{δ∈A_{n}} v_{cd}(δ)| \begin{matrix}c=a+b \\ d=ab+ba \end{matrix} = ∑_{σ∈S_{n}} v_{ab}(σ),

where A_{n} is the set of André permutations, v_{cd}(σ) is the cd-statistic of an André permutation and v_{ab}(σ) is the ab-statistic of a permutation. Using Purtill’s proof as a motivation we introduce a new “Foata–Strehl-like” action on permutations. This ℤ_{2}^{n−1}-action allows us to give an elementary proof of Purtill’s theorem and a bijection between André permutations of the first kind and alternating permutations starting with a descent. A modified version of our group action leads to a new class of André-like permutations with structure similar to that of simsun permutations.

Introduction

André permutations and similarly defined classes of permutations occur in three different areas: in the study of descent statistics of the symmetric group, in the description of the action of the symmetric group on the maximal chains of partition lattices, and in cd-index formulas for simplicial and cubical posets. These permutations were first studied by Foata, Strehl, and Schützenberger in a series of papers. In particular, Foata and Strehl defined in [?] and [?] a ℤ_{2}^{n}-action on S_{n} where each orbit contains a unique André permutation of the first kind as a representative.

More recently, S. Sundaram and R. Simion ([?, p. 267]) discovered a closely related class of permutations, called simsun permutations, which play an essential role in the description of the action of the symmetric group on the maximal chains of partition lattices. Almost at the same time, Purtill expressed in [?] the cd-index of a Boolean algebra in terms of cd-variation monomials of André permutations of the first kind. Using R-labeling arguments, Purtill reduced the problem to that of establishing a relationship between the ab-variation of all permutations and the cd-variation of André permutations. He then proceeded to give a recursive a decomposition of all permutations into equivalence classes such that the total ab-variation of all permutations in a given class equals the cd-variation of the unique André permutation of the first kind contained in the class. ^{1}

∗On leave from the Mathematical Institute of the Hungarian Academy of Sciences

†Current address: INSERM U-436, Université Paris VI, 91, bd de l’Hôpital, 75013 PARIS

‡The research of this author was supported by the UQAM Foundation

The main goal of this paper is to introduce a “Foata–Strehl like” ℤ_{2}^{n−1}-action on the symmetric group S_{n} such that the orbits are exactly the equivalence classes recursively defined by Purtill. To accomplish this, we define the min − max tree representation of permutations as well as a group action on these trees. This group action allows not only to give an elementary proof of Purtill’s formula, but also to establish a bijection between André permutations of the first kind and alternating permutations starting with a descent.

A modified version of our tree-representation, min_{1} − min_{2} trees, suggests another ℤ_{2}^{n−1}-action on S_{n}. Under this action we find two sets of possible distinguished orbit representatives: André permutations of the second kind and a new class of permutations which we call “forgotten André permutations”. Like simsun permutations, forgotten André permutations are closed under the removal of the largest letter.

In the preliminary Section ?? we introduce most of our notation, and two fundamental ways of representing permutations by labeled binary trees: decreasing tree representations and min − max tree representations. In Section ?? we describe our Foata–Strehl like action on permutations. In Section ?? we show how min − max trees and our group-action may be used to give a noninductive proof of Purtill’s formula. In Section ?? we show that our group action and the Foata–Strehl group action are not permutation isomorphic. It turns out, that the two actions together generate a transitive action on S_{n}. Finally, in Section ?? we discuss a few analogues of decreasing tree and of min − max tree representations. Generally we find that the most interesting distinguished orbit representatives may be obtained from André permutations of the first kind via trivial transformations, such as reversing or flipping the words. In the case of min_{1} − min_{2} trees, however, we obtain a genuinely new class of André-like permutations, which is studied in greater detail.

Our work inspires several open problems.

1. Find group actions to prove analogues of Purtill’s theorem where André permutations are replaced by André-like permutations.

2. Find a combinatorial proof to explain why all but one of the involutions defined on min-max trees move exactly n!/3 permutations.

3. Find a simple characterization of forgotten André permutations in the spirit of the definition of simsun permutations.

1Purtill’s theorem does have simpler proofs. A simpler R-labeling argument is indicated by Ehrenborg and Readdy in [?, Section 3], and a direct inductive proof avoiding the notion of R-labeling is given in [?]. These proofs may be easily modified to obtain analogous results about André permutations of the second kind, augmented simsun permutations, etc.

1 Words and Tree Representations

In this paper we shall define new group actions on permutations. Our work will involve the manipulation of both words (on ordered alphabets) and trees. We thus begin by introducing the required notation in a rather general context which we shall specialize in later sections. Let w be a word with n distinct letters from an ordered alphabet A = {a_{1} < a_{2} < ⋯ < a_{n}}. Every subword w′ of w of length 1 ≤ k ≤ n can be uniquely written in the following way

w′ = a_{i_{σ_{1}}} a_{i_{σ_{2}}} ⋯ a_{i_{σ_{k}}}

for appropriate {a_{i_{1}} < a_{i_{2}} < ⋯ < a_{i_{k}}} ⊆ A and σ ∈ S_{k}. We call σ the underlying pattern of a w′ and write patt(w′) = σ.

Example 1 Let w = a_{4}a_{3}a_{5}a_{6}a_{1}a_{2}a_{7} and w′ = a_{5}a_{6}a_{1} then patt(w′) = 231.

Next, suppose that ρ ∈ S_{k}. For i ≤ length(w) − k we define the action of ρ at position i + 1 of w, written ρ_{[i+1]}w, in the following way. First write w = uw′v where w′ = a_{i_{μ_{1}}} a_{i_{μ_{2}}} ⋯ a_{i_{μ_{k}}} is the subword of length k starting at position i + 1. Then ρ_{[i+1]}w = ua_{i_{ρ(μ_{1})}} ⋯ a_{i_{ρ(μ_{k})}}v.

Example 2 Let w = a_{7}a_{4}a_{8}a_{1}a_{10}a_{2}a_{5}a_{3}a_{6}a_{9} and ρ = 43512 ∈ S_{5}. Then

ρ_{[3]}w = a_{7}a_{4}a_{1}a_{8}a_{2}a_{5}a_{10}a_{3}a_{6}a_{9}

and trivially, w = σ_{[0]}a_{1} a_{2} ⋯ a_{10} where σ = 7 4 8 1 10 2 5 3 6 9.

The following lemma says essentially that if the words u and w have the same underlying pattern then the words ρ_{[i+1]}w and ρ_{[i+1]}u also have the same underlying pattern.

Lemma 1 Let w = a_{σ_{1}}a_{σ_{2}} ⋯ a_{σ_{n}} and u = b_{σ_{1}}b_{σ_{2}} ⋯ b_{σ_{n}}. Suppose ρ ∈ S_{k} with k ≤ n and 1 ≤ i ≤ n − k. Then patt(ρ_{[i+1]}w) = patt(ρ_{[i+1]}u).

Proof: Suppose that w = xw′y where w′ = a_{i_{λ_{1}}} ⋯ a_{i_{λ_{k}}} with a_{i_{λ_{j}}} = a_{σ_{i+j}}. Similarly, let v = rv′s where v′ = b_{i_{λ_{1}}} ⋯ b_{i_{λ_{k}}} with b_{i_{λ_{j}}} = b_{σ_{i+j}}. By definition,

ρ_{[i+1]}w = x a_{i_{ρ(λ_{1})}} ⋯ a_{i_{ρ(λ_{k})}} y

and

ρ_{[i+1]}u = r b_{i_{ρ(λ_{1})}} ⋯ b_{i_{ρ(λ_{k})}} s.

One now sees that

patt(ρ_{[i+1]}w) = patt(ρ_{[i+1]}u) = σ_{1} ⋯ σ_{i}σ_{i+λ^{−1}(ρ(λ_{1}))} ⋯ σ_{i+λ^{−1}(ρ(λ_{k}))}σ_{i+k+1} ⋯ σ_{n}. □

Let w = w_{λ_{1}} ⋯ w_{λ_{n}} be any word on an ordered alphabet. For each binary tree T on n nodes we associate a unique labeled tree T_{w} whose left-first order reading yields the permutation w. This is done as follows. Traverse T in a left-first manner and label the nodes in the order that they are visited with the letters w_{λ_{1}}, w_{λ_{2}}, …, w_{λ_{n}} Example 3 For σ = 5 2 1 4 6 3 and

[figure: T =; 5; 2; 4; 6; 1; 3; we have T_{σ} =; .]

¿From the construction it is clear that the left-first order reading of T_{w} yields the word w. We also remark that the set T (w) of distinct labeled binary trees constructed in this manner for each w is of cardinality C_{n}, the nth Catalan number.

Two particular binary tree representations will be of fundamental interest in this paper. (All others, discussed in Section ??, are analogous to one of these two.) We describe them by giving the recursive algorithms for their construction.

1. Decreasing trees: Let σ = u m v where m is the minimum letter of σ, u is the subword preceding m and v is the subword that follows m. The decreasing tree T_{σ}^{D} has m as its root. The right subtree of T_{σ}^{D} is obtained by applying the definition recursively to v. Similarly, the left subtree of T_{σ}^{D} is obtained by applying the definition recursively to u.

2. Minimum-maximum trees: Let σ = u m v where m is the leftmost of the minimum and maximum letters of σ, u is the subword preceding m and v is the subword following m. The minimum-maximum (min − max) tree T_{σ}^{m} has m as its root. The right subtree of T_{σ}^{m} is obtained by applying the definition recursively to v. Similarly, the left subtree of T_{σ}^{m} is obtained by applying the definition recursively to u.

Example 4 Figure ?? shows the increasing tree and the min − max tree, respectively, associated with σ = 5 2 1 4 6 3.

[figure: 5; 2; 1; 4; 3; 6; T_{σ}^{D} =; T_{σ}^{m} =; 5; 2; 1; 4; 6; 3]

Figure 1: Decreasing tree and min − max tree associated with σ = 5 2 1 4 6 3.

Our work will require the following notation:

1. If T is a binary tree with k nodes α(T) = {a_{1} < a_{2} < ⋯ < a_{k}} is the ordered set of labels of T.

2. w(T) is the word obtained by traversing T in a left-first manner.

3. T_{σ,i}^{m} is the subtree of T_{σ}^{m} formed by all the right descendants of the label i.

4. For convenience, we shall write patt(T_{σ,i}^{m}) for patt(w(T_{σ,i}^{m})).

5. We say that an interior node in T_{σ}^{m} is a min node (resp. max) if it is the minimum letter (resp. maximum) among all its descendants.

2 The Group F_{n}

We recall from [?] the definition of the x-factorization of a permutation using the notation of Viennot [?]. Definition 1 Let σ = σ_{1}σ_{2} ⋯ σ_{n} and let x = σ_{i}. The x-factorization of σ is given by σ = u λ(x) x ρ(x) v where

1. λ(x) = σ_{j} ⋯ σ_{i−1} with σ_{l} > x for j ≤ l ≤ i − 1, u = σ_{1} ⋯ σ_{j−1}, and σ_{j−1} < x.

2. ρ(x) = σ_{i+1} ⋯ σ_{k} with σ_{l} > x for i + 1 ≤ l ≤ k,v = σ_{k+1} ⋯ σ_{n}, and σ_{k+1} < x. Note that above any of u, λ(x), ρ(x) and v can be the empty word. Example 5 Let σ = 8 7 2 4 1 9 10 5 3 11 6 2 12. The 3-factorization of σ is:

\underbrace{8 7 2 4 1}_{u} \underbrace{9 10 5}_{λ(3)} 3 \underbrace{11 6}_{ρ(3)} \underbrace{2 12}_{v}

The 5-factorization is:

\underbrace{8 7 2 4 1}_{u} \underbrace{9 10}_{λ(5)} 5 \underbrace{3 11 6 2 12}_{v}

with ρ(5) = ∅.

We can now define André permutations. Definition 2 σ ∈ S_{n} is an André permutation of the first kind if

1. σ has no double descents (i.e. σ_{i} > σ_{i+1} > σ_{i+2}).

2. Each x-factorization u λ(x) x ρ(x) v of σ, has the property (i) λ(x) = ∅ if ρ(x) = ∅, (ii) max(λ(x)) < max(ρ(x)) if ρ(x) ≠ ∅ and λ(x) ≠ ∅. σ is an André permutation of the second kind if we replace condition (ii) by

min(ρ(x)) < min(λ(x)).

n = 2 : 12
n = 3 : 123 213
n = 4 : 1234 2134 3124 1324 2314

Table 1: André permutations of the first kind

The list of André permutations of the first kind for n ≤ 4 is given in Table ??.

With min − max trees one has an easy way of detecting André permutations of the first kind.

Proposition 1 λ ∈ S_{n} is an André permutation of the first kind ⇔ all interior nodes of T_{λ}^{m} are min nodes.

Proof: (⇒) Suppose that λ is an André permutation of the first kind and that T_{λ}^{m} contains a max node. Take x to be the largest among all max nodes of the tree. Let u x v be the subword of σ obtained by reading in left-first order the subtree that has x as it root. Since every interior node in a min − max tree must have a right child, one has v ≠ ∅. Let i be the left-most letter of v. If ρ(i) = ∅ then σ cannot be an André permutation of the first kind since x ∈ λ(i) ≠ ∅. If on the other hand, ρ(i) ≠ ∅ then max(ρ(i)) < x because x was chosen as the largest of all max nodes. Hence, once again σ is not an André permutation of the first kind. (⇐) Suppose all interior nodes of T_{σ}^{m} are min nodes. It follows easily from the definition of min − max trees that every node is larger than its parent. Thus for each node x in this tree, we get the subword λ(x)xρ(x) by reading the subtree whose root is x in left-first order. We have three cases to check:

1. x is an interior node and ρ(x) = ∅. This is impossible since every interior node in a min − max tree must have a right child.

2. x is an interior node and ρ(x) ≠ ∅. We must have max(λ(x)) < max(ρ(x)) for otherwise max(λ(x)) would have been the root of this subtree.

3. x is a leaf. Here we have λ(x) = ρ(x) = ∅.

This verifies that σ is an André permutation of the first kind. □

For the main result of this work we define a new set of operators {ψ_{1}, ψ_{2}, …, ψ_{n−1}} on S_{n}, motivated by the work Purtill [?]. We shall define ψ_{i}(σ) =^{def} w(ψ_{i}(T_{σ}^{m})). To determine ψ_{i}(T_{σ}^{m}) consider the subtree of T_{σ}^{m} that has σ_{i} as a root and let α(T_{σ,σ_{i}}^{m}) = {a_{1} < a_{2} < ⋯ < a_{s}}. If σ_{i} < a_{1} we relabel the tree according to the permutation

( \begin{matrix}σ_{i} & a_{1} & a_{2} & a_{3} & ⋯ & a_{s} \\ a_{s} & a_{i} & a_{1} & a_{2} & ⋯ & a_{s−1} \end{matrix} ) .

If a_{s} < σ_{i} we relabel the tree according to the permutation

( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{s} & σ_{i} \\ a_{2} & a_{3} & ⋯ & a_{s−1} & a_{1} \end{matrix} ) .

Example 6 Let σ = 3 6 7 1 5 2 10 4 9 8. Then the min − max trees T_{σ}^{m}, ψ_{7} (T_{σ}^{m}), and ψ_{6} (T_{σ}^{m}) are represented in the following three figures.

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

Figure 2: T_{σ}^{m} for σ = 3 6 7 1 5 2 10 4 9 8

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

Figure 3: ψ_{7} (T_{σ}^{m}) for σ = 3 6 7 1 5 2 10 4 9 8

An important property of these operators is the following:

Proposition 2 Let λ = ψ_{i}(σ). If σ_{i} is a min node (resp. max) in T_{σ}^{m} then λ_{i} is a max node (resp. min) in T_{λ}^{m}. All other nodes in T_{λ}^{m} are min (resp. max) iff the corresponding nodes in T_{σ}^{m} are min (resp. max).

Proof: We prove the case when σ_{i} = a_{s+1} is a max (for σ_{i} a min one has an analogous proof). Let α(T_{σ,σ_{i}}^{m}) = {a_{1} < ⋯ < a_{s}}. By the definition of ψ_{i}, λ_{i} = a_{1}. Let us consider the other nodes of T_{λ}^{m}. Clearly, we are only concerned with those interior nodes in T_{λ}^{m} which correspond to the labels {a_{2} < ⋯ < a_{s+1}} in T_{σ}^{m} (other nodes are unaffected by ψ_{i}). Suppose the node labeled with a_{j} (for 2 ≤ j ≤ s + 1) is a max node in T_{σ}^{m}. Then its children in T_{σ}^{m} must be among the set {a_{1} < a_{2} < ⋯ < a_{j−1}}. Under ψ_{i} we have a_{1} → a_{2}, …, a_{j−1} → a_{j}, a_{j} → a_{j+1}. Thus, the node labeled a_{j} in T_{σ}^{m} is labeled a_{j+1} in T_{λ}^{m} and all its children bear smaller labels. When a_{j} is a min, the proof is similar. □

The action of the group F_{n} generated by ψ_{1}, …, ψ_{n−1} is commutative. To prove this we shall need two lemmas which establish situations under which the function patt is invariant under the

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

Figure 4: ψ_{6} (T_{σ}^{m}) for σ = 3 6 7 1 5 2 10 4 9 8

action of ψ_{i}.

Lemma 2 Suppose σ ∈ S_{n} and ψ_{i}(σ_{1} ⋯ σ_{i} ⋯ σ_{n}) = λ_{1} ⋯ λ_{i} ⋯ λ_{n}. Then

patt(T_{σ,σ_{i}}^{m}) = patt(T_{λ,λ_{i}}^{m}).

Proof: Let patt(T_{σ,σ_{i}}^{m}) = ρ_{1} ⋯ ρ_{s} and α(T_{σ,σ_{i}}^{m}) = {a_{1} < ⋯ < a_{s}}. Without loss of generality, we may suppose that a_{s} < σ_{i} = a_{s+1}. By definition, the effect of ψ_{i} on T_{σ}^{m} is given by

( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{i} & ⋯ & a_{s} & a_{s+1} \\ a_{2} & a_{3} & ⋯ & a_{i+1} & ⋯ & a_{s+1} & a_{1} \end{matrix} ) .

Thus, α(T_{λ,λ_{i}}^{m}) = {a_{2} < ⋯ < a_{s+1}} and so w(T_{λ,λ_{i}}^{m}) = a_{ρ_{1}+1}a_{ρ_{2}+1} ⋯ a_{ρ_{s}+1}. Setting i_{1} = 2, i_{2} = 3, …, i_{s} = s + 1 one has w(T_{λ,λ_{i}}^{m}) = a_{i_{ρ_{1}}} a_{i_{ρ_{2}}} ⋯ a_{i_{ρs}} and patt(T_{λ,λ_{i}}^{m}) = ρ_{1}ρ_{2} ⋯ ρ_{s}. □

Lemma 3 Let σ, δ ∈ S_{n} such that T_{σ,σ_{i}}^{m} and T_{δ,δ_{i}}^{m} have the same shape as binary trees. Furthermore suppose patt(T_{σ,σ_{i}}^{m}) = patt(T_{δ,δ_{i}}^{m}) with σ_{j} a descendant of σ_{i} and δ_{j} is a descendant of ρ_{i}. Suppose ψ_{j}(σ) = σ′ and ψ_{j}(δ) = δ′ then patt(T_{σ′,σ′_{i}}^{m}) = patt(T_{δ′,δ′_{i}}^{m}).

Proof: We observe that w(T_{σ,σ_{j}}^{m}) and w(T_{δ,δ_{j}}^{m}) are subwords of the same length and position within w(T_{σ,σ_{i}}^{m}) and w(T_{ρ,ρ_{i}}^{m}), respectively. The effect of ψ_{j} is to permute these subwords according to the same rule within w(T_{σ,σ_{i}}^{m}) and w(T_{δ,δ_{i}}^{m}). Thus, Lemma ?? applies and the result follows. □

Theorem 1 The action of ψ_{1}, …, ψ_{n} on S_{n} is commutative. That is, for all σ ∈ S_{n} we have ψ_{j}(ψ_{i}(σ)) = ψ_{i}(ψ_{j}(σ)) which is equivalent to

ψ_{j}(ψ_{i}(T_{σ}^{m})) = ψ_{i}(ψ_{j}(T_{σ}^{m}))

Proof: When σ_{j} is not a right descendant of σ_{i} (nor vice versa) then ψ_{j} and ψ_{i} permute different sets of labels of T_{σ}^{m} and the commutativity is clear. Thus we suppose without loss of generality that:

1. σ_{j} is a right descendant of σ_{j}.

2. α(T_{σ,σ_{i}}^{m}) = {a_{1} < a_{2} < ⋯ < a_{s}} with a_{s} < σ_{i} = a_{s+1}.

The following diagram will be a guide throughout proof.

σ ⟶^{ψ_{j}} γ ⟶^{ψ_{i}} γ′

σ ⟶^{ψ_{i}} δ ⟶^{ψ_{j}} δ′

We need to show that δ′ = γ′. Let patt(T_{σ,σ_{i}}^{m}) = τ, and patt(T_{γ,γ_{i}}^{m}) = κ. By Lemma ?? we have that patt(T_{γ′,γ′_{i}}^{m}) = patt(T_{γ,γ_{i}}^{m}) = κ. On the other hand we now have α(T_{γ′,γ_{i}}^{m}) = α(T_{γ,γ_{i}}^{m}) = {a_{2} < ⋯ < a_{s} < a_{s+1}}. We resume our calculations so far: ψ_{i}(ψ_{j}(T_{σ}^{m})) = T_{γ′}^{m}, the label in the i^{th} position of T_{δ′}^{m} is a_{1} and

w(T_{δ,δ_{i}}^{m}) = a_{i_{κ_{1}}} ⋯ a_{i_{κs}}  (1)

where, a_{i_{κ_{j}}} = a_{κ_{j}+1}.

We now consider ψ_{j}(ψ_{i}(T_{σ}^{m})). By Lemma ??, patt(T_{σ,σ_{i}}^{m}) = patt(T_{δ,δ_{i}}^{m}) = τ. Combining this with the fact that ψ_{i} permutes the labels according to

( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{s} & σ_{i} \\ a_{2} & a_{3} & ⋯ & σ_{i} & a_{1} \end{matrix} )

one has w(T_{δ,δ_{i}}^{m}) = a_{i_{τ_{1}}} ⋯ a_{i_{τs}} where a_{i_{τ_{k}}} = a_{τ_{k}+1}. We use the fact that patt(T_{σ,σ_{i}}^{m}) = patt(T_{δ,δ_{i}}^{m}) and Lemma ?? to get patt(T_{δ′,δ′_{i}}^{m}) = patt(T_{γ,γ′_{i}}^{m}) = κ. Furthermore, α(T_{δ′,δ′_{i}}^{m}) = α(T_{δ,δ_{i}}^{m}) = α(T_{γ′,γ′_{i}}^{m}). This forces w(T_{δ′,δ′_{i}}^{m}) = a_{i_{κ_{1}}} ⋯ a_{i_{κs}}. Finally, we note that the i^{th} position in T_{δ′}^{m} has the label a_{1}. Hence T_{δ′}^{m} = T_{γ′}^{m} and the proof is complete. □

We can now proceed to show one of the most important properties of the action of the group F_{n}.

Corollary 1 The action of F_{n} partitions S_{n} into disjoint orbits each with a unique André permutation of the first kind as representative.

Proof: We first note that every permutation belongs to the orbit of some André permutation of the first kind. If σ is an arbitrary permutation then we find the corresponding André permutation in the following way. Let σ_{m_{1}}, σ_{m_{2}}, …, σ_{m_{k}} be the max nodes of T_{σ}^{m}. By Proposition ??, applying ψ_{m_{1}}ψ_{m_{2}} ⋯ ψ_{m_{k}} to σ changes all the max nodes to min nodes and leaves the min nodes unchanged. The result is then a tree with all min nodes and by Proposition ?? the corresponding permutation is an André permutation of the first kind.

Suppose that κ and γ are two André permutations of the first kind that belong to the same orbit. Then we have

ψ_{j_{1}} ⋯ ψ_{j_{s}}κ = γ.

By the commutativity of the ψ_{i} we may assume that there are no repetitions among the ψ_{j_{k}}. Now since each ψ_{j_{k}} transforms a min node into a max node T_{γ}^{m} must have some max nodes. But this contradicts the fact that γ is an André permutation of the first kind. Thus, γ = κ. □

We terminate this section with a bijection between André permutations of the first kind and alternating permutations starting with a descent.

Proposition 3 Each F_{n} orbit K_{δ} associated to an André permutation of the first kind δ contains exactly two alternating permutations, one starting with an ascent the other with a descent.

Proof: The required permutations are given by the following equations:

( ∏_{{1≤i≤n−1 \atop i odd}} ψ_{i}) δ and ( ∏_{{2≤i≤n−1 \atop i even}} ψ_{i}) δ. □

3 Variation Statistics

In this section we simplify the proof of Purtill’s formula, using the action F_{n}. We recall the ab-variation of a permutation originally introduced by Foata and Schützenberger in [?]. ^{2}

For σ = σ_{1}σ_{2} ⋯ σ_{n} ∈ S_{n} and 2 ≤ i ≤ n,

v_{ab,i}(σ) = \{ \begin{matrix}a & if σ_{i} > σ_{i−1} \\ b & if σ_{i} < σ_{i−1} \end{matrix}

One then sets v_{ab}(σ) = w_{ab,2}(σ)w_{ab,3}(σ) ⋯ w_{ab,n}(σ).

Example 7 Let σ = 9 1 3 5 6 8 4 2 7, w_{ab}(σ) = baaaabba.

[figure: 8; 1; 9; 2; 3; 5; 6; 4; 7]

Figure 5: T_{σ}^{m} for σ = 9 1 3 5 6 8 4 2 7

Using the min − max tree representation of permutations, one has another way of obtaining the ab statistic of a permutation. We relabel each node of T_{σ}^{m} to obtain T_{σ}^{ab} in the following way: a node with no descendants is labeled with ∅ (the empty word); a node with only right descendants is labeled with b if it’s greater than its descendants and with a, otherwise; a node with left and right descendants is labeled with with ba if it’s the maximum of its subtrees, if it’s a minimum it is labeled with ab. The left-first reading of T_{σ}^{ab} gives the ab variation of σ.

2Originally, Foata and Schützenberger used letters +, −, s and t instead of a, b, c and d respectively. It was Purtill who changed the notation in [?], in order to bring it closer to the standard notation used in the study of cd-indices of Eulerian posets. His example was followed by virtually all subsequent authors in the subject.

The second statistic we consider, the cd-variation, is defined for André permutations of the first kind only. Given an André permutation of the first kind δ we first find v_{ab}(δ). Next, every consecutive pair ba is replaced by the letter d and each remaining a is replaced by the letter c.

Example 8 Let δ = 5 8 2 6 7 9 1 3 4 10, v_{ab}(δ) = abaaabaaa and v_{cd}(δ) = cdccdcc.

Once again, the min − max tree representation of permutations provides another way of obtaining the cd statistic of an André permutation of the first kind. We relabel each node of T_{σ}^{m} to obtain T_{σ}^{cd} in the following way: a node with no descendants is labeled with ∅ (the empty word); a node with only right descendants is labeled with d; a node with left and right descendants is labeled with with c. The left-first reading of T_{σ}^{cd} gives the cd variation of σ.

Theorem 2 (Purtill) Let A_{n} ⊂ S_{n} be the subset of André permutations of the first kind. Then

∑_{σ∈A_{n}} v_{cd}(σ)| \begin{matrix}c=a+b \\ d=ab+ba \end{matrix} = ∑_{σ∈S_{n}} v_{ab}(σ).

Proof: Let δ ∈ A_{n}, and K_{δ} be the orbit of δ under the action of ψ_{1}, …, ψ_{n−1}. Since one can decompose S_{n} as a disjoint union

S_{n} = ⋃_{δ∈A_{n}} K_{δ},

it is enough to show that

v_{cd}(δ)| \begin{matrix}c=a+b \\ d=ab+ba \end{matrix} = ∑_{σ∈K_{δ}} v_{ab}(σ).

Consider first the set of trees S obtained from T_{δ}^{cd} when c is replaced by ab or ba and d by a or b. The monomials obtained by the left-first reading of this set of trees are clearly the monomials of v_{cd}(δ)| \begin{matrix}c=a+b \\ d=ab+ba \end{matrix} . We now note that applying the operator ψ_{j} to a permutation σ affects T_{σ}^{ab} by

changing the node corresponding to σ_{j} in one of the following four ways: ab → ba, ba → ab, a → b or b → a. All other nodes remain unchanged. Thus we conclude that S = { T_{σ}^{ab} | σ ∈ K_{δ} }. □

4 Comparison of F_{n} and the Foata–Strehl group action

Foata and Strehl ([?]) introduce a group G_{m} generated by a set of operators { φ_{1}, φ_{2}, … φ_{n−1} } which act on S_{n} as follows. Let σ ∈ S_{n} and σ = u λ(i) i ρ(i) v the i-factorization of σ. Then

φ_{i}(σ) = u ρ(i) i λ(i) v.

We remark that this action may be realized by considering the decreasing tree of a permutation T_{σ}^{D}. More precisely, φ_{i}(T_{σ}^{D}) is obtained by exchanging the right and left subtrees of the node i.

The permutation corresponding to the decreasing tree φ_{i}(T_{σ}^{D}) is φ_{i}(σ). It is shown in [?] that there is a unique André permutation of the first kind for each S_{n} orbit under the action of G_{m}.

The group F_{n} generated by ψ_{1}, …, ψ_{n−1} partitions S_{n} into the same number of orbits as the group G_{n} of Foata and Strehl. This is so because in both cases each orbit has a unique André permutation of the first kind as orbit representative. Moreover, if δ is an André permutation of the first kind then T_{δ}^{m} and T_{δ}^{D} are the same. Let N be the number of interior nodes in T_{δ}^{m} = T_{δ}^{D}. It is not difficult to show that the orbit of ρ under both actions contains 2^{N} elements.

Thus, one might guess that these ℤ_{2}^{n−1}-actions are isomorphic. In this section, we shall prove that this is not the case. The main idea underlying this result is that ψ_{n−1} has no fixed points and ψ_{i} has \frac{n!}{3} fixed points, for i ≤ n − 2. The number of fixed points of φ_{i}, on the other hand is (n − 2)!(i − 1)i. This suffices since the fixed points sets of the generators {ψ_{i} : 1 ≤ i ≤ n − 1} and {ϕ_{i} : 1 ≤ i ≤ n − 1} of F_{n} and G_{n} respectively are maximal elements in the respective fixed point set lattices of the two groups.

To count the number of fixed points of ψ_{i} we first introduce an algorithm which takes a word of length n and recursively builds up a tree, reading the word from right to left. Insertion Algorithm Input: σ = σ_{1} ⋯ σ_{n}, a word on an ordered alphabet ⟶ Output: a tree I(σ_{1} ⋯ σ_{n}) whose left-first reading gives σ.

1. I(σ_{n}) = •σ_{n}

2. Given I(σ_{i+1}σ_{i+2} ⋯ σ_{n}), I(σ_{i}σ_{i+1} ⋯ σ_{n}) is constructed as follows. Let a_{i_{1}}, a_{i_{2}}, …, a_{i_{k}} be the sequence of labels on the left backbone of I(σ_{i+1}σ_{i+2} ⋯ σ_{n}); that is, the root, its left son, the left son of its left son, etc.

(i) If there exists a least j such that

a_{i} = min ({a_{i}} ∪ {a_{i_{j}}} ∪ {descendants of a_{i_{j}}})

or

a_{i} = max ({a_{i}} ∪ {a_{i_{j}}} ∪ {descendants of a_{i_{j}}})

then a_{i_{j}} is replaced by a_{i} in the tree and the subtree formed by a_{i_{j}} and all its descendants becomes the right subtree of a_{i}.

(ii) If no such j exists, then a_{i} becomes the left son of a_{i_{k}}.

Example 9 Figure ?? shows the insertion algorithm for σ = 5 2 1 4 6 3. Below each arrow, we indicate whether a step of type (i) or of type (ii) was used.

Proposition 4 T_{σ}^{m} = I(σ).

Proof: We show by induction on the length of σ that I(σ) has the following property: Let σ_{i} be the left-most among the minimum and the maximum of σ_{1} ⋯ σ_{n}. Then σ_{i} is the root of I(σ), its left subtree is I(σ_{1} ⋯ σ_{i−1}) and its right subtree is I(σ_{i+1} ⋯ σ_{n}). Since T_{σ}^{m} satisfies the same properties, we may deduce that T_{σ}^{m} = I(σ).

When |σ| = 1, there is nothing to prove. Suppose then the property is established for all |σ| < n. Let σ_{s} be the left-most among the minimum and maximum of σ_{2} ⋯ σ_{n}. By induction, σ_{s} is the root of I(σ_{2} ⋯ σ_{n}), its left subtree is I(σ_{s} ⋯ σ_{s−1}) and its right subtree is I(σ_{s+1} ⋯ σ_{n}).

[figure: 4; 6; 3; 1; 4; 6; 3; insert 6; (i); insert 2; (ii); 1; 4; 6; 3; 2; 5; 2; 1; 4; 6; 3; 3; 6; 3; insert 4; (ii); (i); insert 1; (i); insert 5]

Figure 6: Insertion algorithm for σ = 5 2 1 4 6 3

Now, if σ_{1} is the min or max letter of σ then σ_{1} = min ({σ_{1}} ∪ {σ_{s}} ∪ {descendants of σ_{s}}) or σ_{1} = max ({σ_{1}} ∪ {σ_{s}} ∪ {descendants of σ_{s}}), respectively. Thus, the insertion algorithm gives that I(σ_{2} ⋯ σ_{n}) becomes the right subtree of σ_{1} and the claim is proved.

Otherwise, if σ_{1} is neither the min or the max of σ then σ_{s} is. Furthermore, σ_{1} is inserted into I(σ_{2}, …, σ_{s−1}) according to the insertion algorithm. Hence we have, I(σ_{1}, …, σ_{s−1}) as the left subtree of a_{s} and I(σ_{s+1} ⋯ σ_{n}) as its right subtree. □

Lemma 4 σ_{i} has a child in I(σ_{1} ⋯ σ_{n}) if and only if σ_{i} has a child in I(σ_{i} ⋯ σ_{n})

Proof: (⇐) Suppose σ_{i} has a child in I(σ_{i} ⋯ σ_{n}). According to the insertion algorithm, successive insertions either leave σ_{i} and its descendants untouched or σ_{i} and it’s descendants become the right subtree of one of σ_{1}, …, σ_{i+1}. In either case, the children of σ_{i} are unaffected by these insertions. (⇐) Suppose that σ_{i} has a child in I(σ_{1} ⋯ σ_{n}). Assume contrary to hypothesis that σ_{i} has no children in I(σ_{i} ⋯ σ_{n}) and that j < i is the largest index such that σ_{j} is a child of σ_{i}. For this to happen we must have that σ_{i} is the left most node on the left backbone of I(σ_{j+1} ⋯ σ_{n}) and that it has no children in I(σ_{j+1} ⋯ σ_{n}). By the insertion algorithm, σ_{j} is compared to every node and its subtree on the left backbone of I(σ_{j+1} ⋯ σ_{n}). It may be inserted as a left son of σ_{i} only if it is not the min or max of in any of these comparisons. But even if all the other comparisons fail we must have either σ_{j} < σ_{i} or σ_{j} > σ_{i}. Hence, σ_{i} becomes the right child of σ_{j} and we have a contradiction. □

The following proposition resumes the importance of the previous two results:

Proposition 5 σ is a fixed point of ψ_{i} if and only if patt(σ_{i} ⋯ σ_{n}) is a fixed point of ψ_{1}.

Proof: We have the following list of implications: σ is a fixed point of ψ_{i}

⇔ σ_{i} has no children in T_{σ}^{m}  (clear from the definition of ψ_{i})
⇔ σ_{i} has no children in I(σ)  (by Proposition ?? )
⇔ σ_{i} has no children in I(σ_{i}σ_{i+1} ⋯ σ_{n})  (by Lemma ??)
⇔ patt(σ_{i}σ_{i+1} ⋯ σ_{n}) is a fixed point of ψ_{1} (clear from the definition of ψ_{1}).  □

We now proceed to find

fix_{n}ψ_{i} =^{def} |{σ ∈ S_{n} | ψ_{i}σ = σ }|.

By Proposition ??, one has

fix_{n}ψ_{i} = \binom{n}{i − 1}(i − 1)! fix_{n−i+1}ψ_{1}.

So we have reduced the problem to finding f(k) =^{def} fix_{k}ψ_{1}. To this end, we count the numbers of min − max trees T_{σ}^{m} such that σ_{1} has no children. We observe immediately that f(1) = 1, f(2) = 0 and f(3) = 2. For k > 3 we note that if σ_{1} has no children in T_{σ}^{m} then:

1. One of 1 or n is the root of T_{σ}^{m} the other is in the right subtree of the root (by definition).

2. The root of T_{σ}^{m} has two children for otherwise the left-first reading of T_{σ}^{m} will yield that the σ_{1} is the root (which has children).

Thus, we may arbitrarily choose which j elements (j > 1) to place in the left subtree of the root. For each left subtree of the root such that σ_{1} has no children we have all (n − 1 − j)! permutations on the remaining letters in the right subtree of the root. This gives rise to the recursion

f(k) = 2 ∑_{j=1}^{k−2} \binom{k − 2}{j}f(j)(k − 1 − j)!.

Setting

H(x) = ∑_{k≥1} \frac{f(k)}{k!}x^{k}

We have

H′′(x) = ∑_{k≥2} \frac{f(k)}{(k − 2)!}x^{k−2}  (2)

= 2 ∑_{k≥2} ∑_{j=1}^{k−2} \frac{f(j)}{j!}x^{k}(n − j − 1)  (3)

= 2 ∑_{k≥2} ∑_{j=1}^{k−2} \frac{f(j)}{j!}x^{j}(n − j − 1)x^{n−j−2}  (4)

= 2 ∑_{k≥1} \frac{f(j)}{j!}x^{j} ∑_{j≥2}(j − 1)x^{j−2}  (5)

= 2 ∑_{k≥1} \frac{f(j)}{j!}x^{j} \frac{d}{dx} \{\frac{1}{1 − x}\}  (6)

= \frac{2 H(x)}{(1 − x)^{2}}  (7)

We look for a solution for this differential equation of the form H(x) = S(ln(1 − x)). ¿From Eq. (??) one has

H′′(x) = \frac{2 S(ln(1 − x))}{(1 − x)^{2}}

and by direct computation

H′′(x) = S′′(ln(1 − x)) (\frac{1}{1 − x})^{2} − S′(ln(1 − x)) (\frac{1}{1 − x})^{2} .

Combining these last two, we have

S′′ − S′ − 2 S = 0,

whose general solution is

S(y) = a e^{2y} + b e^{−y}.

Upon setting y = ln(1 − x),

H(x) = a (1 − x)^{2} + b \frac{1}{1 − x}.

The initial conditions on f then give a = −\frac{1}{3} and b = \frac{1}{3}. Thus,

H(x) = x + ∑_{k≥3} \frac{1}{3}x^{k}.

Hence f(k) = \frac{k!}{3}. Therefore we have

fix_{n}ψ_{i} = \binom{n}{i − 1}(i − 1)!f(n − i + 1) = \{ \begin{matrix}\frac{n!}{3} & if 1 ≤ i < n − 1 \\ 0 & if i = n − 1. \end{matrix}

Remark Obtaining such a simple formula after a long calculation is quite surprising. One would hope to find a simple combinatorial explanation for this phenomenon. Note also that the uniformity of the fixed point set size suggests that F_{n} might be used in certain random algorithms on permutations.

The computation of the number of fixed points of the generators of the Foata–Strehl action is rather straightforward. From the definition of this action we see that σ is fixed under φ_{i} if σ_{σ_{i}^{−1}+1} < i and σ_{σ_{i}^{−1}−1} < i; for then ρ(i) = λ(i) = ∅. Thus, when i = σ_{k} and 1 < k < n we have i − 1 choices for σ_{σ_{i−1}^{−1}}, i − 2 choices for σ_{σ_{i+1}^{−1}} and (n − 3)! ways of distributing the remaining letters.

i−1  n−2  i−2
↓  ↓  ↓
σ = \underbrace{σ_{1} ⋯}_{arbitrary} σ_{σ_{i}^{−1}−1} i σ_{σ_{i}^{−1}+1} \underbrace{⋯ σ_{n}}_{arbitrary}

When i = σ_{1} or σ_{n}, we have i − 1 choices for σ_{2} or i − 1 choices for σ_{n−1}, respectively, and (n − 2)! ways of distributing the remaining letters.

i−1
↓
σ = i σ_{2} \underbrace{σ_{3} ⋯ σ_{n}}_{arbitrary}

or

i−1
↓
σ = \underbrace{σ_{1} ⋯ σ_{n−2}}_{arbitrary} σ_{n−1} i

Therefore, we have

fix_{n}φ_{i} = |{ σ ∈ S_{n} | ϕ_{i}(σ) = σ }|
= (n − 2)(i − 1)(i − 2)(n − 3)! + 2(i − 1)(n − 2)!
= (n − 2)!(i − 1)i.

Theorem 3 The action of C_{n}, the group generated by F_{n} ∪ G_{n}, on S_{n} is transitive. That is, given σ, τ ∈ S_{n} there exists f ∈ C_{n} such that σ = fτ.

Proof: It suffices to show that for any σ we can find f_{σ} ∈ C_{n} such that f_{σ}σ = id. Let σ ∈ S_{n}, n > 1 and assume by induction that for every k < n if κ, γ ∈ S_{k} then we can find g ∈ C_{k} such that κ = gτ. Now, let

σ = u 1 v

with the letter n in v (we can assume that this is so for if not, we apply ψ_{σ_{1}^{−1}} to σ). Let |v| = m. By induction, we may find an operator g_{1} ∈ C_{m} such that

g patt(v) = m m − 1 ⋯ 1.

This means that there is an element h_{1} ∈ C_{n} (involving only ψ_{i} with i ≥ |u| + 2 and φ_{i} with i ∈ { n, v_{1}, v_{2}, …, v_{m−1}} and thus not affecting the first |u| + 1 letters of σ) such that h_{1}σ = u 1 n v_{1} v_{2} ⋯ v_{m−1}, where v_{1} > v_{2} > ⋯ > v_{m−1}. Now, since 1 is the root of T_{h_{1}σ}^{m} and the letters of v are in its right subtree, we have

ψ_{σ_{1}^{−1}}(h_{1}σ) = u n v_{1} v_{2} ⋯ v_{m−1} 1

and

φ_{1}ψ_{σ_{1}^{−1}}(h_{1}σ) = 1 u n v_{1} v_{2} ⋯ v_{m−1} = 1 w.

Next we can apply the inductive hypothesis to find g_{2} ∈ C_{n−1} such that g_{2}patt(w) = 1 2 ⋯ n − 1. Hence, we can find an element h_{2} ∈ C_{n} that gives

h_{2}ψ_{σ_{1}^{−1}}(h_{1}σ) = 1 2 ⋯ n. □

5 Alternative Tree Representations and Group Action

In this section we look at some alternative tree representations of permutations and corresponding group actions. We will see that each such representation together with its action yields a partition of S_{n} into orbits with distinguished representatives. In all cases but one the distinguished representatives are clearly André-like permutations. The exceptional case will lead us to a new class of permutations.

1. Increasing trees: Let σ = a m b where m is the maximum letter of σ. The increasing tree T_{σ}^{I} of σ has m as its root. We apply the definition recursively to obtain T_{a}^{I} and T_{b}^{I} as the left and right children of m, respectively.

2. Modified min − max trees: Let σ = a m b where m is the right most of the minimum and maximum letters of σ. The modified min − max tree T̃_{σ}^{m} of σ has m as its root. We apply the definition recursively to obtain T̃_{a}^{m} and T̃_{b}^{m} as the left and right children of m, respectively.

3. min_{1} − min_{2} trees: Let min_{1}(σ) the smallest and min_{2}(σ) the second smallest letter of σ. Next write σ = a m b where m is the leftmost of min_{1}(σ) and min_{2}(σ). T_{σ}^{mm} has m as its root. We apply the definition recursively to obtain T_{a}^{mm} and T_{b}^{mm} as the left and right children of m, respectively.

Definition 3 Let σ = σ_{1} ⋯ σ_{n} be a permutation.

1. The reverse of σ is the permutation σ_{n} ⋯ σ_{1}.

2. The flip of σ is the permutation λ = λ_{1} ⋯ λ_{n}, where λ_{i} = n − λ_{i} + 1.

We denote the reverse and the flip of σ respectively by rev(σ) and flip(σ) respectively.

Similarly, for a labeled binary tree T we call the reverse of T the tree obtained by exchanging left and right subtrees at every interior node, and the flip of T the tree obtained by replacing the every label ℓ by n − ℓ + 1. We denote the reverse and the flip of T respectively by rev(T) flip(T), respectively.

Increasing trees are intimately related to decreasing trees in the following way. We have

T_{σ}^{I} = flip (T_{flip(σ)}^{D}) ,

i.e., the increasing tree of σ may be obtained by flipping the decreasing tree of flip(σ). Hence, we may define a group action G_{n}^{⋆} on increasing trees analogous to the Foata-Strehl action G_{n} on decreasing trees. One remarks that G_{n}^{⋆} is permutation isomorphic to G_{n}. Table ?? presents group actions and corresponding distinguished orbit representatives when reversal of trees and permutations is allowed.

Tree type Group action Interior nodes Orbit representatives for which each
of distinguished interior node has the other extreme
tree reps  in its right subtree in its left subtree
Decreasing  G_{n}  min  André I  reverse André I
Increasing  G_{n}^{∗}  max  flip André I  flip-reverse André I

Table 2: Distinguished orbit representatives for the actions G_{n} and G_{n}^{∗}

In analogy with the case of increasing and decreasing trees, modified min − max trees are closely related to min − max trees. In fact, for every permutation σ we have

T̃_{σ}^{m} = rev (T_{rev(σ)}^{m}) ,

i.e., the modified min − max tree of a permutation σ is the reverse of the min − max tree of rev(σ). Hence the group action F_{n}^{∗} defined on modified min − max trees, in analogy with the action of F_{n} on min − max trees, is permutation-isomorphic to F_{n}. Table ?? gives the choices of orbit representatives for these two actions.

Tree type  Group Action Orbit representatives for which

each interior node has type

min  max
min − max  F_{n}  André I  flip André I
Modified min − max  F_{n}^{∗}  reverse André I flip-reverse André I

Table 3: Distinguished orbit representatives for the actions F_{n} and F_{n}^{∗}

Observe that whenever we choose the same class of distinguished orbit representatives from Table ?? and from Table ??, the same labeled binary tree is associated to the same permutation in both situations.

Let us take a closer look at min_{1} − min_{2} trees. As with min − max and modified min − max trees, these trees suggest another ℤ_{2}^{n−1}-action on S_{n}. This action is denoted by H_{n} and is generated by η_{1}, …, η_{n−1} where η_{i}(T_{σ}^{mm}) is the tree obtained from T_{σ}^{mm} by permuting σ_{i} ↔ min(w(T_{σ,σ_{i}}^{mm})) and

η_{i}(σ) =^{def} w(η_{i}(T_{σ}^{mm})).

Example 10 Let σ = 3 6 7 1 5 2 10 4 9 8. Then the min_{1} − min_{2} trees T_{σ}^{mm} and η_{6} (T_{σ}^{mm}) are represented in Figures ?? and ??.

[figure: 3; 1; 2; 5; T_{σ}^{mm} =; 6; 7; 10; 4; 9; 8]

Figure 7: T_{σ}^{mm} for σ = 3 6 7 1 5 2 10 4 9 8

[figure: 3; 1; 4; 5; η_{6} (T_{σ}^{mm}) =; 6; 7; 10; 2; 9; 8]

Figure 8: η_{6} (T_{σ}^{mm}) for σ = 3 6 7 1 5 2 10 4 9 8

Hence η_{6}(σ) = 3 6 7 1 5 4 10 2 9 8.

Most proofs of Section ?? may be easily transcribed into results on H_{n}. This way we obtain the following analogues of Propositions ?? and ??.

Proposition 6 λ ∈ S_{n} is an André permutation of the second kind ⇔ all interior nodes of T_{λ}^{mm} are min_{1} nodes.

Proposition 7 Let λ = η_{i}(σ). If σ_{i} is a min_{1} node (resp. min_{2}) in T_{σ}^{mm} then λ_{i} is a min_{2} node (resp. min_{1}) in T_{λ}^{mm}. All other nodes in T_{λ}^{mm} are min_{1} (resp. min_{2}) iff the corresponding nodes in T_{σ}^{mm} are min_{1} (resp. min_{2}).

Denoting by T_{σ,i}^{mm} the subtree of T_{σ}^{mm} formed by all the right descendants of the label i, we have the following analogues of the Lemmas ?? and ??.

Lemma 5 Suppose σ ∈ S_{n} and η_{i}(σ_{1} ⋯ σ_{i} ⋯ σ_{n}) = λ_{1} ⋯ λ_{i} ⋯ λ_{n}. Then

patt(T_{σ,σ_{i}}^{mm}) = patt(T_{λ,λ_{i}}^{mm}).

Lemma 6 Let σ, δ ∈ S_{n} such that T_{σ,σ_{i}}^{mm} and T_{δ,δ_{i}}^{mm} have the same shape as binary trees. Furthermore suppose patt(T_{σ,σ_{i}}^{mm}) = patt(T_{δ,δ_{i}}^{mm}) with σ_{j} a descendant of σ_{i} and δ_{j} is a descendant of ρ_{i}. Suppose η_{j}(σ) = σ′ and η_{j}(δ) = δ′ then patt(T_{σ′,σ′_{i}}^{mm}) = patt(T_{δ′,δ′_{i}}^{mm}).

Using these lemmas we may transcribe the proof of Theorem ?? into the following.

Proposition 8 The action of η_{1}, …, η_{n} on S_{n} is commutative.

Corollary 2 The action of H_{n} partitions S_{n} into disjoint orbits each with a unique André permutation of the second kind as representative.

As in the case of min − max trees and modified min − max trees, passing from min_{1} − min_{2} trees to modified min_{1} − min_{2} trees involves reversing all trees, all permutations, and all distinguished orbit representatives.

The list of obvious analogies ends here. H_{n} does not seem to be usable in an analogous way to F_{n} to prove

∑_{σ∈A_{n}^{II}} v_{cd}(σ)| \begin{matrix}c=a+b \\ d=ab+ba \end{matrix} = ∑_{σ∈S_{n}} v_{ab}(σ),

where A_{n}^{II} denotes the set of André permutations of the second kind in S_{n}. (This formula is true, as it is implicitly noted in [?].)

We remark another essential difference between min − max and min_{1} − min_{2} trees. Analogously to the min − max case one would expect that applying flip to André permutations of the second kind should yield min_{1} − min_{2} trees with min_{2} interior nodes (i.e. the distinguished orbit reps). This in fact does not happen and instead we get a new class of permutations.

Definition 4 We call a permutation σ a forgotten André permutation, if every interior node of T_{σ}^{mm} is min_{2}.

Forgotten André permutations have the following recursive description:

– the second smallest letter precedes the smallest letter;

– the letters preceding the second smallest letter form a forgotten André permutation;

– the letters following the second smallest letter form a forgotten André permutation.

Surprisingly, forgotten André permutations share a common property with simsun permutations, a class which properly contains André permutations of the second kind. Simsun permutations were defined by S. Sundaram and R. Simion in [?], as follows. A permutation σ ∈ S_{n} is a simsun permutation if for all i ∈ {0, 1, …, n}, after removing the i largest letters from σ, the remaining word has no double descents. In particular, the class of simsun permutations is closed under removal of the largest letter. The same holds for forgotten André permutations.

Theorem 4 Let σ ∈ S_{n} be a forgotten André permutation. Then τ ∈ S_{n−1}, obtained from σ by removing the letter n, is also a forgotten André permutation.

This theorem is the consequence of the following two lemmas.

Lemma 7 Let σ ∈ S_{n}. Then the letter n is either the label of a leaf, or the label of an internal node with only one descendant in T_{σ}^{mm}.

In fact, if n is not a leaf, then it cannot be a min_{1} node, for it is the largest letter. If n is a min_{2} node then it has exactly one descendant.

Lemma 8 Let σ ∈ S_{n}, and let τ ∈ S_{n−1} be the permutation obtained by removing the letter n from σ.

1. If n is a leaf, then T_{τ}^{mm} may be obtained from T_{σ}^{mm} by removing the leaf n.

2. If n is an interior node with only child j and n is the right child of i, then T_{τ}^{mm} may be obtained from T_{σ}^{mm} by contracting n, (i.e., by removing the node n, and attaching the node j to the node i at the place of n).

3. An interior node of T_{τ}^{mm} is min_{1} if and only if, the same interior node of T_{σ}^{mm} is min_{1}.

Proof: By Lemma ??, n is either a leaf or a node with only one descendant in T_{σ}^{mm}.

1. n is a leaf: After removing n, the minimum and the second minimum element remain unchanged in every subtree, with only one possible exception: n may be the second smallest element in the subtree of its parent, which we denote by i. But then n must be the only descendant of i, and i becomes a leaf. Hence we obtained a min_{1} − min_{2} tree which encodes τ. By the uniqueness of the construction of min_{1} − min_{2} trees, we have obtained T_{τ}^{mm}.

2. n has one child: Let j be the only child of n, and i the parent of n. Whether n is a right or left child of i, contracting it does not change the minimum nor the second minimum element in the subtree of i. The same holds for all other subtrees. □

Proof of Theorem ??: Let σ ∈ S_{n} be a forgotten André permutation. By definition, all interior nodes of T_{σ}^{mm} are min_{2}. Let τ be the permutation obtained by removing the letter n. By Lemma ??, every interior node of T_{σ}^{mm} is min_{2}. Hence τ is a forgotten André permutation. □

Remark Lemmas ?? and ?? may also be used to give a new proof of the fact that the class of André permutations of the second kind is closed under removal of the largest letter.

Theorem ?? suggests that forgotten André permutations might have a characterization which is similar to the definition of simsun permutations. More precisely, it might suffice to add a restriction analogous to the prohibition of double descents to the requirement of closure under removal of the largest letter. We leave this as an open question to the interested reader.

References

[1] R. Ehrenborg and M. Readdy, The r-cubical lattice and a generalization of the cd-index, European Journal of Combinatorics 17 (1996), 709–725.

[2] D. Foata and M.P. Schützenberger, Nombres d’Euler et permutations alternantes, manuscript, University of Florida, Gainesville, 1971.

[3] 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).

[4] 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.

[5] 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.

[6] G. Hetyei, On the cd-variation polynomials of André and simsun permutations, Discrete Comput. Geom. 16 (1996) 259–275.

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

[8] R.P. Stanley, Flag f-vectors and the cd-index, Math. Z. 216 (1994), 483–499.

[9] S. Sundaram, The Homology Representations of the Symmetric Group on Cohen-Macaulay Subposets of the Partition Lattice, Adv. Math. 104 (1994), 225-296.

[10] G. Viennot, Interprétations combinatoires des nombres d’Euler et de Genocchi, unpublished manuscript, (1981/82).