sted) on longest increasing and decreasing subsequences. If we apply the

Schensted correspondence to the permutation w and get a pair (P, Q) of

reverse SYT of shape » = (»1 , »2 , . . .), then Property 1 tells us that

d(w) = »1 .

In words, the length of the longest decreasing subsequence of w is equal to the

largest part of » (the length of the ¬rst row of P ). Now apply the Schensted

¯¯

correspondence to the reverse permutation w, obtaining the pair (P , Q) of

¯

reverse SYT. When we reverse a permutation, increasing subsequences are

changed to decreasing subsequences and vice versa. In particular, d(w) = ¯

¯

i(w). By Property 1, d(w) is just the length of the ¬rst row of P . By Property

¯

¯

2, the length of the ¬rst row of P is just the length of the ¬rst column of P .

Thus i(w) = (»), the number of parts of ».

We have shown that for a permutation w with i(w) = p and d(w) = q,

the shape » of the corresponding reverse SYT P (and Q) satis¬es (») = p

and »1 = q. Hence the number An (p, q) of permutations w of 1, 2, . . . , n with

i(w) = p and d(w) = q is equal to the number of pairs (P, Q) of reverse SYT

of the same shape », where » is a partition of n with (») = p and »1 = q.

How many such pairs are there? Given the partition », the number of choices

for P is just f » , the number of SYT of shape ». (Recall that the number of

SYT of shape » and the number of reverse SYT of shape » is the same, since

we can replace i by n + 1 ’ i.) Similarly there are f » choices for Q, so there

2

are f » choices for (P, Q). Hence we obtain our main result on increasing

and decreasing subsequences:

Schensted™s Theorem. The number An (p, q) of permutations w of

2

1, 2, . . . , n satisfying i(w) = p and d(w) = q is equal to the sum of all f » ,

where » is a partition of n satisfying (») = p and »1 = q.

Let us see how the Erd˝s-Szekeres theorem follows immediately from

o

Schensted™s theorem. If a partition » of n satis¬es (») = p and »1 = q, then

n = »1 + »2 + · · · + »p

¤ q + q + · · · + q (p terms in all)

= pq.

34

Hence if n > pq, then either (») ≥ p + 1 or »1 ≥ q + 1. If we apply the

Schensted correspondence to a permutation w of 1, 2, . . . , n then we get a

pair of reverse SYT of some shape », where » is a partition of n. We have

just shown that (») ≥ p + 1 or »1 ≥ q + 1, so by Schensted™s theorem either

i(w) ≥ p + 1 or d(w) ≥ q + 1.

We can evaluate each f » appearing in Schensted™s theorem by the hook-

length formula. Hence the theorem is most interesting when there are few

partitions » satisfying (») = p and »1 = q. The most interesting case occurs

when n = pq. The fact that there is at least one permutation satisfying

i(w) = p and d(w) = q (when n = pq) shows that the Erd˝s-Szekeres theorem

o

is best possible (see equation (21)). Now we are asking for a much stronger

result ” how many such permutations are there? By Schensted™s theorem,

we ¬rst need to ¬nd all partitions » of n such that (») = p and »1 = q.

Clearly there is only one such partition, namely, the partition with p parts

2

all equal to q. Hence for this partition » we have An (p, q) = f » . We may

assume for de¬niteness that p ¤ q (since An (p, q) = An (q, p)). In that case

the hook-lengths of » are given by 1 (once), 2 (twice), 3 (three times), . . ., p

(p times), p + 1 (p times), . . ., q (p times), q + 1 (p ’ 1 times), q + 2 (p ’ 2

times), . . ., p + q ’ 1 (once). We ¬nally obtain the amazing formula (for

n = pq)

2

(pq)!

An (p, q) = 1 2 .

1 2 · · · pp (p + 1)p · · · q p (q + 1)p’1 (q + 2)p’2 · · · (p + q ’ 1)1

For instance, when p = 4 and q = 6 we easily compute that

2

24!

A24 (4, 6) =

11 22 33 44 54 64 73 82 91

= 19, 664, 397, 929, 878, 416.

This large number is still only a small fraction .00000003169 of the total

number of permutations of 1, 2, . . . , 24.

35

6 Reduced decompositions.

There is a remarkable and unexpected connection between standard Young

tableaux and the building up of a permutation by interchanging (transposing)

two adjacent entries. We begin with the identity permutation 1, 2, . . . , n.

We wish to construct from it a given permutation as quickly as possible by

interchanging adjacent elements. By “as quickly as possible,” we mean in

as few interchanges (called adjacent transpositions) as possible. This will

be the case if we always transpose two elements a, b appearing in ascending

order. For instance, one way to get the permutation 41352 from 12345 with

a minimum number of adjacent transpositions is as follows, where we have

marked in boldface the pair of elements to be interchanged:

12345 ’ 13245 ’ 13425 ’ 14325 ’ 41325 ’ 41352. (22)

Such sequences of interchanges are used in some of the sorting algorithms

studied in computer science (see Section 11), although there it is natural

to consider the reverse process whereby a list of numbers such as 41352 is

step-by-step converted to the “sorted” list 12345. Note that the ¬ve steps

in the sequence (22) are the minimum possible, since in the ¬nal permuta-

tion 41352 there are ¬ve pairs (i, j) out of order, i.e., i appears to the left

of j and i > j (namely, (4, 1), (4, 3), (4, 2), (3, 2), (5, 2)), and each adjacent

transposition can make at most one pair which was in order go out of order.

It would be ine¬cient to transpose a pair (a, b) that is in order in the ¬nal

permutation, since we would only have to change it back later. A pair of

elements of a permutation w that is out of order is called an inversion of

w. The number of inversions of w is denoted inv(w) and is an important

invariant of a permutation, in a sense measuring how “mixed up” the per-

mutation is. For instance, inv(41352) = 5, the inversions being the ¬ve pairs

(4, 1), (4, 3), (4, 2), (3, 2), (5, 2).

A sequence of adjacent transpositions that converts the identity permu-

tation to a permutation w in the smallest possible number of steps (namely,

inv(w) steps) is called a reduced decomposition of w. Equation (22) shows

one reduced decomposition of the permutation w = 41352, but there are

many others. We can therefore ask for the number of reduced decomposi-

tions of w. We denote this number by r(w). The reader can check that

every permutation of the numbers 1, 2, 3 has only one reduced decomposi-

36

tion, except that r(321) = 2. The two reduced decompositions of 321 are

123 ’ 213 ’ 231 ’ 321 and 123 ’ 132 ’ 312 ’ 321.

The remarkable connection between r(w) and SYT™s is the following. For

each permutation w, one can associate a small collection Y (w) of Young

diagrams (with repetitions allowed) whose number of squares is inv(w), such

that r(w) is the sum of the number of SYT whose shapes belong to Y (w). We

are unable to explain here the exact rule (based on a variant of the Schensted

correspondence) for computing Y (w), but we will discuss the most interesting

special case. We also will not explain exactly what is meant by a “small”

collection, but in general its number of elements will be much smaller than

r(w) itself.

Example. Here are a few examples of the collection Y (w).

(a) If w = 41352 (the example considered in equation (22)), then Y (w)

consists of the single diagram

of shape (3, 1, 1). Since there are six SYT of this shape (computed from

the hook-length formula (17) or by direct enumeration), it follows that

there are six reduced decompositions of 41352.

(b) If w = 654321 then again Y (w) is given by a single diagram, this time

.

Hence

r(w) = f (5,4,3,2,1)

37

15!

=

15 · 34 · 53 · 72 · 9

= 292, 864.

(c) If w = 321654, then Y (w) consists of the diagrams whose shapes are

(writing for instance 42 as short for (4, 2)) 42, 411, 33, 321, 321, 3111,

222, 2211. Note that the shape 321 appears twice. We get

r(w) = f 42 + f 411 + f 33 + 2f 321 + f 3111 + f 222 + f 2211

= 9 + 10 + 5 + 2 · 16 + 10 + 5 + 9

= 80.

Clearly the formula for r(w) will be the simplest when Y (w) consists of

a single partition », for then we have r(w) = f » , given explicitly by (17). A

simple though surprising characterization of all permutations for which Y (w)

consists of a single partition is given by the next result. Such permutations

are called vexillary after the Latin word vexillum for “¬‚ag,” because of a

relationship between reduced decompositions and certain objects in algebraic

geometry known as ¬‚ag varieties.

Vexillary theorem. Let w = w1 w2 · · · wn be a permutation of 1, 2, . . . , n.

Then Y (w) consists of a single partition » if and only if there do not exist

a < b < c < d such that wb < wa < wd < wc . Moreover, if ±i is the number

of j™s for which i < j and wi > wj , then the parts of » are just the nonzero

±i ™s.

As an illustration of the above theorem, let w = 526314. One sees by in-

spection that w satis¬es the conditions of the theorem. We have (±1 , . . . , ±6 ) =

(4, 1, 3, 1, 0, 0). Hence » = (4, 3, 1, 1) and r(w) = f (4,3,1,1) = 216.

It is immediate from the above result that all the permutations of 1, . . . , n

for n ¤ 3 are vexillary, and that there is just one nonvexillary permutation

of 1, 2, 3, 4, namely, 2143. It has been computed that if v(n) denotes the

number of vexillary permutations of 1, 2, . . . , n then v(5) = 103 (out of 120

permutations of 1, 2, . . . , n in all), v(6) = 513 (out of 720), v(7) = 2761 (out

of 5040), and v(8) = 15767 (out of 40320). Simple methods for computing

38

and approximating v(n) have been given by Julian West (b. 1964) and Amitai

Regev (b. 1940).

There is one class of vexillary permutations of particular interest. These

are the permutations w0 = n, n ’ 1, . . . , 1, for which » = (n ’ 1, n ’ 2, . . . , 1).

There is an elegant bijection between the SYT of shape (n’1, n’2, . . . , 1) and

the reduced decompositions of w0 , due to Paul Henry Edelman (b. 1956) and

Curtis Greene (b. 1944). Begin with an SYT of shape (n ’ 1, n ’ 2, . . . , 1)

and write the number i at the end of the ith row, with n written at the

bottom of the ¬rst column. We will call the numbers outside the diagram

exit numbers. An example is given by:

1 3 4 6 1

2 8 10 2

5 9 3

7 4

5

Now take the largest number in the SYT (in this case 10) and let it “exit”

the diagram to the southeast (between the 2 and 3). Whenever a number

exits the diagram, transpose the two exit numbers that it goes between.

Hence we now have:

39

1 3 4 6 1

2 8 3

5 9 2

7 4

5

In the hole left by the 10, move the largest of the numbers directly to the

left or above the hole. Here we move the 8 into the hole, creating a new hole.

Continue to move the largest number directly to the left or above a hole into

the hole, until such moves are no longer possible. Thus after exiting the 10,

we move the 8, 3, and 1 successively into holes, yielding:

1 4 6 1

2 3 8 3

5 9 2

7 4

5

Now repeat this procedure, ¬rst exiting the largest number in the diagram

(ignoring the exit numbers), then transposing the two exit numbers between

which this largest number exits, and then ¬lling in the holes by the same

method as before. Hence for our example 9 exits, 5 ¬lls in the hole left by 9,

and 2 ¬lls in the hole left by 5, yielding: