\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_1w(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 $ij'$. 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 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*j$ and $ij$, so
$w(i+1)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 ti:w(k)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*