\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 $ij$ 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