\documentstyle[12pt,epsf]{article}

\setlength{\oddsidemargin}{0.5in}
\setlength{\evensidemargin}{0.5in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.2in}
\setlength{\textwidth}{6in}
\font\tenmsym=msym10
\font\sevenmsym=msym7
\font\fivemsym=msym5
\newfam\msymfam \def\msym{\fam\msymfam\tenmsym}
\textfont\msymfam=\tenmsym
\scriptfont\msymfam=\sevenmsym
\scriptscriptfont\msymfam=\fivemsym

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{observation}[theorem]{Observation}


\newcommand{\qed}{ \mbox{  $\Box$} \\ \vspace{2mm} }
\newenvironment{proof}{\noindent\mbox{\sc Proof} }{\qed}
\newenvironment{example}{\mbox{\sc Example} }{}
\newenvironment{definition}{\mbox{\sc Definition} }{\qed}
\newenvironment{remark}{\mbox{\sc Remark} }{\qed}


\newcommand{\mP}{{\msym P}}
\newcommand{\DEF}{\buildrel {\rm def} \over =}
\newcommand{\Ess}{{\cal E}}
\newcommand{\Vex}{{\cal V}}
\def\NE{{\mathop{\rm ne}\nolimits}}
\def\SE{{\mathop{\rm se}\nolimits}}
\def\SW{{\mathop{\rm sw}\nolimits}}
\def\rt{{\mathop{\rm rt\ }\nolimits}}

\pagestyle{myheadings}   
\markright{\sc the electronic journal of combinatorics 2 (1995), \#R6\hfill}
\thispagestyle{empty}

\begin{document}

\title {\bf The size of Fulton's essential set}
\author{
{\sc  Kimmo Eriksson$^1$ and Svante Linusson$^2$}
}
\date{\small Submitted: January 2, 1995; Accepted: April 3, 1995.}
\maketitle


\begin{abstract}
The {\em essential set} of a permutation was defined by Fulton as
the set of southeast corners of the diagram of the permutation.
In this paper we determine explicit formulas for the average size
of the essential set in the two cases of arbitrary permutations
in $S_n$ and $321$-avoiding permutations in $S_n$.  Vexillary permutations
are discussed too.  We also prove that the generalized Catalan numbers
${r+k-1\choose n}-{r+k-1\choose n-2}$ count $r\times k$-matrices
dotted with $n$ dots that are extendable to $321$-avoiding permutation
matrices.
\par\noindent
{\bf 1991 Mathematics Subject Classification.} 
primary 05A15; secondary 05E99, 14M15.
\end{abstract}

\section{Introduction}
There is an extensive theory, well presented by Macdonald \cite{Ma},
on the Schubert polynomial of a permutation
$w$.  Important in this theory is the {\em diagram} of $w$, obtained
from the permutation matrix of $w$ by shading, for every square $(i,w(i))$,
all squares to the east in row $i$ and squares to the south in
column $w(i)$.   In a ground-breaking paper from 1992, Fulton \cite{Fu} 
introduced the {\em essential set} of $w$ as the set of southeast
corners of the diagram of $w$, which together with a rank function was
used as a powerful tool in Fulton's algebraic treatment of Schubert
polynomials and degeneracy loci.  However, we feel that the essential
set as a combinatorial object is interesting {\em per se}, deserving
to be studied combinatorially.  In another paper \cite{EL} we characterize 
the essential sets that can arise from arbitrary permutations, as well as 
from certain classes of permutations.  The present paper is devoted to
enumerative aspects.

Before treating the essential set though, we immediately take a
detour.  It is well-known (Knuth \cite{Kn}) that the Catalan number
$C_n = {2n \choose n}/(n+1) = {2n-1 \choose n}-{2n-1 \choose n-2}$ 
counts $321$-avoiding permutations in $S_n$.  We prove the following
generalization:
\[
{r+k-1\choose n} - {r+k-1 \choose n-2}
\]
is the number of rectangular $r\times k$-matrices with $n$ dots that are
{\em extendably $321$-avoiding}, that is, that can be embedded
in the northwest corner of a $321$-avoiding permutation matrix.

Coming then to the essential sets, we present two main results (and some 
minor ones).   First, the average size of the essential set of a permutation
in $S_n$ is
\[
{{n-1 \choose 3} + 6{n \choose 2} \over 6n} \sim {1 \over 36}n^2.
\]
Second, the average size of the essential set of a $321$-avoiding permutation
in $S_n$ is
\[
{4^{n-2} \over C_n} \sim {\sqrt{\pi} \over 16} n^{3/2},
\]
the proof of which relies on the result on extendably $321$-avoiding matrices.
Finally, we discuss what can be said about the important {\em vexillary}
permutations.

We thank Dan Laksov for drawing our attention to this problem.



\section{Extendably $321$-avoiding matrices}
\label{sc:three-and-half}
We say that $w$ contains a {\em $321$-pattern} if there are indices 
$i_1<i_2<i_3$  such that $w(i_1)>w(i_2)>w(i_3))$. We say that $w$ is 
{\em $321$-avoiding} if it does not contain a $321$-pattern. 
$321$-avoiding permutations have been studied by several people
(Knuth, Billey-Jockusch-Stanley, Simion, Stanley, Fan, \dots).

In this section we shall obtain a nice generalization of the
fact that $321$-avoiding permutations are counted by Catalan numbers.
We shall always regard permutations as permutation matrices, and the 
generalization deals with rectangular matrices that have at most one dot 
in each row and column.  

First, the following very simple characterization of $321$-avoiding permutation
matrices is essential: Let the {\em upper triangle} of a $m \times n$-matrix
denote the set of elements $(i,j)$ such that $i<j$; let the {\em lower
triangle} be the complement, that is, the set of $(i,j)$ such that $i\ge j$.
Then a permutation matrix $w$ is $321$-avoiding if and only if there
are no pair of dots $(i,j)$ and $(i',j')$ in the same triangle such that
$i<i'$ while $j>j'$.  In other words, in both triangles the dots come in
a spread from northwest to southeast, as illustrated in Figure \ref{fg:4}.
Clearly, this property is sufficient for being $321$-avoiding.  For the 
converse, suppose we have a violation in, say, the lower triangle, so there 
are dots at $(i,j)$ and $(i',j')$ where $i'>i\ge j>j'$.  In the $n-j$ columns 
east of $(i,j)$ there can be at most $n-i-1\le n-j-1$ dots south of row $i$, 
so at least one dot is located northeast of $(i,j)$, completing a 
$321$-pattern together with $(i,j)$ and $(i',j')$.

\begin{figure}[htb]
\centerline{\epsfysize=30mm\epsfbox{Fulton.fig4.ps}}
\caption{\label{fg:4}
The permutation $3142576$ is $321$-avoiding: in the upper triangle, as
well as in the lower triangle, the dots come in a strictly falling spread.
}
\end{figure}

Now, let us consider any properly dotted $r\times k$-matrix, containing
$n$ dots.  It is natural to say that such a matrix is $321$-avoiding
if it contains no triple $(i_1,j_1)$, $(i_2,j_2)$, $(i_3,j_3)$ of dots such
that $i_1<i_2<i_3$ while $j_1 > j_2 > j_3$.  If all dotless rows and
columns are omitted, we have a $321$-avoiding permutation matrix of
size $n\times n$, and it is known that there are 
$C_n = {2n \choose n} / (n+1)$ such permutation matrices, see 
the remark below Theorem \ref{th:catalan}.  
Hence, the number of $r\times k$-matrices
that are $321$-avoidingly dotted with $n$ dots is simply
${r \choose n}{k \choose n}C_n$.

However, we will be interested only in such a dotted matrix if it is
{\em extendably $321$-avoiding}, by which we mean that
it can be extended by southern rows and eastern columns, each
containing exactly one dot, such that a $321$-avoiding permutation
matrix is obtained.  (If the original matrix contained $n$ dots,
then it must be extended by $r-n$ columns, so that all
rows have dots, and $k-n$ rows, so that all columns have dots.)
Shifting viewpoint, we can reformulate the definition: extendably
$321$-avoiding matrices are the northeast submatrices of $321$-avoiding
permutation matrices.

\begin{figure}[htb]
\centerline{\epsfysize=30mm\epsfbox{Fulton.fig6.ps}}
\caption{\label{fg:6}
An extendably $321$-avoiding $4 \times 5$-matrix with three dots
(indicated with bold border), 
extended to a $321$-avoiding permutation matrix.
}
\end{figure}

We are now going to prove the following enumerative result:

\begin{theorem}\label{th:catalan}
There are 
${r+k-1 \choose n} - {r+k-1 \choose n-2}$
extendably $321$-avoiding $r \times k$-matrices with $n$ dots.
\end{theorem}

\begin{remark}\label{rm:321}
A simple manipulation gives that 
\[
{r+k-1 \choose n} - {r+k-1 \choose n-2} = 
{r+k+1-2n \over r+k+1-n}{r+k \choose n}
\]
Observe that with $r = k = n$ this formula specializes
to the Catalan numbers $C_n = {2n \choose n} / (n+1)$
counting ordinary $321$-avoiding permutations.  See Knuth \cite[p. 64]{Kn}.
Several proofs of this are collected in Stanley \cite[exerc. 17(p)]{St2}.
\end{remark}

If $M$ is an extendably $321$-avoiding $r \times k$-matrix with $n$ dots
(so $n\le r,k$),
let $R(M)$ denote the set of $i\in [1,r]$ such that there is a dot
in row $i$ in the {\em lower} triangle, and let $K(M)$ denote the set of
$j\in [2,k]$ such that there is a dot in column $j$ in the {\em upper} 
triangle.

\begin{lemma}\label{lm:RMKM}
An extendably $321$-avoiding dotted matrix $M$ is determined by the pair
$(R(M),K(M))$.
\end{lemma}
\begin{proof}
Recall the characterization of $321$-avoiding permutation matrices as
having falling spreads in both the upper and lower triangles.
Thus, when $M$ is extended, no new dot may be placed north of any
dot in the upper triangle, so $M$ must have no such empty row.
Hence, the first dot in the upper triangle (i.e. the dot with the lowest
column coordinate in $K(M)$) must have the lowest row coordinate {\em not} 
contained in $R(M)$, the next dot must have the next such coordinates etc.  
Analogously for the lower triangle.
\end{proof}

We obviously have $|R(M)|+|K(M)|=n$, since the terms count the dots
in the lower and upper triangles respectively.  Since $R(M)$ is a 
subset of $[1,r]$ and $K(M)$ is a subset of $[2,k]$, we can
choose a pair $(R(M),K(M))$ of correct cardinality in ${r+k-1 \choose n}$
ways, explaining the first term of Theorem \ref{th:catalan}.  
However, not all such pairs are good for determining an
extendably $321$-avoiding matrix.  In order to prove Theorem \ref{th:catalan}
we must show that the number of bad pairs is ${r+k-1 \choose n-2}$.

We shall use the following model to represent the pair $(R,K)$:
Distribute $n$ chips on one set of $r$ squares indexed 
${\bf r}_1,{\bf r}_2,\ldots, {\bf r}_r$
and one set of $k-1$ squares indexed ${\bf k}_2,{\bf k}_3,\ldots, {\bf k}_k$,
such that there is a chip at ${\bf r}_i$ if $i\in R$, and a 
chip at ${\bf k}_j$ if $j\in K$.  
A pair $(R,K)$ is bad if the algorithm for retrieving the matrix (in the
proof of the lemma above) fails, that is, if it produces a dot in
the lower triangle with column coordinate in $K$ (so that the dot
should have been the upper triangle), or vice versa.  

Suppose that there is a dot in the lower
triangle at $(i+1,j+1)$, $i\ge j$, with $j+1\in K$.  This corresponds
exactly to a chip at ${\bf k}_{j+1}$ and in total $i$ chips at squares 
${\bf r}_1,\dots, {\bf r}_i, {\bf k}_2,\ldots,{\bf k}_j$.  
There are never more than one chip at each square.
Since $i\ge j$ there must be at least $j$ chips at squares 
${\bf r}_1,\dots, {\bf r}_j, {\bf k}_2,\ldots,{\bf k}_j$.  
It is then easy to see that this implies that there must exist some 
{\em least} j such that there is a chip at ${\bf k}_{j+1}$ and exactly
$j$ chips at squares
${\bf r}_1,\dots, {\bf r}_j, {\bf k}_2,\ldots,{\bf k}_j$.  
This same situation must, by a similar argument, occur also in the case of 
a dot in the upper triangle that should have been in the lower triangle.
Hence, bad chips distributions are characterized as containing this
situation.  

We shall now play the following game from the bad situation above:
Place your left hand above square ${\bf r}_j$ and your right hand above
 square ${\bf k}_{j+1}$.  
The playing rule is:

\begin{enumerate}
\item{} If there are chips in both current squares, they are picked up, 
one in each hand.
\item{} If both current squares are empty, each hand drops a chip in the 
squares.
\item{} If there is one chip in total in the two current squares, then nothing 
is done.
\end{enumerate}
After each step, move both hands to the squares
with index one less and repeat the process. 

\begin{figure}[htb]
\centerline{\epsfysize=24mm\epsfbox{Fulton.fig7.ps}}
\caption{\label{fg:7}
The game played from a bad situation.  The left squares are
$\{{\bf r}_1,{\bf r}_2,{\bf r}_3,{\bf r}_4\}$, the right squares are
$\{{\bf k}_2,{\bf k}_3,{\bf k}_4,{\bf k}_5\}$.
}
\end{figure}


Since $j$ was minimal for a bad situation, we know that there must be
chips in both squares ${\bf r}_j$ and ${\bf k}_{j+1}$ so the first step
will be of type 1.  For the remaining $j-1$ steps we know there are
exactly $j-1$ chips on the squares; thus, for every pair that is emptied,
there will be an empty pair that is filled.  Therefore, after playing
up to ${\bf r}_1$ and ${\bf k}_2$, we will still have one chip left in each
hand, and hence $n-2$ chips distributed on the squares.

The process can be reversed; there are ${r+k-1 \choose n-2}$ possible
distributions of $n-2$ chips with at most one chip at each square.
Take two additional chips, one in each hand, and start playing the inverse
game, which incidentally have the same rules but starts at squares
${\bf r}_1$ and ${\bf k}_2$ and moves on to increasing indices.  As
soon as the hands are emptied, the game stops.  (This must happen
before we run out of squares, thanks to the condition that both $r$ and
$k$ must be greater than or equal to $n$.)  When the game stops, say at
squares ${\bf r}_j$ and ${\bf k}_{j+1}$, we have obtained a chips distribution
with a 'bad situation'.  Hence, we have obtained a bijection between
such bad distributions and the set of distributions of $n-2$ chips.
This completes the proof of Theorem \ref{th:catalan}. \qed



\section{Enumerative aspects of the essential set}
\label{sc:one}
The combinatorial object that we are studying is the essential set
of a permutation, together with its rank function.  They are
defined as follows.  First, let every permutation $w\in S_n$ be
represented by its dotted permutation matrix, regarded
as an $n \times n$-collection of squares in the plane, where square
$(i, w(i))$ has a dot for all $i\in [1,n]$, and all other squares are
white, so there is exactly one dot in each row and column.

We get the {\em diagram} of the permutation  by shading the squares 
in each row from the dot and eastwards, and shading the squares in each
column from the dot and southwards. The diagram is defined as
the unshaded region after this operation.  The standard reference on 
diagrams and Schubert polynomials is Macdonald's book \cite{Ma}. 

We call a white square a {\em white corner} if it has no white
neighbor neither to the east nor to the south.  In other words, the white 
corners are the southeast corners of the components of the diagram.
The {\em essential set} $\Ess(w)$ of a permutation $w$ is defined to be the set
of white corners of the diagram of $w$.

For every white corner $(i,j)$ of $w$, its {\em rank} is defined by
\[
r_w(i,j) \DEF \#\{\mbox{ dots northwest of } (i,j)\}
 = \#\{(i',j') \mbox{ with dot } : i'\le i, j'\le j\}
\]
A fundamental property of the ranked essential set of $w$  is that it uniquely
determines $w$.

\begin{figure}[htb]
\centerline{\epsfysize=45mm\epsfbox{Fulton.fig1.ps}}
\caption{\label{fg:1}
Diagram and ranked essential set of the permutation $4271635$.}
\end{figure}

All concepts should be evident from Figure \ref{fg:1}.  Answering a 
question of Fulton, a characterization of the class of ranked sets of squares
that arise as essential sets of permutations was given by Eriksson and 
Linusson \cite{EL}:  

\begin{theorem}[Eriksson and Linusson \cite{EL}]\label{th:MAIN}
Let $E\subseteq [1,n]\times [1,n]$ be a set of squares with rank 
function $r(i,j)$.  Add the squares $(0,n)$ and $(n,0)$ to 
$E$ both with rank zero.
$E\backslash \{(0,n),(n,0)\}$ is the essential set
of an $n\times n$ permutation matrix if and only if:
\begin{itemize}
\item[C1.] For each $(i,j)\in E$ we have 
\begin{enumerate}
\begin{enumerate}
\item{} $r(i,j)\ge 0$ and 
\item{} $r^\SE(i,j)\ge 0$. 
\end{enumerate}
\end{enumerate}
\item[C2.] For every pair $(i,j),(i',j')\in E$ such that $i\ge i',j\le j'$
and $E\cap [i',i]\times [j,j']=\{(i,j),(i',j')\}$  we have 
\begin{enumerate}
\begin{enumerate}
\item{} $r^\NE(i,j)-r^\NE(i',j')\ge 1$ and
\item{} $r^\SW(i',j')-r^\SW(i,j)\ge 1$.
\end{enumerate}
\end{enumerate}
\item[C3.]  For every pair $(i,j),(i',j')\in E$ such that $i<i',j<j'$
and $E\cap [i+1,i']\times [j+1,j']=\{(i',j')\}$,
let $(i'',j'')\in E $ be the square of $ E $ with
the largest $i''$ satisfying $i''\le i$, $j''\ge j'$ and 
$ E \cap [i'',i]\times[j',j'']=\{(i'',j'')\}$;
symmetrically, let $(i''',j''')$ be the square of $ E $ with
the largest $j'''$ satisfying $j'''\le j$, $i'''\ge i'$ and 
$ E \cap [i',i''']\times [j''',j]=\{(i''',j''')\}$. 
We have
\[
r(i',j')\ge r(i,j)+r^\NE(i,j)+r^\SW(i,j)-r^\NE(i'',j'')-r^\SW(i''',j''').
\]
\end{itemize}
\end{theorem}

The alternative rank functions $r^\NE$, $r^\SW$ and $r^\SE$ are defined
by:
\[
r^\NE(i,j)\DEF i-r(i,j) = \#\{\mbox{ dots northeast of } (i,j)\},
\]
\[
r^\SW(i,j)\DEF j-r(i,j)  = \#\{\mbox{ dots southwest of } (i,j)\},
\]
\[
r^\SE(i,j)\DEF n-(i+j)+r(i,j) = \#\{\mbox{ dots southeast of } (i,j)\}
\]
As mentioned in Macdonald's book \cite{Ma}, the white squares of the 
diagram of a permutation $w$ correspond exactly to the inversions of
$w$: $(i ,j)$ is a white square exactly when both $w(i)>j$ and $i<w^{-1}(j)$.  
As observed by Fulton, every row with a white corner corresponds to a descent: 
if $(i,j)$ is a white corner, then $w(i+1)\le j$ while $w(i)>j$, so 
$w(i+1)<w(i)$; conversely, if $w(i+1)<w(i)$, then the square $(i, w(i+1))$ 
must be white, so there must be a white corner in row $i$.

\subsection{Arbitrary permutations}
We shall begin by studying the distribution of ranks of white
corners for arbitrary permutations in $S_n$.
Define $P_n(x)$ to be the polynomial that keeps track of the distribution 
of ranks:
\[
P_n(x) \DEF \sum_{w\in S_n} \sum_{c\in \Ess(w)} x^{r_w(c)}
\]
Define $P^\NE_n(x)$, $P^\SW_n(x)$ and $P^\SE_n(x)$ in the analogous way,
that is, with the rank function taken to be $r_w^\NE$, $r_w^\SW$ and
 $r_w^\SE$ respectively.
We shall prove that $P^\SW_n(x) = P^\NE_n(x)$ and, more surprisingly,
$P_n(x) = P^\SE_n(x)$ by considering the two involutions $w\mapsto w^{-1}$ 
(transposition of the permutation matrix) and $w\mapsto \rt w$ (rotation of 
the matrix $180^\circ$).

\begin{lemma}
By transposition, we have 
\[
\sum_{c\in \Ess(w)} x^{r^\NE_w(c)} = 
\sum_{c\in \Ess(w^{-1})} x^{r_{w^{-1}}^\SW(c)},
\]
and hence $P^\SW_n(x) = P^\NE_n(x)$. By rotation $180^\circ$, we have
\[
\sum_{c\in \Ess(w)} x^{r_w(c)} = 
\sum_{c\in \Ess(\rt w)} x^{r_{\rt w}^\SE(c)},
\]
and hence $P^\SE_n(x) = P_n(x)$. 
\end{lemma}
\begin{proof}
Clearly, transposition of the permutation matrix induces a transposition
of the set of ranked white corners, and then the first statement follows from
the definitions of $r^\NE_w$ and $r^\SW_w$.

Similarly, for the second statement it is enough to prove that if $(i,j)$
is a white corner in $w$, then $(n-i,n-j)$ must be a white corner in $\rt w$,
since, by the definitions, $r_w(i,j) = r^\SE_{\rt w}(n-i, n-j)$. 
First note that the square $(i,j)$ of the permutation matrix is mapped to 
$n-i+1, n-j+1$ under rotation.
If $(i,j)$ is a white corner of the diagram of $w$, 
we know that the dots in rows $i$ and $i+1$
and in columns $j$ and $j+1$ must be placed in squares $(i,c)$, $(i+1,c')$,
$(r,j)$ and $(r',j+1)$ respectively, where $c>j$, $c'\le j$, $r>i$ and
$r' \le i$.  After rotation of the permutation matrix, this means that $\rt w$
has dots in squares 
$(n-i, n-c'+1)$, $(n-i+1, n-c+1)$, $(n-r'+1, n-j)$, $(n-r+1, n-j+1)$,
and the inequalities above give that this dot placement makes $(n-i,n-j)$
a white corner of the diagram of $\rt w$.
\end{proof}

In Table \ref{tb:1} and Table \ref{tb:2} we have tabulated the 
polynomials $P_n(x)$ and $P^\NE_n(x)$  for small $n$.  
The value of $P_n(1)$ is of course the sum of the coefficients, 
which is equal to the total number of white corners of all permutations 
in $S_n$, so in particular $P_n(1)= P^\NE_n(1)$.


\begin{table}[htb]
\begin{tabular}{||r|l|r||}	
\hline
$n$ & $P_n(x) $ & $P_n(1)$ \\
\hline
\hline
 2 & $ 1   $ & 1 \\
\hline
 3 & $ 5 +1x  $ & 6 \\
\hline
 4 & $ 26 +9x +2x^2  $ & 37 \\
\hline
 5 & $ 154 +70x +26x^2 +6x^3  $ & 256 \\
\hline
 6 & $1044 +562x +268x^2 +102x^3 +24x^4  $ & 2000 \\
\hline
 7 & $ 8028 +4860x +2700x^2 +1308x^3 +504x^4 +120x^5  $ & 17520 \\
\hline
8 & $ 69264 +45756x + 28224x^2+ 15828x^3+ 7728x^4+ 3000x^5+ 720x^6$ & 170520 \\
\hline
\end{tabular}
\caption{\label{tb:1} Table of $P_n(x)$, the rank generating function for 
white corners of $S_n$.}
\end{table}



\begin{theorem}\label{th:pn1}
The total number of white corners in $S_n$ is 
\[
P_n(1) = (n-1)!{{n-1 \choose 3} + 6{n \choose 2} \over 6}.
\]
By dividing with $n!$, the number of permutations in $S_n$,
we obtain 
\[
{{n-1 \choose 3} + 6{n \choose 2} \over 6n}
\]
as the average number of white squares.
\end{theorem}
\begin{proof}
 When is $(i,j)$ a white corner?  There are four cases:
 
 {\em Case 1: } Dots in $(i+1,j)$ and $(i,j+1)$.  The $n-2$ dots
 that are left can be placed in $(n-2)!$ ways.
 
 {\em Case 2: } Dots in $(i+d_1,j)$, $(i+1,j-d_2)$ 
 and $(i,j+1)$, where 
 $d_1\in [1,n-(i+1)]$ and $d_2\in [1,j-1]$.  The $n-3$ dots
 that are left can be placed in $(n-3)!$ ways.
 
 {\em Case 3: } Dots in $(i,j+d'_1)$, $(i-d'_2,j+1)$ and $(i+1,j)$, where 
 $d'_1\in [1,n-(j+1)]$ and $d'_2\in [1,i-1]$.  The $n-3$ dots
 that are left can be placed in $(n-3)!$ ways.
 
 {\em Case 4: } Dots in $(i+d_1,j)$, $(i+1,j-d_2)$, $(i,j+d'_1)$, and
 $(i-d'_2,j+1)$, where $d_1\in [1,n-(i+1)]$, $d_2\in [1,j-1]$,
 $d'_1\in [1,n-(j+1)]$ and $d'_2\in [1,i-1]$.  The $n-4$ dots
 that are left can be placed in $(n-4)!$ ways.
 
 Hence, the total number of white corners will be the sum of the
 number of occurrences of each square as a white corner:
 \[
 P_n(1) = \sum_{i=1}^{n-1} \sum_{j=1}^{n-1} 
 [(n-2)!+(n-(i+1))(j-1)(n-3)!+(n-(j+1))(i-1)(n-3)!+
 \]
 \[
 +(n-(i+1))(j-1)(n-(j+1))(i-1)(n-4)! ]
 \]
 By standard summation formulas, this sums up to
  $(n-1)!({n-1 \choose 3} + 6{n \choose 2})/ 6$.
\end{proof}


Returning to the table for $P_n(x)$, one might or might not be
familiar with the sequence $1, 5, 26, 154, 1044, 8028, \ldots$
of the values of $P_n(0)$, that is, the constant terms.
They are obtained as a weighted sum of (signless) Stirling numbers of the
first kind, as we shall see.  Following Stanley \cite{St},
we denote these Stirling numbers by $c(n,k)$, defined as the number
of permutations $w\in S_n$ with exactly $k$ cycles.

\begin{proposition}
The number of rank zero white corners of permutations in $S_n$ is
\[
P_n(0) = \sum_{k=0}^n (k-1)c(n,k).
\]
\end{proposition}
\begin{proof}
There is a white corner with rank zero in row $i$ precisely when
the dot in row $i+1$ is to the left of all previous dots, that is,
precisely $w(i+1)$ is a left-to-right minimum of $w$ on word-form,
other than the first element of the word, which is trivially a 
left-to-right minimum.  Stanley
\cite{St} gives a simple bijection from $S_n$ to $S_n$ that takes
permutations with $k$ left-to-right minima to permutations with
$k$ cycles.  Thus, instead of summing the number of rank zero white
corners, we may sum the number of cycles minus one, and
\[
\sum_{w\in S_n} (-1+\mbox{ \# of cycles in } w) =  \sum_{k=0}^n (k-1)c(n,k).
\]
\end{proof}

Let us now shift attention to the northeast-rank function $r_w^\NE$ and
Table \ref{tb:2}.

\begin{table}[htb]
\begin{tabular}{||r|l||}	
\hline
$n$ & $P^\NE_n(x) $  \\
\hline
\hline
 2 &   $1x  $ \\
\hline
 3 &   $4x+ 2x^2   $ \\
\hline
 4 &   $19x+ 12x^2+ 6x^3  $ \\
\hline
 5 &   $108x+ 76x^2+ 48x^3 +24x^4  $ \\
\hline
 6 &   $718x+ 544x^2+ 378x^3+ 240x^4+ 120x^5 $ \\
\hline
 7 &   $5472x+ 4392x^2+ 3240x^3+ 2256x^4+ 1440x^5+ 720x^6   $ \\
\hline
 8 &   $47052x+ 39600x^2+ 30564x^3+ 22464x^4+ 15720x^5+ 10080x^6+ 5040x^7$ \\
\hline
\end{tabular}
\caption{\label{tb:2} 
Table of  $P^\NE_n(x)$, the northeast-rank generating function for 
white corners of $S_n$.}
\end{table}

In the table of $P^\NE_n(x)=a_{n-1}x+a_{n-2}x^2+\ldots + a_1x^{n-1}$ one 
recognizes that $a_1 = (n-1)!$, $a_2 = 2a_1$, and for the other coefficients 
we have that $a_k>ka_1$.  This behavior is explained by the following 
proposition.





\begin{proposition}\label{pr:descents}
Let $\Ess'(w)$ be the set of white corners of $w$ that are the
{\em last} white corners in their rows.  Then for $1\le t<n$,
\[
\sum_{w\in S_n} \mbox{ \# } \{c\in \Ess'(w) : r_w^\SW(c)=t\} = (n-t)(n-1)!
\]
\end{proposition}
\begin{proof}
We will prove the proposition by induction on $n$.  It is trivially true
for $n=2$.  Given a permutation matrix $w\in S_n$, we remove the first 
row and the column of the dot
in the first row and glue together the two pieces to get a new
permutation matrix $w'\in S_{n-1}$.  The set of white corners last in a 
row and their southwest ranks are the same for $w$ and $w'$ except for
a possible white corner on the first row of $w$.  When applied to all 
the $(n-1)!$ permutation matrices in $S_n$ with a dot 
in $(1,j)$ for a fix $j$, the procedure
gives all permutation matrices in $S_{n-1}$ once.  There is a white corner
at position $(1,j-1)$ if and only if the dot on the second row is
in one of the first $j-1$ columns.  Hence there are $(j-1)(n-2)!$ of those
with $r^\SW(1,j-1)=j-1$.
Summing over all $j$ we get, by induction,
\[
\sum_{w\in S_n} \mbox{ \# }\{ c\in \Ess'(w) : r_w^\SW(c)=t\} =
(n-1-t)(n-2)!n+t(n-2)!= (n-t)(n-1)!
\]
\end{proof}
\begin{remark}
Observe the interpretation of Proposition \ref{pr:descents}
in terms of descents that follows from
\[
r_w^\SW(i,j)= \mbox{\# } \{k>i:w(k)<w(i)\}.
\]
For a given descent $w(i)>w(i+1)$ we have that $r_w^\SW(i,j)$ counts the 
number of inversions having $w(i)$ as the larger element.
Looking at all possible descents in all permutations of
$S_n$, the number of them having exactly $t$ smaller elements later in the 
permutation is $(n-t)(n-1)!$. 

In the statement of Proposition \ref{pr:descents} we can replace 
"last in their rows" and $r^\SW$ with "first in their rows" and $r^\NE$.  
This can be proven easily by the $180^\circ$ rotation operator $\rt$ 
introduced above.  
We then get a corresponding interpretation in terms of descents:   Looking 
at the smaller element in all descents in all permutations of
$S_n$, the number of them having exactly $t$ larger elements earlier in the 
permutation is $(n-t)(n-1)!$.   

Using the transposition instead, we get a statement about the white corners 
last or first in their columns.
\end{remark}



\subsection{321-avoiding permutations}\label{ssc:321}
We will here consider the essential set of $321$-avoiding permutations.

Define $A_n(x)$ (and $A^\NE_n(x)$ etc. in analogy) by summing the
ranked white squares over all $321$-avoiding permutations.  It
should be quite obvious that the property of being $321$-avoiding
is invariant under transposition and rotation, so once again we have
the identitites  $A_n(x) = A_n^\SE(x)$ and $A^\NE_n(x)=A_n^\SW(x)$.

\begin{table}[htb]
\begin{tabular}{||r|l|r||}	
\hline
$n$ & $A_n(x) $ & $A_n(1)$ \\
\hline
\hline
$2$ & $1  $ & 1 \\
\hline
$3$ & $3+ 1x  $ & 4 \\
\hline
$4$ & $9+ 5x + 2x^2   $ & 16 \\
\hline
$5$ & $28+ 19x + 12x^2 + 5x^3   $ & 64 \\
\hline
$6$ & $90+ 68x + 51x^2 + 33x^3 + 14x^4  $ & 256 \\
\hline
$7$ & $297+ 240x + 197x^2 + 150x^3 + 98x^4 + 42x^5  $ & 1024 \\
\hline
$8$ & $1001+ 847x + 735x^2 + 609x^3 + 466x^4 + 306x^5 + 132x^6   $ & 4096 \\
\hline
\end{tabular}
\caption{\label{tb:3}
Table of $A_n(x)$, the rank generating function for white corners of
$321$-avoiding permutations in $S_n$.}
\end{table}

In the table of $A_n(x)$, one can observe (at least) three things: 
first, $A_n(1)$ is a power of four; second, the coefficients of the 
highest-degree terms are the Catalan numbers; third, the constant terms 
$A_n(0)$ is equal to $3(n-1)^{-1}{2n-2 \choose n}$.  The two latter
observations have unexciting proofs, which we omit.  The first
observation is explained better from the Table \ref{tb:4}.

\begin{table}[htb]
\begin{tabular}{||r|l||}	
\hline
$n$ & $A^\NE_n(x) $  \\
\hline
\hline
$2$ & $ 1x   $  \\
\hline
$3$ & $ 3x+ 1x^2    $  \\
\hline
$4$ & $ 10x+ 5x^2 + 1x^3    $  \\
\hline
$5$ & $ 35x+ 21x^2 + 7x^3 + 1x^4    $  \\
\hline
$6$ & $ 126x+ 84x^2 + 36x^3 + 9x^4 + 1x^5    $  \\
\hline
$7$ & $ 462x+ 330x^2 + 165x^3 + 55x^4 + 11x^5 + 1x^6    $  \\
\hline
$8$ & $ 1716x+ 1287x^2 + 715x^3 + 286x^4 + 78x^5 + 13x^6 + 1x^7 $ \\
\hline
\end{tabular}
\caption{\label{tb:4} 
Table of $A^\NE_n(x)$, the northeast-rank generating function for 
white corners of $321$-avoiding permutations in $S_n$.}
\end{table}

In Table \ref{tb:4} one quickly recognizes binomial coefficients from
every other row of Pascal's triangle.  We have the following result,
the proof of which is quite long and hard.

\begin{lemma}\label{lm:pascal}
The coefficients of $A^\NE_n(x)$ come from the last half of row
$2n-3$ of Pascal's triangle, that is,
\[
A^\NE_n(x) = \sum_{r=1}^{n-1} {2n-3 \choose n-1-r}x^r.
\]
\end{lemma}

By summing these binomial coefficients, we immediately get a proof of the
appealing result that the we conjectured from the first table:

\begin{theorem}
The total number of white corners in $321$-avoiding permutations
in $S_n$ is 
\[
A_n(1) = A^\NE_n(1) = 2^{2n-4}.
\]
By dividing by $C_n$, the number of $321$-avoiding permutations in
$S_n$, we get the average size of the essential set to be
\[
{2^{2n-4} \over C_n} \sim {\sqrt{\pi} \over 16} n^{3/2}
\]
\end{theorem}

Now let us proceed with the proof of Lemma \ref{lm:pascal}, which
stated that the total number of white corners ranked $r$ in the set
of all $321$-avoiding permutations in $S_n$ is
${2n-3 \choose n-1-r}$. Here, ``rank'' will always refer to the 
northeast-rank $r^\NE(i,j)$ that counts the number of dots northeast 
of $(i,j)$.

Our approach will be to count the number of $321$-avoiding permutations
in $S_n$ that has a rank $r$ white corner in a given square $(i,j)$.
What will such a permutation matrix look like?  It will be convenient
in this context to define $(i,j)^\NE$ to be the square such that the
area to the northeast, where the rank function count the dots, 
is an $i \times j$-rectangle, see Figure \ref{fg:4areas}.

\begin{figure}[htb]
\centerline{\epsfysize=55mm\epsfbox{Fulton.fig5.ps}}
\caption{\label{fg:4areas}
A $321$-avoiding permutation with a northeast-rank $r$ white corner at 
$(i,j)^\NE$.}
\end{figure}

The bold-marked square is $(i,j)^\NE$.
In the striped areas, that is, in the squares north of $(i,j)^\NE$ in the
same column and south of $(i,j)^\NE$ in the next column, as well as in
the squares west of $(i,j)^\NE$ in the same row, and east of $(i,j)^\NE$ in 
the next row, we know there can be no dot since $(i,j)^\NE$ is a white corner.
This gives a decomposition of the rest of the matrix in four areas:
northeast, where the rank say there are $r$ dots; northwest, where
there must be a dot in every one of the first $j$ rows that does not
contain one of the $r$ counted dots, so $j-r$ dots in all; southeast,
where there must analogously be $i-r$ dots; and southwest, where the
remaining $n+r-(i+j)$ dots must be.

\begin{lemma}\label{lm:4areas}
Let $\gamma(i,j,r)$ be the number of $321$-avoiding permutations in $S_n$ that 
have a white corner at $(i,j)^\NE$  of northeast-rank $r$. Then 
$\gamma(i,j,r)$ is $0$ if $i+j>n+r-1$ and otherwise
\[
\left[ {n-2+i-j \choose i-r} - {n-2+i-j \choose i-r-1} \right]
\left[ {n-2+j-i \choose j-r} - {n-2+j-i \choose j-r-1} \right].
\]
\end{lemma}
\begin{proof}
Both the southwest and the northeast area must contain at least one dot,
which is possible only if $i+j>n+r-1$.
The permutation can be $321$-avoiding only if the dots in the 
northeast area, as well as in the southwest area, lie in a
strictly falling spread, since any violating pair would form a $321$-pattern
together with any dot in the other area.  
Thus, the positions of these dots are determined by the positioning of the 
dots in the northwest and southeast areas.  For these areas, it is easy to see 
that it is necessary and sufficient that the dot placement is extendably 
$321$-avoiding.  (For the southeast area, the extension is to the north 
and west, but it is completely analogous to the extension to the south and 
east discussed earlier.)   By Theorem \ref{th:catalan}, such a pair of 
extendably $321$-avoiding dotted rectangles can be chosen in 
$[ {n-2+i-j \choose i-r} - {n-2+i-j \choose i-r-1} ]
[ {n-2+j-i \choose j-r} - {n-2+j-i \choose j-r-1} ]$ ways.
\end{proof}

We now need to sum these numbers for all squares.  To do
this we need the following result, which we have not been able to
find in the literature but which most certainly have been discovered
many times before:  Let $F_m(x) \DEF \sum_{n} {2n+m \choose n}x^n$,
for any integer $m$.
Then \[
F_m(x) = {1 \over \sqrt{1-4x}} \left({1-\sqrt{1-4x} \over 2x}\right)^m,
\]
as can be proved by induction through clever use of the standard recurrence
for the binomial coefficients.


\begin{lemma}\label{lm:genfcn}
For any integers $k$ and $m$, the following identity holds:
\[
\sum_{n_1+n_2 = k}
 \left[{m+2n_1 \choose n_1} - {m+2n_1 \choose n_1-1}\right]
 \left[{m+2n_2 \choose n_2} - {m+2n_2 \choose n_2-1}\right] =
\]
\[
 {2m+1+2k \choose k} - {2m+1+2k \choose k-1} 
\]
\end{lemma}
\begin{proof}
The statement corresponds to the generating function identity
\[
(F_m(x)-xF_{m+2}(x))^2 = F_{2m+1}-xF_{2m+3}(x),
\]
which can be verified by direct computation from the explicit
expression for $F_m(x)$.
\end{proof}

Now we are able to sum the numbers for every diagonal, that is,
squares $(i,j)^\NE$ with fix $i+j$.

\begin{lemma}\label{lm:diag}
Fix an integer $k$ and a rank $r$.  Among all $321$-avoiding permutation
in $S_n$, the total number of northwest-rank $r$ white corners in squares 
$(i,j)^\NE$ such that $i+j=k+2r$ is $0$ if $i+j>n+r-1$, and 
${2n-3 \choose k} - {2n-3 \choose k-1}$ otherwise.
\end{lemma}
\begin{proof}
We are computing $\sum_{i+j=k+2r} \gamma(i,j,r)$.  By
Lemma \ref{lm:4areas}, and after the substitutions 
$n_1:=i-r, n_2:=j-r, m:=n-2-k$, this sum takes the form
\[
\sum_{n_1+n_2 = k}
 \left[ {m+2n_1 \choose n_1} - {m+2n_1 \choose n_1-1} \right]
 \left[ {m+2n_2 \choose n_2} - {m+2n_2 \choose n_2-1} \right]
\]
Thanks to Lemma \ref{lm:genfcn}, this is equal to
${2m+1+2k \choose k} - {2m+1+2k \choose k-1}$.  Doing the substitutions
backwards, we obtain the desired result.
\end{proof}

At last we can prove Lemma \ref{lm:pascal}.  The total number of
rank $r$ white corners is of course the sum over all the diagonals
$\{(i,j)^\NE : i+j=k+2r\}$, $k\le n+r-1$.  By Lemma \ref{lm:diag}
this is $({2n-3 \choose n+r-1} - {2n-3 \choose n+r-2})+
({2n-3 \choose n+r-2} - {2n-3 \choose n+r-3})+
({2n-3 \choose n+r-3} - {2n-3 \choose n+r-4})+\ldots$,
so all terms except for the first cancel in pairs. Hence the result
is ${2n-3 \choose n+r-1}$, as claimed. \qed


\subsection{Vexillary permutations}\label{ssc:vex}
Let $\Vex_n$ denote the set of vexillary permutations in $S_n$.
By summing only over permutations in $\Vex_n$ we get another polynomial:
\[
V_n(x) \DEF \sum_{w\in \Vex_n} \sum_{c\in \Ess(w)} x^{r_w(c)}
\]
As we did for $P_n(x)$ in the $S_n$ case, define $V^\NE_n(x)$, 
$V^\SW_n(x)$ and $V^\SE_n(x)$ in the analogous way.

The two maps on permutation matrices that we used in the lemma above
behave well on vexillary permutations; recall Fulton's description of
these as having no pair of white corners $(i,j)$ and $(i',j')$ with
$i<i'$ and $j<j'$.  Transposition of the matrix induces a transposition of
the white corners, while rotation of the 
matrix induces a rotation of the white corners with an additional
translation of $(-1,-1)$, and the vexillary property is evidently
invariant under both transposition, rotation and translation of the
pattern of white corners.  Hence, the same result holds in the vexillary
case:

\begin{lemma}
$V^\SW_n(x) = V^\NE_n(x)$, and $V^\SE_n(x) = V_n(x)$. 
\qed
\end{lemma}

Below are the tables for $V_n(x)$ and $V^\NE_n(x)$ for $n= 2,3,\ldots,8$.
$V_n(1)= V^\NE_n(1)$ is the total number of white corners of
all the permutations in $\Vex_n$, that is, of all vexillary permutations
in $S_n$.

\begin{table}[htb]
\begin{tabular}{||r|l|r||}	
\hline
$n$ & $V_n(x) $ & $V_n(1)$ \\
\hline
\hline
$2$ & $1  $ & 1 \\
\hline
$3$ & $5+ 1x  $ & 6 \\
\hline
$4$ & $25+ 9x + 1x^2   $ & 35 \\
\hline
$5$ & $133+ 65x + 13x^2 + 1x^3   $ & 212 \\
\hline
$6$ & $749+ 446x + 123x^2 + 17x^3 + 1x^4  $ & 1336 \\
\hline
$7$ & $4422+ 3034x + 1039x^2 + 199x^3 + 21x^4 + 1x^5  $ & 8716 \\
\hline
$8$ & $27147+ 20752x + 8342x^2 + 2000x^3 + 293x^4 + 25x^5 + 1x^6   $ & 58560 \\
\hline
\end{tabular}
\caption{Table of $V_n(x)$, the rank generating function for 
white corners of $\Vex_n$}
\end{table}

\begin{remark}\label{rm:vex}
We would like very much an expression for $V_n(1)$, the total number of
white corners of permutations in $\Vex_n$, but it has eluded us. By using
the same approach as for $321$-avoiding permutations in section 
\ref{ssc:321} one easily proves that
\[
V_n(x) = \sum_{(i,j)\in [1,n]\times [1,n]} \sum_{r=0}^{n-2} 
         v(i,n-j,i-m)v(j,n-i,j-m),
\]
where $v(i,j,m)$ is the number of $i\times j$-matrices properly dotted with
$m$ dots such that (1) there is a dot in row $i$ and in column $1$; and
(2) by extending the matrix with dotted columns to the {\em west} and
dotted rows to the {\em south}, a vexillary permutation matrix can be
obtained.  However, since $v(n,n,n)=|\Vex_n|$, these numbers are evidently 
not easy to come by, see the remark at the end of this paper.
\end{remark}

  From observation in the table, we can at least state the following
conjecture with a fair degree of certitude.

\begin{conjecture}\label{cn:pol}
For fixed integer $k\ge 2$ and variable $n$, the 
coefficient of $x^{n-k}$ in $V_n(x)$ can be expressed as a polynomial
in $n$ of degree $k-2$.
\end{conjecture}

We have been able to prove this for $k=2$ and $k=3$.

\begin{table}[htb]
\begin{tabular}{||r|l||}	
\hline
$n$ & $V^\NE_n(x) $  \\
\hline
\hline
$2$ & $ 1x   $  \\
\hline
$3$ & $ 4x+ 2x^2    $  \\
\hline
$4$ & $ 17x+ 12x^2 + 6x^3    $  \\
\hline
$5$ & $ 80x+ 63x^2 + 46x^3 + 23x^4    $  \\
\hline
$6$ & $ 410x+ 339x^2 + 278x^3 + 206x^4 + 103x^5    $  \\
\hline
$7$ & $ 2248x+ 1910x^2 + 1644x^3 + 1375x^4 + 1026x^5 + 513x^6    $  \\
\hline
$8$ & $ 13006x+ 11245x^2 + 9931x^3 + 8722x^4 + 7373x^5 + 5522x^6 + 2761x^7 $ \\
\hline
\end{tabular}
\caption{Table of $V^\NE_n(x)$, the northeast-rank generating function 
for white corners of $\Vex_n$}
\end{table}

For $V_n^\NE(x)$ at least we have obtained some partial results.
Let $v_n$ denote $|\Vex_n|$, the number of permutations in $S_n$ that are
vexillary. The number sequence $v_1,v_2,v_3,\dots$ starts 
1, 2, 6, 23, 103, 513, \dots, see the remark below.

\begin{proposition}\label{pr:vn}
In $V_n^\NE(x)$, the coefficients of $x^{n-1}$ and $x^{n-2}$
are $v_{n-1}$ and $2v_{n-1}$ respectively.
\end{proposition}
\begin{proof}
The only possibility for a white corner $c$ with $r^\NE(c)=n-1$ is
$c=(n-1,1)$ in which case the dot of column $1$ is in $(n,1)$.  But then
the permutation is vexillary if and only if the permutation submatrix
$[1,n-1]\times [2,n]$ is vexillary, that is, having the white corners
in a spread from southwest to northeast.  Hence, there are $v_{n-1}$
white corners $c$ with $r^\NE(c)=n-1$  among vexillary $n$-permutations.

For northeast-rank $n-2$ white corners, the reasoning is almost similar
but in several cases.  We simply sketch it here:
Either there is a dot in $(n-1,1)$, in which case the permutation will be
vexillary precisely when the submatrix where row $n-1$ and column $1$ are
deleted is vexillary. There are $v_{n-1}$ of these, and we will always get
a white corner of northeast-rank $n-2$ in row $n-2$.
Similarly, we get $v_{n-1}$ permutations with the white corner in column
$2$ when there is a dot in $(n,2)$.  Now we have counted twice the
cases with dots both in $(n-1,1)$ and $(n,2)$, so these must be subtracted,
but they correspond bijectively to the cases where there are dots in $(n,1)$
and $(n-1,2)$, and these shall be added since they give a white corner of
proper rank in $(n-2,2)$.  These are all cases, so we get in all $2v_{n-1}$
white corners of northeast-rank $n-2$.
\end{proof}


\begin{remark}\label{rm:vn}
There is no really nice formula known for $v_n$.  However, J. West
has proved the formula 
$v_n = \sum_{|\lambda|=n, l(\lambda)\le 3} (f^\lambda)^2$; the interested
reader is refered to Macdonald \cite[p. 22]{Ma}, where the above formula,
combined with results of A. Regev, is said to imply the following
asymptotic: $v_n \sim c{9^n \over n^4}$, 
where $c$ is some constant.
\end{remark}

{ $^1$ Stockholm University, Stockholm, Sweden; 
kimmo@nada.kth.se}

{ $^2$ KTH, Stockholm, Sweden; linusson@math.kth.se}

\begin{thebibliography}{ABC}
 
\bibitem{BJS} S. Billey, W. Jockusch, and R. P. Stanley, {\em Combinatorial
properties of Schubert polynomials}, J. Algebraic Comb. {\bf 2} (1993), 
345--374.

\bibitem{EL} K. Eriksson and S. Linusson, {\em Combinatorics of Fulton's
essential set}, preprint, 1994.

\bibitem{Fu} W. Fulton, {\em Flags, Schubert polynomials, degeneracy loci, and
determinantal formulas}, Duke Math. J. {\bf 65} (1992), 381--420.

\bibitem{Kn} D. E. Knuth, {\em The Art of Computer Programming, vol. 3}, 
Addison-Wesley, Reading, MA, 1973.

\bibitem{Ma} I. G. Macdonald, {\em Notes on Schubert polynomials}, 
D\'epartement de math\'e\-mathiques et d'informatique, Universit\'e du
Qu\'ebec, Montr\'eal, 1991.

\bibitem{St} R. P. Stanley, {\em Enumerative combinatorics vol. 1}, 
Wadsworth \& Brooks/Cole, Belmont, CA, 1986.

\bibitem{St2} R. P. Stanley, {\em Enumerative combinatorics vol. 2}, 
book manuscript, 1994.

\bibitem{We} J. West, PhD thesis, MIT (1992).

\end{thebibliography}
\end{document} 
