<<

. 4
( 14 .)



>>




20
increasing. An example of an SYT of shape (4, 3, 2) is given by
1346
278 (16)
59
There are exactly ten SYT of size four (that is, with four entries), given by
1234 123 124 134 12 13 12 13 14 1
4 3 2 34 24 3 2 2 2
4 4 3 3
4
Standard Young tableaux have a number of interpretations which make them
of great importance in a variety of algebraic, combinatorial, and probabilistic
problems. Here we will only mention a classical problem called the ballot
problem, which has numerous applications in probability theory. Given a
partition » = (»1 , . . . , » ) as above with »1 + · · · + » = n, we suppose that
an election is being held among candidates A1 , . . . , A . At the end of the
election candidate Ai receives »i votes. The voters vote in succession one
at a time. We record the votes of the voters as a sequence a1 , a2 , . . . , an ,
where aj = i if the jth voter votes for Ai . The sequence a1 , a2 , . . . , an is
called a ballot sequence (of shape ») if at no time during the voting does any
candidate Ai trail another candidate Aj with j > i. Thus the candidates
maintain their relative order (allowing ties) throughout the election. For
instance, the sequence 1, 2, 1, 3, 1, 3, 4, 2 is not a ballot sequence, since at the
end A2 and A3 receive the same number of votes, but after six votes A2 trails
A3 . On the other hand, the sequence 1, 2, 1, 3, 1, 2, 4, 3 is a ballot sequence.
Despite the di¬erence in their descriptions, a ballot sequence is nothing more
than a disguised version of an SYT. Namely, if T is an SYT, then de¬ne
aj = i if j appears in the ith row of T . A little thought should convince the
reader that the sequence a1 , a2 , . . . , an is then a ballot sequence, and that
all ballot sequences come in this way from SYT™s. For instance, the SYT of
equation (16) corresponds to the ballot sequence 1, 2, 1, 1, 3, 1, 2, 2, 3.

It is natural (at least for a practitioner of combinatorics) to ask how many
SYT there are of a given shape ». This number is denoted f » . For instance,
there are nine SYT of shape (4, 2), which we write as f 4,2 = 9. These nine
SYT are given by
1234 1235 1236 1245 1246 1256 1345 1346 1356
56 46 45 36 35 34 26 25 24

21
A formula for f » (stated in terms of ballot sequences) was given by MacMa-
hon in 1900. A simpli¬ed version was given was James Sutherland Frame
(1907“1997), Robinson (mentioned earlier in connection with the Schensted
correspondence), and Robert McDowell Thrall (b. 1914) in 1954, and is
known as the Frame-Robinson-Thrall hook-length formula. To state this
formula, we de¬ne a Young diagram of shape » as a left-justi¬ed array of
squares with »i squares in the ith row. For instance, a Young diagram of
shape (5, 5, 2) looks like

.




An SYT of shape » can then be regarded as an insertion of the numbers
1, 2, . . . , n (each appearing once) into the squares of a Young diagram of
shape » such that every row and column is increasing. If s is a square of a
Young diagram, then de¬ne the hook-length of s to be the number of squares
to the right of s and in the same row, or below s and in the same column,
counting s itself once. In the following ¬gure, we have inserted inside each
square of the Young diagram of shape (5, 5, 2) its hook-length.

7 6 4 3 2
6 5 3 2 1
2 1

The hook product H» of a partition » is the product of the hook-lengths of
its Young diagram. Thus for instance from the above ¬gure we see that
H5,5,2 = 7 · 6 · 4 · 3 · 2 · 6 · 5 · 3 · 2 · 1 · 2 · 1 = 362, 880.
The Frame-Robinson-Thrall hook-length formula states that
n!
f» = , (17)

where » is a partition of n and n! (read “n factorial”) is short for 1 · 2 · · · n.
For instance,
12!
f 5,5,2 = = 1320.
362, 880

22
It is remarkable that such a simple formula for f » exists, and no really
simple proof is known. The proof of Frame-Robinson-Thrall amounts to sim-
plifying MacMahon™s formula for f » , which MacMahon obtained by solving
di¬erence equations (the discrete analogue of di¬erential equations). Other
proofs were subsequently given, including several bijective proofs, but none
is as simple as the proof we have sketched of equation (8) using Schensted™s
correspondence.

In addition to their usefulness in combinatorics, SYT also play a signi¬-
cant role in the theory of symmetry. This important theory was developed
primarily by Alfred Young (1873“1940), who was a clergyman by profes-
sion and a fellow of Clare College, Cambridge, a Canon of Chelmsford, and
Rector of Birdbrook, Essex (1910“1940). Roughly speaking, this theory de-
scribes the possible “symmetry states” of n objects. See the Box entitled
“Connections with representation theory” for more details. An immediate
consequence of this theory is that the number of ordered pairs of SYT of the
same shape and with n squares is equal to n!, the number of permutations
of n objects. For instance, when n = 3 we get the six pairs

12 12 12 13
123 123 33 32

11
13 12 13 13 22 .
23 22 33
The fact that the number of pairs of SYT of the same shape and with n
squares is n! can also be expressed by the formula
2
f» = n!, (18)
»n

where » n denotes that » is a partition of n. A combinatorialist will imme-
diately ask whether there is a bijective proof of this formula. In other words,
given a permutation w of the numbers 1, 2, . . . , n, which may be regarded as
simply a way of listing them in some order, such as 5, 2, 7, 6, 1, 4, 3 (or just
5276143 when no confusion can arise), can we associate with w a pair (T1 , T2 )
of SYT of the same shape and with n squares, such that every such pair oc-
curs exactly once? In fact we have already seen the solution to this problem
” it is just a special case of the Schensted correspondence! There is only one

23
134 976
268 842
59 51
7 3

Figure 3: An SYT and its corresponding reverse SYT

minor technicality that needs to be explained before we apply the Schensted
correspondence. Namely, the column-strict plane partitions we were dealing
with before have every row and column decreasing, while SYT have every
row and column increasing. However, given a plane partition whose entries
are the integers 1, 2, . . . , n, each appearing once (so it will automatically be
column-strict), we need only replace i by n + 1 ’ i to obtain an SYT of the
same shape. We will call a plane partition whose (nonzero) parts are the
integers 1, 2, . . . , n, each appearing once, a reverse SYT. An example of an
SYT and the corresponding reverse SYT obtained by replacing i with n+1’i
is shown in Figure 3.

So consider now a permutation such as 5, 2, 6, 1, 4, 7, 3. Write this as the
second line of a two-line array whose ¬rst line is n, n ’ 1, . . . , 1. Here we get
the two-line array
7654321
A= .
5261473
When we apply the Schensted correspondence to this two-line array, we will
obtain a pair of column-strict plane partitions of the same shape whose parts
are 1, 2, . . . , n, each appearing once. Namely, we get

743 764
621 531 .
5 2

If we replace i by 8 ’ i, we get the following pair of SYT of the same shape
(3, 3, 1):
145 124
267 357 .
3 6


24
The process is reversible; that is, beginning with a pair (P, Q) of SYT of
the same shape, we can reconstruct the permutation that produced it. (The
details of this argument are left as an exercise.) Therefore the number of
pairs of SYT of the same shape and with n entries is equal to the number
of permutations a1 , . . . , an of 1, 2, . . . , n, yielding the formula (18). This
remarkable connection between permutations and tableaux is the foundation
for an elaborate theory of permutation enumeration. In the next section we
give a taste of this theory.




BOX: Connections with representation theory. In this box we
assume familiarity with the fundamentals of representation theory. First we
consider the group G = GL(n, C) of all invertible linear transformations on
an n-dimensional complex vector space V . We will identify G with the group
of n — n invertible complex matrices. A polynomial representation of G of
degree N is a homomorphism • : G ’ GL(N, C), such that for A ∈ G,
the entries of the matrix •(A) are polynomials (independent of the choice
of A) in the entries of A. For instance, one can check directly that the map
• : GL(2, C) ’ GL(3, C) de¬ned by
®2 
b2
a 2ab
ab
’ ° ac ad + bc bd »
• (19)
cd 2 2
c 2cd d

preserves multiplication (and the identity element), and hence is a polynomial
representation of GL(2, C) of degree 3. Let • : GL(n, C) ’ GL(N, C) be a
polynomial representation. If the eigenvalues of A are x1 , . . . , xn , then the
eigenvalues of •(A) are monomials in the xi ™s. For instance, in equation (19)
one can check that if x1 and x2 are the eigenvalues of A, then the eigenvalues
of •(A) are x2 , x1 x2 , and x2 . The trace of •(A) (the sum of the eigenvalues)
1 2
is therefore a polynomial in the xi ™s which is a sum of N monomials. This
polynomial is called the character of •, denoted char(•). For • as in (19),
we have
char(•) = x2 + x1 x2 + x2 .
1 2

Some of the basic facts concerning the characters of GL(n, C) are the follow-
ing:

25
• Every polynomial representation (assumed ¬nite-dimensional) of the
group GL(n, C) is completely reducible, i.e., a direct sum of irreducible
polynomial representations. These irreducible constituents are unique
up to equivalence.

• The characters of irreducible representations are homogeneous sym-
metric functions in the variables x1 , . . . , xn , and only depend on the
representation up to equivalence.

• The characters of inequivalent irreducible representations are linearly
independent.


The e¬ect of these properties is that once we determine the character of
a polynomial representation • of GL(n, C), then there is a unique way to
write this character as a sum of irreducible characters. The representation
• is determined up to equivalence by the multiplicity of each irreducible
character in char(•). Hence we are left with the basic question of describing
the irreducible character of GL(n, C). The main result is the following.

Fundamental theorem on the polynomial characters of GL(n, C).
The irreducible characters of GL(n, C) are in one-to-one correspondence with
the partitions » = (»1 , . . . , »n ) with at most n parts. The irreducible character
s» = s» (x1 , . . . , xn ) corresponding to » is given by

xT ,
s» (x1 , . . . , xn ) =
T

where T ranges over all column-strict plane partitions of shape » and largest
part at most n, and where xT denotes the monomial

xT = xnumber of 1™s in T xnumber of 2™s in T · · · .
1 2



For instance, let n = 2 and let » = (2, 0) be the partition with just one
part equal to two (and no other parts). The column-strict plane partitions
of shape (2, 0) with largest part at most 2 are just 11, 21, and 22. Hence
(abbreviating s(2,0) as s2 ),

s2 (x1 , x2 ) = x2 + x1 x2 + x2 .
1 2


26
This is just the character of the representation de¬ned by equation (19).
Hence this representation is one of the irreducible representations of GL(2, C).

As another example, suppose that n = 3 and » = (2, 1, 0). The corre-
sponding column-strict plane partitions are
21 22 31 31 32 32 33 33 .
1 1 1 2 1 2 1 2
Hence
s» (x1 , x2 , x3 ) = x2 x2 + x1 x2 + x2 x3 + 2x1 x2 x3 + x2 x3 + x1 x2 + x2 x2 .
1 2 1 2 3 3

The fact that we have eight column-strict plane partitions in this case is

<<

. 4
( 14 .)



>>