% LaTeX 2e input file for
% "A note on major sequences and external activity in trees"
\documentclass[12pt]{article}
\usepackage{emlines2}
\usepackage{amsfonts,amssymb}
\usepackage{c:/texfiles/texinput/latexcad/latexcad}
%
%\usepackage{smlfigs} % Authors' .sty file for footnotesize in figure
%                       captions. Inserted below.
% smlfigs.sty
% A LaTeX .sty file to print Figure headings at 10pt.
% Uri Peled, 14 Jan 92.
% The following is from book.sty :
% \@makecaption{NUMBER}{TEXT} : Macro to make a figure or table caption.  
%      NUMBER : Figure or table number--e.g., 'Figure 3.2' 
%      TEXT   : The caption text.
%  Macro should be called inside a \parbox of right width, with \normalsize.
% changed 25 Jun 86 to fix according to Howard Trickey:
% instead of \unhbox\@tempboxa\par we do #1: #2\par
%
%\long\def\@makecaption#1#2{
%   \vskip 10pt 
%   \setbox\@tempboxa\hbox{#1: #2}
%   \ifdim \wd\@tempboxa >\hsize   % IF longer than one line:
%       #1: #2\par                 %   THEN set as ordinary paragraph.
%     \else                        %   ELSE  center.
%       \hbox to\hsize{\hfil\box\@tempboxa\hfil}  
%   \fi}
%
% We change it to have the words "Figure ...:" at 10pt:
\makeatletter  % '@' is now a normal "letter" for TeX
\renewcommand{\@makecaption}[2]{%
   \vskip 10pt 
   \setbox\@tempboxa\hbox{\footnotesize #1: #2}
   \ifdim \wd\@tempboxa >\hsize   % IF longer than one line:
       {\footnotesize #1: #2\par} %   THEN set as ordinary paragraph.
     \else                        %   ELSE  center.
       \hbox to\hsize{\hfil\box\@tempboxa\hfil}  
   \fi}
\makeatother   % '@' is restored as a "non-letter" character for TeX

\title{\bf A note on major sequences\\
and external activity in trees\\[5mm]}
%
\author{Janet S. Beissinger\\
Institute for Mathematics and Science Education\\
The University of Illinois at Chicago (M/C 250)\\
950 S. Halsted Street, Chicago, IL 60607-7019\\
\texttt{Beissing@uic.edu}\\[5mm]
\mbox{ }and\\[5mm]
Uri N. Peled\\
Dept.\ of Mathematics, Statistics, and Computer Science\\
The University of Illinois at Chicago (M/C 249)\\
851 S. Morgan Street, Chicago, IL 60607-7045\\
\texttt{uripeled@uic.edu}\\[7mm]}
\date{Submitted: September 20, 1996; Accepted October 31, 1996.
}

% To conform to EJC format of hsize=6in, vsize=9in, do the following:
\setlength{\hoffset}{0in}
\setlength{\textwidth}{6in}
\setlength{\voffset}{0in}
\setlength{\textheight}{9in}
\addtolength{\textheight}{-\topmargin}
\addtolength{\textheight}{-\headheight}
\addtolength{\textheight}{-\headsep}
\addtolength{\textheight}{-\footskip}

\newcommand{\clist}[3]{#1_{#2}, \ldots, #1_{#3}}
\newcommand{\s}{\mathrm{sort}}
\newtheorem{lem}{The Decomposition Lemma}
\renewcommand{\thelem}{} % Don't number it, since it's the only one.
\newcommand{\qed}{\hspace*{\fill} $\scriptstyle \blacksquare$ \par}
\begin{document}

\maketitle
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 4 (no. 2) (1997),
\#R4\hfill}
\thispagestyle{empty}
%
\begin{abstract}
A bijection is given from major sequences of length $n$ (a variant of parking
functions) to trees on $\{0,\ldots,n\}$ that maps a sequence
with sum ${{n+1}\choose 2} + k$ to a tree with external activity $k$.
\\[\baselineskip]
Key Words: Major sequence, external activity, parking function,
bijection
\\[\baselineskip]
Mathematical Reviews Subject Numbers:
Primary 05A19; Secondary 05A15, 05C05, 05C30
\end{abstract}
\clearpage


%\setcounter{page}{1} % Make this page Number 1, not 2.
We present a bijection from major
seqeunces (a variant of parking funtions) of length $n$ to trees on
$\{0,\ldots,n\}$ that takes area to external activity. Our main tool
is a decomposition of major sequences due to Kreweras~\cite{Kreweras}.

An integer sequence $S = (\clist{s}{1}{n})$ is called a \emph{major
sequence of length $n$}~\cite{Kreweras} if its non-decreasing rearrangement
$(\clist{z}{1}{n})$ satisfies
%
\[ z_i \geq i \quad \mbox{for all} \quad 1 \leq i \leq n \quad
   \mbox{and} \quad z_n \leq n.
\]
%
Another way to view $(\clist{z}{1}{n})$ is as a lattice path from
$(0,0)$ to $(n,n)$ that never drops below the main diagonal.
In Figure~\ref{fig1} the top lattice path represents the nondecreasing
rearrangement of the major sequence
%
\[(7,8,8,3,3,5,3,7)\]
%
and the bottom represents the identity
%
\[(1,2,3,4,5,6,7,8).\]
%

  \setlength{\unitlength}{1.5mm}
  \placedrawing[hbt]{test1.lp}{The nondecreasing rearrangement of the
  major sequence $(7,8,8,3,3,5,3,7)$ with length 8 and area 8.}{fig1}
We note that $(\clist{s}{1}{n})$ is a major sequence iff
$(\clist{n-s}{1}{n})$ is a \emph{parking function}
as defined in Stanley~\cite{Stanley, Stanley2}, i.e.,
a sequence of $n$ integers between $0$ and $n-1$ at most $i$ of which
are $\geq n-i$ for all $1 \leq i \leq n$.

The \emph{area} of the major sequence $S = (\clist{s}{1}{n})$ is defined
as
%
\[ a(S) = \sum_{i=1}^n s_i - {{n+1} \choose 2}. \]
%
It is non-negative and is the area between the lattice path and
the main diagonal.
The area of the sequence in Figure~\ref{fig1} is $8$, as illustrated by
the shaded boxes.
We denote by $\mathcal{M}_n(k)$ the set of major sequences
of length $n$ and area $k$, and define the \emph{area enumerator for major
sequences of length $n$} as
%
\[ M_n(t) = \sum_S t^{a(S)}, \]
%
where the sum is over all major sequences of length $n$.

To define external activity, we consider a complete graph $K$ on
$\{0,\ldots,n\}$. We
order its edges lexicographically, i.e., edge $ij$ with $i < j$ is
smaller than edge $kl$ with $k < l$ iff $(i < k)$ or $(i = k, j < l)$.
Let $T$ be a spanning tree of $K$. An edge of $K - T$ is called
\emph{externally active for $T$} if it is the smallest edge in the unique
cycle that it closes with edges of $T$.
For example, the tree $T$ in Figure~\ref{fig2} has exactly 8 externally
active edges, namely $01$, $02$, $03$, $04$, $05$, $23$, $26$ $45$.

\begin{figure}[hbt]
\vspace{5mm}
\begin{center}
    \input{t.pic}
  \caption{A tree with external activity 8 and 10 inversions.} \label{fig2}
\end{center}
\end{figure}
%
\noindent
The \emph{external activity} $e(T)$ is the number of externally
active edges for $T$.
We denote by $\mathcal{E}_{n+1}(k)$ the set of trees on the vertex set
$\{0,\ldots,n\}$ with external activity $k$, and define the
\emph{external activity enumerator for trees on $\{0,\ldots,n\}$} as
%
\[ E_{n+1}(t) = \sum_T t^{e(T)}, \]
%
where the sum is over all trees on $\{0,\ldots,n\}$.
We remark that $E_{n+1}(t)$ is the Tutte polynomial of $K$ evaluated
at $(1,t)$. See Gessel~\cite{Gessel} and Gessel and
Sagan~\cite{Gesselsagan} for many properties of the Tutte polynomial and
further references.

If $T$ is a tree on $\{0,\ldots,n\}$, an \emph{inversion} of $T$ is a
pair $(i,j)$ such that $1 \leq j < i \leq n$ and $i$ lies on the path
from $0$ to $j$ in $T$. For example, the tree $T$ in Figure~\ref{fig2} has
exactly 10 inversions, namely $(2,1)$, $(3,1)$, $(3,2)$, $(6,1)$,
$(6,2)$, $(6,3)$, $(7,4)$, $(7,5)$, $(8,1)$, $(8,2)$.
We denote by $i(T)$ the number of inversions of $T$.
We also denote by $\mathcal{I}_{n+1}(k)$ the set of trees
on $\{0,\ldots,n\}$ with $k$ inversions and define the \emph{inversion
enumerator for trees on $\{0,\ldots,n\}$} as
%
\[ I_{n+1}(t) = \sum_T t^{i(T)}, \]
%
where the sum is over all trees on $\{0,\ldots,n\}$.

Bj\"{o}rner discovered that
%
\begin{equation} \label{iequale}
I_{n+1}(t) = E_{n+1}(t),
\end{equation}
%
using his results on shellability and homology in matroids as well as
a result of Gessel and Wang~\cite{Gesselwang}
(see Exercise~7.7~(c), page~271 of~\cite{Bjorner}).
Beissinger~\cite{Beissinger} proved (\ref{iequale}) by providing a bijection
from $\mathcal{I}_{n+1}(k)$ to $\mathcal{E}_{n+1}(k)$.

Kreweras~\cite{Kreweras} showed that
%
\begin{equation} \label{mequali}
M_n(t) = I_{n+1}(t),
\end{equation}
%
and gave a bijection from $\mathcal{M}_n(k)$ to $\mathcal{I}_{n+1}(k)$.

An immediate consequence of~(\ref{iequale}) and (\ref{mequali}) is
%
\begin{equation} \label{mequale}
 M_n(t) = E_{n+1}(t).
\end{equation}
%
We prove~(\ref{mequale}) by presenting a direct bijection from
$\mathcal{M}_n(k)$ to $\mathcal{E}_{n+1}(k)$. It uses the decomposition of
major sequences that Kreweras used, but because it avoids inversions,
it is simpler than both the bijections of Kreweras and of Beissinger.

We reproduce Kreweras' decomposition below for completeness.
In preparation for it we note that, by definition, if $(\clist{s}{1}{n}$)
is a major sequence and we increase $s_n$ (or any other $s_i$) to a
larger integer not exceeding $n$, the new sequence is still major.
Conversely, if we repeatedly decrease $s_n$ by $1$, eventually the
sequence will no longer be major. We denote by $s_n^*$ the smallest
integer $s$ such that $(\clist{s}{1}{n-1},s)$ is still a major sequence,
and call $(\clist{s}{1}{n-1},s_n^*)$ the \emph{reduced form} of
$(\clist{s}{1}{n})$.
For example, for the major sequence $(7,8,8,3,3,5,3,7)$ that we saw in
Figure~\ref{fig1}, $s_8^* = 4$, and the nondecreasing rearrangement of
its reduced form is shown in Figure~\ref{fig3}.
  \setlength{\unitlength}{1.5mm}
  \placedrawing[hbt]{test2.lp}{The nondecreasing rearrangement of
  $(7,8,8,3,3,5,3,4)$, the reduced form of the major sequence
  $(7,8,8,3,3,5,3,7)$ of Figure~\protect\ref{fig1}.}{fig3}

If $x = (\clist{x}{1}{n})$ is an integer sequence, we denote its
nondecreasing rearrangement by $\s(x) = \s(\clist{x}{1}{n})$.
For any integer $c$, we denote the sequence
$(x_1+c,\ldots,x_n+c)$ by $x+c$.

\begin{lem}
Let $(\clist{s}{1}{n})$ be a major sequence and let
%
\[ (\clist{z}{1}{n})  = \s(\clist{s}{1}{n-1},s_n^*) \]
%
be the nondecreasing rearrangement of its reduced form. Then
\begin{enumerate}
  \item There exists a unique $l$ satisfying $z_l = s_n^*$,
  namely $l = s_n^*$;
  \item $z_{l-1} < z_l < z_{l+1}$ (where $z_0$ and $z_{n+1}$ are
  understood to be $0$ and $n+1$, respectively);
  \item $(\clist{z}{1}{l-1})$ and $(\clist{z}{l+1}{n}) - l$ are major
  sequences;
  \item $a(\clist{s}{1}{n-1},s_n^*) = a(\clist{z}{1}{l-1}) +
        a((\clist{z}{l+1}{n}) - l)$, and consequently
        $a(\clist{s}{1}{n}) = a(\clist{z}{1}{l-1}) +
        a((\clist{z}{l+1}{n}) - l) + (s_n - s_n^*)$.
\end{enumerate}
\end{lem}
%
\textbf{Proof.} 1. Clearly $z_l = s_n^*$ for some $l$.
Since $(\clist{z}{1}{n})$ is a major sequence, we
have $z_l \geq l$ and therefore $s_n^* \geq l$.
But if this inequality is strict, then
$(\clist{z}{1}{l-1},z_l-1,\clist{z}{l+1}{n})$,
which is a rearrangement of $(\clist{s}{1}{n-1},s_n^*-1)$,
would still be a major sequence, contrary to the definition of $s_n^*$.
Hence $s_n^* = l$.\\
2. This follows immediately from 1) above, for if $z_{l \pm 1} = z_l$,
then $s_n^*$ would equal both $l$ and $l \pm 1$.\\
3. This also follows from 1) above, since the lattice path returns to
the main diagonal at $(l,l)$, and is also easy to verify
algebraically using 2).\\
4. This too follows from the fact that the lattice path returns to the
main diagonal at $(l,l)$, and is verifiable by an easy calculation.
\qed

\subsection*{The Bijection}
\mbox{} % start an indented paragraph below

We now construct a mapping $f$ from the set of major sequences to the
set of labeled trees that maps $\mathcal{M}_n(k)$ to $\mathcal{E}_{n+1}(k)$
as follows.
%
\begin{enumerate}
%
\item Given a major sequence $S = (\clist{s}{1}{n})$, find
its reduced form
%
\[ (\clist{s}{1}{n-1},s_n^*).\]
%
\item Set
%
\[ E_1 = \{ i : 1 \leq i \leq n-1, s_i < s_n^* \}, \quad
   E_2 = \{ i : 1 \leq i \leq n-1, s_i > s_n^* \}. \]
%
By Part~2 of the Decomposition Lemma, $E_1$ and $E_2$ partition
$\{1,\ldots,n-1\}$. Set
%
\[ S_1 = (s_i : i \in E_1 ), \quad S_2 = (s_i : i \in E_2 ) - s_n^* . \]
%
By part~3 of the Decomposition Lemma, $S_1$ and $S_2$ are major
sequences of length $l-1$ and $n-l$, respectively, with $l = s_n^*$ as
in the lemma. Recursively obtain the trees $T_1 = f(S_1)$ and $T_2 =
f(S_2)$ on $\{0,\ldots,l-1\}$ and $\{0,\ldots,n-l\}$ respectively, with
$e(T_1) = a(S_1)$ and $e(T_2) = a(S_2)$, and thus by Part~4 of the
Decomposition Lemma
%
\[ e(T_1) + e(T_2) + (s_n - s_n^*) = a(S). \]
%
\item Relabel the vertices of $T_1 - \{0\}$ with the elements of $E_1$,
preserving their order, which gives the tree $T_1'$ with
$e(T_1') = e(T_1)$. Relabel the vertices of $T_2$ with the elements of
$E_2 \cup \{n\}$, preserving their order, which gives the tree $T_2'$ with
$e(T_2') = e(T_2)$.
%
\item Let $r$ be the $(s_n - s_n^* +1)$-st smallest
vertex in $T_2'$ (this vertex exists since $1 \leq s_n - s_n^* + 1 = s_n
- l + 1 \le n - l + 1$). Connect vertex $0$ of $T_1'$ with vertex $r$ of
$T_2'$ to obtain the tree $T = f(S)$ on $\{0,\ldots,n\}$.
%
\item We have
%
\[ e(T) = e(T_1') + e(T_2') + (s_n - s_n^*) \]
%
because the only externally active edges of $T$ between $T_1'$ and
$T_2'$ are the $s_n - s_n^*$ edges joining $0$ with the vertices of
$T_2'$ smaller than $r$. Therefore
%
\[ e(T) = a(S), \]
%
as required.
\end{enumerate}

For example, given our major sequence $(7,8,8,3,3,5,3,7)$, we find that
$s_8^*=4$, $S_1 = (3,3,3)$, $S_2 = (3,4,4,1)$
and $E_1 = \{ 4,5,7 \}$, $E_2 = \{ 1,2,3,6 \}$. Note that in
Figure~\ref{fig3}, $\s(S_1)$ is shown to the left of the bar of height
$s_n^* = 4$ and $\s(S_2)$ is shown above the dotted line to the right of
that bar. Note also that $E_1$ and $E_2$ are the
sets of positions of those elements of $S$ that are used to form $S_1$ and
$S_2$, respectively.
The trees $T_1$ and $T_2$, obtained recursively, are shown in
Figure~\ref{fig4}. 

\begin{figure}[hbt]
\vspace{5mm}
\begin{center}
    \input{t1t2.pic}
  \caption{Trees $T_1$ and $T_2$ obtained in Step~2 of the bijection.}
  \label{fig4}
\end{center}
\end{figure}
%
\noindent
The relabelings $T_1'$ and $T_2'$ obtained in Step~3 are shown in
Figure~\ref{fig5}.
%
\begin{figure}[hbt]
\vspace{5mm}
\begin{center}
    \input{t1t2prim.pic}
  \caption{Trees $T_1'$ and $T_2'$ obtained in Step~3 of the bijection.}
  \label{fig5}
\end{center}
\end{figure}
%
\noindent
The vertex $r$ in Step~4 is the fourth smallest vertex in
$T_2'$, namely $r=6$, and the final tree $T$ is the one
shown in Figure~\ref{fig2}.

We now present the inverse mapping $f^{-1}$ from trees to major sequences.
%
\begin{enumerate}
%
\item Given a tree $T$ on $\{0,\ldots,n\}$, let $0r$ be the first edge
along the path from $0$ to $n$ in $T$. Deleting this edge leaves two
subtrees: $T_1'$ with $l$ vertices including $0$, and $T_2'$ with
$n+1-l$ vertices including $r$.
%
\item Relabel the vertices of $T_1'$ as $0, \ldots, l-1$, preserving
their order, to obtain the tree $T_1$. Recursively obtain the major
sequence
%
\[ S_1=(\clist{a}{1}{l-1}) = f^{-1}(T_1). \]
%
This $S_1$ will be a subsequence of the sequence $S$ that we are
constructing. Specifically, put the elements of $S_1$ in order
into the positions of $S$ indexed by the vertices of
$T_1' - \{0\}$, i.e., if $i$ is the $j$-th smallest vertex in
$T_1' - \{0\}$, set $s_i = a_j$. Relabel the vertices of $T_2'$ as
$0, \ldots, n-l$, preserving their order, to obtain the tree $T_2$.
Recursively obtain the major sequence
%
\[ S_2=(\clist{b}{1}{n-l}) = f^{-1}(T_2). \]
%
Put the elements of $S_2 + l$ in order into the positions of $S$ indexed
                                       %<TeX_Marker>
by the vertices of $T_2' - \{n\}$, i.e., if $i$ is the $j$-th smallest
vertex in $T_2' - \{n\}$, set $s_i = b_j + l$.
%
\item We assert that $(\clist{s}{1}{n-1},l)$ is a major sequence.
Indeed, since the elements of $S_1$ are smaller than $l$ and
the elements of $S_2 + l$ are larger than $l$, we have
%
\[ \s(\clist{s}{1}{n-1},l) = (\clist{z}{1}{l-1},l,\clist{z}{l+1}{n}), \]
%
where $(\clist{z}{1}{l-1}) = \s(S_1)$
and $(\clist{z}{l+1}{n}) = \s(S_2 + l)$.
Hence $z_i \geq i$ for $1 \leq i \leq l-1$ and $z_{l+i} \geq l+i$ for
$1 \leq i \leq n-l$, and furthermore $z_n \leq (n-l) + l = n$, proving
the assertion.
%
\item Put $s_n = l + q$, where $q$ is the number of vertices of $T_2'$
smaller than $r$. We have
%
\[ s_n \leq (\mbox{number of vertices of } T_1') +
   (\mbox{number of vertices of } T_2' - 1) = n. \]
   %
Since we have obtained $S = (\clist{s}{1}{n})$ from the major sequence
$(\clist{s}{1}{n-1},l)$ by increasing its last component, but not above
$n$, $S$ is a major sequence.
%
\item Using induction and the familiar arguments, we obtain
%
\begin{eqnarray*}
  a(S) & = & a(\clist{z}{1}{l-1}) + a((\clist{z}{l+1}{n}) - l) + q \\
  & = & a(S_1) + a(S_2) + q \\
  & = & e(T_1) + e(T_2) + q \\
  & = & e(T_1') + e(T_2') + q \\
  & = & e(T).
\end{eqnarray*}
%
Furthermore, the major sequence $S$ just constructed satisfies
$s_n^* = l$, as can be seen from the argument in~3 above. From this it
follows easily that $f(S) = T$, and therefore we have indeed inverted
$f$, so $f$ is a bijection.
\end{enumerate}

We remark that in mapping major sequences to trees, Kreweras'
algorithm and ours use the same decomposition, but obtain different
trees. The algorithms differ, first, in how vertex $r$ is chosen and,
second, in the fact that Kreweras' algorithm permutes a subset of the
labels of $T_2'$ (to obtain the correct number of inversions) and ours
does not have to. A similar permutation of a subset of labels also
occurs in Beissinger's algorithm.

\subsection*{Acknowledgement}
\mbox{} % start an indented paragraph below

We thank Richard Stanley for encouraging us to work on this problem, and
for providing us with valuable references.
\bibliography{majorseq}
\bibliographystyle{plain}
\end{document}