\documentclass[12pt]{amsart} \renewcommand{\Bbb}{\mathbb} \headheight=8.5pt \textheight=574pt \textwidth=432pt \oddsidemargin=18.88pt \evensidemargin=18.88pt \topmargin=14.21pt \renewcommand{\baselinestretch}{1.0} \newcommand{\Bnn}{{\Bbb N}} \newcommand{\Cnn}{{\Bbb C}} \newcommand{\Zzz}{\Bbb Z} \newcommand{\bigcenter}[1]{\begin{center} {\Large\bf #1} \end{center}} %\newcommand{\qed}{\mbox{$\Diamond$}\vspace{\baselineskip}} \newcommand{\ler}{left-to-right } \newtheorem{theorem}{Theorem} \newtheorem{conjecture}{Conjecture} \newtheorem{lemma}{Lemma} \newtheorem{proposition}{Proposition} \newtheorem{definition}{Definition} \newtheorem{corollary}{Corollary} \newtheorem{example}{Example} %\newenvironment{proof}{\noindent {\bf Proof:}}{{\qed}} \newcommand{\df}{\stackrel{\mbox{\rm def }}{=}} \newcommand{\di}{\displaystyle} %\newcommand{\bigtimes}[1]{{{\large\times}\atop {#1}}} \newcommand{\bl}[2]{{\left\langle #1 \:\: \vrule \:\: #2 \right\rangle}} \newcommand{\fact}[2]{{^{\di #1}\left/ _{\di#2}\right.} } % \newcommand{\rest}[2] {#1\left| {_{#2}}\right. } \newcommand{\vanish}[1]{} %\parskip=12pt \begin{document} %\setlength{\baselineskip}{1.2\baselineskip} \title [A Combinatorial proof of a result of Hetyei and Reiner] {A Combinatorial proof of a result of Hetyei and Reiner on Foata-Strehl type permutation trees} \author{Mikl\'os B\'ona} \thanks{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.} \address{Department of Mathematics \\ Massachusetts Institute of Technology \\ Cambridge, MA 02139} \begin{abstract} We give a combinatorial proof of the known \cite{hetyei} result that there are exactly $n!/3$ permutations of length $n$ in the minmax tree representation of which the $i$th 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. \end{abstract} \maketitle \section{Background and definitions} In \cite{hetyei} the authors gave a new proof for a theorem of Purtill \cite{purtill} by introducing a new $\Zzz_2^{n-1}$-action on the symmetric group $S_n$. This had the flavor of a $\Zzz_2^n$-action defined and succesfully used by Foata and Strehl \cite{Foata-Strehl1} \cite{Foata-Strehl2}, 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,\cdots ,p_n)$ called {\em minimum-maximum trees} or, in the rest of this paper, {\em minmax} trees. These are defined as follows. \begin{definition} 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 {\em minmax tree} $T^m_p$ has $m$ as its root. The right subtree of $T^m_p$ is obtained by applying the definition recursively to $v$. Similarly, the left subtree of $T^m_p$ is obtained by applying the definition recursively to $u$. \end{definition} So every node of $T^m_p$ 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\'e-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. $$ \begin{picture}(378,122)(105,677) \thicklines \put(160,760){\circle*{6}} \put(240,780){\circle*{6}} \put(320,760){\circle*{6}} \put(280,740){\circle*{6}} \put(200,740){\circle*{6}} \put(240,720){\circle*{6}} \put(360,740){\circle*{6}} \put(400,720){\circle*{6}} \put(440,700){\circle*{6}} \put(480,680){\circle*{6}} \put(160,760){\line( 4, 1){ 80}} \put(240,780){\line( 4,-1){ 80}} \put(320,760){\line( 2,-1){160}} \put(320,760){\line(-2,-1){ 40}} \put(160,760){\line( 2,-1){ 80}} \put(155,770){3} \put(235,790){1} \put(315,770){2} \put(275,750){5} \put(195,750){6} \put(235,730){7} \put(355,750){10} \put(395,730){4} \put(435,710){9} \put(475,690){8} \put(175,660){Figure 1: $T^m_p$ for $p = 3\,6\,7\,1\,5\,2\,10\,4\,9\,8$.} \end{picture} $$ \vskip .8 cm If $a=a_1,a_2,\cdots ,a_k$ is a subword of the $n$-permutation $p$, then the {\em pattern} of $a$ is the unique $k$-permutation for which the pairwise comparisons between the $i$th and $j$th 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\leq i \leq n$. Then $\psi_i(T^m_p)$ is obtained from $T^m_p$ by changing only the subtree whose root is the entry $p_i$. If $p_i$ was a minimum node, then we take the {\em 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 {\em pattern} is the same as it was before the operation. Similarly, if $p_i$ was a maximum node, then we put the {\em 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 $\psi_7$. $$ \begin{picture}(378,122)(105,677) \thicklines \put(160,760){\circle*{6}} \put(240,780){\circle*{6}} \put(320,760){\circle*{6}} \put(280,740){\circle*{6}} \put(200,740){\circle*{6}} \put(240,720){\circle*{6}} \put(360,740){\circle*{6}} \put(400,720){\circle*{6}} \put(440,700){\circle*{6}} \put(480,680){\circle*{6}} \put(160,760){\line( 4, 1){ 80}} \put(240,780){\line( 4,-1){ 80}} \put(320,760){\line( 2,-1){160}} \put(320,760){\line(-2,-1){ 40}} \put(160,760){\line( 2,-1){ 80}} \put(155,770){3} \put(235,790){1} \put(315,770){2} \put(275,750){5} \put(195,750){6} \put(235,730){7} \put(355,750){4} \put(395,730){8} \put(435,710){10} \put(475,690){9} \put(165,660){Figure 2: $\psi_7(T^m_p)$ for $p = 3\,6\,7\,1\,5\,2\,10\,4\,9\,8$.} \end{picture} $$ \vskip .8 cm It is clear that $\psi_i(T^m_p)=T^m_p$ if and only if $p_i$ is a leaf in $T^m_p$. Hetyei and Reiner proved that any for any $i\leq n-2$, $p_i$ is a leaf in exactly $n!/3$ permutations of length $n$ (in the rest of this paper, $n$-permutations), thus $\psi_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\leq i \leq n-2$. Thus this group action has even more symmetries, which supports the inventors' claim that it could be used in analysing random permutations. \section{The Proof of the Theorem} First we make some simple observations which will be useful later. For any $i\leq 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 {\em 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. \begin{definition} Let $1\leq i\leq n-2$. Then the {\em $i$th 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$. \end{definition} 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. \begin{lemma} The number of $n$-permutations whose minmax tree contains $p_1$ as a leaf is $n!/3$. \end{lemma} \begin{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 $i$th entry is $n+1-p_i$) has an isomorphic minmax tree to $T^m_p$. 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: \begin{itemize} \item If $p_1=1$, then $p_1$ is the root of the minmax tree. \item If $p_2=1$, then $p_2$ is the root, and $p_1$ is a leaf. \item 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. \end{itemize} 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