Combinatorial Aspects
of the
Lascoux-Schützenberger Tree


A Bit of History

In a remarkable seminal paper (Europ. J. Comb. 5 (1984), 359-372) R. Stanley set himself the task of enumerating, for a given tex2html_wrap_inline202 the collection tex2html_wrap_inline204 of the reduced words yielding sigma. To be precise, for a given word tex2html_wrap_inline208, let us set

Gessel Quasi-symmetric Functions

These polynomials are known as the ``Gessel quasi-symmetric functions''. Stanley was led to the bold step of setting for each tex2html_wrap_inline202 with tex2html_wrap_inline214 and N large enough

Stanley Symmetric Function

Stanley proves that tex2html_wrap_inline220 is symmetric and conjectures that it has a Schur function expansion of the form

Schur positivity

with coeffcients tex2html_wrap_inline224 and tex2html_wrap_inline86 a suitable collection of partitions of the integer tex2html_wrap_inline228. Stanley proves this conjecture for the so called ``vexillary '' permutations. These are the permutations that avoid the pattern ``2143''. He also shows that for these permutations, tex2html_wrap_inline86 reduces to a single term, in fact tex2html_wrap_inline234, where for a permutation sigma, the symbol tex2html_wrap_inline238 denotes the partition obtained by rearranging the inversion code of sigma. In the years that followed there appeared several proofs of Stanley's conjecture . Two combinatorial proofs were given by Edelman-Greene (Advances in Math. Math. 63 (1987), 42-99) and Lascoux-Schützenberger (C. R. Acad. Sci. Paris 295 (1982) 629-633). These two proofs used essentially the same basic idea.

In a course given at UCSD in winter 2001, Garsia noted that a new algorithm for the calculation of Littlewood-Richardson coefficients given by Lascoux-Schützenberger in (Letters in Math. Physics 10 (1985) 111-124) yielded what may certainly be viewed as the most fascinating approach to determining the coefficients in (1). Garsia's proof of the validity of this algorithm may be found in full detail in the manuscript The Saga of Reduced Factorizations of Elements of the Symmetric Group, which gives a complete account of the material covered in the course. Since Garsia's proof relies on the theory of Schubert polynomials it cannot be considered elementary. A paper giving a completely elementary, purely combinatorial proof of the validity of the algorithm will soon be available.

This proof is based on the construction, for each permutation tex2html_wrap_inline202, of a Robinson-Schensted-like correspondence mapping each word tex2html_wrap_inline244 into the pair tex2html_wrap_inline246 where tex2html_wrap_inline248 is a `` Grassmanian'' permutation (i.e. a permutation with only one descent) and T(w) is a standard tableau of shape tex2html_wrap_inline254. The following Applet carries out this correspondence. Experimenting with this Applet the user may notice that for the permutation tex2html_wrap_inline256 the map tex2html_wrap_inline258 is essentially the Schensted correspondence where T(w) is the ``right tableau'', on the other hand for the permutation tex2html_wrap_inline120 the map turns out to be essentially the Edelman-Greene correspondence. The Applet starts from a line diagram of a word tex2html_wrap_inline244 and ends with the line diagram of a word tex2html_wrap_inline124. As a result one obtains a very beautiful combinatorial proof and interpretation for the coefficients tex2html_wrap_inline268 in (1).

To be precise, the bijection proceeds along the branches of a tree associated to each permutation by Lascoux-Schützenberger. So a few words describing this tree should perhaps be included here. For this we need some notation. To begin let tex2html_wrap_inline270 denote the transposition (r,s). Next for a permutation tex2html_wrap_inline274 and an integer tex2html_wrap_inline276 set


For a given permutation tex2html_wrap_inline138 set tex2html_wrap_inline140. This given, the children of a permutation sigma in the LS tree are obtained by the following ``Branching Algorithm''

  1. Locate the last descent of sigma. If this occurs at r then let s be the largest index such that s>r and tex2html_wrap_inline152.
  2. Set tex2html_wrap_inline296.
  3. If tex2html_wrap_inline298 then the children of sigma are the permutations tex2html_wrap_inline302. Otherwise sigma has only one child, namely tex2html_wrap_inline310 .

It can be shown that if we go down a tree constructed by this branching process, starting from a root tex2html_wrap_inline312 with first descent at tex2html_wrap_inline314 and last descent at tex2html_wrap_inline316 then in no more than tex2html_wrap_inline318 steps we must encounter a Grassmanian permutation. This given, the LS tree of a permutation tex2html_wrap_inline312 is simply the tree constructed by this branching process with the requirement to stop the first time we hit a Grassmanian child. In this manner all the leaves will be Grassmanian. Denoting their collection ``tex2html_wrap_inline322'', it is shown in SAGA that we have the following remarkable fact


Since Grassanian permutations are vexillary, it follows from Stanley's theorem that for each of these leaves we have tex2html_wrap_inline326. Thus (2) not only gives the Schur function expansion of tex2html_wrap_inline328 but it yields a beautiful combinatorial interpretation for the coefficients. Now (2) itself is but an immediate consequence of the following key identity


where tex2html_wrap_inline332 here denotes the collection of children of sigma. In SAGA this identity is derived from Monk's rule for Schubert polynomials.

Now to prove (3) (and therefore also (2)) combinatorially all we need to do is construct a descent preserving bijection between the following two sets of words

Sets 1

Moreover once this bijection is constructed, we can start with tex2html_wrap_inline338 and, by iteration, go down the LS tree of tex2html_wrap_inline312 until we reach the word of a leaf. In ultimate analysis we obtain in this manner a descent preserving bijection between the following two sets of words

Sets 2

The Applet carries out this bijection.