Notes on Schubert Polynomials
Chapter 1

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia

Last update: 25 June 2013


For each integer n1, let Sn denote the symmetric group of degree n, that is to say the group of all permutations of the set [1,n]={1,2,,n}. Each wSn 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[1,n] under w is w(i). We shall sometimes denote w by the sequence (w(1),w(2),,w(n)). Thus for example (53214) is the element of S5 that sends 1 to 5, 2 to 3, 3 to 2, 4 to 1 and 5 to 4.

For i=1,2,,n-1 let si denote the transposition that interchanges i and i+1, and fixes all other elements of [1,n]. We have

(1.1) { si2=1, sisj=sjsi if|i-j| >1, sisi+1si= si+1sisi+1 (1in-2).

Also, for each wSn, let

I(w)= { (i,j):1i<jn andw(i)>w(j) } .

We regard I(w) as a subset of the square Σn=[1,n]×[1,n], and we shall adopt the convention of matrices, that in Σn the first coordinate increases from north to south, and the second coordinate from west to east. The group Sn×Sn acts on Σn:(u×v)(i,j)=(u(i),v(j)). In particular, Sn acts diagonally: w(i,j)= (w×w)(i,j)= (w(i),w(j)).

Let wSn, 1rn-1. Then wsr is the permutation

( w(1),, w(r+1), w(r),, w(n) )

and it is clear that

(1.2) I(wsr)= { srI(w) {(r,r+1)} ifw(r)< w(r+1), srI(w)- {(r+1,r)} ifw(r)> w(r+1).

Let (w)=CardI(w). Then from (1.2) we have

(1.3) (wsr)= { (w)+1 ifw(r)< w(r+1), (w)-1 ifw(r)> w(r+1).

(1.4) s1,,sn-1 generate the group Sn.


We shall show by induction on (w) that each wSn is a product of s's. If (w)=0, then w=1 and there is nothing to prove. If (w)>0 then w(r)>w(r+1) for some r, and hence (wsr)=(w)-1 by (1.3). Hence wsr=sa1sap say, and therefore (as sr2=1) w=sa1sapsr.

For each wSn. the length of w is the minimal length of a sequence (a1,,ap) such that w=sa1sap.

(1.5) The length of wSn is equal to (w)=CardI(w).


Let (w) temporarily denote the length of w. The proof of (1.4) shows that w can be written as a word of length (w) in the si, so that (w)(w). Conversely, let w=sa1sap be any expression of w as a product of si. To show that (w)(w) it is enough to show that (w)p. Let w=sa1sap-1; from (1.3) we have (w)(w)+1 and hence

(w)p-1 (w)p.

Hence the proof is completed by induction on p.

(1.6) Let wSn. Then

(i) (w)=0 if and only if w=1.
(ii) (w)=1 if and only if w=sr(1rn-1).
(iii) (w-1)=(w).
(iv) Let w0=(n,n-1,,2,1)Sn. Then (w0w)= (ww0)= 12n(n-1)- (w).


(i), (ii) require no comment. Also (iii) is clear, since w=sa1sap if and only if w-1=sapsa1.

(iv) The set I(w0) consists of all (i,j)Σn such that i<j, so that (w0)=12n(n-1). Next, we have

ww0= ( w(n), w(n-1), ,w(1) )

so that I(ww0) is the complement of I(w) in I(w0), and therefore

(ww0)=12 n(n-1)-(w).

Finally, since w02=1 we have, by virtue of (iii) above,

(w0w) = (w-1w0) = 12n(n-1)- (w-1) = 12n(n-1)- (w).

The element w0 is called the longest element of Sn.

For each wSn let R(w) denote the set of all sequences (a1,,ap) of length p=(w) such that w=sa1sap. Such sequences are called reduced words for w. Clearly,

(a1,,ap) R(w) (ap,,a1) R(w-1).

(1.7) Let (a1,,ap)R(w). Then

I(w)= { sapsar+1 (aρ,aρ+1): 1rp } .


Let w=wsap=sa1sap-1. Then (w)=p-1 and hence by (1.2) and (1.3) we have

I(w)=sapI (w) {(ap,ap+1)}

from which (1.7) follows by induction on p.

(1.8) (Exchange Lemma). Let (a1,,ap), (b1,,bp) R(w). Then

( b1,a1,, âi,,ap ) R(w)for somei= 1,2,,p.


By (1.7), applied to w-1, we have (b1,b1+1)I(w-1) and hence

(b1,b1+1)= sa1sai-1 (ai,ai+1)

for some i=1,,p. It follows that

sb1=sa1 sai-1sai (sa1sai-1) -1 ,

so that sb1sa1 sai-1 = sa1sai and therefore

sb1sa1 ŝaisap =sa1sap=w.

(1.9) Let w=sa1sar where r>(w). Then

w=sa1 ŝap ŝaq sar

for some pair (p,q) such that 1p<qr.


Since (sa1)=1 and (sa1sar)<r there exists q2 such that

(sa1saq-1) =q-1, (sa1saq) <q.

Let v=sa1saq-1, so that (v)=q-1 and (vsaq)q-1, whence by (1.3) we have (vsaq)=q-2. Let (b1,,bq-2) be a reduced word for vsaq, then (b1,,bq-2,aq) and (a1,,aq-1) are reduced words for v. By (1.8) (applied to v-1) it follows that v=sa1ŝapsaq-1 for some p=1,2,,q-1, and hence

w=vsaqsar= sa1ŝap ŝaqsar.

If i<j, let tij denote the transposition that interchanges i and j and fixes each ki,j. For each permutation w, let eij(w) denote the number of k such that i<k<j and w(k) lies between w(i) and w(j). Consideration of I(w) and I(wtij) shows that

(1.10) (wtij)= { (w)-2eij(w) -1 ifw(i)>w(j), (w)+2eij(w) +1 ifw(i)<w(j).

In particular, (wtij)=(w)±1 if and only if eij=0.

(1.11) Let v,w be permutations and let (a1,,ap) be a reduced word for w. Then the following conditions are equivalent:

(i) (v)<(w) and v-1w is a transposition,
(ii) v= sa1ŝar sap for some r=1,2,,p.


(i) (ii). Suppose that v-1w=tij, so that v=wtij. Then (1.10) shows that w(i)>w(j), so that (i,j)I(w). Hence by (1.7) we have (i,j)=sapsar+1(ar,ar+1) for some r=1,2,,p, and therefore

(1) tij = (sapsar+1) sar (sapsar+1)-1 = sapsar+1 sarsar+1 sap.


v=wtij = (sa1sap) (sapsarsap) = sa1ŝar sap.

(ii) (i). Clearly (v)<(w), and the calculation above shows that v-1w is the transposition (1).

The Bruhat order

Let v,w be permutations such that

(a) (w)=(v)+1,
(b) w=tv where t is a transposition.
Since tv=vt with t=v-1tv also a transposition, we can replace (b) by
(b) w=vt where t is also a transposition.
If (a) and (b) (or (b)) are satisfied we shall say that w covers v and write vw.

(1.12) Let v,wSn and let w0 be the longest element of Sn. Then the following conditions are equivalent

(a) vw;
(b) v-1w-1;
(c) ww0vw0;
(d) w0ww0v.

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

(1.13) Let (a1,,ap) be a reduced word for w. Then vw if and only if v=sa1ŝaisap for some i=1,2,,p such that (a1,,âi,,ap) is reduced.

This follows from (1.11).

(1.14) Let w be a permutation and let i1. Then either wsiw or siww. Moreover we have siww if and only if there is a reduced word for w starting with i.


The first statement follows from (1.3) and (1.6)(iii). If siww, let (a1,,ap) be a reduced word for siw; then w=sisa1sap is a reduced expression for w. Conversely if w=sisa1sap is reduced, it is clear that (siw)=(w)-1, and hence siww.

(1.15) Let v,w be permutations and let i1 be such that


Then vw if and only if both wsiw and sivsiw.


Assume that vw, and let (a1,,ap) be a reduced word for w. Suppose that a1=i. By (1.13) we have v=sa1ŝarsap for some r. If r=1 then siv=sa1v=w, and if r>1 then siv=sa2ŝarsap has length <p-1=(v), so that sivv by (1.14). Since both these possibilities are excluded by our hypothesis, we can conclude that a1i. Hence (1.14) shows that wsiw. It follows that sisa1sap is a reduced expression for siw, and sisa1ŝarsap is one for siv. Hence (1.13) shows that sivsiw.

Conversely, assume that wsiw and sivsiw. As before, let w=sa1sap be a reduced expression. Then siw=sisa1sap is reduced, and since sivw it follows from (1.13) that siv=sisa1ŝarsap for some r=1,2,,p. Hence v=sa1ŝarsap and so vw by (1.13) again.

The Bruhat order, denoted by , is the partial order on Sn that is the transitive closure of the relation . In other words, if v and w are permutations, vw means that there exists r0 and v0,v1,,vr in Sn such that

v=v0v1 vr=w

(which implies that (w)=(v)+r).

(1.16) Let v,wSn and i1 be such that sivv and siww. Then the following conditions are equivalent:

(i) vw,
(ii) siv<w,
(iii) sivsiw.


(i) (ii). We have siv<vw, hence siv<w.

(ii) (i). By definition there exist v0,v1,,vm, where m1, such that

siv=v0v1 vm=w.

We have v0siv0 and sivmvm. Hence there exists k=1,2,,m such that vjsivj for 0jk-1, and sivkvk.

Suppose 1jk-1. Then vj-1sivj-1 and vj-1vj; also vjsivj-1, otherwise we should have sivj=vj-1 and hence sivjvj. Hence by (1.15) we have

(1) sivj-1sivj (1jk-1).

Next, we have vk-1sivk-1 and vk-1vk. If vksivk-1 we should by (1.15) have vksivk, contradicting the definition of k. Hence

(2) vk=sivk-1.

From (1) and (2) it follows that

v=siv0si v1sivk-1 =vkvm=w

and hence vw.

This shows that (i) and (iii) are equivalent. To show that (ii) and (iii) are equivalent, assume that v,wSn for some n1, let w0 be the longest element of Sn, and replace v,w respectively by siww0 and sivw0. Then we have

sivsiw siww0sivw0 (by (1.12)) ww0<sivw0 (by (i)(ii)) siv<w (by (1.12) again)

and the proof is complete.

(1.17) Let v,w be permutations and let a=(a1,,ap) be a reduced word for w. Then the following conditions are equivalent:

(i) vw;
(ii) there exists a subsequence b=(b1,,bq) of a such that v=sb1sbq;
(iii) there exits a reduced subsequence b=(b1,,bq) of a such that v=sb1sbq.


It follows from (1.13) that (i) (iii), and from (1.9) that (ii) and (iii) are equivalent. Thus it remains to prove that (iii) (i).

We proceed by induction on r=p+q=(v)+(w). If r=0, we have v=w=1, so assume that r1. We distinguish two cases:

(a) vsa1v. In this case we have b1a1, hence (b1,,bq) is a subsequence of (a2,,ap), which is a reduced word for sa1w. By the inductive hypothesis we have vsa1w<w, hence v<w.

(b) sa1vv. In this case (sa1v)+(w)=p-1+q=r-1, and sa1v=sa1sb1sbq. If a1=b1 we have sa1v=sb2sbq, and if a1b1 then (a1,b1,,bq) is a non-reduced subsequence of (a1,,ap). Hence the inductive hypothesis implies that sa1v<w. But also sa1ww, hence vw by (1.16).

(1.18) Let wSn and let t be a transposition. Then

(wt)<(w) wt<w.

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 wSn let K(w) denote the column-strict tableau (of shape δ=(n-1,n-2,,1)) whose jth column, for 1jn-1, consists of the numbers w(1),,w(n-j) arranged in increasing order from north to south.

(1.19) Let v,wSn. Then vw if and only if K(v)K(w) (i.e., each entry in K(v) is less than or equal to the corresponding entry in K(w)).


If vw it is easily seen that K(v)K(w), and hence vw implies K(v)K(w).

Conversely, suppose that K(v)K(w) and let j=j(v,w) be the smallest integer 1 such that v(j)w(j). (If v=w we define j(v,w)=n.) We proceed by descending induction on j(v,w). If j(v,w)=n we have v=w, so assume j(v,w)=j<n. Then w(j) is not equal to any v(1),,v(j) and hence is equal to v(k) for some k>j. For each i<j the (n-i)th columns of K(v) and K(w) are identical, and since K(v)K(w) it follows that v(j)<w(j), i.e. v(j)<v(k). Let v=vtjk, then by (1.10) we have (v)<(v) and hence v<v by (1.18). Also v(i)=v(i)=w(i) for i<j, and v(j)=v(k)=w(j) so that j(v,w)>j. Hence vw by the inductive hypothesis, and therefore v<w.

The diagram of a permutation

We may regard I(w) as a "diagram" of wSn. However, for many purposes it is more convenient to define the diagram of w to be

D(w)=(1×w) I(w).

Thus we have (i,j)D(w) if and only if (i,w-1j)I(w); that is

(1.20) (i,j)D(w) i<w-1jand j<wi.

Hence the points (i,j) in the square Σn=[1,n]2 not in D(w) are those for which either iw-1j or jwi.

The graph G(w) of w is the set of points (i,w(i)) (1in), or equivalently (w-1j,j) (1jn). The complement of D(w) in Σn therefore consists of all the lattice points due south or due east of some point of G(w), hence is the union of the hooks with corners at the points of G(w). For example, if w=(365142) and n=6, the diagram D(w) 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 Sn with the subgroup of permutations wSm that fix n+1,n+2,,m. We may then form the group


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

The diagram D(w) of wSn is unchanged by this identification of Sn with the subgroup of S fixing all m>n, and hence is well-defined for all wS. Also, it is clear from the definitions and (1.7) that


(i) D(w-1) is the transpose of D(w) (i.e., we have (i,j)D(w-1) if and only if (j,i)D(w)).
(ii) CardD(w)=(w).
(iii) If (a1,,ap)R(w), then D(w) consists of the lattice points ( sapsar+1 (ar),sa1 sar-1(ar) ) for r=1,2,,p.

In particular, it follows from (iii) above that


(i) If (wsr)>(w), then D(wsr)= (sr×1)D(w) {(r,wr)}.
(ii) If (srw)>(w), then D(wsr)= (1×sr)D(w) {(w-1r,r)}.

The code of a permutation

Let wSn, and for each i1 let

ci(w)=Card { j:j>iandw(j) <w(i) } .

Thus ci(w) is the number of points in the ith row of I(w), or equivalently the number of points in the ith row of D(w). The vector

c(w)= (c1(w),,cn(w)) n

is called the code of w. As with partitions, we may disregard any string of zeros at the right-hand end of c(w), and with this convention the code c(w) (like the diagram D(w)) is unchanged by the embedding of Sn in Sm where m>n and is well-defined for all wS.

The permutation w may be reconstructed from its code c(w)=(c1,c2,) as follows :- for each i1, w(i) is the (ci+1)th element, in increasing order, of the sequence of positive integers from which w(1),w(2),,w(i-1) have been deleted. The sum |c|=c1+c2+ is equal to (w). Each sequence c=(c1,c2,) of non-negative integers such that |c|< occurs as the code of a unique permutation wS.

The length of c(w) is the largest r such that cr(w)0. From the definition, r is the last descent of the permutation w, that is to say w(r)>w(r+1) and w(r+1)<w(r+2)<.


(i) If (wsr)>(w) (i.e., if w(r)<w(r+1)) then c(wsr)=src (w)+εr, where εr is the sequence with 1 in the rth place and 0 elsewhere.
(ii) If (a1,,ap)R(w) then c(w)=i=1p sapsai+1 (εai).


(i) follows from (1.21)(i), and (ii) follows from (i) by induction on p.

(1.24) Let i1. Then

ci(w)>ci+1 (w)w(i)> w(i+1).


Suppose that w(i)>w(i+1). Then the (i+1)th row of I(w) is strictly contained in the ith row, whence ci(w)>ci+1(w). Conversely, if w(i)<w(i+1), then the ith row of I(w) is contained in the (i+1)th row, so that ci(w)ci+1(w).

To compute the code of w-1 in terms of the code (c1,c2,) of w, we introduce the following notation. If u=(u1,u2,) is any sequence and r is an integer 0, let

ζru= ( u1,u2,,ur, 0,ur+1,ur+2 , )

so that the operation ζr introduces a zero after the rth place. Then we have

(1.25) c(w-1)= i1 ζc1 ζci-1 (1ci)

where (1ci) is the sequence consisting of ci 1's.


By induction on the length of c(w) it is enough to show that if w1 is the permutation whose code is (c2,c3,) then

(1) c(w-1)= (1c1)+ ζc1c (w1-1).

Now the diagram of w1 is obtained from that of w by deleting the first row (of length c1) and then moving each column after the c1th one space to the left. On reading the diagrams of w and w1 by columns, we obtain (1).

The shape λ(w) of a permutation w is the partition whose parts are the non-zero ci(w), arranged in weakly decreasing order. We have

|λ(w)|=Card D(w)=(w).

Next, recall that for two partitions λ=(λ1,λ2,) and μ=(μ1,μ2,) the relation λμ means that |λ|=|μ| and λ1++λiμ1++μi for all i1 [Mac1979, Ch.I], With this understood, the shapes of w and w-1 are related by

(1.26) λ(w)λ(w-1).


Let λ=λ(w), μ=λ(w-1). Define a matrix M=(mij) as follows: mij=1 if (i,j)D(w), and mij=0 otherwise. Then M is a (0,1) matrix with row-sums λ1,λ2, in some order, and column-sums μ1,μ2, in some order. Hence (see e.g. [Mac1979, Ch.I, §6]) we have λμ.

Vexillary permutations

Special interest attaches to those permutations wS for which λ(w)=λ(w-1). They may be characterized in various ways:

(1.27) The following conditions on a permutation wS are equivalent:

(i) the set of rows of D(w) is totally ordered by inclusion;
(i) the set of rows of I(w) is totally ordered by inclusion;
(ii) the set of columns of D(w) is totally ordered by inclusion;
(ii) the set of columns of I(w) is totally ordered by inclusion;
(iii) there do not exist a,b,c,d such that 1a<b<c<d and w(b)<w(a)<w(d)<w(c);
(iv) there exist u,vS such that (u×v)D(w) is the diagram D(λ) of a partition λ;
(v) λ(w)= λ(w-1).


Since D(w)=(1×w)I(w) it is clear that (i) (i) and (ii) (ii). Morever (i) (ii), for either is false if and only if there exist a,β,c,δ[1,n] such that a<c, β<δ and (a,β),(c,δ) belong to D(w), whilst (a,δ) and (c,β) do not. Let b=w-1(β) and d=w-1(δ); then we have a<b<c<d and w(b)<w(a)<w(d)<w(c). 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 λ(w)=λ and λ(w-1)=λ, whence (v) is satisfied. Conversely, if λ(w)=λ and λ(w-1)=λ, then D(w) can be brought into coincidence with D(λ) by suitable permutations of the rows and of the columns, whence (iv) is satisfied.

An element wS is said to be vexillary if it satisfies the equivalent conditions of (1.27). By (1.27) (iii), the first non-vexillary permutation is (2143) in S4.

For each wSn let


where as before w0=(n,n-1,,2,1) is the longest element of Sn. Then


(i) (w)=(w).
(ii) I(w) is the reflection of I(w) in the "antidiagonal" i+j=n+1.
(iii) λ(w)=λ(w).


(i) follows from (1.6) (or from (ii) below).

(ii) If i<j then

(i,j)I(w) w0ww0(i)> w0ww0(j) w(n+1-i)<w (n+1-j) (n+1-j,n+1-i) I(w).

(iii) now follows from (ii).

From (1.27) and (1.28) it follows that

(1.29) w is vexillary w-1 is vexillary w is vexillary.

Dominant permutations

We consider next two particular types of vexillary permutations.

(1.30) Let wS. 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(w) is the diagram of a partition.


Clearly (iii) implies (i) and (ii).

Conversely, suppose that c(w) is a partition λ=(λ1,,λm), where λ1λm0. We shall show by induction on i that

(i,j)D(w) 1jλi.

This is true for i=1, so assume that 1<im and that the statement is true for i-1. Then we have w(k)λi-1 for 1ki-1, and w(k)=λi-1 for some ki-1. Since λiλi-1 it follows that the ith row of D(w) consists of the points (i,j), 1jλ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(w-1) is the diagram of a partition. Hence so is D(w), by (1.21) (i), and the proof is complete.

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 wS. Then the following conditions are equivalent:

(i) c1(w) cr(w) and ci(w)=0 for i>r;
(ii) w(i)< w(i+1) unless i=r.


(i) (ii). By (1.15) we have w(1)<<w(r) and w(r+1)<<w(n). (ii) (i). We have

c(w)= ( w(1)-1,, w(r)-r ) .

If w satisfies the equivalent conditions of (1.31), w is called a Grassmannian permutation. By (1.27)(iii), Grassmannian permutations are vexillary, and wSn is Grassmannian if and only if w=w0ww0 is Grassmannian.

Enumeration of vexillary permutations

Let w be a permutation, c=c(w)=(c1,c2,) its code. Consider the following two conditions on the sequence c:

(V1) If i<j and ci>cj, then Card { k:i<k<jandck <cj } ci-cj;
(V2) If i<j and cicj, then ckci whenever i<k<j.

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


For each i1, let

ρi= { j:(i,j)D(w) }

be the ith row of D(w).

Suppose first that w is vexillary with code c=(c1,c2,). Let i<k<j be such that cicj>ck. Then ρiρjρk (where denotes strict containment), hence there exists tρj, tρk. Let s=w(k), then s<t and (since tρi) we have sρi and sρj. Hence for fixed (i,j) such that i<j and ci>cj, the number of k between i and j such that cj>ck is at most Card(ρi-ρj)=ci-cj, so that (V1) is satisfied.

Next let w be vexillary, i<k<j and ci<cj, so that ρiρj. Let sρi. If sρk then w(k)s<w(i), so that w(k) lies in ρi but not in ρj, which is impossible. Hence sρk and therefore ρiρk. So we have cick, and (V2) is satisfied.

Conversely, suppose that the code c of w satisfies (V1) and (V2). Then so does the sequence (c2,c3,) and we may therefore assume that the set {ρ2,ρ3,} is totally ordered by inclusion.

Let j>1 and suppose first that c1cj. If ρ1ρj, there exists sρj such that sρ1, so that w(1)<s<w(j). There are at least c1-cj+1 elements tρ1 such that tρj, and since each such t satisfies t<w(1)<w(j), it is of the form t=w(k) for some k between 1 and j. Since w(k)=t<w(1)<s, it follows that sρk. Since either ρkρj or ρjρk, we conclude that ρkρj (strict inclusion) and hence that ck<cj. Hence there are at least c1-cj+1 values of k between 1 and j for which ck<cj, contradicting (V1). Hence ρ1ρj.

Finally, let j>1 and c1<cj, so that w(1)<w(j). If ρ1ρj there exists sρ1 such that sρj; we have s=w(k) for some k between 1 and j, and since w(k)<w(1) we have ck<c1, contradicting (V2). Hence ρ1ρj in this case, and the proof is complete.

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

(V3) If ci>ci+1 for some i1, then ci>cj for all j>i.

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=(2571634) is not vexillary (since e.g. it contains the subword 2163) but its code is c=(13402), which satisfies (V1) and (V3) (but not (V2)).

Let w be a permutation with code c(w)=(c1,c2,). For each i1 such that ci0, let

ei=max { j:jiand cjci } .

Arrange the numbers ei in increasing order of magnitude, say ϕ1ϕm. The sequence

ϕ(w)= ( ϕ1,,ϕm )

is called the flag of w. It is a sequence of length equal to (λ), where λ is the shape of w.

Remark. There is another definition of the flag of a permutation w, due to M.Wachs [Wac1985]. For each i1 such that ci0, let

di=min { j:j>iand w(j)<w(i) } .

Arrange the numbers di-1 in increasing order of magnitude, say ϕ1*ϕm*, and let

ϕ*(w)= ( ϕ1*,, ϕm* ) .

These two notions are not equivalent. In fact

(1.33) (J. Alfano) We have ϕ(w)=ϕ*(w) if and only if the permutation w satisfies (V2).


If ci0 we have w(j)>w(i) for i<j<di, and hence cjci for these values of j. Hence di-1ei in all cases, and we shall have ϕ(w)=ϕ*(w) if and only if di-1=ei for each i. But this condition means that, for each i1, the set of ji such that cjci is an interval; and this is just a restatement of the condition (V2).

We shall show that a vexillary permutation is uniquely determined by its shape λ(w) and its flag ϕ(w).

Let us write λ=λ(w) in the form

(1.34) λ= ( p1m1, p2m2,, pkmk )

where p1>p2>>pk>0 and each mi1. For 1rk let

fr=max {j:cjpr}

so that f1fk. If c=(c1,c2,) is the code of w, each nonzero ci is equal to pr for some r, and

ei=max {j:jiandcjpr} =fr.

It follows that (whether w is vexillary or not)

(1.35) ϕ(w)= ( f1m1, f2m2,, fkmk ) .

Moreover we must have

(1.36) frm1++mr (1rk)

since in the sequence (c1,c2,) there are m1++mr terms pr, and they must all occur in the first fr places of the sequence.

(1.37) Suppose w is a vexillary pennutation with shape λ and flag ϕ given by (1.34) and (1.35). Then the fr must satisfy the inequalities

0fr-fr-1 mr+pr-1-pr.


If fr-1=fr there is nothing to prove, so assume that fr-1<fr and therefore cfr=pr. Let

s=max{i:ci=pr-1} fr-1.

Since cs=pr-1>pr=cfr and w is vexillary, we have by (V1)

(1) Card { k:s<kfrand ck<pr } pr-1-pr.


(2) Card { k:s<kfr andck=pr } mr,

since exactly mr terms of the sequence c are equal to pr.

Finally we have

(3) Card { k:s<kfr andck>pr } =fr-1-s

because ckpr for all k>fr-1, and ckpr-1 for all k such that s<kfr-1, by virtue of (V2).

From (1), (2), and (3) we deduce that

fr-spr-1- pr+mr+fr-1 -s

which proves (1.37).

(1.38) For each sequence (f1,,fk) satisfying (1.36) and (1.37) there is a unique vexillary permutation w with shape λ and flag ϕ= ( f1m1,, fkmk ) . The code c of w is constructed as follows: first the m1 entries equal to p1 are inserted at the right-hand end of the interval [1,f1]; then the m2 entries in c equal to p2 are inserted in the rightmost available spaces in the interval [1,f2], and so on: for each r1, when all the terms >pr in the sequence c have been inserted, the mr entries equal to pr are inserted in the rightmost available spaces of the interval [1,fr].


Suppose first that w is vexillary. If 1ifr and ci=pr, then by (V2) we have cjpr for all j such that i<j<fr. Hence the entries equal to pr 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 cicj: say ci=pr, cj=ps, rs. Then the number of k such that i<k<j and ck<ps is equal to the number of blank spaces in the interval [fr,fs] after all the entries pi, r+1is have been inserted, hence is at most

fs-fr- ( mr+1++ ms )

which by (1.37) is pr-ps. Hence the sequence c satisfies (V1). Suppose next that i<j and ci<cj: say ci=ps, cj=pr with r<s. Then we have jfrfs. From the definition of the sequence c, it follows that for each k such that ikfs we have ckps, and hence ckci whenever i<k<j. Consequently the condition (V2) is satisfied, and the proof is complete.

If w is a permutation and r0, we denote by 1r×w the permutation

1r×w= ( 1,2,,r,r+w(1) ,r+w(2), ) .

Let us say that two permutations w,w are diagonally equivalent if either w=1r×w or w=1r×w for some r0. Graphically, this means that the diagram of w can be brought into coincidence with that of w by a translation along the diagonal i=j, and w is vexillary if and only if w is vexillary. The equivalence classes of vexillary permutations of a given shape λ are then determined by the differences fr-fr-1 (2rk), and hence it follows from (1.37) and (1.38) that

(1.39) The number of diagonal equivalence classes of vexillary permutations of shape λ=(p1m1,,pkmk) is

r=2k ( pr-1-pr+mr +1 ) .

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 λ (i.e., the nodes with coordinates (m1++mr-1,pr), 2rk).

Example. If λ=(3221) the flag ϕ=(f1,f22,f3) must satisfy 0f2-f13, 0f3-f22. Hence there are (3+1)(2+1)=12 vexillary classes, and the representatives of these classes for which w(1)1 (or equivalently c1(w)0) are as follows:

ϕ(w)c(w)w 444412232457136 34441232246513 24441322254613 14443122425613 33342231346215 2334232135421 1334322143521 144530221415632 333522301346152 233523201354162 133532201435162 14463022014156273

1223223122301 1232232123201 1322322132201 3122302201302201

Let λ=(p1m1,,pkmk) as before and let

λ= ( q1n1, q2n2,, qknk )

be the conjugate partition, where q1>q2>>qk>0 and each ni1. We have

(1.40) { pr=n1+ +ns, qr=m1+ +ms,

where s=k+1-r (1rk). The border of the diagram of λ is a staircase with risers of heights m1,m2,,mk (starting from the top) and treads of lengths n1,n2,,nk (starting at the bottom).

Recall (1.27) that if w is vexillary of shape λ, then w-1 is vexillary of shape λ.

(1.41) Let w be a vexillary permutation of shape λ and flag ϕ(w)= ( f1m1,, fkmk ) . Then the flag of w-1 is

ϕ(w-1)= ( g1n1,, gknk )


(*) gi+qi= fk+1-i+ pk+1-i (1ik).


We proceed by induction on (w)=|λ|. Let c=(c1,c2,) be the code of w, and let w be the permutation with code c=(c2,c3,). We may assume that c10. Then c1=pr for some r, and we have

λ(w) = ( p1m1,, prmr-1 ,,pkmk ) , ϕ(w) = ( (f1-1)m1 ,, (fr-1)mr-1 ,, (fk-1)mk ) .

Since w is vexillary, its code c satisfies the conditions (V1) and (V2). Hence c also satisfies these conditions, and therefore w is vexillary. It follows that λ(w-1)=λ(w), so that

λ(w-1)= ( (q1-1)n1 ,, (qs-1)ns, qs+1ns+1 ,, qknk )

where s=k+1-r. We have (w)=(w)-c1, so that the inductive hypothesis applies to w. Hence if g1,,gk are defined by the formula (*), we have

(1) ϕ(w-1)= ( g1n1,, gsns, (gs+1-1)ns+1 ,, (gk-1)nk ) .

But if w-1 has code c(w-1)=(d1,d2,) then by (1.25) we have

(2) c(w-1)= ( d1+1,, dpr+1,0, dpr+1, dpr+2, ) .

From (1) and (2) and (1.40) it follows that

ϕ(w-1)= ( g1n1,, gsns, gs+1ns+1, ,gknk )

as required.

If wSn, let wn=w0ww0, where w0 is the longest element in Sn. If w is vexillary, of shape λ, then wn is vexillary of shape λ, by (1.27) and (1.28). Let

ϕ(wn)= ( f1n1,, fknk )

be the flag of wn. Then we have

(1.42) fi=n- fk+1-i (1ik) .

For once we shall leave the proof to the reader.

Let Nn denote the number of non-vexillary wSn, and let


be the probability that an element of Sn is non-vexillary. The first few values of Nn and Pn are

nNnPn 100 200 300 41.042 517.142 6207.288 72279*.452

* was computed by A. Garsia. I would guess that N8 is of the order of 24000.

If we divide up the sequence (w(1),,w(n)) 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 S4 contains only one non-vexillary permutation), we see that the probability that wSn is vexillary is at most (23/24)[n/4], hence decreases exponentially to zero. (A. Lascoux.) Thus the vexillary permutations in Sn 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 wSn is primitive if w(1)1 and w(n)n. For each n1, let Vn (resp. Un) denote the number of vexillary (resp. primitive vexillary) permutations wSn. Since each primitive vexillary wSn gives rise to r+1 imprimitive vexillary permutations in Sn+r, namely 1p×w×1q where p,q0 and p+q=r, it follows that

Vn=1+Un+2 Un-1+3Un-2 +

Hence the generating functions

V(t) = n1 Vntn U(t) = n1 Untn

are related by

(1.43) V(t)= t1-t+ U(t)(1-t)2 .

For each partition λ0, let Un,λ denote the number of primitive vexillary permutations of shape λ in Sn, and let

Uλ(t)= n1Un,λ tn,

so that

(1.44) U(t)=λ0 Uλ(t).

Each Uλ(t) is a polynomial, and we shall now show how to compute it. Write λ in the form

λ= ( p1m1, p2m2, ,pkmk )

as before, where p1>p2>>pk>0. By (1.37) a vexillary permutation w of shape λ is uniquely determined by its flag ϕ(w)= ( f1m1,, fkmk ) , where (f1,,fk) is any vector of positive integers satisfying the inequalities (1.36), (1.37):

frm1++mr (1rk), 0<fr-fr-1 mr+pr-1- pr(2rk).

Moreover we shall have w(1)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

(1) fr=m1++mr for somer+1,,k.

In general, if c=(c1,c2,) is the code of a permutation w, then wSn if and only if nci+i for 1ir, where r is the length of c. In other words, the least n for which wSn is n=max{ci+i:1ir}. In the case of a vexillary permutation w as above, with flag (f1m1,,fkmk), the numbers ci+i will increase strictly as i runs through each non-empty interval [fr-1+1,fr] (r=1,,k), and hence w will be primitive in Sn if and only if w satisfies (1) above and

(2) n=max { pr+fr: 1rk } .

Let πr=m1++mr for 1rk and put


so that ur0 for each r. From (1.36) we have

(3) π1+u1 π2+u2 πk+uk


mr+pr-1-pr fr-fr-1 = (ur+πr)- (ur-1+πr-1) = mr+ur-rr-1

so that

(4) p1+u1 p2+u2 pk+uk.

It now follows that

(1.45) Uλ(t)= u tmax{pr+πr+ur:1rk}

summed over the integer vectors u=(u1,,uk)k having at least one zero component, and satisfying the inequalities (3), (4) above. We have

Uλ(1)=r=2k ( mr+pr-1- pr+1 )


Uλ(t)= Uλ(t)

(since wSn is primitive vexillary of shape λ if and only if w-1 is primitive vexillary of shape λ).

Added in proof

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

(1) Vn= |λ|=n(λ)3 (fλ)2

where fλ is the degree of the irreducible representation of the symmetric group Sn indexed by the partition λ. From this and results of A. Regev (Advances in Math. 41 (1981) 115-136) it follows that

(2) Vnc9n n-4

as n, where c is a constant that Regev determines explicitly.

The formula (1) gives that N8=24553.

Notes and References

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

page history