<<

. 6
( 14 .)



>>

We now have all the ingredients to state the main result (due to Schen-
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:

<<

. 6
( 14 .)



>>