Notes on Schubert Polynomials
Chapter 1

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 25 June 2013

Permutations

For each integer $n\ge 1,$ let $S_n$ denote the symmetric group of degree $n,$ that is to say the group of all permutations of the set $[1,n]=\{1,2,\dots ,n\}\text{.}$ Each $w\in S_n$ is a mapping of $[1,n]$ onto itself. As is customary, we write all mappings on the left of their arguments, so that the image of $i\in [1,n]$ under $w$ is $w\left(i\right)\text{.}$ We shall sometimes denote $w$ by the sequence $(w\left(1\right),w\left(2\right),\dots ,w\left(n\right))\text{.}$ Thus for example $\left(53214\right)$ is the element of $S_5$ that sends 1 to 5, 2 to 3, 3 to 2, 4 to 1 and 5 to 4.

For $i=1,2,\dots ,n-1$ let $s_i$ denote the transposition that interchanges $i$ and $i+1,$ and fixes all other elements of $[1,n]\text{.}$ We have

$$\begin{array}{cc}\text{(1.1)}& \{\begin{array}{cc}{s}_i^2=1,& \\ s_i{s}_j=s_j{s}_i& \text{if}\hspace{0.17em}|i-j|>1,\\ s_i{s}_{i+1}{s}_i=s_{i+1}{s}_i{s}_{i+1}& (1\le i\le n-2)\text{.}\end{array}\end{array}$$

Also, for each $w\in S_n,$ let

$$I\left(w\right)=\{(i,j):1\le i<j\le n\hspace{0.17em}\text{and}\hspace{0.17em}w\left(i\right)>w\left(j\right)\}\text{.}$$

We regard $I\left(w\right)$ as a subset of the square ${\Sigma }_n=[1,n]\times [1,n]\text{,}$ and we shall adopt the convention of matrices, that in ${\Sigma }_n$ the first coordinate increases from north to south, and the second coordinate from west to east. The group $S_n\times S_n$ acts on ${\Sigma }_n:(u\times v)(i,j)=(u\left(i\right),v\left(j\right))\text{.}$ In particular, $S_n$ acts diagonally: $w(i,j)=(w\times w)(i,j)=(w\left(i\right),w\left(j\right))\text{.}$

Let $w\in S_n,$ $1\le r\le n-1\text{.}$ Then $w{s}_r$ is the permutation

$$(w\left(1\right),\dots ,w(r+1),w\left(r\right),\dots ,w\left(n\right))$$

and it is clear that

$$\begin{array}{cc}\text{(1.2)}& I\left(w{s}_r\right)=\{\begin{array}{cc}{s}_{r}I\left(w\right)\cup \left\{(r,r+1)\right\}& \text{if}\hspace{0.17em}w\left(r\right)<w(r+1),\\ s_{r}I\left(w\right)-\left\{(r+1,r)\right\}& \text{if}\hspace{0.17em}w\left(r\right)>w(r+1)\text{.}\end{array}\end{array}$$

Let $\ell \left(w\right)=\text{Card}\hspace{0.17em}I\left(w\right)\text{.}$ Then from (1.2) we have

$$\begin{array}{cc}\text{(1.3)}& \ell \left(w{s}_r\right)=\{\begin{array}{cc}\ell \left(w\right)+1& \text{if}w\left(r\right)<w(r+1),\\ \ell \left(w\right)-1& \text{if}w\left(r\right)>w(r+1)\text{.}\end{array}\end{array}$$

(1.4) $s_1,\dots ,s_{n-1}$ generate the group $S_n\text{.}$

		Proof.
	We shall show by induction on $\ell \left(w\right)$ that each $w\in S_n$ is a product of $s\text{'s.}$ If $\ell \left(w\right)=0,$ then $w=1$ and there is nothing to prove. If $\ell \left(w\right)>0$ then $w\left(r\right)>w(r+1)$ for some $r,$ and hence $\ell \left(w{s}_r\right)=\ell \left(w\right)-1$ by (1.3). Hence $w{s}_r=s_{a_1}\dots s_{a_p}$ say, and therefore (as $s_r^2=1\text{)}$ $w=s_{a_1}\dots s_{a_p}{s}_r\text{.}$ $\square$

For each $w\in S_n\text{.}$ the length of $w$ is the minimal length of a sequence $(a_1,\dots ,a_p)$ such that $w=s_{a_1}\dots s_{a_p}\text{.}$

(1.5) The length of $w\in S_n$ is equal to $\ell \left(w\right)=\text{Card}\hspace{0.17em}I\left(w\right)\text{.}$

		Proof.
	Let $\ell \prime \left(w\right)$ temporarily denote the length of $w\text{.}$ The proof of (1.4) shows that $w$ can be written as a word of length $\ell \left(w\right)$ in the $s_i,$ so that $\ell \prime \left(w\right)\le \ell \left(w\right)\text{.}$ Conversely, let $w=s_{a_1}\dots s_{a_p}$ be any expression of $w$ as a product of $s_i\text{.}$ To show that $\ell \left(w\right)\le \ell \prime \left(w\right)$ it is enough to show that $\ell \left(w\right)\le p\text{.}$ Let $w\prime =s_{a_1}\dots s_{a_{p-1}}\text{;}$ from (1.3) we have $\ell \left(w\right)\le \ell \left(w\prime \right)+1$ and hence $$\ell \left(w\prime \right)\le p-1\Rightarrow \ell \left(w\right)\le p\text{.}$$ Hence the proof is completed by induction on $p\text{.}$ $\square$

(1.6) Let $w\in S_n\text{.}$ Then

(i)	$\ell \left(w\right)=0$ if and only if $w=1\text{.}$
(ii)	$\ell \left(w\right)=1$ if and only if $w=s_r(1\le r\le n-1)\text{.}$
(iii)	$\ell \left(w^{-1}\right)=\ell \left(w\right)\text{.}$
(iv)	Let $w_0=(n,n-1,\dots ,2,1)\in S_n\text{.}$ Then $\ell \left(w_{0}w\right)=\ell \left(w{w}_0\right)=\frac{1}{2}n(n-1)-\ell \left(w\right)\text{.}$

		Proof.
	(i), (ii) require no comment. Also (iii) is clear, since $w=s_{a_1}\dots s_{a_p}$ if and only if $w^{-1}=s_{a_p}\dots s_{a_1}\text{.}$ (iv) The set $I\left(w_0\right)$ consists of all $(i,j)\in {\Sigma }_n$ such that $i<j,$ so that $\ell \left(w_0\right)=\frac{1}{2}n(n-1)\text{.}$ Next, we have $$w{w}_0=(w\left(n\right),w(n-1),\dots ,w\left(1\right))$$ so that $I\left(w{w}_0\right)$ is the complement of $I\left(w\right)$ in $I\left(w_0\right),$ and therefore $$\ell \left(w{w}_0\right)=\frac{1}{2}n(n-1)-\ell \left(w\right)\text{.}$$ Finally, since $w_0^2=1$ we have, by virtue of (iii) above, $$\begin{array}{ccc}\ell \left(w_{0}w\right)& =& \ell \left(w^{-1}{w}_0\right)\\ & =& \frac{1}{2}n(n-1)-\ell \left(w^{-1}\right)\\ & =& \frac{1}{2}n(n-1)-\ell \left(w\right)\text{.}\end{array}$$ $\square$

The element $w_0$ is called the longest element of $S_n\text{.}$

For each $w\in S_n$ let $R\left(w\right)$ denote the set of all sequences $(a_1,\dots ,a_p)$ of length $p=\ell \left(w\right)$ such that $w=s_{a_1}\dots s_{a_p}\text{.}$ Such sequences are called reduced words for $w\text{.}$ Clearly,

$$(a_1,\dots ,a_p)\in R\left(w\right)⟺(a_p,\dots ,a_1)\in R\left(w^{-1}\right)\text{.}$$

(1.7) Let $(a_1,\dots ,a_p)\in R\left(w\right)\text{.}$ Then

$$I\left(w\right)=\{s_{a_p}\dots s_{a_{r+1}}(a_{\rho },a_{\rho }+1):1\le r\le p\}\text{.}$$

		Proof.
	Let $w\prime =w{s}_{a_p}=s_{a_1}\dots s_{a_{p-1}}\text{.}$ Then $\ell \left(w\prime \right)=p-1$ and hence by (1.2) and (1.3) we have $$I\left(w\right)=s_{a_p}I\left(w\prime \right)\cup \left\{(a_p,a_p+1)\right\}$$ from which (1.7) follows by induction on $p\text{.}$ $\square$

(1.8) (Exchange Lemma). Let $(a_1,\dots ,a_p),(b_1,\dots ,b_p)\in R\left(w\right)\text{.}$ Then

$$(b_1,a_1,\dots ,{â}_i,\dots ,a_p)\in R\left(w\right)\hspace{0.17em}\text{for some}\hspace{0.17em}i=1,2,\dots ,p\text{.}$$

		Proof.
	By (1.7), applied to $w^{-1},$ we have $(b_1,b_1+1)\in I\left(w^{-1}\right)$ and hence $$(b_1,b_1+1)=s_{a_1}\dots s_{a_{i-1}}(a_i,a_i+1)$$ for some $i=1,\dots ,p\text{.}$ It follows that $$s_{b_1}=s_{a_1}\dots s_{a_{i-1}}{s}_{a_i}{\left(s_{a_1}\dots s_{a_{i-1}}\right)}^{-1},$$ so that $s_{b_1}{s}_{a_1}\dots s_{a_{i-1}}=s_{a_1}\dots s_{a_i}$ and therefore $$s_{b_1}{s}_{a_1}\dots {ŝ}_{a_i}\dots s_{a_p}=s_{a_1}\dots s_{a_p}=w\text{.}$$ $\square$

(1.9) Let $w=s_{a_1}\dots s_{a_r}$ where $r>\ell \left(w\right)\text{.}$ Then

$$w=s_{a_1}\dots {ŝ}_{a_p}\dots {ŝ}_{a_q}\dots s_{a_r}$$

for some pair $(p,q)$ such that $1\le p<q\le r\text{.}$

		Proof.
	Since $\ell \left(s_{a_1}\right)=1$ and $\ell \left(s_{a_1}\dots s_{a_r}\right)<r$ there exists $q\ge 2$ such that $$\ell \left(s_{a_1}\dots s_{a_{q-1}}\right)=q-1,\hspace{0.17em}\ell \left(s_{a_1}\dots s_{a_q}\right)<q\text{.}$$ Let $v=s_{a_1}\dots s_{a_{q-1}},$ so that $\ell \left(v\right)=q-1$ and $\ell \left(v{s}_{a_q}\right)\le q-1,$ whence by (1.3) we have $\ell \left(v{s}_{a_q}\right)=q-2\text{.}$ Let $(b_1,\dots ,b_{q-2})$ be a reduced word for $v{s}_{a_q},$ then $(b_1,\dots ,b_{q-2},a_q)$ and $(a_1,\dots ,a_{q-1})$ are reduced words for $v\text{.}$ By (1.8) (applied to $v^{-1}\text{)}$ it follows that $v=s_{a_1}\dots {ŝ}_{a_p}\dots s_{a_{q-1}}$ for some $p=1,2,\dots ,q-1,$ and hence $$w=v{s}_{a_q}\dots s_{a_r}=s_{a_1}\dots {ŝ}_{a_p}\dots {ŝ}_{a_q}\dots s_{a_r}\text{.}$$ $\square$

If $i<j,$ let $t_{ij}$ denote the transposition that interchanges $i$ and $j$ and fixes each $k\ne i,j\text{.}$ For each permutation $w,$ let $e_{ij}\left(w\right)$ denote the number of $k$ such that $i<k<j$ and $w\left(k\right)$ lies between $w\left(i\right)$ and $w\left(j\right)\text{.}$ Consideration of $I\left(w\right)$ and $I\left(w{t}_{ij}\right)$ shows that

$$\begin{array}{cc}\text{(1.10)}& \ell \left(w{t}_{ij}\right)=\{\begin{array}{cc}\ell \left(w\right)-2e_{ij}\left(w\right)-1& \text{if}\hspace{0.17em}w\left(i\right)>w\left(j\right),\\ \ell \left(w\right)+2e_{ij}\left(w\right)+1& \text{if}\hspace{0.17em}w\left(i\right)<w\left(j\right)\text{.}\end{array}\end{array}$$

In particular, $\ell \left(w{t}_{ij}\right)=\ell \left(w\right)\pm 1$ if and only if $e_{ij}=0\text{.}$

(1.11) Let $v,w$ be permutations and let $(a_1,\dots ,a_p)$ be a reduced word for $w\text{.}$ Then the following conditions are equivalent:

(i)	$\ell \left(v\right)<\ell \left(w\right)$ and $v^{-1}w$ is a transposition,
(ii)	$v=s_{a_1}\dots {ŝ}_{a_r}\dots s_{a_p}$ for some $r=1,2,\dots ,p\text{.}$

		Proof.
	(i) $\Rightarrow$ (ii). Suppose that $v^{-1}w=t_{ij},$ so that $v=w{t}_{ij}\text{.}$ Then (1.10) shows that $w\left(i\right)>w\left(j\right),$ so that $(i,j)\in I\left(w\right)\text{.}$ Hence by (1.7) we have $(i,j)=s_{a_p}\dots s_{a_{r+1}}(a_r,a_{r+1})$ for some $r=1,2,\dots ,p,$ and therefore $$\begin{array}{cc}\text{(1)}& \begin{array}{ccc}{t}_{ij}& =& \left(s_{a_p}\dots s_{a_{r+1}}\right)s_{a_r}{\left(s_{a_p}\dots s_{a_{r+1}}\right)}^{-1}\\ & =& s_{a_p}\dots s_{a_{r+1}}{s}_{a_r}{s}_{a_{r+1}}\dots s_{a_p}\text{.}\end{array}\end{array}$$ Consequently $$\begin{array}{ccc}v=w{t}_{ij}& =& \left(s_{a_1}\dots s_{a_p}\right)\left(s_{a_p}\dots s_{a_r}\dots s_{a_p}\right)\\ & =& s_{a_1}\dots {ŝ}_{a_r}\dots s_{a_p}\text{.}\end{array}$$ (ii) $\Rightarrow$ (i). Clearly $\ell \left(v\right)<\ell \left(w\right),$ and the calculation above shows that $v^{-1}w$ is the transposition (1). $\square$

The Bruhat order

Let $v,w$ be permutations such that

(a)	$\ell \left(w\right)=\ell \left(v\right)+1,$
(b)	$w=tv$ where $t$ is a transposition.

Since $tv=vt\prime$ with $t\prime =v^{-1}tv$ also a transposition, we can replace (b) by

$\text{(b}\prime \text{)}$

$w=vt\prime$ where $t\prime$ is also a transposition.

If (a) and (b) (or $\text{(b}\prime \text{))}$ are satisfied we shall say that $w$ covers $v$ and write $v\to w\text{.}$

(1.12) Let $v,w\in S_n$ and let $w_0$ be the longest element of $S_n\text{.}$ Then the following conditions are equivalent

(a)	$v\to w\text{;}$
(b)	$v^{-1}\to w^{-1}\text{;}$
(c)	$w{w}_0\to v{w}_0\text{;}$
(d)	$w_{0}w\to w_{0}v\text{.}$

This follows from the definition and (1.6)(iii), (iv).

(1.13) Let $(a_1,\dots ,a_p)$ be a reduced word for $w\text{.}$ Then $v\to w$ if and only if $v=s_{a_1}\dots {ŝ}_{a_i}\dots s_{a_p}$ for some $i=1,2,\dots ,p$ such that $(a_1,\dots ,{â}_i,\dots ,a_p)$ is reduced.

This follows from (1.11).

(1.14) Let $w$ be a permutation and let $i\ge 1\text{.}$ Then either $w\to s_{i}w$ or $s_{i}w\to w\text{.}$ Moreover we have $s_{i}w\to w$ if and only if there is a reduced word for $w$ starting with $i\text{.}$

		Proof.
	The first statement follows from (1.3) and (1.6)(iii). If $s_{i}w\to w,$ let $(a_1,\dots ,a_p)$ be a reduced word for $s_{i}w\text{;}$ then $w=s_i{s}_{a_1}\dots s_{a_p}$ is a reduced expression for $w\text{.}$ Conversely if $w=s_i{s}_{a_1}\dots s_{a_p}$ is reduced, it is clear that $\ell \left(s_{i}w\right)=\ell \left(w\right)-1,$ and hence $s_{i}w\to w\text{.}$ $\square$

(1.15) Let $v,w$ be permutations and let $i\ge 1$ be such that

$$v\to s_{i}v\ne w\text{.}$$

Then $v\to w$ if and only if both $w\to s_{i}w$ and $s_{i}v\to s_{i}w\text{.}$

		Proof.
	Assume that $v\to w,$ and let $(a_1,\dots ,a_p)$ be a reduced word for $w\text{.}$ Suppose that $a_1=i\text{.}$ By (1.13) we have $v=s_{a_1}\dots {ŝ}_{a_r}\dots s_{a_p}$ for some $r\text{.}$ If $r=1$ then $s_{i}v=s_{a_1}v=w,$ and if $r>1$ then $s_{i}v=s_{a_2}\dots {ŝ}_{a_r}\dots s_{a_p}$ has length $<p-1=\ell \left(v\right),$ so that $s_{i}v\to v$ by (1.14). Since both these possibilities are excluded by our hypothesis, we can conclude that $a_1\ne i\text{.}$ Hence (1.14) shows that $w\to s_{i}w\text{.}$ It follows that $s_i{s}_{a_1}\dots s_{a_p}$ is a reduced expression for $s_{i}w,$ and $s_i{s}_{a_1}\dots {ŝ}_{a_r}\dots s_{a_p}$ is one for $s_{i}v\text{.}$ Hence (1.13) shows that $s_{i}v\to s_{i}w\text{.}$ Conversely, assume that $w\to s_{i}w$ and $s_{i}v\to s_{i}w\text{.}$ As before, let $w=s_{a_1}\dots s_{a_p}$ be a reduced expression. Then $s_{i}w=s_i{s}_{a_1}\dots s_{a_p}$ is reduced, and since $s_{i}v\ne w$ it follows from (1.13) that $s_{i}v=s_i{s}_{a_1}\dots {ŝ}_{a_r}\dots s_{a_p}$ for some $r=1,2,\dots ,p\text{.}$ Hence $v=s_{a_1}\dots {ŝ}_{a_r}\dots s_{a_p}$ and so $v\to w$ by (1.13) again. $\square$

The Bruhat order, denoted by $\le ,$ is the partial order on $S_n$ that is the transitive closure of the relation $\to \text{.}$ In other words, if $v$ and $w$ are permutations, $v\le w$ means that there exists $r\ge 0$ and $v_0,v_1,\dots ,v_r$ in $S_n$ such that

$$v=v_0\to v_1\to \dots \to v_r=w$$

(which implies that $\ell \left(w\right)=\ell \left(v\right)+r\text{).}$

(1.16) Let $v,w\in S_n$ and $i\ge 1$ be such that $s_{i}v\to v$ and $s_{i}w\to w\text{.}$ Then the following conditions are equivalent:

(i)	$v\le w,$
(ii)	$s_{i}v<w,$
(iii)	$s_{i}v\le s_{i}w\text{.}$

		Proof.
	(i) $\Rightarrow$ (ii). We have $s_{i}v<v\le w,$ hence $s_{i}v<w\text{.}$ (ii) $\Rightarrow$ (i). By definition there exist $v_0,v_1,\dots ,v_m,$ where $m\ge 1,$ such that $$s_{i}v=v_0\to v_1\to \dots \to v_m=w\text{.}$$ We have $v_0\to s_i{v}_0$ and $s_i{v}_m\to v_m\text{.}$ Hence there exists $k=1,2,\dots ,m$ such that $v_j\to s_i{v}_j$ for $0\le j\le k-1,$ and $s_i{v}_k\to v_k\text{.}$ Suppose $1\le j\le k-1\text{.}$ Then $v_{j-1}\to s_i{v}_{j-1}$ and $v_{j-1}\to v_j\text{;}$ also $v_j\ne s_i{v}_{j-1},$ otherwise we should have $s_i{v}_j=v_{j-1}$ and hence $s_i{v}_j\to v_j\text{.}$ Hence by (1.15) we have $$\begin{array}{cc}\text{(1)}& s_i{v}_{j-1}\ne s_i{v}_j(1\le j\le k-1)\text{.}\end{array}$$ Next, we have $v_{k-1}\to s_i{v}_{k-1}$ and $v_{k-1}\to v_k\text{.}$ If $v_k\ne s_i{v}_{k-1}$ we should by (1.15) have $v_k\to s_i{v}_k,$ contradicting the definition of $k\text{.}$ Hence $$\begin{array}{cc}\text{(2)}& v_k=s_i{v}_{k-1}\text{.}\end{array}$$ From (1) and (2) it follows that $$v=s_i{v}_0\to s_i{v}_1\to \dots \to s_i{v}_{k-1}=v_k\to \dots \to v_m=w$$ and hence $v\le w\text{.}$ This shows that (i) and (iii) are equivalent. To show that (ii) and (iii) are equivalent, assume that $v,w\in S_n$ for some $n\ge 1,$ let $w_0$ be the longest element of $S_n,$ and replace $v,w$ respectively by $s_{i}w{w}_0$ and $s_{i}v{w}_0\text{.}$ Then we have $$\begin{array}{cccc}{s}_{i}v\le s_{i}w& ⟺& s_{i}w{w}_0\le s_{i}v{w}_0& \text{(by (1.12))}\\ & ⟺& w{w}_0<s_{i}v{w}_0& \text{(by (i)}⟺\text{(ii))}\\ & ⟺& s_{i}v<w& \text{(by (1.12) again)}\end{array}$$ and the proof is complete. $\square$

(1.17) Let $v,w$ be permutations and let $a=(a_1,\dots ,a_p)$ be a reduced word for $w\text{.}$ Then the following conditions are equivalent:

(i)	$v\le w\text{;}$
(ii)	there exists a subsequence $b=(b_1,\dots ,b_q)$ of $a$ such that $v=s_{b_1}\dots s_{b_q}\text{;}$
(iii)	there exits a reduced subsequence $b=(b_1,\dots ,b_q)$ of $a$ such that $v=s_{b_1}\dots s_{b_q}\text{.}$

		Proof.
	It follows from (1.13) that (i) $\Rightarrow$ (iii), and from (1.9) that (ii) and (iii) are equivalent. Thus it remains to prove that (iii) $\Rightarrow$ (i). We proceed by induction on $r=p+q=\ell \left(v\right)+\ell \left(w\right)\text{.}$ If $r=0,$ we have $v=w=1,$ so assume that $r\ge 1\text{.}$ We distinguish two cases: (a) $v\to s_{a_1}v\text{.}$ In this case we have $b_1\ne a_1,$ hence $(b_1,\dots ,b_q)$ is a subsequence of $(a_2,\dots ,a_p),$ which is a reduced word for $s_{a_1}w\text{.}$ By the inductive hypothesis we have $v\le s_{a_1}w<w,$ hence $v<w\text{.}$ (b) $s_{a_1}v\to v\text{.}$ In this case $\ell \left(s_{a_1}v\right)+\ell \left(w\right)=p-1+q=r-1,$ and $s_{a_1}v=s_{a_1}{s}_{b_1}\dots s_{b_q}\text{.}$ If $a_1=b_1$ we have $s_{a_1}v=s_{b_2}\dots s_{b_q},$ and if $a_1\ne b_1$ then $(a_1,b_1,\dots ,b_q)$ is a non-reduced subsequence of $(a_1,\dots ,a_p)\text{.}$ Hence the inductive hypothesis implies that $s_{a_1}v<w\text{.}$ But also $s_{a_1}w\to w,$ hence $v\le w$ by (1.16). $\square$

(1.18) Let $w\in S_n$ and let $t$ be a transposition. Then

$$\ell \left(wt\right)<\ell \left(w\right)\Rightarrow wt<w\text{.}$$

This follows from (1.11) and (1.17).

To recognize when two permutations are comparable for the Bruhat order, the following rule may be used. For each $w\in S_n$ let $K\left(w\right)$ denote the column-strict tableau (of shape $\delta =(n-1,n-2,\dots ,1)\text{)}$ whose $j^{\text{th}}$ column, for $1\le j\le n-1,$ consists of the numbers $w\left(1\right),\dots ,w(n-j)$ arranged in increasing order from north to south.

(1.19) Let $v,w\in S_n\text{.}$ Then $v\le w$ if and only if $K\left(v\right)\le K\left(w\right)$ (i.e., each entry in $K\left(v\right)$ is less than or equal to the corresponding entry in $K\left(w\right)\text{).}$

		Proof.
	If $v\to w$ it is easily seen that $K\left(v\right)\le K\left(w\right),$ and hence $v\le w$ implies $K\left(v\right)\le K\left(w\right)\text{.}$ Conversely, suppose that $K\left(v\right)\le K\left(w\right)$ and let $j=j(v,w)$ be the smallest integer $\ge 1$ such that $v\left(j\right)\ne w\left(j\right)\text{.}$ (If $v=w$ we define $j(v,w)=n\text{.)}$ We proceed by descending induction on $j(v,w)\text{.}$ If $j(v,w)=n$ we have $v=w,$ so assume $j(v,w)=j<n\text{.}$ Then $w\left(j\right)$ is not equal to any $v\left(1\right),\dots ,v\left(j\right)$ and hence is equal to $v\left(k\right)$ for some $k>j\text{.}$ For each $i<j$ the ${(n-i)}^{\text{th}}$ columns of $K\left(v\right)$ and $K\left(w\right)$ are identical, and since $K\left(v\right)\le K\left(w\right)$ it follows that $v\left(j\right)<w\left(j\right),$ i.e. $v\left(j\right)<v\left(k\right)\text{.}$ Let $v\prime =v{t}_{jk},$ then by (1.10) we have $\ell \left(v\right)<\ell \left(v\prime \right)$ and hence $v<v\prime$ by (1.18). Also $v\prime \left(i\right)=v\left(i\right)=w\left(i\right)$ for $i<j,$ and $v\prime \left(j\right)=v\left(k\right)=w\left(j\right)$ so that $j(v\prime ,w)>j\text{.}$ Hence $v\prime \le w$ by the inductive hypothesis, and therefore $v<w\text{.}$ $\square$

The diagram of a permutation

We may regard $I\left(w\right)$ as a "diagram" of $w\in S_n\text{.}$ However, for many purposes it is more convenient to define the diagram of $w$ to be

$$D\left(w\right)=(1\times w)I\left(w\right)\text{.}$$

Thus we have $(i,j)\in D\left(w\right)$ if and only if $(i,w^{-1}j)\in I\left(w\right)\text{;}$ that is

$$\begin{array}{cc}\text{(1.20)}& (i,j)\in D\left(w\right)⟺i<w^{-1}j\hspace{0.17em}\text{and}\hspace{0.17em}j<wi\text{.}\end{array}$$

Hence the points $(i,j)$ in the square ${\Sigma }_n={[1,n]}^2$ not in $D\left(w\right)$ are those for which either $i\ge w^{-1}j$ or $j\ge wi\text{.}$

The graph $G\left(w\right)$ of $w$ is the set of points $(i,w\left(i\right))$ $(1\le i\le n),$ or equivalently $(w^{-1}j,j)$ $(1\le j\le n)\text{.}$ The complement of $D\left(w\right)$ in ${\Sigma }_n$ therefore consists of all the lattice points due south or due east of some point of $G\left(w\right),$ hence is the union of the hooks with corners at the points of $G\left(w\right)\text{.}$ For example, if $w=\left(365142\right)$ and $n=6,$ the diagram $D\left(w\right)$ consists of the points circled in the picture below:

$$1 2 3 4 5 6 1 2 3 4 5 6$$

If $m>n,$ we shall identify $S_n$ with the subgroup of permutations $w\in S_m$ that fix $n+1,n+2,\dots ,m\text{.}$ We may then form the group

$$S_{\infty }=\bigcup _{n\ge 1}{S}_n$$

consisting of all permutations of the set of positive integers that fix all but a finite number of them.

The diagram $D\left(w\right)$ of $w\in S_n$ is unchanged by this identification of $S_n$ with the subgroup of $S_{\infty }$ fixing all $m>n,$ and hence is well-defined for all $w\in S_{\infty }\text{.}$ Also, it is clear from the definitions and (1.7) that

(1.21)

(i)	$D\left(w^{-1}\right)$ is the transpose of $D\left(w\right)$ (i.e., we have $(i,j)\in D\left(w^{-1}\right)$ if and only if $(j,i)\in D\left(w\right)\text{).}$
(ii)	$\text{Card}\hspace{0.17em}D\left(w\right)=\ell \left(w\right)\text{.}$
(iii)	If $(a_1,\dots ,a_p)\in R\left(w\right),$ then $D\left(w\right)$ consists of the lattice points $$(s_{a_p}\dots s_{a_{r+1}}\left(a_r\right),s_{a_1}\dots s_{a_{r-1}}\left(a_r\right))$$ for $r=1,2,\dots ,p\text{.}$

In particular, it follows from (iii) above that

(1.22)

(i)	If $\ell \left(w{s}_r\right)>\ell \left(w\right),$ then $D\left(w{s}_r\right)=(s_r\times 1)D\left(w\right)\cup \left\{(r,wr)\right\}\text{.}$
(ii)	If $\ell \left(s_{r}w\right)>\ell \left(w\right),$ then $D\left(w{s}_r\right)=(1\times s_r)D\left(w\right)\cup \left\{(w^{-1}r,r)\right\}\text{.}$

The code of a permutation

Let $w\in S_n,$ and for each $i\ge 1$ let

$$c_i\left(w\right)=\text{Card}\{j:j>i\hspace{0.17em}\text{and}\hspace{0.17em}w\left(j\right)<w\left(i\right)\}\text{.}$$

Thus $c_i\left(w\right)$ is the number of points in the $i^{\text{th}}$ row of $I\left(w\right),$ or equivalently the number of points in the $i^{\text{th}}$ row of $D\left(w\right)\text{.}$ The vector

$$c\left(w\right)=(c_1\left(w\right),\dots ,c_n\left(w\right))\in {\mathbb{N}}^n$$

is called the code of $w\text{.}$ As with partitions, we may disregard any string of zeros at the right-hand end of $c\left(w\right),$ and with this convention the code $c\left(w\right)$ (like the diagram $D\left(w\right)\text{)}$ is unchanged by the embedding of $S_n$ in $S_m$ where $m>n$ and is well-defined for all $w\in S_{\infty }\text{.}$

The permutation $w$ may be reconstructed from its code $c\left(w\right)=(c_1,c_2,\dots )$ as follows :- for each $i\ge 1,$ $w\left(i\right)$ is the ${(c_i+1)}^{\text{th}}$ element, in increasing order, of the sequence of positive integers from which $w\left(1\right),w\left(2\right),\dots ,w(i-1)$ have been deleted. The sum $\left|c\right|=c_1+c_2+\dots$ is equal to $\ell \left(w\right)\text{.}$ Each sequence $c=(c_1,c_2,\dots )$ of non-negative integers such that $\left|c\right|<\infty$ occurs as the code of a unique permutation $w\in S_{\infty }\text{.}$

The length of $c\left(w\right)$ is the largest $r$ such that $c_r\left(w\right)\ne 0\text{.}$ From the definition, $r$ is the last descent of the permutation $w,$ that is to say $w\left(r\right)>w(r+1)$ and $w(r+1)<w(r+2)<\dots \text{.}$

(1.23)

(i)	If $\ell \left(w{s}_r\right)>\ell \left(w\right)$ (i.e., if $w\left(r\right)<w(r+1)\text{)}$ then $$c\left(w{s}_r\right)=s_{r}c\left(w\right)+{\epsilon }_r,$$ where ${\epsilon }_r$ is the sequence with $1$ in the $r^{\text{th}}$ place and $0$ elsewhere.
(ii)	If $(a_1,\dots ,a_p)\in R\left(w\right)$ then $$c\left(w\right)=\sum _{i=1}^p{s}_{a_p}\dots s_{a_{i+1}}\left({\epsilon }_{a_i}\right)\text{.}$$

		Proof.
	(i) follows from (1.21)(i), and (ii) follows from (i) by induction on $p\text{.}$ $\square$

(1.24) Let $i\ge 1\text{.}$ Then

$$c_i\left(w\right)>c_{i+1}\left(w\right)⟺w\left(i\right)>w(i+1)\text{.}$$

		Proof.
	Suppose that $w\left(i\right)>w(i+1)\text{.}$ Then the ${(i+1)}^{\text{th}}$ row of $I\left(w\right)$ is strictly contained in the $i^{\text{th}}$ row, whence $c_i\left(w\right)>c_{i+1}\left(w\right)\text{.}$ Conversely, if $w\left(i\right)<w(i+1),$ then the $i^{\text{th}}$ row of $I\left(w\right)$ is contained in the ${(i+1)}^{\text{th}}$ row, so that $c_i\left(w\right)\le c_{i+1}\left(w\right)\text{.}$ $\square$

To compute the code of $w^{-1}$ in terms of the code $(c_1,c_2,\dots )$ of $w,$ we introduce the following notation. If $u=(u_1,u_2,\dots )$ is any sequence and $r$ is an integer $\ge 0,$ let

$${\zeta }_{r}u=(u_1,u_2,\dots ,u_r,0,u_{r+1},u_{r+2},\dots )$$

so that the operation ${\zeta }_r$ introduces a zero after the $r^{\text{th}}$ place. Then we have

$$\begin{array}{cc}\text{(1.25)}& c\left(w^{-1}\right)=\sum _{i\ge 1}{\zeta }_{c_1}\dots {\zeta }_{c_{i-1}}\left(1^{c_i}\right)\end{array}$$

where $\left(1^{c_i}\right)$ is the sequence consisting of $c_i$ 1's.

		Proof.
	By induction on the length of $c\left(w\right)$ it is enough to show that if $w_1$ is the permutation whose code is $(c_2,c_3,\dots )$ then $$\begin{array}{cc}\text{(1)}& c\left(w^{-1}\right)=\left(1^{c_1}\right)+{\zeta }_{c_1}c\left(w_1^{-1}\right)\text{.}\end{array}$$ Now the diagram of $w_1$ is obtained from that of $w$ by deleting the first row (of length $c_1\text{)}$ and then moving each column after the $c_1^{\text{th}}$ one space to the left. On reading the diagrams of $w$ and $w_1$ by columns, we obtain (1). $\square$

The shape $\lambda \left(w\right)$ of a permutation $w$ is the partition whose parts are the non-zero $c_i\left(w\right),$ arranged in weakly decreasing order. We have

$$\left|\lambda \left(w\right)\right|=\text{Card}\hspace{0.17em}D\left(w\right)=\ell \left(w\right)\text{.}$$

Next, recall that for two partitions $\lambda =({\lambda }_1,{\lambda }_2,\dots )$ and $\mu =({\mu }_1,{\mu }_2,\dots )$ the relation $\lambda \ge \mu$ means that $\left|\lambda \right|=\left|\mu \right|$ and ${\lambda }_1+\dots +{\lambda }_i\ge {\mu }_1+\dots +{\mu }_i$ for all $i\ge 1$ [Mac1979, Ch.I], With this understood, the shapes of $w$ and $w^{-1}$ are related by

(1.26) $\lambda \left(w\prime \right)\ge \lambda \left(w^{-1}\right)\text{.}$

		Proof.
	Let $\lambda =\lambda \left(w\right),$ $\mu =\lambda \left(w^{-1}\right)\text{.}$ Define a matrix $M=\left(m_{ij}\right)$ as follows: $m_{ij}=1$ if $(i,j)\in D\left(w\right),$ and $m_{ij}=0$ otherwise. Then $M$ is a $(0,1)$ matrix with row-sums ${\lambda }_1,{\lambda }_2,\dots$ in some order, and column-sums ${\mu }_1,{\mu }_2,\dots$ in some order. Hence (see e.g. [Mac1979, Ch.I, §6]) we have $\lambda \prime \ge \mu \text{.}$ $\square$

Vexillary permutations

Special interest attaches to those permutations $w\in S_{\infty }$ for which $\lambda \left(w\right)\prime =\lambda \left(w^{-1}\right)\text{.}$ They may be characterized in various ways:

(1.27) The following conditions on a permutation $w\in S_{\infty }$ are equivalent:

(i)	the set of rows of $D\left(w\right)$ is totally ordered by inclusion;
$\text{(i)}\prime$	the set of rows of $I\left(w\right)$ is totally ordered by inclusion;
(ii)	the set of columns of $D\left(w\right)$ is totally ordered by inclusion;
$\text{(ii)}\prime$	the set of columns of $I\left(w\right)$ is totally ordered by inclusion;
(iii)	there do not exist $a,b,c,d$ such that $1\le a<b<c<d$ and $w\left(b\right)<w\left(a\right)<w\left(d\right)<w\left(c\right)\text{;}$
(iv)	there exist $u,v\in S_{\infty }$ such that $(u\times v)D\left(w\right)$ is the diagram $D\left(\lambda \right)$ of a partition $\lambda \text{;}$
(v)	$\lambda \left(w\right)\prime =\lambda \left(w^{-1}\right)\text{.}$

		Proof.
	Since $D\left(w\right)=(1\times w)I\left(w\right)$ it is clear that (i) $\iff$ $\text{(i)}\prime$ and (ii) $\iff$ $\text{(ii)}\prime \text{.}$ Morever (i) $\iff$ (ii), for either is false if and only if there exist $a,\beta ,c,\delta \in [1,n]$ such that $a<c,$ $\beta <\delta$ and $(a,\beta ),(c,\delta )$ belong to $D\left(w\right),$ whilst $(a,\delta )$ and $(c,\beta )$ do not. Let $b=w^{-1}\left(\beta \right)$ and $d=w^{-1}\left(\delta \right)\text{;}$ then we have $a<b<c<d$ and $w\left(b\right)<w\left(a\right)<w\left(d\right)<w\left(c\right)\text{.}$ Thus (i), (ii) and (iii) are all equivalent. Next, it is clear that the conjunction of (i) and (ii) is equivalent to (iv). Thus it remains to show that (iv) and (v) are equivalent. If (iv) is satisfied, then $\lambda \left(w\right)=\lambda$ and $\lambda \left(w^{-1}\right)=\lambda \prime ,$ whence (v) is satisfied. Conversely, if $\lambda \left(w\right)=\lambda$ and $\lambda \left(w^{-1}\right)=\lambda \prime ,$ then $D\left(w\right)$ can be brought into coincidence with $D\left(\lambda \right)$ by suitable permutations of the rows and of the columns, whence (iv) is satisfied. $\square$

An element $w\in S_{\infty }$ is said to be vexillary if it satisfies the equivalent conditions of (1.27). By (1.27) (iii), the first non-vexillary permutation is $\left(2143\right)$ in $S_4\text{.}$

For each $w\in S_n$ let

$$\bar{w}=w_{0}w{w}_0$$

where as before $w_0=(n,n-1,\dots ,2,1)$ is the longest element of $S_n\text{.}$ Then

(1.28)

(i)	$\ell \left(\bar{w}\right)=\ell \left(w\right)\text{.}$
(ii)	$I\left(\bar{w}\right)$ is the reflection of $I\left(w\right)$ in the "antidiagonal" $i+j=n+1\text{.}$
(iii)	$\lambda \left(\bar{w}\right)=\lambda \left(w\right)\prime \text{.}$

		Proof.
	(i) follows from (1.6) (or from (ii) below). (ii) If $i<j$ then $$\begin{array}{ccc}(i,j)\in I\left(\bar{w}\right)& ⟺& w_{0}w{w}_0\left(i\right)>w_{0}w{w}_0\left(j\right)\\ & ⟺& w(n+1-i)<w(n+1-j)\\ & ⟺& (n+1-j,n+1-i)\in I\left(w\right)\text{.}\end{array}$$ (iii) now follows from (ii). $\square$

From (1.27) and (1.28) it follows that

(1.29) $w$ is vexillary $⟺w^{-1}$ is vexillary $⟺$ $\bar{w}$ is vexillary.

Dominant permutations

We consider next two particular types of vexillary permutations.

(1.30) Let $w\in S_{\infty }\text{.}$ Then the following conditions are equivalent:

(i)	the code of $w$ is a partition;
(ii)	the code of $w^{-1}$ is a partition;
(iii)	$D\left(w\right)$ is the diagram of a partition.

		Proof.
	Clearly (iii) implies (i) and (ii). Conversely, suppose that $c\left(w\right)$ is a partition $\lambda =({\lambda }_1,\dots ,{\lambda }_m),$ where ${\lambda }_1\ge \dots \ge {\lambda }_m\ge 0\text{.}$ We shall show by induction on $i$ that $$(i,j)\in D\left(w\right)⟺1\le j\le {\lambda }_i\text{.}$$ This is true for $i=1,$ so assume that $1<i\le m$ and that the statement is true for $i-1\text{.}$ Then we have $w\left(k\right)\le {\lambda }_{i-1}$ for $1\le k\le i-1,$ and $w\left(k\right)={\lambda }_{i-1}$ for some $k\le i-1\text{.}$ Since ${\lambda }_i\le {\lambda }_{i-1}$ it follows that the $i^{\text{th}}$ row of $D\left(w\right)$ consists of the points $(i,j),$ $1\le j\le {\lambda }_i,$ as required. Hence (i) implies (iii), and the same argument applied to $w^{-1}$ shows that if the code of $w^{-1}$ is a partition, then $D\left(w^{-1}\right)$ is the diagram of a partition. Hence so is $D\left(w\right),$ by (1.21) (i), and the proof is complete. $\square$

A permutation is said to be dominant if it satisfies the equivalent conditions of (1.30). Dominant permutations are clearly vexillary, and $w$ is dominant if and only if $w^{-1}$ is dominant.

Grassmannian permutations

(1.31) Let $w\in S_{\infty }\text{.}$ Then the following conditions are equivalent:

(i)	$c_1\left(w\right)\le \dots \le c_r\left(w\right)$ and $c_i\left(w\right)=0$ for $i>r\text{;}$
(ii)	$w\left(i\right)<w(i+1)$ unless $i=r\text{.}$

		Proof.
	(i) $\Rightarrow$ (ii). By (1.15) we have $w\left(1\right)<\dots <w\left(r\right)$ and $w(r+1)<\dots <w\left(n\right)\text{.}$ (ii) $\Rightarrow$ (i). We have $$c\left(w\right)=(w\left(1\right)-1,\dots ,w\left(r\right)-r)\text{.}$$ $\square$

If $w$ satisfies the equivalent conditions of (1.31), $w$ is called a Grassmannian permutation. By (1.27)(iii), Grassmannian permutations are vexillary, and $w\in S_n$ is Grassmannian if and only if $\bar{w}=w_{0}w{w}_0$ is Grassmannian.

Enumeration of vexillary permutations

Let $w$ be a permutation, $c=c\left(w\right)=(c_1,c_2,\dots )$ its code. Consider the following two conditions on the sequence $c\text{:}$

(V1)	If $i<j$ and $c_i>c_j,$ then $$\text{Card}\hspace{0.17em}\{k:i<k<j\hspace{0.17em}\text{and}\hspace{0.17em}{c}_k<c_j\}\le c_i-c_j\text{;}$$
(V2)	If $i<j$ and $c_i\le c_j,$ then $c_k\ge c_i$ whenever $i<k<j\text{.}$

(1.32) A permutation $w$ is vexillary if and only if its code $c\left(w\right)$ satisfies (V1) and (V2).

		Proof.
	For each $i\ge 1,$ let $${\rho }_i=\{j:(i,j)\in D\left(w\right)\}$$ be the $i^{\text{th}}$ row of $D\left(w\right)\text{.}$ Suppose first that $w$ is vexillary with code $c=(c_1,c_2,\dots )\text{.}$ Let $i<k<j$ be such that $c_i\ge c_j>c_k\text{.}$ Then ${\rho }_i\supseteq {\rho }_j\supset {\rho }_k$ (where $\supset$ denotes strict containment), hence there exists $t\in {\rho }_j,$ $t\notin {\rho }_k\text{.}$ Let $s=w\left(k\right),$ then $s<t$ and (since $t\in {\rho }_i\text{)}$ we have $s\in {\rho }_i$ and $s\notin {\rho }_j\text{.}$ Hence for fixed $(i,j)$ such that $i<j$ and $c_i>c_j,$ the number of $k$ between $i$ and $j$ such that $c_j>c_k$ is at most $\text{Card}({\rho }_i-{\rho }_j)=c_i-c_j,$ so that (V1) is satisfied. Next let $w$ be vexillary, $i<k<j$ and $c_i<c_j,$ so that ${\rho }_i\subseteq {\rho }_j\text{.}$ Let $s\in {\rho }_i\text{.}$ If $s\notin {\rho }_k$ then $w\left(k\right)\le s<w\left(i\right),$ so that $w\left(k\right)$ lies in ${\rho }_i$ but not in ${\rho }_j,$ which is impossible. Hence $s\in {\rho }_k$ and therefore ${\rho }_i\subseteq {\rho }_k\text{.}$ So we have $c_i\le c_k,$ and (V2) is satisfied. Conversely, suppose that the code $c$ of $w$ satisfies (V1) and (V2). Then so does the sequence $(c_2,c_3,\dots )$ and we may therefore assume that the set $\{{\rho }_2,{\rho }_3,\dots \}$ is totally ordered by inclusion. Let $j>1$ and suppose first that $c_1\ge c_j\text{.}$ If ${\rho }_1⊉{\rho }_j,$ there exists $s\in {\rho }_j$ such that $s\notin {\rho }_1,$ so that $w\left(1\right)<s<w\left(j\right)\text{.}$ There are at least $c_1-c_j+1$ elements $t\in {\rho }_1$ such that $t\notin {\rho }_j,$ and since each such $t$ satisfies $t<w\left(1\right)<w\left(j\right),$ it is of the form $t=w\left(k\right)$ for some $k$ between $1$ and $j\text{.}$ Since $w\left(k\right)=t<w\left(1\right)<s,$ it follows that $s\notin {\rho }_k\text{.}$ Since either ${\rho }_k\subseteq {\rho }_j$ or ${\rho }_j\subseteq {\rho }_k,$ we conclude that ${\rho }_k\subset {\rho }_j$ (strict inclusion) and hence that $c_k<c_j\text{.}$ Hence there are at least $c_1-c_j+1$ values of $k$ between $1$ and $j$ for which $c_k<c_j,$ contradicting (V1). Hence ${\rho }_1\supseteq {\rho }_j\text{.}$ Finally, let $j>1$ and $c_1<c_j,$ so that $w\left(1\right)<w\left(j\right)\text{.}$ If ${\rho }_1⊈{\rho }_j$ there exists $s\in {\rho }_1$ such that $s\notin {\rho }_j\text{;}$ we have $s=w\left(k\right)$ for some $k$ between $1$ and $j,$ and since $w\left(k\right)<w\left(1\right)$ we have $c_k<c_1,$ contradicting (V2). Hence ${\rho }_1\subseteq {\rho }_j$ in this case, and the proof is complete. $\square$

Remark. It is stated in [LSc1985, prop. 2.4] that $w$ is vexillary if and only if $c\left(w\right)$ satisfies (V1) and

(V3)	If $c_i>c_{i+1}$ for some $i\ge 1,$ then $c_i>c_j$ for all $j>i\text{.}$

Since (V3) is implied by (V2), it follows from (1.32) that every vexillary code satisfies (V1) and (V3). However, the conjuction of (V1) and (V3) is not sufficient for vexillarity: for example, the permutation $w=\left(2571634\right)$ is not vexillary (since e.g. it contains the subword 2163) but its code is $c=\left(13402\right),$ which satisfies (V1) and (V3) (but not (V2)).

Let $w$ be a permutation with code $c\left(w\right)=(c_1,c_2,\dots )\text{.}$ For each $i\ge 1$ such that $c_i\ne 0,$ let

$$e_i=\text{max}\{j:j\ge i\hspace{0.17em}\text{and}\hspace{0.17em}{c}_j\ge c_i\}\text{.}$$

Arrange the numbers $e_i$ in increasing order of magnitude, say ${\varphi }_1\le \dots \le {\varphi }_m\text{.}$ The sequence

$$\varphi \left(w\right)=({\varphi }_1,\dots ,{\varphi }_m)$$

is called the flag of $w\text{.}$ It is a sequence of length equal to $\ell \left(\lambda \right),$ where $\lambda$ is the shape of $w\text{.}$

Remark. There is another definition of the flag of a permutation $w,$ due to M.Wachs [Wac1985]. For each $i\ge 1$ such that $c_i\ne 0,$ let

$$d_i=\text{min}\{j:j>i\hspace{0.17em}\text{and}\hspace{0.17em}w\left(j\right)<w\left(i\right)\}\text{.}$$

Arrange the numbers $d_i-1$ in increasing order of magnitude, say ${\varphi }_1^{*}\le \dots \le {\varphi }_m^{*},$ and let

$${\varphi }^{*}\left(w\right)=({\varphi }_1^{*},\dots ,{\varphi }_m^{*})\text{.}$$

These two notions are not equivalent. In fact

(1.33) (J. Alfano) We have $\varphi \left(w\right)={\varphi }^{*}\left(w\right)$ if and only if the permutation $w$ satisfies (V2).

		Proof.
	If $c_i\ne 0$ we have $w\left(j\right)>w\left(i\right)$ for $i<j<d_i,$ and hence $c_j\ge c_i$ for these values of $j\text{.}$ Hence $d_i-1\le e_i$ in all cases, and we shall have $\varphi \left(w\right)={\varphi }^{}\left(w\right)$ if and only if $d_i-1=e_i$ for each $i\text{.}$ But this condition means that, for each $i\ge 1,$ the set of $j\ge i$ such that $c_j\ge c_i$ is an interval; and this is just a restatement of the condition (V2). $\square$

We shall show that a vexillary permutation is uniquely determined by its shape $\lambda \left(w\right)$ and its flag $\varphi \left(w\right)\text{.}$

Let us write $\lambda =\lambda \left(w\right)$ in the form

$$\begin{array}{cc}\text{(1.34)}& \lambda =(p_1^{m_1},p_2^{m_2},\dots ,p_k^{m_k})\end{array}$$

where $p_1>p_2>\dots >p_k>0$ and each $m_i\ge 1\text{.}$ For $1\le r\le k$ let

$$f_r=\text{max}\{j:c_j\ge p_r\}$$

so that $f_1\le \dots \le f_k\text{.}$ If $c=(c_1,c_2,\dots )$ is the code of $w,$ each nonzero $c_i$ is equal to $p_r$ for some $r,$ and

$$e_i=\text{max}\{j:j\ge i\hspace{0.17em}\text{and}\hspace{0.17em}{c}_j\ge p_r\}=f_r\text{.}$$

It follows that (whether $w$ is vexillary or not)

$$\begin{array}{cc}\text{(1.35)}& \varphi \left(w\right)=(f_1^{m_1},f_2^{m_2},\dots ,f_k^{m_k})\text{.}\end{array}$$

Moreover we must have

$$\begin{array}{cc}\text{(1.36)}& f_r\ge m_1+\dots +m_r(1\le r\le k)\end{array}$$

since in the sequence $(c_1,c_2,\dots )$ there are $m_1+\dots +m_r$ terms $\ge p_r,$ and they must all occur in the first $f_r$ places of the sequence.

(1.37) Suppose $w$ is a vexillary pennutation with shape $\lambda$ and flag $\varphi$ given by (1.34) and (1.35). Then the $f_r$ must satisfy the inequalities

$$0\le f_r-f_{r-1}\le m_r+p_{r-1}-p_r\text{.}$$

		Proof.
	If $f_{r-1}=f_r$ there is nothing to prove, so assume that $f_{r-1}<f_r$ and therefore $c_{f_r}=p_r\text{.}$ Let $$s=\text{max}\{i:c_i=p_{r-1}\}\le f_{r-1}\text{.}$$ Since $c_s=p_{r-1}>p_r=c_{f_r}$ and $w$ is vexillary, we have by (V1) $$\begin{array}{cc}\text{(1)}& \text{Card}\hspace{0.17em}\{k:s<k\le f_r\hspace{0.17em}\text{and}\hspace{0.17em}{c}_k<p_r\}\le p_{r-1}-p_r\text{.}\end{array}$$ Also $$\begin{array}{cc}\text{(2)}& \text{Card}\hspace{0.17em}\{k:s<k\le f_r\hspace{0.17em}\text{and}\hspace{0.17em}{c}_k=p_r\}\le m_r,\end{array}$$ since exactly $m_r$ terms of the sequence $c$ are equal to $p_r\text{.}$ Finally we have $$\begin{array}{cc}\text{(3)}& \text{Card}\hspace{0.17em}\{k:s<k\le f_r\hspace{0.17em}\text{and}\hspace{0.17em}{c}_k>p_r\}=f_{r-1}-s\end{array}$$ because $c_k\le p_r$ for all $k>f_{r-1},$ and $c_k\ge p_{r-1}$ for all $k$ such that $s<k\le f_{r-1},$ by virtue of (V2). From (1), (2), and (3) we deduce that $$f_r-s\le p_{r-1}-p_r+m_r+f_{r-1}-s$$ which proves (1.37). $\square$

(1.38) For each sequence $(f_1,\dots ,f_k)$ satisfying (1.36) and (1.37) there is a unique vexillary permutation $w$ with shape $\lambda$ and flag $\varphi =(f_1^{m_1},\dots ,f_k^{m_k})\text{.}$ The code $c$ of $w$ is constructed as follows: first the $m_1$ entries equal to $p_1$ are inserted at the right-hand end of the interval $[1,f_1]\text{;}$ then the $m_2$ entries in $c$ equal to $p_2$ are inserted in the rightmost available spaces in the interval $[1,f_2],$ and so on: for each $r\ge 1,$ when all the terms $>p_r$ in the sequence $c$ have been inserted, the $m_r$ entries equal to $p_r$ are inserted in the rightmost available spaces of the interval $[1,f_r]\text{.}$

		Proof.
	Suppose first that $w$ is vexillary. If $1\le i\le f_r$ and $c_i=p_r,$ then by (V2) we have $c_j\ge p_r$ for all $j$ such that $i<j<f_r\text{.}$ Hence the entries equal to $p_r$ in the sequence $c$ must be inserted as described above. Conversely, if the sequence $c$ is constructed as above, we claim that $c$ satisfies (V1) and (V2), and hence $w$ is vexillary by (1.32). Suppose first that $i<j$ and $c_i\ge c_j\text{:}$ say $c_i=p_r,$ $c_j=p_s,$ $r\le s\text{.}$ Then the number of $k$ such that $i<k<j$ and $c_k<p_s$ is equal to the number of blank spaces in the interval $[f_r,f_s]$ after all the entries $p_i,$ $r+1\le i\le s$ have been inserted, hence is at most $$f_s-f_r-(m_{r+1}+\dots +m_s)$$ which by (1.37) is $\le p_r-p_s\text{.}$ Hence the sequence $c$ satisfies (V1). Suppose next that $i<j$ and $c_i<c_j\text{:}$ say $c_i=p_s,$ $c_j=p_r$ with $r<s\text{.}$ Then we have $j\le f_r\le f_s\text{.}$ From the definition of the sequence $c,$ it follows that for each $k$ such that $i\le k\le f_s$ we have $c_k\ge p_s,$ and hence $c_k\ge c_i$ whenever $i<k<j\text{.}$ Consequently the condition (V2) is satisfied, and the proof is complete. $\square$

If $w$ is a permutation and $r\ge 0,$ we denote by $1_r\times w$ the permutation

$$1_r\times w=(1,2,\dots ,r,r+w\left(1\right),r+w\left(2\right),\dots )\text{.}$$

Let us say that two permutations $w,w\prime$ are diagonally equivalent if either $w\prime =1_r\times w$ or $w=1_r\times w\prime$ for some $r\ge 0\text{.}$ Graphically, this means that the diagram of $w\prime$ can be brought into coincidence with that of $w$ by a translation along the diagonal $i=j,$ and $w\prime$ is vexillary if and only if $w$ is vexillary. The equivalence classes of vexillary permutations of a given shape $\lambda$ are then determined by the differences $f_r-f_{r-1}$ $(2\le r\le k),$ and hence it follows from (1.37) and (1.38) that

(1.39) The number of diagonal equivalence classes of vexillary permutations of shape $\lambda =(p_1^{m_1},\dots ,p_k^{m_k})$ is

$$\prod _{r=2}^k(p_{r-1}-p_r+m_r+1)\text{.}$$

We may remark that this number is the product of the hook lengths at the re-entrant nodes of the border of the diagram of $\lambda$ (i.e., the nodes with coordinates $(m_1+\dots +m_{r-1},p_r),$ $2\le r\le k\text{).}$

Example. If $\lambda =\left(32^{2}1\right)$ the flag $\varphi =(f_1,f_2^2,f_3)$ must satisfy $0\le f_2-f_1\le 3,$ $0\le f_3-f_2\le 2\text{.}$ Hence there are $(3+1)(2+1)=12$ vexillary classes, and the representatives of these classes for which $w\left(1\right)\ne 1$ (or equivalently $c_1\left(w\right)\ne 0\text{)}$ are as follows:

$$\begin{array}{ccc}\varphi \left(w\right)& c\left(w\right)& w\\ 4444& 1223& 2457136\\ 3444& 1232& 246513\\ 2444& 1322& 254613\\ 1444& 3122& 425613\\ 3334& 2231& 346215\\ 2334& 2321& 35421\\ 1334& 3221& 43521\\ 1445& 30221& 415632\\ 3335& 22301& 346152\\ 2335& 23201& 354162\\ 1335& 32201& 435162\\ 1446& 302201& 4156273\end{array}$$

$$\begin{array}{ccc} & & \\ 1223& 2231& 22301\\ \\ & & \\ 1232& 2321& 23201\\ \\ & & \\ 1322& 3221& 32201\\ \\ & & \\ 3122& 302201& 302201\end{array}$$

Let $\lambda =(p_1^{m_1},\dots ,p_k^{m_k})$ as before and let

$$\lambda \prime =(q_1^{n_1},q_2^{n_2},\dots ,q_k^{n_k})$$

be the conjugate partition, where $q_1>q_2>\dots >q_k>0$ and each $n_i\ge 1\text{.}$ We have

$$\begin{array}{cc}\text{(1.40)}& \{\begin{array}{c}{p}_r=n_1+\dots +n_s,\\ q_r=m_1+\dots +m_s,\end{array}\end{array}$$

where $s=k+1-r$ $(1\le r\le k)\text{.}$ The border of the diagram of $\lambda$ is a staircase with risers of heights $m_1,m_2,\dots ,m_k$ (starting from the top) and treads of lengths $n_1,n_2,\dots ,n_k$ (starting at the bottom).

Recall (1.27) that if $w$ is vexillary of shape $\lambda ,$ then $w^{-1}$ is vexillary of shape $\lambda \prime \text{.}$

(1.41) Let $w$ be a vexillary permutation of shape $\lambda$ and flag $\varphi \left(w\right)=(f_1^{m_1},\dots ,f_k^{m_k})\text{.}$ Then the flag of $w^{-1}$ is

$$\varphi \left(w^{-1}\right)=(g_1^{n_1},\dots ,g_k^{n_k})$$

where

$$\begin{array}{cc}(*)& g_i+q_i=f_{k+1-i}+p_{k+1-i}(1\le i\le k)\text{.}\end{array}$$

		Proof.
	We proceed by induction on $\ell \left(w\right)=\left|\lambda \right|\text{.}$ Let $c=(c_1,c_2,\dots )$ be the code of $w,$ and let $w\prime$ be the permutation with code $c\prime =(c_2,c_3,\dots )\text{.}$ We may assume that $c_1\ne 0\text{.}$ Then $c_1=p_r$ for some $r,$ and we have $$\begin{array}{ccc}\lambda \left(w\prime \right)& =& (p_1^{m_1},\dots ,p_r^{m_r-1},\dots ,p_k^{m_k}),\\ \varphi \left(w\prime \right)& =& ({(f_1-1)}^{m_1},\dots ,{(f_r-1)}^{m_r-1},\dots ,{(f_k-1)}^{m_k})\text{.}\end{array}$$ Since $w$ is vexillary, its code $c$ satisfies the conditions (V1) and (V2). Hence $c\prime$ also satisfies these conditions, and therefore $w\prime$ is vexillary. It follows that $\lambda \left({w\prime }^{-1}\right)=\lambda \left(w\prime \right)\prime ,$ so that $$\lambda \left({w\prime }^{-1}\right)=({(q_1-1)}^{n_1},\dots ,{(q_s-1)}^{n_s},q_{s+1}^{n_s+1},\dots ,q_k^{n_k})$$ where $s=k+1-r\text{.}$ We have $\ell \left(w\prime \right)=\ell \left(w\right)-c_1,$ so that the inductive hypothesis applies to $w\prime \text{.}$ Hence if $g_1,\dots ,g_k$ are defined by the formula $(*),$ we have $$\begin{array}{cc}\text{(1)}& \varphi \left({w\prime }^{-1}\right)=(g_1^{n_1},\dots ,g_s^{n_s},{(g_{s+1}-1)}^{n_{s+1}},\dots ,{(g_k-1)}^{n_k})\text{.}\end{array}$$ But if ${w\prime }^{-1}$ has code $c\left({w\prime }^{-1}\right)=(d_1,d_2,\dots )$ then by (1.25) we have $$\begin{array}{cc}\text{(2)}& c\left(w^{-1}\right)=(d_1+1,\dots ,d_{p_r}+1,0,d_{p_r+1},d_{p_r+2},\dots )\text{.}\end{array}$$ From (1) and (2) and (1.40) it follows that $$\varphi \left(w^{-1}\right)=(g_1^{n_1},\dots ,g_s^{n_s},g_{s+1}^{n_{s+1}},\dots ,g_k^{n_k})$$ as required. $\square$

If $w\in S_n,$ let ${\bar{w}}_n=w_{0}w{w}_0,$ where $w_0$ is the longest element in $S_n\text{.}$ If $w$ is vexillary, of shape $\lambda ,$ then ${\bar{w}}_n$ is vexillary of shape $\lambda \prime ,$ by (1.27) and (1.28). Let

$$\varphi \left({\bar{w}}_n\right)=({\overline{f_1}}^{n_1},\dots ,{\overline{f_k}}^{n_k})$$

be the flag of ${\bar{w}}_n\text{.}$ Then we have

$$\begin{array}{cc}\text{(1.42)}& \overline{f_i}=n-f_{k+1-i}(1\le i\le k)\text{.}\end{array}$$

For once we shall leave the proof to the reader.

Let $N_n$ denote the number of non-vexillary $w\in S_n,$ and let

$$P_n=N_n/n!$$

be the probability that an element of $S_n$ is non-vexillary. The first few values of $N_n$ and $P_n$ are

$$\begin{array}{ccc}n& N_n& P_n\\ 1& 0& 0\\ 2& 0& 0\\ 3& 0& 0\\ 4& 1& .042\\ 5& 17& .142\\ 6& 207& .288\\ 7& {2279}^{*}& .452\end{array}$$

${}^{*}$ was computed by A. Garsia. I would guess that $N_8$ is of the order of $24000\text{.}$

If we divide up the sequence $(w\left(1\right),\dots ,w\left(n\right))$ into consecutive blocks of length $4,$ and observe that the probability that such a block satisfies the vexillarity condition (1.27)(iii) is $23/24$ (because $S_4$ contains only one non-vexillary permutation), we see that the probability that $w\in S_n$ is vexillary is at most ${(23/24)}^{[n/4]},$ hence decreases exponentially to zero. (A. Lascoux.) Thus the vexillary permutations in $S_n$ become sparser and sparser as $n$ increases.

Instead of counting non-vexillary permutations, we may attempt to count vexillary permutations. Let us say that a permutation $w\in S_n$ is primitive if $w\left(1\right)\ne 1$ and $w\left(n\right)\ne n\text{.}$ For each $n\ge 1,$ let $V_n$ (resp. $U_n\text{)}$ denote the number of vexillary (resp. primitive vexillary) permutations $w\in S_n\text{.}$ Since each primitive vexillary $w\in S_n$ gives rise to $r+1$ imprimitive vexillary permutations in $S_{n+r},$ namely $1_p\times w\times 1_q$ where $p,q\ge 0$ and $p+q=r,$ it follows that

$$V_n=1+U_n+2U_{n-1}+3U_{n-2}+\dots$$

Hence the generating functions

$$\begin{array}{ccc}V\left(t\right)& =& \sum _{n\ge 1}{V}_n{t}^n\\ U\left(t\right)& =& \sum _{n\ge 1}{U}_n{t}^n\end{array}$$

are related by

$$\begin{array}{cc}\text{(1.43)}& V\left(t\right)=\frac{t}{1-t}+\frac{U\left(t\right)}{{(1-t)}^2}\text{.}\end{array}$$

For each partition $\lambda \ne 0,$ let $U_{n,\lambda }$ denote the number of primitive vexillary permutations of shape $\lambda$ in $S_n,$ and let

$$U_{\lambda }\left(t\right)=\sum _{n\ge 1}{U}_{n,\lambda }{t}^n,$$

so that

$$\begin{array}{cc}\text{(1.44)}& U\left(t\right)=\sum _{\lambda \ne 0}{U}_{\lambda }\left(t\right)\text{.}\end{array}$$

Each $U_{\lambda }\left(t\right)$ is a polynomial, and we shall now show how to compute it. Write $\lambda$ in the form

$$\lambda =(p_1^{m_1},p_2^{m_2},\dots ,p_k^{m_k})$$

as before, where $p_1>p_2>\dots >p_k>0\text{.}$ By (1.37) a vexillary permutation $w$ of shape $\lambda$ is uniquely determined by its flag $\varphi \left(w\right)=(f_1^{m_1},\dots ,f_k^{m_k}),$ where $(f_1,\dots ,f_k)$ is any vector of positive integers satisfying the inequalities (1.36), (1.37):

$$\begin{array}{c}{f}_r\ge m_1+\dots +m_r(1\le r\le k),\\ 0<f_r-f_{r-1}\le m_r+p_{r-1}-p_r(2\le r\le k)\text{.}\end{array}$$

Moreover we shall have $w\left(1\right)\ne 1$ if and only if the first element of the code of $w$ is not zero, and this will be the case if and only if

$$\begin{array}{cc}\text{(1)}& f_r=m_1+\dots +m_r\text{for some}\hspace{0.17em}r+1,\dots ,k\text{.}\end{array}$$

In general, if $c=(c_1,c_2,\dots )$ is the code of a permutation $w,$ then $w\in S_n$ if and only if $n\ge c_i+i$ for $1\le i\le r,$ where $r$ is the length of $c\text{.}$ In other words, the least $n$ for which $w\in S_n$ is $n=\text{max}\{c_i+i:1\le i\le r\}\text{.}$ In the case of a vexillary permutation $w$ as above, with flag $(f_1^{m_1},\dots ,f_k^{m_k}),$ the numbers $c_i+i$ will increase strictly as $i$ runs through each non-empty interval $[f_{r-1}+1,f_r]$ $(r=1,\dots ,k),$ and hence $w$ will be primitive in $S_n$ if and only if $w$ satisfies (1) above and

$$\begin{array}{cc}\text{(2)}& n=\text{max}\{p_r+f_r:1\le r\le k\}\text{.}\end{array}$$

Let ${\pi }_r=m_1+\dots +m_r$ for $1\le r\le k$ and put

$$u_r=f_r-{\pi }_r$$

so that $u_r\ge 0$ for each $r\text{.}$ From (1.36) we have

$$\begin{array}{cc}\text{(3)}& {\pi }_1+u_1\le {\pi }_2+u_2\le \dots \le {\pi }_k+u_k\end{array}$$

and

$$\begin{array}{ccc}{m}_r+p_{r-1}-p_r& \ge & f_r-f_{r-1}\\ & =& (u_r+{\pi }_r)-(u_{r-1}+{\pi }_{r-1})\\ & =& m_r+u_r-r_{r-1}\end{array}$$

so that

$$\begin{array}{cc}\text{(4)}& p_1+u_1\ge p_2+u_2\ge \dots \ge p_k+u_k\text{.}\end{array}$$

It now follows that

$$\begin{array}{cc}\text{(1.45)}& U_{\lambda }\left(t\right)=\sum _u{t}^{\text{max}\{p_r+{\pi }_r+u_r:1\le r\le k\}}\end{array}$$

summed over the integer vectors $u=(u_1,\dots ,u_k)\in {\mathbb{N}}^k$ having at least one zero component, and satisfying the inequalities (3), (4) above. We have

$$U_{\lambda }\left(1\right)=\prod _{r=2}^k(m_r+p_{r-1}-p_r+1)$$

and

$$U_{\lambda }\left(t\right)=U_{\lambda \prime }\left(t\right)$$

(since $w\in S_n$ is primitive vexillary of shape $\lambda$ if and only if $w^{-1}$ is primitive vexillary of shape $\lambda \prime \text{).}$

Added in proof

Julian West, a student of R. Stanley, has recently shown that

$$\begin{array}{cc}\text{(1)}& V_n=\sum _{\underset{\ell \left(\lambda \right)\le 3}{\left|\lambda \right|=n}}{\left(f^{\lambda }\right)}^2\end{array}$$

where $f^{\lambda }$ is the degree of the irreducible representation of the symmetric group $S_n$ indexed by the partition $\lambda \text{.}$ From this and results of A. Regev (Advances in Math. 41 (1981) 115-136) it follows that

$$\begin{array}{cc}\text{(2)}& V_n\sim c{9}^n{n}^{-4}\end{array}$$

as $n\to \infty ,$ where $c$ is a constant that Regev determines explicitly.

The formula (1) gives that $N_8=24553\text{.}$

Notes and References

This is a typed excerpt of the book Notes on Schubert Polynomials by I. G. Macdonald.

page history