
290 Combinatorics of Permutations, Second Edition
4 3 1
7 6 5 8 2
9
FIGURE 7.13
A balanced tableau.
out to be remarkably interesting. It was first answered by Richard Stanley
[238], who proved his own conjecture showing that the number of maximal
chains of P
n
is equal to the number of Standard Young Tableaux of shape
(n − 1,n− 2, ···, 2, 1). The proof in [238] uses symmetric functions, so the
quest for a combinatorial proof has continued. At this point, we mention
that a chain connecting permutation p to the identity permutation is called
a reduced decomposition of p, so the task at hand is finding the number of
reduced decompositions of n(n − 1) ···21.
A