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)

H»

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