The Robinson-Schensted and Schützenberger algorithms, an elementary approach

Marc A. A. van Leeuwen CWI Postbus 94079 1090 GB Amsterdam, The Netherlands

                                   email: M.van.Leeuwen@cwi.nl

Dedicated to Dominique Foata on the occasion of his 60^{th} birthday

Submitted: February 6, 1995; Accepted: July 25, 1995

Abstract We discuss the Robinson-Schensted and Schützenberger algorithms, and the fundamental identities they satisfy, systematically interpreting Young tableaux as chains in the Young lattice. We also derive a Robinson-Schensted algorithm for the hyperoctahedral groups. Finally we show how the mentioned identities imply some fundamental properties of Schützenberger’s glissements.

§0. Introduction.

The two algorithms referred to in our title are combinatorial algorithms dealing with Young tableaux. The former was found originally by G. de B. Robinson [Rob], and independently rediscovered much later, and in a different form, by C. Schensted [Sche]; it establishes a bijective correspondence between permutations and pairs of Young tableaux of equal shape. The latter algorithm (which is sometimes associated with the term jeu de taquin) was introduced by M. P. Schützenberger [Schü1], who also demonstrated its great importance in relation to the former algorithm; it establishes a shape preserving involutory correspondence between Young tableaux. These algorithms have been studied mainly for their own sake—they exhibit quite remarkable combinatorial properties—rather than primarily serving (as is usually the case with algorithms) as a means of computing some mathematical value.

0.1. Some history.

The Robinson-Schensted algorithm is the older of the two algorithms considered here. It was first described in 1938 by Robinson [Rob], in a paper dealing with the representation theory of the symmetric and general linear groups, and in particular with an attempt to prove the correctness of the rule that Littlewood and Richardson [LiRi] had given for the computation of the coefficients in the decomposition of products of Schur functions. Robinson’s description of the algorithm is rather obscure however, and his proof of the Littlewood-Richardson rule incomplete; apart from the fact that the supposed proof was reproduced in [Littl], the algorithm does not appear to have received much mention in the literature of the subsequent decades. The great interest the algorithm enjoys nowadays by combinatorialists was triggered by its independent reformulation by Schensted [Sche] published in 1961, whose main objective was counting permutations with given lengths of their longest increasing and decreasing subsequences; it was not recognised until several years later that this algorithm is essentially the same as Robinson’s, despite its rather different definition. The combinatorial significance of Schensted’s algorithm was indicated by Schützenberger [Schü1], who at the same time introduced the other algorithm that we shall be considering (the operation called I in [Schü1, §5]): he stated a number of important identities satisfied by the correspondences defined by the two algorithms, and relations between them. That paper represents a big step forward in the understanding of the Robinson-Schensted algorithm, but the important results are somewhat obscured by the complicated notation and many minor errors, and by the fact that its emphasis lies on treating the limiting case of infinite permutations and Young tableaux, a generalisation that has been ignored in the further development of the subject.

Another significant contribution is due to D. E. Knuth [Kn1], who gave a generalisation of the Robinson-Schensted algorithm, where standard Young tableaux are replaced by semi-standard tableaux, and permutations are correspondingly generalised; he also gave a description of the classes of (generalised) permutations obtained by fixing one of the two tableaux. Knuth has probably also contributed considerably to the popularity of the algorithms by his very readable description in [Kn2]. Schensted’s theorem about increasing and decreasing subsequences is extended by C. Greene [Gre1], to give a direct interpretation of the shape of the Young tableaux corresponding to a permutation, and in [Schü3] a completely new approach is presented, based on the results of Knuth and Greene, in which the basic procedure of the Schützenberger algorithm plays a central rôle, rather than Schensted’s construction. In a series of joint papers with A. Lascoux, this has led to the study of an interesting non-commutative algebraic structure, called the plactic monoid (for details and further references, see [LaSch]). Another important contribution was Zelevinsky’s observation in [Zel] that Knuth’s generalisation of the Robinson-Schensted algorithm can be further generalised to deal with “pictures”, a concept generalising both permutations and various kinds of tableaux; these pictures are directly related to the Littlewood-Richardson rule, bringing back the Robinson-Schensted algorithm into the context where it originated. This approach is developed further in [FoGr], and in a recent paper [vLee4], the current author has brought this generalisation in connection with the approach of [Schü3].

0.2. Variants of the algorithms. While the previous subsection mentions developments related to the original algorithms, or to very natural generalisations, there also have been many developments in the direction of finding variants of them (mostly of the Robinson-Schensted algorithm) in slightly different contexts. One such development is based upon enumerative identities in representation theory that correspond to the Robinson-Schensted correspondence and its generalisation by Knuth. The ordinary Robinson-Schensted correspondence gives an identity that counts dimensions in the decomposition of the group algebra of S_{n} as representation of S_{n} × S_{n} (action from left and right). Knuth’s generalisation (which at first glance does not seem to add very much, since it can be made to factor via the ordinary algorithm in an obvious way) leads to identities that describe the decomposition into irreducibles of V^{⊗n} as representation of GL(V) × S_{n}, respectively the decomposition of k[V ⊗ W] as representation of GL(V) × GL(W); moreover they actually describe how the dimension of each individual weight space with respect to (a maximal torus in) GL(V) or GL(W) is distributed among the irreducible components. This has led to successful attempts to find variants of the Robinson-Schensted algorithm (often also called Robinson-Schensted-Knuth algorithm) which are similarly related to the representation theory of other groups, see [Sag1], [Bere], [Sund1], [Stem], [Sund2], [Pro], [BeSt], [Oka2], [Ter]. A survey of a number of these generalisations can be found in [Sag2].

Another development centres around the observation that the definition of the Robinson-Schensted algorithm depends only on a few basic properties of the Young lattice, and that a large part of the theory can be developed similarly for other partially ordered sets which share these properties. The observation appears to have been made independently by S. V. Fomin [Fom2] and R. P. Stanley (who termed these sets ‘differential posets’) [Stan3]. The approach of the former is based on results from the study of finite partially ordered sets, which are closely related to the results of Greene, and it leads to explicit bijective algorithms; the latter approach is enumerative in nature, and leads to very general identities valid in arbitrary differential posets (efficiently formulated using a powerful machinery, involving such things as formal power series in non-commuting linear operators), but it is not mentioned whether corresponding bijections can be automatically derived from them. The two approaches are combined and extended to even more general situations in a series of recent papers [Roby], [Fom3], [Fom4], [FomSt], [Fom5], [Fom6]. In a similar fashion the Schützenberger algorithm can be generalised by replacing the Young lattice by the set of finite order ideals in any poset; this is essentially what is done in [Schü2], and some constructions can be done in an even more general setting, as described in [Schü4]. In the current paper we shall only explicitly discuss the case of the Young lattice, but we shall indicate several places where the arguments used can be applied in a more general setting (and where the validity of these generalisations ends).

Finally, there are at least two instances of interpretations of the Robinson-Schensted correspondence in subjects outside combinatorics (which might prove to give the best explanation as to why some specific permutation should correspond to some specific pair of tableaux), namely an algebraic interpretation in terms of primitive ideals in enveloping algebras (see [Jos], [Vog, Theorem 6.5]), or equivalently of cells in Coxeter groups as defined in [KaLu], and a geometric interpretation in terms of subvarieties of the

§the electronic journal of combinatorics 3 (2) (1996), #R15 3

flag manifold [Stb]. Of latter interpretation there is an analogous one for the Schützenberger algorithm, that is first described in [Hes] (however without explicit reference to the Schützenberger algorithm); both interpretations are described in an uniform way in [vLee3].

0.3. Overview.

In this paper we shall study the basic algorithms mentioned in the title, and no generalisations or variants of them, except in a few cases where variants arise in a natural way. We shall do so systematically from a specific perspective, that proves to be very useful in understanding their basic combinatorial properties: Young tableaux will be interpreted as representing chains of partitions, and the algorithms shall be studied by their “local” behaviour in the sense of these chains, i.e., by the effect that adding or removing an element to the chain has on the outcome of the algorithms. This naturally leads to the formulation of recursion relations for the correspondences defined by the algorithms, and a reformulation of the algorithms themselves as processes that compute doubly indexed families of partitions according to rules governing local configurations; these rules are derived from the recursion relations, and they only partially specify the global order of computation. Tabulating all the partitions in these families gives insightful pictorial representations of the computation, from which fundamental symmetry properties of the correspondences can be read off, that are not at all obvious from their iterative definitions. It also becomes quite easy to understand the fixed points of these symmetries; from their study we shall arrive at a Robinson-Schensted algorithm for the hyperoctahedral groups, which is the natural combinatorial analogue of the ordinary Robinson-Schensted algorithm for the symmetric groups.

Many of the results discussed can been found in the literature, sometimes arrived at by similar methods, more often by completely different methods, but we feel it is useful to bring them all together within a single systematic framework, since the literature of this subject is rather scattered and diverse in its methods and notations. We do not treat all the known properties of the algorithms however: we focus on identities satisfied by the bijective correspondences defined by them. Not treated are for instance Knuth’s elementary transformations that keep one tableau invariant, described in [Kn1], the poset theoretic interpretation of the Robinson-Schensted correspondence by Greene [Gre1], nor the generalisation of the algorithms to pictures given by Zelevinsky [Zel]; the methods used here are not the most suited ones to study these matters. Nevertheless, our approach is self-contained, and it does not require any results from these alternative views on the algorithms. On the other hand, all three subjects mentioned for which our current approach does not work well, can be studied very effectively in the context of Schützenberger’s theory of glissement; this was shown already in the original paper [Schü3] for Knuth’s transformations and Greene’s interpretation, and in [vLee4] for pictures. It appears that the study of glissement, in particular in the generalisation to pictures, is a very effective approach to the theory, complementary the approach presented here. Therefore we include at the end of this paper a section on glissement, indicating its connection to the algorithms discussed here, and to the results that were presented.

Since the form in which the algorithms are defined is one of the main issues, our discussion will start from their basic definitions, and we do not require any combinatorial facts as prerequisites. The remaining sections of this paper treat the following subjects. In §1, the necessary combinatorial notions are introduced, and to whet the reader’s appetite we prove some simple purely enumerative propositions, that are directly related to the Robinson-Schensted algorithm. After this we first discuss the Schützenberger algorithm, because it is slightly simpler than the Robinson-Schensted algorithm; this is done in §2. We first give the traditional definition, which is in terms of moving around entries through the squares of a diagram, and then consider what this means in terms of chains of partitions; this leads to recursion relations, and a pictorial representation of the computation. These are then used to derive the fundamental symmetry of the Schützenberger correspondence, and to study its fixed points, called self-dual tableaux, which turn out to correspond to so-called domino tableaux. This is followed by a similar discussion of the Robinson-Schensted algorithm in §3. In §4 we formulate and prove the central theorem that relates the two algorithms to each other, again using a family of partitions in the proof, that helps to visualise the argument. This theorem, in combination with the earlier discussion of self-dual tableaux, leads to the derivation of the Robinson-Schensted algorithm for the hyperoctahedral groups.

In §5 we use the results obtained so far for an alternative and elementary approach to Schützenberger’s theory of ‘glissements’, set forth in [Schü3].

1. Some simple enumerative combinatorics.

1.1. Definitions.

A partition λ of some n ∈ N is a weakly decreasing sequence ‘λ_{0} ≥ λ_{1} ≥ ⋯’ of natural numbers, that ends with zeros, and whose sum |λ| = ∑_{i} λ_{i} equals n. The terms λ_{i} of this sequence are called the parts of the partition. Although conceptually partitions are infinite sequences, the trailing zeros are usually suppressed, so we write λ = (λ_{0}, …, λ_{m}) if λ_{i} = 0 for i > m. We denote by P_{n} the (obviously finite) set of all partitions of n, and by P the union of all P_{n} for n ∈ N.

To each λ ∈ P_{n} is associated an n-element subset of N × N, called its Young diagram Y (λ); it is defined by (i, j) ∈ Y (λ) ⟺ j < λ_{i} (so that #Y (λ) = |λ|, where the operator ‘#’ denotes the number of elements of a finite set). The elements of a Young diagram will be called its squares, and we may correspondingly depict the Young diagram; we shall draw the square (0, 0) in the top left corner, and the square (i, j) will be drawn i rows below and j columns to the right of it. For instance, for λ = (6, 4, 4, 2, 1) ∈ P_{17} we have

Y (λ) = .

Clearly any partition λ ∈ P is completely determined by Y (λ), and it is often convenient to mentally identify the two. In this spirit we shall use set theoretical notations for partitions, that are defined by passing to their Young diagrams: e.g., λ ⊆ μ for λ, μ ∈ P is taken to mean Y (λ) ⊆ Y (μ). The set N × N is a partially ordered set (or poset for short) under the natural partial ordering given by (i, j) ≤ (i′, j′) whenever i ≤ i′ and j ≤ j′; Young diagrams are just the finite order ideals of this poset, i.e., finite subsets S of N × N for which s ∈ S, s′ ∈ N × N and s′ ≤ s imply s′ ∈ S. From this characterisation it is clear that the set of all Young diagrams is closed under transposition (reflection in the main diagonal). We write (i, j)^{t} = (j, i) for individual squares, and also write λ^{t} for the partition with s ∈ Y (λ) ⟺ s^{t} ∈ Y (λ^{t}); this is called the transpose partition of λ. Obviously transposition is an involution on each set P_{n}. The parts of λ^{t} can be interpreted as the column lengths of Y (λ), so that we have λ_{j}^{t} = #{ i | λ_{i} > j }.

The relation ‘⊆’ makes P itself into a poset, which is called the Young lattice: one easily verifies that any λ, μ ∈ P have an infimum and supremum, namely λ ∩ μ respectively λ ∪ μ (the notation follows the“partitions as diagrams” view). The partial ordering is graded by the subsets P_{n} of P: whenever λ ⊂ μ we have |λ| < |μ|, and one can find a chain of intermediate partitions connecting λ with μ that meets every P_{i} with |λ| < i < |μ|. For λ ∈ P we introduce notations for the sets of its direct predecessors and successors in this lattice:

λ^{−} =^{def} { μ ∈ P_{|λ|−1} | μ ⊂ λ }, λ^{+} =^{def} { μ ∈ P_{|λ|+1} | μ ⊃ λ }.

Clearly μ ∈ λ^{−} is equivalent to λ ∈ μ^{+}; when it holds, the difference Y (λ) \ Y (μ) consists of a single square s, which lies both at the end of a row and of a column of Y (λ), while it lies one position beyond both the end of a row and of a column of Y (μ). In this case we shall write s = λ − μ as well as λ = μ + s and μ = λ − s, and call s a corner of λ, and a cocorner of μ. So the partition λ = (6, 4, 4, 2, 1) whose diagram is displayed above, has corners (0, 5), (2, 3), (3, 1), and (4, 0), and cocorners (0, 6), (1, 4), (3, 2), (4, 1), and (5, 0). There is a corner in column j of Y (λ) if and only if j + 1 occurs (at least once) as a part of λ, while there is a cocorner in column j if and only if j occurs as a part of λ (this is always the case for j = 0). Hence we have the simple but important identity

#λ^{+} = #λ^{−} + 1  for all λ ∈ P.  (1)

Another identity, which is even more obvious than this one, will also be of importance, namely

#(λ^{+} ∩ μ^{+}) = #(λ^{−} ∩ μ^{−})  for λ ≠ μ  (2)

since both sides are clearly 0 unless |λ| = |μ|, and even then they can be at most 1, which happens when the equivalent conditions λ^{+} ∩ μ^{+} = {λ ∪ μ} and λ^{−} ∩ μ^{−} = {λ ∩ μ} are satisfied. The fact that the Young lattice is a graded poset satisfying equations (1) and (2) means that it is a ‘differential poset’ as defined in [Stan3]; since the identities that shall be derived in this section only depend on these two equations, they remain valid when the Young lattice is replaced by any differential poset.

The principal reason for referring to the elements of a Young diagram Y (λ) as squares (rather than as points), is that it allows one to represent maps f: Y (λ) → Z by filling each square s ∈ Y (λ) with the number f(s). We shall call such a filled Young diagram a Young tableau (or simply a tableau) of shape λ if it satisfies the following condition*, that we shall refer to as the tableau property: all numbers are distinct, and they increase along each row and column. If T is a Young tableau of shape λ we write λ = sh T; transposing the Young diagram and its entries leads to a tableau of shape λ^{t} which shall be denoted by T^{t}.

1.2. Young tableaux and chains of partitions.

The tableau property is equivalent to the map f: Y (λ) → Z corresponding to the tableau being injective and monotonic (i.e., a morphism of partially ordered sets). It can also be formulated in a recursive way, which focuses on one square at a time. It is based on the following simple observation.

1.2.1. Proposition. Let T consist of a diagram Y (λ) filled with integer numbers. Then T is a Young tableau if and only if either

(i) λ = (0), or (ii) the highest entry occurring in T appears in a unique square s, which is a corner of λ, and the

restriction of T to Y (λ) \ {s} is a Young tableau.

Proof. It is immediate from the tableau property that in a non-empty tableau the highest entry must be unique and occur at the end of a row and a column, whence the conditions of the proposition are necessary (note incidentally that s being a corner of λ is a prerequisite for the final statement of (ii) to make sense). An equally elementary verification shows that the conditions are sufficient.

Since the tableau referred to in 1.2.1(ii) is strictly smaller than T, it is clear that the proposition can be used as a recursive characterisation of Young tableaux. It also allows us to associate a saturated decreasing chain ch T in the Young lattice with any tableau T. For a non-empty tableau T of shape λ define ⌈T ⌉ to be the corner of λ containing the highest entry of T, and T^{−} the restriction of T to Y (λ) \ {⌈T ⌉}, i.e., T with its highest entry removed. Now define recursively

ch T = sh T : ch T^{−},

where λ : c denotes the chain in P formed by prepending λ to the chain c; the terminating case for this definition is for the empty tableau, that we shall denote by ⊙, for which we set ch ⊙ = ((0)). A central point in our approach is that we shall view any tableau T as representing ch T; clearly any saturated decreasing chain in P can be represented as ch T for some tableau T, and T is completely determined by ch T together with its set of entries. Two tableaux T, T′ will be called similar (written T ∼ T′) when ch T = ch T′. In this case T′ can be obtained from T by renumbering the entries in an order preserving way (for the corresponding maps f, f′: Y (λ) → Z this means f′ = g ∘ f for some monotonic map g: Z → Z). We call T normalised if its set of entries (i.e., Im f ) equals {1, 2, …, | sh T |}, and define T_{λ} to be the set of normalised Young tableaux of shape λ. Clearly ‘∼’ is an equivalence relation, and every equivalence class contains a unique normalised element. As an example we have

* In the literature various kinds of filled Young diagrams are called (Young) tableaux, often adorned with

adjectives like standard; unfortunately its meaning is not standard. Since we need only the kind defined

here, we follow [Kn2] in calling them simply Young tableaux.

T = 3 6 11 5 8 7 19  ∼  T′ = 1 3 6 2 5 4 7 ∈ T_{(3,2,1,1)},

since we have

ch T = (  ,  ,  ,  ,  ,  ,  , (0)) = ch T′.

1.3. Some enumerative identities. ¿From the bijection of T_{λ} with the set of saturated decreasing chains in the Young lattice starting in λ, we get the identity:

#T_{λ} = ∑_{μ∈λ^{−}} #T_{μ}  for all partitions λ ≠ (0).  (3)

This identity has a remarkable analogue for λ^{+} instead of λ^{−}, which is directly related to the Robinson-Schensted algorithm.

1.3.1. Lemma. For all λ ∈ P

(|λ| + 1)#T_{λ} = ∑_{μ∈λ^{+}} #T_{μ}.

Proof. By induction on n = |λ|. We have #T_{(0)} = #T_{(1)} = 1, so the lemma holds for n = 0; now assume that n > 0 and that the lemma holds for all μ ∈ P_{n−1}. Then we have, using (3), the induction hypothesis, (1), (2) and once again (3):

(n + 1)#T_{λ} = #T_{λ} + n ∑_{μ∈λ^{−}} #T_{μ} = #T_{λ} + ∑_{μ∈λ^{−}} ∑_{λ′∈μ^{+}} #T_{λ′} = (1 + #λ^{−})#T_{λ} + ∑_{μ∈λ^{−}} ∑_{{λ′∈μ^{+} \atop λ′≠λ}} #T_{λ′}

= #λ^{+}#T_{λ} + ∑_{μ∈λ^{+}} ∑_{{λ′∈μ^{−} \atop λ′≠λ}} #T_{λ′} = ∑_{μ∈λ^{+}} ∑_{λ′∈μ^{−}} #T_{λ′} = ∑_{μ∈λ^{+}} #T_{μ}.

We derive from this lemma a pair of interesting combinatorial identities.

1.3.2. Proposition. The total number t_{n} = ∑_{λ∈P_{n}} #T_{λ} of normalised tableaux of n squares satisfies the recursion relation

t_{0} = 1 and t_{n+1} = t_{n} + nt_{n−1} for all n ∈ N

(to be interpreted in the obvious way for n = 0).

Proof. A straightforward computation:

∑_{λ∈P_{n+1}} #T_{λ} = ∑_{λ∈P_{n+1}} ∑_{μ∈λ^{−}} #T_{μ} = ∑_{μ∈P_{n}} #μ^{+}#T_{μ} = ∑_{μ∈P_{n}}(1 + #μ^{−})#T_{μ}

= ∑_{μ∈P_{n}} #T_{μ} + ∑_{ν∈P_{n−1}} ∑_{μ∈ν^{+}} #T_{μ} = ∑_{μ∈P_{n}} #T_{μ} + n ∑_{ν∈P_{n−1}} #T_{ν}.

This proposition implies that the total number of normalised tableaux of size n is equal to the number of involutions in the symmetric group S_{n} (i.e., elements whose square is the identity, including the identity itself), since the latter number is easily seen to satisfy the same recursion. Indeed, an involution in S_{n+1} either fixes the last of the elements that S_{n+1} operates upon, in which case it is further determined by its action on the first n elements, or it exchanges the last element with one of the first n (say number i), in which case it is determined by i (with 1 ≤ i ≤ n) and by its action on the remaining n − 1 elements. ¿From the proposition it also follows that the exponential generating function for the sequence t_{n} (n ∈ N) is e^{x+ \frac{1}{2} x^{2}} (which means that t_{n} equals the n-th derivative evaluated at x = 0 of this function), see for instance [Stan2, Example 1.1.13]. The following consequence of our lemma is even nicer than the first one.

1.3.3. Proposition.

∑_{λ∈P_{n}}(#T_{λ})^{2} = n! for all n ∈ N.

Proof. By induction:

∑_{λ∈P_{n}}(#T_{λ})^{2} = ∑_{λ∈P_{n}} ∑_{μ∈λ^{−}} #T_{λ}#T_{μ} = ∑_{μ∈P_{n−1}} ∑_{λ∈μ^{+}} #T_{λ}#T_{μ} = n ∑_{μ∈P_{n−1}}(#T_{μ})^{2} = n · (n − 1)! = n!

Remarks. The numbers #T_{λ} for λ ∈ P_{n} appear in the representation theory of S_{n} as the dimensions of its irreducible representations. In that context proposition 1.3.3 states the well known relation between those dimensions and the order of the group. There is also an interpretation for proposition 1.3.2, in the formulation that the number of normalised tableaux of size n equals the number of involutions in S_{n}, by a result of Frobenius and Schur (see [FrSch]) which in the case of groups such as S_{n}, where all representations can be realised over the real numbers, can be formulated as follows: for any g ∈ G the number #{ x ∈ G | x^{2} = g } is the sum of all values at g of the irreducible characters. (The cited result actually also tells how to take into account any possible non-real irreducible representations.) Taking for g the identity, the character values become dimensions and the indicated set that of all involutions in S_{n}, so we get the mentioned identity. The derivation of the propositions is not new either, which is not surprising given its simplicity; it appears in [McL], and appears to have been given already by A. Young. Nevertheless it does not seem to be very well known, given that it is often said that the Robinson-Schensted algorithm gives the combinatorial proof of proposition 1.3.3. We should also note that there is an explicit formula for the individual numbers #T_{λ} (the Frame-Robinson-Thrall formula, see for instance [Kn2, theorem H]), but no proof of that formula is known which is even nearly as simple as the proofs given above. (Nevertheless this formula may have been of crucial importance for the Robinson-Schensted algorithm, since it enabled Schensted to derive from his bijective correspondence the simple counting formula he was after; without it he might not have considered the bijection to be of much interest.)

An obvious question is whether explicit bijections can be given that correspond to these propositions. This is indeed possible: as we have already hinted at, the Robinson-Schensted algorithm defines such a bijection for proposition 1.3.3, and from this a bijection for proposition 1.3.2 can be obtained by embedding the set of all tableaux diagonally into the set of pairs of tableaux of equal shape (involutions correspond to pairs of equal tableaux, as we shall see below). However, the relation with the Robinson-Schensted algorithm is even stronger than this; it is possible to deduce the Robinson-Schensted algorithm from the proof of proposition 1.3.3. This is fairly straightforward, since most of the quantities appearing in the identities are cardinalities of finite sets, there are no cancellations: only additions and multiplications occur. We urge the interested reader to try this as an exercise, which is much more instructive than if we give all the details here. At one point a choice has to be made, namely a bijection corresponding to the basic identity (1). To arrive at the usual Robinson-Schensted correspondence, one should map each corner to the cocorner in the next row, and the additional point (corresponding to the term ‘1’) to the cocorner in the first row. As noted in [Fom2], a bijective correspondence can similarly be constructed for any differential poset (with saturated chains in the poset taking the place of Young tableaux), once a particular bijectivisation of (1) is chosen.

§2. The Schützenberger algorithm.

In this section we consider an algorithm due to Schützenberger that defines a non-trivial shape preserving transformation S of tableaux, under which the set of entries is replaced by the set of their negatives.

2.1. Definition of the Schützenberger algorithm.

The Schützenberger algorithm is based on the repeated application of a basic procedure that modifies a given tableau in a specific manner, and which we shall call this the deflation procedure D, since it starts by emptying the square in the upper left-hand corner, and the proceeds to rearrange the remaining squares to form a proper tableau. The procedure can be reversed step by step, giving rise to an inflation procedure D^{−1}. More precisely, these procedures convert into each other the following sets of data: on one hand a non-empty tableau P, and on the other hand a tableau T, a specified cocorner s of sh T, and a number m that is smaller than all entries of T; we write (T, s, m) = D(P) and P = D^{−1}(T, s, m). These procedures are such that we always have the following relations: the set of entries of P are those of T together with m, and sh P = sh T + s. Our description of these procedures is slightly informal; a more formal and elaborate description can be found in the excellent exposition [Kn2].

Deflation procedure. Given a tableau P, the triple (T, s, m) = D(P) is computed as follows. The first step is to put m equal to the smallest entry of P, and remove that entry, leaving an empty square at the origin. Then the following step is repeated until the empty square is a corner of the shape sh P of the original tableau: move into the empty square the smaller one of the entries located directly to the right of and below it (if only one of these positions contains an entry, move that entry). When the position of the empty square finally is a corner of sh P, then s is defined to be this corner, and T is the tableau formed by the remaining non-empty squares.

Because the empty square moves either down or to the right in each step, termination is evidently guaranteed. That T is indeed a tableau can be seen by observing that at each stage of the process the entries of the non-empty squares remain increasing along each row and column. In fact, when there are entries both to the right and below the empty square, the choice to move the smaller one is dictated by the tableau property. By the same consideration it also becomes clear that D is invertible, and that its inverse procedure D^{−1} can be defined as follows:

Inflation procedure. Given a tableau T, a cocorner s of sh T and a number m smaller than any of the entries of T, the tableau P = D^{−1}(T, s, m) is computed as follows. The first step is to attach an empty square to T at position s. Then the following step is repeated until the empty square is at the origin: move into the empty square the larger one of the entries located directly to the left of and above it (if only one of these positions contains an entry, move that entry). When the empty square has arrived at the origin, it is filled with the number m to form the tableau P.

One easily verifies that the procedure reverses D step by step, and also preserves the tableau property. We demonstrate these procedures by an example:

P = 1 2 5 10 3 4 9 6 7 11 8  2 5 10 3 4 9 6 7 11 8 2  5 10 3 4 9 6 7 11 8 2 4 5 10 3  9 6 7 11 8 2 4 5 10 3 7 9 6 11 8 2 4 5 10 3 7 9 6 11 8

so that we have

T = 2 4 5 10 3 7 9 6 11 8 ,  s = (2, 2),  m = 1.

Before we continue it is convenient to introduce the following notations.

2.1.1. Definition.

(i) Let P be a non-empty tableau, and (T, s, m) = D(P). We define P^{↓} = T. (ii) Let x = (r, c) and y be distinct squares. The relation x ∥ y is defined to hold if either y = (r + 1, c)

or y = (r, c + 1). In this case x and y are called adjacent.

In (i), the arrow is meant to suggest the lowest entry of P being squeezed out. The adjacency relation defined in (ii) is not symmetric, because whenever we need it it will be clear that it can hold only in one direction.

Now let us state the effect of D in terms of chains of partitions. In case P has only one square we obviously have P^{↓} = ⊙, so we assume that P has at least 2 squares. The highest entry h of P lies at some corner of sh P, so it either does not move at all, or it moves in the final step into a square for which it is the only candidate; therefore its presence will not affect the movement of any other entry. This means that deflation commutes with removal of the highest entry:

P^{↓−} = P^{−↓}.  (4)

Consequently, if by induction we assume that we know ch P^{−↓}, then all that is needed to determine ch P^{↓} = sh P^{↓} : ch P^{↓−} is to find sh P^{↓}. Here there are two cases to distinguish, namely whether h does or does not move. The former case applies when the final position sh P^{−} − sh P^{−↓} of the empty square in the computation of P^{−↓} is adjacent to the position ⌈P ⌉ of h, and if so, h moves into that square, making sh P^{↓} = sh P^{−}. In the latter case the fact that h does not move can be expressed as ⌈P^{↓}⌉ = ⌈P ⌉, and since ⌈P ⌉ ∉ sh P^{−}, we now obviously have sh P^{↓} ≠ sh P^{−}; since sh P^{↓−} and sh P differ only by two squares, there are no more than 2 intermediate partitions, and the inequality determines sh P^{↓} completely. Hence ch P^{↓} is determined by (4) in combination with

sh P^{↓} = sh P^{−} ⟺ (sh P^{−} − sh P^{−↓}) ∥ ⌈P ⌉.  (5)

It is easy to see that the condition on the right is equivalent to the existence of only one intermediate partition between sh P^{↓−} and sh P, so the determination of sh P^{↓} can be summarised by the condition sh P^{↓−} ⊂ sh P^{↓} ⊂ sh P, and the rule that we have sh P^{↓} ≠ sh P^{−} whenever that is possible. Although it may seem that we have used only a few aspects of the definition of D, we can in fact use the stated rule to recursively compute ch P^{↓}, and since the set of entries of P^{↓} is just that of P without the minimal entry, to compute P^{↓} itself. The situation for the inverse computation P = D^{−1}(T, s, m) is quite similar, except that the basic step now precedes the recursive computation. We have sh P = sh T + s, and from (4) it follows that T^{−} = P^{−↓}, and in particular sh T^{−} ⊂ sh P^{−} ⊂ sh P; if this does not determine sh P^{−} completely, it is taken to be different from sh T. Once sh P^{−} is determined, ch P^{−} is determined by recursive application of these rules. It is useful to attach names to the relations between several partitions that we have encountered here.

2.1.2. Definition An arrangement of 4 partitions ({κ \atop μ} {λ \atop ν}) with λ, μ ∈ κ^{−} ∩ ν^{+} is called

(i) a configuration of type S1 if λ = μ and (λ − ν) ∥ (κ − λ), (ii) a configuration of type S2 if λ ≠ μ and κ = λ ∪ μ, ν = λ ∩ μ.

Note that for the recursive description of the deflation and inflation procedures we have only used very few properties of the Young lattice, namely that it is a graded poset with a minimal element, and for any pair of comparable elements that differ by 2 in grading, there are at most 2 elements strictly in between them. Let us call an arbitrary poset with these properties a thin interval poset, then for any such poset one can define similar deflation and inflation procedures, that operate on saturated decreasing chains in the poset. Unless stated otherwise, everything we shall say about the Schützenberger algorithm in this section (i.e., not involving the Robinson-Schensted algorithm) can also be generalised for arbitrary thin interval posets. There are many kinds of thin interval posets, for instance the set of order ideals of any finite poset is a thin interval poset under the inclusion ordering (one may also start with an infinite poset, considering only finite order ideals, provided each element is contained in some finite order ideal).

The full Schützenberger algorithm essentially consists of repetition of the basic procedure. Repeating the application of the deflation procedure to P, we find a sequence of tableaux P, P^{↓}, P^{↓↓}, …, ⊙, whose shapes form a saturated decreasing chain in the Young lattice starting in λ = sh P; there is a unique tableau P^{∗} for which this chain equals ch P^{∗} and whose set of entries are the negatives of those of P. The negation of the entries of the tableau is related to the way the algorithm operates: the entry m that is removed in passing from P to P^{↓} is the minimal one among the entries of P, but the entry that will occupy ⌈P^{∗}⌉ = sh P − sh P^{↓} in P^{∗} is the maximal one, which is −m. The algorithm S has an inverse algorithm S^{−1}, which is just as easy to compute, but slightly more difficult to formulate. To compute S^{−1}(P^{∗}) one starts with an empty tableau, and successively computes tableaux whose shapes are the partitions occurring in ch P^{∗}, and each one is obtained from its predecessor by an appropriate application of D^{−1}; the final tableau so constructed is S^{−1}(P^{∗}). More precisely, one sets P_{0} = ⊙ and then successively P_{i} = D^{−1}(P_{i−1}, s_{i}, −m_{i}) for i = 1, …, n, where (m_{1}, …, m_{n}) is the set of entries of P^{∗} in increasing order, and s_{i} is the square whose entry in P^{∗} is m_{i}; then P = S^{−1}(P^{∗}) = P_{n}. It is obvious from the definition that S and S^{−1} commute with transposition: S(P^{t}) = S(P)^{t} and S^{−1}(P^{t}) = S^{−1}(P)^{t}.

We give an example of performing the algorithm S: we display the successive stages P, P^{↓}, P^{↓↓}, …, and meanwhile the entries of P^{∗} that are determined up to this point. Reading from right to left illustrates the computation of S^{−1}(P^{∗}), where those entries of P^{∗} that have already served their purpose are erased.

\begin{matrix}P^{↓···↓} \\ P^{∗} \end{matrix}  1 2 4 3 7 5 6  2 4 3 7 5 6 ; −1 3 4 5 7 6 ; −1 ; −2 4 7 5 6 ; −1 ; −3 ; −2 5 7 6 ; −1 ; −3 ; −4 ; −2 6 7 ; −1 ; −5−3 ; −4 ; −2 7 ; −6−1 ; −5−3 ; −4 ; −2 ⊙ ; −7−6−1 ; −5−3 ; −4 ; −2

2.2. Involution property of S.

The correspondence defined by the Schützenberger algorithm is in fact an involution, although this is not obvious from the definition.

2.2.1. Theorem. For all λ ∈ P the algorithm S defines an involution, i.e., for all tableaux P

S(P) = S^{−1}(P).

This fact was first stated and proved by Schützenberger in [Schü1, §5], but the proof is indirect, based on the relation of S with the Robinson-Schensted algorithm. In a somewhat disguised form, dealing with the more general context of sets of order ideals in finite posets (a particular case of thin interval posets), the theorem is proved in [Schü4, III.4], and the result is also essentially contained in [Schü2, Corollaire 11.1]. Our proof is quite similar to that of [Hes, 4.5, Proposition, (d)], although it is not mentioned in [Hes] that the operation called D there is in fact the Schützenberger correspondence.

Proof. Since the set of entries is clearly the same for S(P) and S^{−1}(P), it suffices to prove that ch S(P) = ch S^{−1}(P). In view of (4), we may define a doubly indexed collection of tableaux P^{[i,j]} for i + j ≤ n where n = | sh P |, by setting for P^{[0,0]} = P, and for all applicable i, j: P^{[i,j+1]} = (P^{[i,j]})^{−} and P^{[i+1,j]} = (P^{[i,j]})^{↓}; furthermore we set λ^{[i,j]} = sh P^{[i,j]}. Clearly we have ch P = (λ^{[0,0]}, λ^{[0,1]}, …, λ^{[0,n]}) and ch S(P) = (λ^{[0,0]}, λ^{[1,0]}, …, λ^{[n,0]}). Moreover, we have seen that any configuration ({λ^{[i,j]} \atop λ^{[i+1,j]}} {λ^{[i,j+1]} \atop λ^{[i+1,j+1]}} ) is one of type S1 or S2, and this determines λ^{[i+1,j]} when the other three partitions are given. Since these configurations also occur in the description of the inflation procedure D^{−1} in terms of chains of partitions, it follows by an easy induction that for the intermediate tableaux P_{i} occurring in the construction of S^{−1}(P) one has ch P_{i} = (λ^{[0,n−i]}, λ^{[1,n−i]}, …, λ^{[i,n−i]}); for i = n this gives us ch S^{−1}(P) = ch S(P).

The following picture shows the partitions λ^{[i,j]} for P = 1 3 4 2 6 8 5 7 , where one has S(P) = −8 ; −7 ; −5 ; −6 ; −3 ; −2 ; −4 ; −1 .

0  1  2  3  4 5 6 7 0  ∘
1  ∘
2  ∘
3  ∘
4  ∘
5  ∘
6  ∘
7  ∘
8  ∘

It is clear from the proof that the theorem remains valid if we replace the Young lattice by any thin interval poset, and S by the corresponding operation on saturated chains in the poset. Moreover, we can generalise in a different way, since it is clear that by the same local application of the rules, the complete family of partitions λ^{[i,j]} is not only determined by the values λ^{[0,j]} along the top edge, or by the values λ^{[i,0]} along the left edge, but also by any sequence of values starting with λ^{[0,0]} and repeatedly going either one step down (increasing the first index by 1) or to the right (increasing the second index by 1) until the empty partition is reached. Even if the values are only given on such a zig-zag path is that ends before the empty partition is reached, all values within the rectangle that encloses the path are still determined (i.e., for index values between 0 and the values reached at the end of the path). One finds in the literature various formulations of operations that effectively switch between several representative sequences for such a family of partitions, often described in a less transparent way; we mention the conversions of [Haim1, Definition 3.7] and the tableau switching of [BeSoSt].

2.3. Self-dual tableaux and domino tableaux. Having established this symmetry of the Schützenberger correspondence it is interesting to consider the fixed points of the symmetry: tableaux P with P = S(P). Since such tableaux cannot be normalised in the ordinary sense, we use an adapted concept of normalisation.

2.3.1. Definition. A Young tableau P is called a self-dual tableau if S(P) = P. A normalised self-dual tableau is a self-dual tableau whose set of entries moreover forms a complete interval in Z from −n to +n for some n, with the possible exclusion of the number 0.

For such tableaux P, the family of partitions λ^{[i,j]} defined above becomes symmetric, i.e., λ^{[i,j]} = λ^{[j,i]} for all i, j, because λ^{[i,0]} = λ^{[0,i]} for all i, and the rule determining the remaining values is symmetric. In particular we have near the main diagonal that λ^{[i,i+1]} = λ^{[i+1,i]} for i + 1 ≤ | sh P |/2, and by (5) this means that Y (λ^{[i,i]}) and Y (λ^{[i+1,i+1]}) differ by a pair of adjacent squares, which we shall term a domino. Conversely, if the Young diagrams of all pairs of successive partitions on the main diagonal differ by a domino, then λ^{[i,j]} = λ^{[j,i]} for all i, j, since each λ^{[i,i+1]} = λ^{[i+1,i]} is determined by unique interpolation between λ^{[i,i]} and λ^{[i+1,i+1]}, and this determines enough values λ^{[i,j]} to fix them all. Let us define for λ ∈ P the set λ^{++} to consist of all those partitions that can be formed by adding a domino to λ, and similarly define λ^{−−} as the set of partitions that can be formed by removing a domino from λ, formally

λ^{−−} =^{def} { ν ∈ P_{|λ|−2} | ∃!μ: ν ⊂ μ ⊂ λ }  and  λ^{++} =^{def} { ν ∈ P_{|λ|+2} | ∃!μ: λ ⊂ μ ⊂ ν },

where ‘∃!’ denotes unique existence. If λ^{−−} = ∅, then λ is called a core; it is easy to see that this is the case if and only if λ is a “staircase partition”, of the form λ = (r, r − 1, …, 2, 1) for some r ∈ N.

For a self-dual tableau, the sequence of partitions λ^{[i,i]} along the main diagonal ends in one of the cores (0) or (1), and it can be encoded by filling the shape of the self-dual tableau, but without the Young diagram of this final core, with numbered dominos. In connection with the Robinson-Schensted algorithm for hyperoctahedral groups that we shall describe later, it will be useful to define the concept of domino tableau to be a bit more general, allowing for other cores than (0) and (1); the subclass with core (0) or (1) will be indicated as total domino tableaux.

2.3.2. Definition. Let r ∈ N and λ ∈ P; a domino tableau of rank r and shape λ is a Young diagram Y (λ) filled with non-negative integers, such that 0 occurs at position (i, j) if and only if i + j < r, each other occurring number occurs precisely in a pair of adjacent squares, and such that entries are weakly increasing along both rows and columns. A domino tableau of rank 0 or 1 is called a total domino tableau. A domino tableau is called normalised if its set of non-zero entries is {1, …, n} for some n ∈ N.

The set of squares with entry 0 is called the core of the domino tableau. For a domino tableau U containing a non-zero entry, define U^{−} to be the domino tableau obtained by removing the domino with the highest entry, and define ch U to be the chain (sh U, sh U^{−}, sh U^{−−}, …), ending with the core of U. The construction above proves the following fact.

2.3.3. Proposition. For any partition λ the set of normalised self-dual tableaux of shape λ is in bijection with the set of normalised total domino tableaux of shape λ.

An algorithm for finding the self-dual tableau corresponding to a given total domino tableau U, without referring to the family of partitions λ^{[i,j]}, can be formulated as follows. Set T_{0} equal to the restriction of U to its core (so either T_{0} = ⊙ or T_{0} = 0 ), and let (m_{1}, …, m_{n}) be the set of non-zero entries of U, in increasing order; then for i = 1, …, n compute T_{i} from T_{i−1} as follows. Let the entry m_{i} occur in U in the squares s, t with s ∥ t; compute T′_{i} = D^{−1}(T_{i−1}, −m_{i}, s), and add square t with entry m_{i} to T′_{i} to form T_{i}. The final tableau T_{n} is the desired self-dual tableau. There is an obvious inverse algorithm, that will succeed if and only if its input is actually a self-dual tableau.

2.4. More about domino tableaux. In this subsection we give some more considerations about domino tableaux that are not essential for the remainder of our discussion. These considerations also apply exclusively to domino tableaux, not to their analogues that can be defined in arbitrary thin interval posets.

One immediate consequence of proposition 2.3.3 is that a necessary and sufficient condition for a shape λ to admit any self-dual tableaux is that it admits total domino tableaux, i.e., that Y (λ) or Y (λ) \ {(1, 1)} can be tiled with dominos (it is easy to see that such a tiling can always be numbered so as to make it into a total domino tableau). Whether this is the case can be decided by computing d = ∑_{(i,j)∈Y (λ)}(−1)^{i+j}: the shape λ admits only domino tableaux of rank r, where r = −2d if d ≤ 0 and r = 2d − 1 if d > 0, whence it admits self-dual tableaux if and only if d ∈ {0, 1}. That this is so can be seen by verifying that the statement holds for cores, and that d is unaffected by adding or removing dominos.

Remark. There is another argument that the core of a domino tableau is uniquely determined by its shape, which does not require analysing the set of all possible cores. It also has the advantage of allowing a generalisation to so-called rim hooks of size q instead of dominos, and q-cores instead of staircase shaped cores (see for instance [JaKer, 2.7.16] or [FomSt]). To this end note that a partition λ can be completely described by listing the orientations of the successive segments of the boundary of Y (λ) from bottom left to top right, where each segment runs across the end of a row or column. For instance, for λ = (6, 4, 4, 2, 1) the orientations are … vvvvvhvhvhhvvhhvhhhhh…, where ‘v’ stands for vertical and ‘h’ for horizontal, and the sequence starts with infinitely many v’s and ends with infinitely many h’s, since we include segments that run across rows or columns of length 0. The point where the boundary crosses the main diagonal is uniquely determined as the point between segments with equally many h’s before it as v’s after it, in the example … vvvhvhvh|hvvhhvhhh. . .. If we take any pair of segments in the sequence and interchange their orientation, then the associated partition may change considerably, but the midpoint of the sequence remains in place. Now the basic observation is that the removal of a domino, whether horizontal or vertical, is equivalent to interchanging the orientations of a pair of segments two places apart, from … hxv… to … vxh…, where x denotes the intermediate segment whose orientation does not change. Therefore if we split the sequence of edge orientations alternatingly into two subsequences, each domino removal will affect just one of these subsequences, and no further removal is possible when both subsequences are of the form … vvv|hhh. . .. Since the midpoints defined for the subsequences do not move when dominos are removed, the core is predetermined by the displacement of these midpoints relative to the position inherited from the midpoint of the full sequence (the sum of these displacements is 0). What this analysis also shows, is that for any given core and n ∈ N, there is a bijection from the set of shapes λ that admit any domino tableaux with the given core and n dominos, to the set of ordered pairs (μ, ν) of partitions with |μ| + |ν| = n (because removal of a domino from the original partition corresponds to removal of a square from the partition corresponding to one of the subsequences). This in turn implies a bijection from the set of normalised domino tableaux of such a shape λ corresponding to the pair (μ, ν), to the set of ordered pairs of Young tableaux of shapes μ and ν, whose combined set of entries is 1, …, n. In particular the number of domino tableaux with n dominos and given core is independent of that core, as is the number of different shapes among those domino tableaux.

When discussing the Robinson-Schensted algorithm for the hyperoctahedral groups, we shall obtain yet another proof of the fact that any shape admits domino tableaux of one rank only. There we shall also see that arbitrary domino tableaux are in a sense a natural generalisation of total domino tableaux; however, only total domino tableaux correspond to self-dual Young tableaux, and it remains to be seen whether any similar interpretation can be given to other domino tableaux. One interesting fact is the following. Suppose we replace in the totally ordered set Z the element 0 by a sufficiently large totally ordered set, whose elements we shall call “infinitesimal numbers” and are assumed to be neither positive nor negative. Then we may fill the core of a given domino tableau with infinitesimal numbers, in such a way that it becomes an arbitrary (infinitesimal) Young tableau. We can then apply to algorithm for constructing a self-dual tableau from a domino tableau, but taking this tableau as the starting point T_{0} for the inflation operations. What we then obtain is a tableau X with positive and negative numbers, and infinitesimal numbers in between. Now unless the domino tableau had rank 0 or 1, the shape of X prevents it from being (similar to) a self-dual tableau. On the other hand, one easily shows that the positions of all positive numbers in X are the same as in S(X), and moreover these positions are independent of the original arrangement of the infinitesimals in the core (since the inflation procedure D^{−1} affects smaller numbers only after the larger ones are settled). Much less obviously, the same statements also hold for the negative numbers, because as we shall prove later, the positions of the k highest entries of any tableau T determine positions of the k lowest entries of S(T) (the analogue of this final statement the context of thin interval posets does not hold in general). In this way domino tableaux may be considered to represent equivalence classes of Young tableaux that are “as self-dual as possible” given their shape λ, in the sense that S(X) differs from S only in the positions of the infinitesimals, and the number of positive entries (and also that of negative entries) is equal to the maximal number of dominos that can be removed from λ; equivalence of such almost self-dual tableaux is defined by all positive and negative entries having the same positions. Note however that if only the positions of these ordinary entries are specified, then not all ways to fill in the remaining positions with infinitesimal numbers that satisfy the tableau condition necessarily lead to an almost self-dual tableau: for some such fillings an attempt to find the domino tableau representing it, by applying the algorithm that reconstructs domino tableaux from their self-dual tableaux, will fail before the infinitesimals have been rearranged into the core, because it constructs pairs of squares that do not form a domino (and if one carries on nonetheless, the infinitesimals may turn out not to end up all inside the core either). This fact prevents us from forgetting altogether about the arrangement of the infinitesimal numbers when describing equivalence classes of almost self-dual tableaux.

§3. The Robinson-Schensted algorithm.

In the is section we shall discuss the Robinson-Schensted algorithm along the same lines as we have done for the Schützenberger algorithm. It defines a bijection between permutations and pairs of Young tableaux of equal shape, that corresponds to proposition 1.3.3, i.e., a bijection RS: S_{n} → ⋃_{λ∈P_{n}} T_{λ} × T_{λ}.

3.1. Definition of the Robinson-Schensted algorithm.

The Robinson-Schensted algorithm is based on a procedure to insert a new number into a Young tableau, thereby displacing certain entries and eventually leading to a tableau with one square more than the original one. More precisely, there is a pair of mutually inverse procedures that convert into each other the following sets of data: on one hand a tableau T and a number m not occurring as entry of T, and on the other hand a non-empty tableau P and a specified corner s of sh P. We shall call the computation of P and s given T and m the insertion procedure I, and write (P, s) = I(T, m). The inverse operation will be called the extraction procedure I^{−1}, and its application is written as (T, m) = I^{−1}(P, s). The procedures are such that the following relations always hold: the set of entries of P is that of T together with the number m, and the sh P = sh T + s (so that s is a corner of sh P and a cocorner of sh T).

Insertion procedure. Given a tableau T and a number m, the pair (P, s) = I(T, m) is determined as follows. The first step is to insert m into row 0 of T, where it either replaces the smallest entry larger than m, or, if no such entry exists, it is simply appended at the end of the row. Then the following (similar) step is repeated, as long as a number, say k, has been replaced at the most recent step. The number k is inserted into the row following its original row, either replacing the smallest entry larger than itself, or, if no such entry exists, by being appended at the end of that row. The tableau obtained after the last step is P, while the square occupied during that step is s.

Since we are moving a row down at each step, it is obvious that the procedure must terminate, possibly by creating a new row of length 1 at the last step. It is fairly easy to prove directly that P satisfies the tableau property, but we omit such a proof, since it will also become evident from the analysis of the algorithm given below. For the extraction procedure we trace our steps backwards, as follows.

Extraction procedure. Given a tableau P and a corner s of sh P, the pair (T, m) = I^{−1}(P, s) is determined as follows. The first step is to remove the square s from P, together with the number it contains. Then repeat the following step until a number has been replaced or removed from row 0. The number removed or replaced in the previous step is moved to the row preceding its original row, where it replaces the largest entry smaller than itself (such an entry exists, since the number originally directly above it is certainly smaller than it). The tableau obtained after the last step is T, while the entry removed or replaced from row 0 is m.

Again it can easily be proved that T is a tableau, and that I^{−1} is the inverse operation of I. The procedures I and I^{−1} have obvious transposed counterparts I^{t} and I^{−t}, whose definition can be obtained by replacing all occurrences of the word ‘row’ by ‘column’; I^{t}(T, m) = (P, s) is equivalent to I(T^{t}, m) = (P^{t}, s^{t}). We illustrate I and I^{−1} by an example that involves four steps. We show the intermediate stages of the procedure I; for an example of the procedure I^{−1}, read from right to left.

m = 7, T = 2 5 6 8 3 10 12 9 13 15 2 5 6 7 3 10 12 9 13 15 2 5 6 7 3 8 12 9 13 15 2 5 6 7 3 8 12 9 10 15 2 5 6 7 3 8 12 9 10 15 13 = P, s = (3, 0)

At each stage except the rightmost there is one number missing: this is the entry that has been superseded but not yet inserted into another row.

The procedures are well behaved with respect to similarity of tableaux; the important aspect of the number m is its ordering position relative to the entries already present in T, and if we preserve this position, then insertion and extraction applied to similar tableaux proceeds identically and the results are again similar tableaux. Counting the number of similarity classes, we see that the bijection established by these procedures corresponds exactly to the enumerative fact stated in lemma 1.3.1.

We now introduce a few useful notations.

3.1.1. Definition.

(i) When (P, s) = I(T, m), define P = T ← m; when (P, s) = I^{t}(T, m), define P = m → T. (ii) Let s be a corner of λ ∈ P, and s′ be the cocorner of λ in the row following that of s. We define

ρ^{+}(λ, λ − s) = λ + s′ and ρ^{−}(λ, λ + s′) = λ − s. We also define ρ^{+}(λ) = λ + t, where t = (0, λ_{0}) is the cocorner of λ in row 0, so ρ^{+}(λ) is the unique element of λ^{+} that is not of the form ρ^{+}(λ, μ); for this case we define ρ^{−}(λ, λ + t) to be an exceptional non-partition value written as ‘⋆’. Define τ^{+} and τ^{−} like ρ^{+} and ρ^{−}, but replacing the word ‘row’ by ‘column’.

(iii) For m ∈ Z and a tableau T define m > T to mean that m exceeds all entries of T, and m < T that all entries of T exceed m.

Now let us study the effect of I in terms of chains of partitions. In the computation of I(T, m), the case m > T is special, since in that case the tableau has a different highest entry after insertion than before. It is also a very simple case, since the insertion involves only adding m to row 0 of T, so that sh(T ← m) = ρ^{+}(sh T) and (T ← m)^{−} = T; in terms of chains of partitions we have

ch(T ← m) = ρ^{+}(sh T) : ch T  if m > T.  (6)

Otherwise, the highest entry h of T will also be the highest entry of T ←m. Since the entries being moved during the insertion procedure form an increasing sequence, h either does not move at all, or is moved at the final step. Also the rule for finding the entry to replace is such that, in the case that h does in fact move, there is no other entry in that row that could have been replaced if h had been absent; therefore the presence of h does not affect the moves of any other entry. This means that insertion commutes with removal of the highest entry:

(T ← m)^{−} = T^{−} ← m  if m ≯ T.  (7)

So in order to determine ch(T ← m) = sh(T ← m) : ch(T ← m)^{−} it suffices to find ch(T^{−} ← m), which we may assume to be known by induction, and to determine sh(T ← m). Here we need to distinguish the cases that h does or does not move. In the latter case, since the final position of h lies outside (T ← m)^{−}, we have sh(T^{−} ← m) ≠ sh T, and we necessarily have sh(T ← m) = sh(T^{−} ← m) ∪ sh T (which has the right size since sh(T^{−} ← m) ∩ sh T = sh T^{−}). In the former case we have sh(T^{−} ← m) = sh T, and the final position of h will be the first square outside T in the row below its initial position ⌈T ⌉; since ⌈T ⌉ is a corner of sh T this new square is indeed a cocorner of sh T, and we conclude

sh(T ← m) = ρ^{+}(sh T, sh T^{−})  if m ≯ T and sh(T^{−} ← m) = sh T.  (8)

Similarly to what we saw for the deflation procedure of the Schützenberger algorithm, the facts collected so far, recorded in the equations (6–8), are sufficient to recursively compute ch(T ← m) in all cases, and since the set of entries of T ← m is that of T with m added to it, to determine T ← m completely. In passing we have shown that ch(T ← m) is indeed a proper chain of partitions, so that insertion presevers the tableau property; the crucial point is that when h moves down, it moves to a cocorner of sh T so that sh(T ← m) ∈ P.

¿From these facts the analysis for the extraction procedure follows directly. Given (T, m) = I^{−1}(P, s), the conditions m > T holds if and only if s = ⌈P ⌉ and ρ^{−}(sh P^{−}, sh P) = ⋆; if so m is the entry of s and T = P^{−}. Otherwise we must have P^{−} = T^{−} ← m by (7), and this will allow us do determine ch T^{−} (and from that ch T) by induction, as soon as we know sh T^{−}. Now sh T = sh P − s, and if this differs from sh P^{−} we have sh T^{−} = (sh P − s) ∩ sh P^{−} = sh P^{−} − s; in the remaining case s = ⌈P ⌉, we have sh T^{−} = ρ^{−}(sh P^{−}, sh P). Again it is useful to give names to the configurations found.

3.1.2. Definition An arrangement of 4 partitions ({κ \atop μ} {λ \atop ν}) with λ, μ ∈ (\{κ\} ∪ κ^{+}) ∩ (\{ν\} ∪ ν^{−}) is called (i) a configuration of type RS1 if κ = λ = μ and ν = ρ^{+}(λ), (ii) a configuration of type RS2 if κ ≠ λ = μ and ν = ρ^{+}(λ, κ), (iii) a configuration of type RS3 if λ, μ ∈ κ^{+}, κ = λ ∩ μ and ν = λ ∪ μ, (iv) a configuration of type RS0 if κ = λ ∧ μ = ν or κ = μ ∧ λ = ν (possibly both).

Although we have not yet encountered RS0, it will prove to be useful later. Observe that if we know that one of these configurations applies, then to determine ν uniquely it suffices to know the values of κ, λ, μ, and whether RS1 applies; conversely, from λ, μ, ν we can always determine κ.

Note that in the recursive description of the insertion and extraction procedures we have used very few properties of the Young lattice, like for the inflation and deflation procedures of the Schützenberger algorithm, but the relevant properties are different this time: we need a differential poset, i.e., a graded poset with minimal element that satisfies (1) and (2), and we need a concrete bijection corresponding to (1) (which will be used in place of ρ^{+} and ρ^{−}); for (2) such a bijection is not necessary, since one can prove that the numbers being equated are either 0 or 1. One can then define the analogues of configurations RS1–RS3, and using them, define insertion and extraction procedures for chains in the differential poset instead of Young tableaux. Unless stated otherwise, everything we shall say about the Robinson-Schensted algorithm in this section can be generalised for arbitrary differential posets.

The full Robinson-Schensted algorithm can now be defined. Its input is a permutation σ ∈ S_{n}, represented as a sequence (σ_{1}, …, σ_{n}) of distinct numbers (where σ maps i ↦ σ_{i}); it returns a pair (P, Q) = RS(σ) of tableaux of equal shape, which it builds up in n stages, as follows. Starting with P_{0} = Q_{0} = ⊙, one successively computes (P_{i}, Q_{i}) for i = 1, …, n by setting (P_{i}, s) = I(P_{i−1}, σ_{i}), and forming Q_{i} by adding the square s with entry i to Q_{i−1}; finally we set (P, Q) = (P_{n}, Q_{n}). Clearly Q_{i} ∈ T_{sh P_{i}}, and the set of entries of P_{i} is {σ_{1}, …, σ_{i}}, so P is also a normalised tableau, with obviously sh P = sh Q. By reversing all the steps one obtains the inverse algorithm RS^{−1}; for the square s used in the extraction (P_{i−1}, σ_{i}) = I^{−1}(P_{i}, s) one takes ⌈Q_{i}⌉.

We illustrate the algorithm, and its inverse, by an example: for the construction of (P, Q) read from left to right, for the inverse process from right to left.

\begin{matrix}σ_{i} \\ P_{i} \\ Q_{i} \end{matrix}  6 6 1  2 2 6 1 2  7 2 7 6 1 3 2  3 2 3 6 7 1 3 2 4  5 2 3 5 6 7 1 3 5 2 4  4 2 3 4 5 7 6 1 3 5 2 4 6  1 1 3 4 2 7 5 6 1 3 5 2 4 6 7

Using I^{t} and I^{−t} instead of I and I^{−1} one can define another bijection RS^{t}: S_{n} → ⋃_{λ∈P} T_{λ} × T_{λ}; we have that RS^{t}(σ) = (P, Q) is equivalent to RS(σ) = (P^{t}, Q^{t}).

3.2. Symmetry property of RS. Like for the Schützenberger correspondence, the Robinson-Schensted correspondence has a symmetry property that is not obvious from the definition. The set S_{n} of permutations forms a group, so its elements can be inverted: in terms of sequences of numbers, the inverse τ = σ^{−1} of σ = (σ_{1}, …, σ_{n}) is the sequence (τ_{1}, …, τ_{n}) whose term τ_{i} is the unique index j such that σ_{j} = i.

3.2.1. Theorem. Applying RS to the inverse of a permutation interchanges the tableaux:

RS(σ) = (P, Q) ⟺ RS(σ^{−1}) = (Q, P) for all σ ∈ S_{n}.

This theorem was already stated (without proof) by Robinson, and it was first proved (for Schensted’s algorithm which was at that time not known to be related to Robinson’s) by Schützenberger in [Schü1, §4] (at least a proof can be reconstructed from it, after correcting a number of misprinted formulae). Other authors have subsequently given different proofs, see for instance [Kn1, Theorem 3]. The proof given here comes about quite naturally if one views tableaux as chains of partitions, and is very similar to the proof given for theorem 2.2.1. The first published account of such a proof for the current theorem appears to be given by S. V. Fomin [Fom2].

Proof. Define a doubly indexed collection of tableaux P^{[i,j]} for 0 ≤ i, j ≤ n, by setting P^{[i,j]} equal to the restriction of P_{i} to the the set of its squares whose entry does not exceed j, where P_{0} = ⊙ and P_{i} = P_{i−1} ← σ_{i} for i = 1, …, n as in the definition of the Robinson-Schensted algorithm, and set λ^{[i,j]} = sh P^{[i,j]}. Then it is obvious from the definitions that ch P = (λ^{[n,n]}, λ^{[n,n−1]}, …, λ^{[n,0]}) and ch Q = (λ^{[n,n]}, λ^{[n−1,n]}, …, λ^{[0,n]}). The sequences of partitions (λ^{[i,n]}, λ^{[i,n−1]}, …, λ^{[i,0]}) are not in general chains in the Young lattice, because some partitions may be repeated (they are sometimes called “multichains” in analogy with “multisets”), but if we omit those partitions that are equal to their successor, then the remaining sequence equals ch P_{i} (the set of non-zero values j for which the partition is retained is just the set of entries of P_{i}). Any configuration ({λ^{[i−1,j−1]} \atop λ^{[i,j−1]}} {λ^{[i−1,j]} \atop λ^{[i,j]}} ) is of type RS1 if j = σ_{i}, and otherwise of type RS0, RS2, or RS3 (the final case correspond to an entry j that has not yet been inserted, or to taking the restriction to entries smaller than the one currently being inserted). These configuration types are symmetric with respect to i and j, and it follows that if λ^{′[i,j]} is the analogous collection of partitions for σ^{−1} in place of σ then λ^{′[i,j]} = λ^{[j,i]}, which immediately implies the theorem.

We give an illustration of the λ^{[i,j]} for σ = (5, 2, 7, 1, 3, 8, 6, 4), where P = 1 3 4 2 6 8 5 7 , and Q = 1 3 6 2 5 7 4 8 ; the arrows indicate the positions (i, σ_{i}).

0 1 2 3 4  5  6  7  8 0  ∘ ∘ ∘ ∘ ∘  ∘  ∘  ∘  ∘
1  ∘ ∘ ∘ ∘ ∘ _{↘}
2  ∘ ∘ _{↘}
3  ∘ ∘  _{↘}
4  ∘ _{↘}
5  ∘  _{↘}
6  ∘  _{↘}
7  ∘  _{↘}
8  ∘  _{↘}

This description by local rules allows for various generalisations; we already mentioned replacing the Young lattice by a differential poset. Also, one may define the family λ^{[i,j]} on a arbitrary region between two zig-zag paths from bottom left to top right with common end points, and allow other sequences of partitions than just empty ones along the top left path; knowledge of the partitions along this path and of the location of any configurations of type RS1 within the region is then equivalent to knowledge of the partitions along the bottom right path. For a rectangular region we get the algorithm of [SaSt].

Comparing our formulation of the algorithm with other ones shows that not all configuration types are equally essential for the computation. The moves occurring in the original formulation of the insertion procedure are related to configurations of types RS1 and RS2; for a description in terms of chains of partitions, type RS3 has to be considered as well, and type RS0 only serves to make the index set for the family λ^{[i,j]} completely regular. Like for type RS1, there is a simple criterion for λ^{[i,j]} to belong to a configuration of type RS0, namely j < σ_{i} ∨ i < σ^{−1}_{j}. On the other hand, types RS2 and RS3 can only be distinguished by performing the algorithm in some form, and this fact somewhat complicates proofs of theorem 3.2.1 that are based directly on the traditional definition of the Robinson-Schensted algorithm.

Two such proofs that use a symmetry principle similar to our proof can easily be understood in relation to the family λ^{[i,j]}. These are the “graph-theoretical viewpoint” of Knuth [Kn1, §4], and the “forme géométrique de la correspondance de Robinson-Schensted” of Viennot [Vien]; although the former uses the language of directed graphs and the latter a geometric terminology, their reasoning can be seen to be essentially identical. From our point of view this is what happens. The set of configurations of types RS1 and RS2 is further subdivided into successive “generations” according to the row of the square λ^{[i,j]} − λ^{[i−1,j]} (so type RS1 becomes generation 0), and these generations are constructed one by one, in a way that preserves the symmetry between i and j. So although the construction is an iterative process, the steps no not correspond to individual insertions, but to the effect of the complete algorithm on a single row of the tableaux. Concretely, one starts with the set Σ = { (i, σ_{i}) | 1 ≤ i ≤ n }, viewed as a partially ordered set by the coordinatewise ordering, and classifies the points of Σ by the maximal length of a chain descending from them. It is not difficult to see that for the point (i, σ_{i}) this length equals the first part of the partition we have associated to it, i.e., λ_{0}^{[i,σ_{i}]}. From this classification row 0 of P and of Q can be directly determined (each class determining one entry of either row). Then to proceed to the remaining rows, a new set of points is constructed to replace Σ, where each class contributes one point less to the new set then its own number of elements; this new set of points corresponds precisely to the configurations of generation 1 as defined above. The process is repeated with this smaller poset, and so on for further generations, each generation determining the corresponding row of P and Q, until for some generation the set of points has become empty.

The family of partitions λ^{[i,j]} also appears in the study of finite posets. To each such poset a partition can be associated in a natural way, as is shown in [Gre2] and in [Fom1]. In this context, λ^{[i,j]} turns out to be the partition associated to the poset Σ ∩ {1, …, i} × {1, …, j}, with Σ as above, see [Fom2, §7]. The theory by which one arrives at this interpretation of λ^{[i,j]} contains some interesting facts that apply in a much broader context than we have been considering here, but their proofs are also much harder than the ones we have dealt with. We mention the following essential points: the fact that what one associates with a finite poset is actually a partition, and it can be described both in terms of chains and of anti-chains ([Gre2, Theorem 1.6] or [Fom1, Lemma 1 and Theorem 1]), the fact if one extends such a poset by an extremal element then the associated partition contains the one before the extension ([Fom1, Theorem 4], and finally that if one defines λ^{[i,j]} as the poset associated to the indicated truncation of Σ, then the local relationships between the λ^{[i,j]} that we have found for the Robinson-Schensted algorithm hold, establishing the connection with the Robinson-Schensted correspondence ([Fom2, Theorem H]).

3.3. Involutory permutations. We return to theorem 3.2.1, and study the fixed points of the symmetry it expresses. Clearly, for any tableau P the permutation σ = RS^{−1}(P, P) is an involution, and this defines a bijection from ⋃_{λ∈P_{n}} T_{λ} to the set of involutions in S_{n}, i.e., one that corresponds to proposition 1.3.2. Since we know that for this situation the family λ^{[i,j]} is satisfies λ^{[i,j]} = λ^{[j,i]} for all i, j, we can find σ as follows with about half as much work as usual, by considering only positions with i ≥ j. We successively compute the tableaux T_{i} corresponding to the sequences (λ^{[i,i]}, λ^{[i,i−1]}, …, λ^{[i,0]}) for i = n, …, 0 (so T_{n} = P); at each step we either find a fixed point of the involution σ, or a pair of points that are interchanged by σ, or nothing happens at all; these correspond to configurations on the main diagonal of type RS1, RS2, and RS0 respectively (type RS3 cannot occur). To start with the last possibility, if the entry i does not occur in the tableau T_{i} (because it has already been removed), then λ^{[i,i]} = λ^{[i,i−1]} = λ^{[i−1,i]} = λ^{[i−1,i−1]}, and T_{i−1} = T_{i}. Having decreased i in this manner until it occurs in T_{i}, we inspect its position ⌈T_{i}⌉; if it lies in row 0, then we have found a fixed point i = σ_{i}, and T_{i−1} = T_{i}^{−}. Otherwise sh T_{i−1} = ρ^{−}(sh T^{−}, sh T), and we compute T_{i−1} by (T_{i−1}, m) = I^{−1}(T_{i}^{−}, s) for the appropriate square s; the numbers i and m that are removed in passing from T_{i} to T_{i−1} are exchanged by σ. When the empty tableau is reached, σ is completely determined. This computation has the following implication, which is due to Schützenberger [Schü1, §4] (this proposition has no analogue in arbitrary differential posets).

3.3.1. Proposition. Let λ ∈ P_{n} and let k = ∑_{i}(−1)^{i}λ_{i} be the number of columns of Y (λ) of odd length, then for each tableau P ∈ T_{λ} the permutation RS^{−1}(P, P) is an involution with k fixed points.

Proof. Since for i > 0 the number of columns of Y (λ) of length i is λ_{i−1}−λ_{i} it is clear that k is indeed the number of odd-length columns. Whenever μ = ρ^{−}(λ, ν), the partition μ is obtained from ν by decreasing two successive parts by 1, so ∑_{i}(−1)^{i}μ_{i} = ∑_{i}(−1)^{i}ν_{i}. Therefore, if RS^{−1}(P, P) is computed as indicated above, then the value of the alternating sum for sh T_{i} only changes when a fixed point i = σ_{i} is found, and if so, it is one more for sh T_{i} than for sh T_{i−1}. It follows that the total number of fixed points will be k.

§4. Relating the two algorithms.

In this section we shall discuss mattes that involve both the Robinson-Schensted and the Schützenberger algorithm. Contrary to the previous sections we shall be using detailed knowledge about the structure of the Young lattice, so there appears to be no possibility to generalise these facts to a wider class of posets.

4.1. The central theorem.

The following important theorem that exhibits the relationship between the Robinson-Schensted and Schützenberger correspondences; it also involves the transpose Robinson-Schensted correspondence RS^{t}.

4.1.1. Theorem. For λ ∈ P_{n}, P, Q ∈ T_{λ}, and σ ∈ S_{n}, the following statements are equivalent:

RS(σ) = (P, Q)  (9)
RS^{t}(ñσ) = (P^{∗}, Q)  (10)
RS^{t}(σñ) = (P, Q^{∗})  (11)
RS(ñσñ) = (P^{∗}, Q^{∗})  (12)

where ñ ∈ S_{n} is the “order reversing” permutation given by ñ_{i} = n + 1 − i, and P^{∗}, Q^{∗} ∈ T_{λ} are such that P^{∗} ∼ S(P) and Q^{∗} ∼ S(Q) (they are obtained by adding n + 1 to all entries of S(P) respectively of S(Q)).

The permutation σñ has as sequence of numbers the reverse of that of σ, so if we look only at the left tableau, the equivalence of (9) and (11) states that ⊙←σ_{1} ←σ_{2} ←⋯←σ_{n} = σ_{1} →σ_{2} →⋯→σ_{n} →⊙; this part was proved by Schensted [Sche, Lemma 7]. The complete equivalence of (9) and (11) was proved by Schützenberger [Schü1, §5]. From this fact and the commutation of S with transposition, one can immediately see that S is an involution (which is how theorem 2.2.1 was first proved), and using theorem 3.2.1 one also obtains the equivalence of (10) and (12) with (9) and (11). The current formulation of the theorem (more or less) is due to Knuth, and can be found in [Kn2, Theorem D]. He expresses the remarkable character of the theorem as follows (p. 60):

“The reader is urged to try out these processes on some simple examples. The unusual nature of these coincidences might lead us to suspect that some sort of witchcraft is operating behind the scenes! No simple explanation for these phenomena is yet known; there seems to be no obvious way to prove even that [ñσñ] corresponds to tableaux having the same shape as P and Q.” Alternative proofs of [Sche, Lemma 7] have been given (or equivalently, for (x→T)←y = x→(T ←y),

which is [Sche, Lemma 6]), but we know of no independent proof of the full statement of theorem 4.1.1, (although it does follow implicitly from the analysis in [Schü3]). This is unfortunate since [Schü1] not only very hard to understand (due in part to its cryptic notation and numerous minor errors), but the mentioned proof is incomplete in an essential way. It is not difficult to see that [Sche, Lemma 6] alone (together with the more obvious properties of the Robinson-Schensted correspondence) is not sufficient to prove the theorem; one has to use some property of S as well. The essential observation that needs to be made, is that if the shapes of T, x→T, T ←y, and (x→T)←y = x→(T ←y) are respectively κ, λ, μ, and ν, then the configuration ({ν \atop λ} {μ \atop κ}) is one of type S1 or S2. Although this fact can actually be distilled from the proof of [Sche, Lemma 6] (see the argument leading to [Sche, Figs. 9,10]), it is not even mentioned in [Schü1]; the omission can be traced down to a non sequitur in the proof of [Schü1, Remarque 1, 1^{∘} cas]. Our proof below corrects this point, and also tries to provide a more rigorous alternative to Schensted’s proof which, although admirably free of technicalities, has a deceptive simplicity: the proof consists of checking a large number of special cases, some of which are discussed in terms of suggestive illustrations; it is however left to the reader to set up and verify the complete list of possible cases, and to find out the precise conditions that are being represented by the illustrations.

Before we turn to the actual proof of the theorem, we need to make a trivial generalisation of the construction describing the computation of S by means of a doubly indexed family of partitions. In that construction the sequences of partitions obtained by varying one index were chains, without repetitions. When combining with the Robinson-Schensted algorithm however, it will be useful to be able to deal with sequences with repetitions as well. To that end it suffices to allow, in addition to the configurations type S1 and S2, a third type of configurations, that is like RS0 except that the inclusions are reversed: define ({κ \atop μ} {λ \atop ν}) to be of type S0 if and only if ({ν \atop λ} {μ \atop κ}) is of type RS0. This simply allows a number of consecutive rows or columns to be replicated: when λ^{[0,j]} = λ^{[0,j+1]} = ⋯ = λ^{[0,k]} one will have λ^{[i,j]} = λ^{[i,j+1]} = ⋯ = λ^{[i,k]} for all i, as well as λ^{[n−k,l]} = λ^{[n−k+1,l]} = ⋯ = λ^{[n−j,l]} for all l; the “reflection” at the anti-diagonal i + j = n occurs because λ^{[n−k,j]} = (0), although (n − k, j) lies above the anti-diagonal. Therefore the generalisation is a very simple one: if for the sequence along the top edge one chooses a representing tableau P for which repetitions in the sequence correspond (as they did in the family of partitions used for the Robinson-Schensted algorithm) to entries that do not occur in P, then S(P) similarly represents the sequence along the left edge. In particular, if we start out without any repetitions along one of these edges, then the new configurations will not occur anywhere, and we just get the original construction. Furthermore, define transposed configurations RS^{t}0–RS^{t}3 like RS0–RS3, but replacing ρ^{+} by τ^{+} (RS^{t}2 and RS^{t}3 are identical to RS2 and RS3, respectively).

Proof of theorem 4.1.1. Our proof will establish the equivalence of (9) and (11), which as we have seen is sufficient, in combination with results obtained earlier, to prove the remaining equivalences. Like our earlier proofs, the current proof will involve an indexed family of partitions, but this time there will be three indices. The idea is to define this family in such a way that by fixing one of the three indices we obtain doubly indexed families that correspond respectively to an application of RS to a truncation of σ, an application of S (with repetitions allowed along the edges, as was just described), and an application of RS^{t} to a truncation of σñ. Fixing the index to the maximal value, n, will give the computations of respectively RS(σ), S(Q), and RS^{t}(σñ); fixing two indices to n will give respectively ch P, ch Q and ch S(Q). The existence of a family meeting these requirements will therefore prove the theorem, and the local laws for the doubly indexed families are sufficient to completely determine all values of the triply indexed family; in fact they overspecify this family, and the essential thing to prove is that the various ways in which the same partition can be determined are consistent with each other.

So we shall prove that there exists a family of partitions λ^{[i,j,k]} for 0 ≤ i, j, k ≤ n and i + k ≥ n satifying the following conditions.

(a) We have λ^{[i,j,k]} = (0) whenever j = 0 or i + k = n.

(b) For i + k > n and j > 0 the configuration ({λ^{[i−1,j−1,k]} \atop λ^{[i,j−1,k]}} {λ^{[i−1,j,k]} \atop λ^{[i,j,k]}} ) is of one of the types RS0–RS3, and it is of type RS1 if and only if j = σ_{i}.

(c) For i + k > n and j > 0 the configuration ({λ^{[i,j−1,k−1]} \atop λ^{[i,j−1,k]}} {λ^{[i,j,k−1]} \atop λ^{[i,j,k]}} ) is of one of the types RS^{t}0–RS^{t}3, and it is of type RS^{t}1 if and only if j = (σñ)_{k} or equivalently j = σ_{n+1−k}.

(d) For i + k > n + 1 the configuration ({λ^{[i,j,k]} \atop λ^{[i,j,k−1]}} {λ^{[i−1,j,k]} \atop λ^{[i−1,j,k−1]}} ) is of one of the types S0–S2. Once the existence of the family λ^{[i,j,k]} is established, the equivalence of (9) and (11) follows, since we have ch P = (λ^{[n,n,n]}, λ^{[n,n−1,n]}, …, λ^{[n,0,n]}), ch Q = (λ^{[n,n,n]}, λ^{[n−1,n,n]}, …, λ^{[0,n,n]}), and ch S(Q) = (λ^{[n,n,n]}, λ^{[n,n,n−1]}, …, λ^{[n,n,0]}). The existence proof is by induction on the triple (i, j, k): using the coordinatewise partial ordering on N × N × N, the induction hypothesis is that the partitions have been defined and the conditions established for all smaller triples. For i + k = n + 1 we either have j = σ_{i} = σ_{n+1−k}, in which case λ^{[i,j−1,k]} = (0) and λ^{[i,j,k]} = (1), or j ≠ σ_{i} = σ_{n+1−k}, in which case λ^{[i,j−1,k]} = λ^{[i,j,k]}; both cases satisfy (b) and (c).

In the remaining cases any subset of the indices i, j, k can be decreased by 1, giving another valid index triple; to avoid unwieldy expressions we give names to the 8 partitions selected by such such triples. Put κ = λ^{[i−1,j−1,k−1]}, λ = λ^{[i,j−1,k−1]}, μ = λ^{[i−1,j−1,k]}, ν = λ^{[i,j−1,k]}, and the same with primes when using j instead of j − 1: κ′ = λ^{[i−1,j,k−1]}, λ′ = λ^{[i,j,k−1]}, μ′ = λ^{[i−1,j,k]}, ν′ = λ^{[i,j,k]}. These partitions can be arranged in an obvious way on the 8 vertices of a cube, and our conditions correspond to the 6 faces of that cube: the configurations ({ν \atop λ} {μ \atop κ}) and ({ν′ \atop λ′} {μ′ \atop κ′} ) should be of type S0–S2, the configurations ({κ \atop λ} {κ′ \atop λ′} ) and ({μ \atop ν} {μ′ \atop ν′} ) of type RS0–RS3, and configurations ({κ \atop μ} {κ′ \atop μ′} ) and ({λ \atop ν} {λ′ \atop ν′} ) of type RS^{t}0–RS^{t}3; of each of these pairs the first may be assumed to be of the required type by indiction. The partitions κ, λ, ν, and κ′, together with knowledge of whether either of the conditions j = σ_{i} and j = (σñ)_{k} holds, determine all the other partitions; in a case-by-case analysis we shall verify that they always do so consistently.

(1) j = σ_{i}. Since i + k > n + 1, this excludes the possibility j = (σñ)_{k}. We have κ = λ = κ′, and λ′ = ρ^{+}(λ); if ν = λ, then the configuration ({μ \atop ν} {μ′ \atop ν′} ) coincides with ({κ \atop λ} {κ′ \atop λ′} ), and all conditions are satisfied. Otherwise ν ∈ λ^{+}, μ = ν = μ′, and ν′ = ρ^{+}(ν), and we must check that ({λ \atop ν} {λ′ \atop ν′} ) is of type RS^{t}2–RS^{t}3 and that ({ν′ \atop λ′} {μ′ \atop κ′} ) = ({ν′ \atop λ′} {ν \atop λ}) is of type S1–S2. From ν ∈ λ^{+} we get ν′ = λ^{′+} (the first part is increased in both cases), so that we have at least the proper inclusions. Now if ν ≠ λ′ then types RS^{t}3 and S2 apply respectively; if on the other hand ν = λ′, then ν′ = ρ^{+}(ρ^{+}(λ)), and we have types RS^{t}2 and S1, since for all partitions λ we have τ^{+}(ρ^{+}(λ), λ) = ρ^{+}(ρ^{+}(λ)), and clearly the squares added by the successive applications of ρ^{+} are adjacent.

(2) j = (σñ)_{k}. This case follows by symmetry from (1), namely by simultaneously interchanging the first and third index of the family and σ and σñ, and transposing all partitions and squares.

Having dealt with j = σ_{i} and j = (σñ)_{k}, the remaining cases where κ is equal to one of λ, μ, and κ′ are easy, since two opposite faces of the cube become equal and all conditions are satisfied. Hence we assume that this is not the case, and for convenience define the squares p = λ − κ, q = ν − λ, and r = κ′ − κ. The remaining cases are distinguished by the possibilities for the relative positions of p, q, and r.

[figure: κ; λ; μ; ν; κ′; λ′; μ′; ν′; p; q; r]

(3) r ∉ {p, q}. In this case all primed partitions are obtained from the unprimed ones by adding the square r, so ({ν′ \atop λ′} {μ′ \atop κ′} ) has the same type as ({ν \atop λ} {μ \atop κ}), and the remaining faces have types RS2 and RS^{t}2.

(4) r = p /∥ q. Then we have μ = κ + q, κ′ = λ = κ + p, and μ′ = ν = μ + p = λ + q, so both ({κ \atop λ} {κ′ \atop λ′} ) and ({μ \atop ν} {μ′ \atop ν′} ) have type RS2: we have λ′ = ρ^{+}(λ, κ) and ν′ = ρ^{+}(ν, μ). Now we make a further distinction: (4a) λ′ = ν, which occurs if and only if q lies in the row following that of p. Now ν′ = ν + s, where s

is the cocorner of ν in the same row as q; since q is a corner of ν, we have a horizontally adjacent pair of squares q ∥ s. Furthermore, ({λ \atop ν} {λ′ \atop ν′} ) is of type RS^{t}2, so we should have τ^{+}(ν, λ) = ν′ = ν + s; indeed s is a cocorner of ν in the column following that of q. Also, q ∥ s implies that ({ν′ \atop λ′} {μ′ \atop κ′} ) = ({ν′ \atop ν} {ν \atop λ}) is of type S1.

(4b) λ′ ≠ ν. Then since the cocorner t of λ in the row following that of p is distinct from q, it is also a cocorner of ν, so λ′ = λ + t and ν′ = ν + t, and ({λ \atop ν} {λ′ \atop ν′} ) is of type RS^{t}3. Furthermore, ({ν′ \atop λ′} {μ′ \atop κ′} ) = ({ν′ \atop λ′} {ν \atop λ}) is of type S2.

(5) p /∥ q = r. This case follows by symmetry from case (4).

(6) r = p ∥ q, and p and q lie in the same row. Then λ = μ = κ′ = κ + p, and μ′ = τ^{+}(λ, κ) = λ + q = ν, so both ({κ \atop λ} {κ′ \atop λ′} ) and ({μ \atop ν} {μ′ \atop ν′} ) have type RS2: we have λ′ = ρ^{+}(λ, κ) and ν′ = ρ^{+}(ν, μ). Now the cocorner t in the row following that of p is also the cocorner of ν in the row following that of q, so λ′ = λ + t and ν′ = ν + t, and ({λ \atop ν} {λ′ \atop ν′} ) is of type RS^{t}3. Furthermore, ({ν′ \atop λ′} {μ′ \atop κ′} ) = ({ν′ \atop λ′} {ν \atop λ}) is of type S2.

(7) r = p ∥ q, and p and q lie in the same column. This case follows by symmetry from case (6). This completes all possible cases, and therefore also the proof of theorem 4.1.1.

Here are some examples of possible positions of the squares in some of the cases we distinguished.

(3)  (4a)  (4b)  (6)
q ; r ; p  p ; q s  p ; t ; q  p q ; t

p q ; r  p ; q s  q ; p ; t  p q ; t

21

Although the statement being proved and the setup of the proof are different, our case-by-case verification is essentially the same as that given in the proof of [Sche, Lemma 6] (the cases actually checked there correspond to our cases (1), (3), and (5)). This shows that in a sense Schensted was already very close to proving the hard part of theorem 4.1.1, namely the equivalence of equations (9) and (11); he could of course not do that completely because the algorithm S was not known to him, and he was also unaware of the symmetry of his correspondence (theorem 3.2.1), so that he could not have derived the other equivalences of theorem 4.1.1. In retrospect this is somewhat remarkable, since the proof of theorem 3.2.1 is relatively simple compared to the proof just given. Of course this is not quite fair, since the simplicity of the former proof is largely a consequence of viewing tableaux as chains of partitions, which Schensted did not do (even though his proof uses induction on the highest entry of P); nevertheless there are some objective reasons for considering theorem 4.1.1 to be harder than theorem 3.2.1, like the fact that it involves the interaction of three distinct ways of modifying tableaux, and its larger number of essentially different cases.

While theorem 4.1.1 gives a clear statement of the relationship between the three full algorithms S, RS, and RS^{t} involved, there is a number of statements, given below, that provide equivalent information, but stated in terms of the effects of the basic procedures; the first one is the slight generalisation of [Sche, Lemma 6] that we mentioned before. The basic technical fact of theorem 4.1.1 is that the relations for the family λ^{[i,j,k]} around a single cube are consistent. The theorem itself (or rather the equivalence of (9) with either (10) or (11)) corresponds to consistency through the complete family, while the statements below correspond to consistency around some smaller collection of cubes, arranged in a single line or plane. It will be convenient to allow applications of RS to sequences of distinct numbers that are not necessarily permutations: the meaning of RS(m_{1}, …, m_{k}) = (P, Q) shall be that P = ⊙←m_{1}←⋯←m_{k}, and Q ∈ T_{| sh P |} is such that ch Q = (sh P, sh(⊙ ← m_{1} ← ⋯ ← m_{k−1}), …, sh(⊙ ← m_{1}), (0)).

4.1.2. Corollary. Let T be a tableau, and m, m′ numbers not occurring as entries of T.

(a) (m → T) ← m′ = m → (T ← m′) and the configuration ({sh(m→T ←m′) \atop sh(m→T)} {sh(T ←m′) \atop sh T}) is of type S1 or S2.

(b) If m < T then (T ←m)^{↓} = T = (m→T)^{↓} = T; otherwise (T ←m)^{↓} = T^{↓}←m and (m→T)^{↓} = m→T^{↓}, and moreover the configuration ({sh T^{↓} \atop sh T} {sh(T^{↓}←m) \atop sh(T ←m)}) is of type RS^{t}2 or RS^{t}3, while the configuration ({sh T^{↓} \atop sh T} {sh(m→T^{↓}) \atop sh(m→T)}) is of type RS2 or RS3.

(c) S(T ← m) = −m → S(T) and S(m → T) = S(T) ← −m.

(d) If RS((m_{1}, …, m_{k})) = (T, Q′), then RS((m, m_{1}, …, m_{k})) = (P, Q), where I^{t}(m, T) = (P, s) and Q ∼ D^{−1}(Q′, s, 0).

In the family λ^{[i,j,k]} used in the proof of theorem 4.1.1, a member of the form λ^{[i,n,k]} is the shape of the tableaux (P, Q) = RS((σ_{n+1−k}, …, σ_{i})), and the general member λ^{[i,j,k]} is the shape of the subtableau of P with entries ≤ j (or equivalently, one may remove the numbers > j from the sequence (σ_{n+1−k}, …, σ_{i})). It follows from corollary 4.1.2 that we can extend the family with a fourth index l, corresponding to removal of all entries ≤ l from the sequence, or from P by deflation, and that the configurations obtained by varying this index and one of the other three will be of types RS^{t}0–RS^{t}3, S0– S2, and RS0–RS3 respectively. Such a family demonstrates the equivalence of (9) and (12) in a direct way. Fortunately, there is no need to reason about the 8 cubic faces of a 4-dimensional hypercube within this family, but as we shall see in the next subsection, considering the hypercube itself can be useful.

4.2. A Robinson-Schensted algorithm for the hyperoctahedral group.

Equivalence of (9) and (12) in theorem 4.1.1 implies that RS(σ) is a pair of (up to similarity) self-dual tableaux if and only if ñσñ = σ, i.e., if σ commutes with ñ. Now for m = 2n and m = 2n + 1, the centraliser of m̃ in the symmetric group S_{m} is isomorphic to the hyperoctahedral group H_{n}, and we have seen that self-dual tableaux of shape λ ∈ P_{m} correspond bijectively to total domino tableaux of shape λ, whose rank will be 0 or 1 according as m is even or odd. Therefore, there exists an algorithmically defined bijection between H_{n} and the set of pairs of domino tableaux of equal shape, rank 0, and with n dominos, and a similar bijection for domino tableaux of rank 1. We shall call these bijections Robinson-Schensted correspondences for the hyperoctahedral group. In this subsection we shall give an algorithmic description of these correspondences that is directly in terms of domino tableaux, bypassing the conversion to self-dual tableaux and use of the (ordinary) Robinson-Schensted algorithm for the symmetric group.

When considering H_{n} as the centraliser of m̃ in S_{m}, it is convenient to view S_{m} as the group of permutations of the set {−n, …, −1, 1, 2, …, n} if m = 2n, and of the set {−n, …, n} if m = 2n + 1; in this representation m̃ acts as multiplication by −1. To remain consistent, we shall also use that same set rather than {1, …, m} for indexing sequences of numbers representing permutations, and as the set of entries for the tableau Q computed by the Robinson-Schensted algorithm. Sequences σ representing elements of H_{n} are then characterised by the condition σ_{−i} = −σ_{i}.

Now let (σ_{−n}, …, σ_{n}) be such a sequence, where σ_{0} = 0 is defined only if m = 2n + 1. Let (P, Q) = RS(σ), where P and Q are self-dual, and let U and V be the domino tableaux corresponding to P and Q; by definition we have ch U = (sh P, sh P^{↓−}, sh P^{↓↓−−}, …) and ch V = (sh Q, sh Q^{↓−}, sh Q^{↓↓−−}, …). We can think of the sequence σ as being built up by starting with either an empty sequence or the sequence (0), and repeatedly extending it at both ends by opposite numbers. If P_{0} is the core tableau (so P_{0} = ⊙ or P_{0} = 0 ), then by 4.1.2(c) each tableau P_{i} = σ_{−i} → ⋯ → σ_{−1} → P_{0} ← σ_{1} ← ⋯ ← σ_{i} is self-dual, and P_{n} = P by 4.1.2(a); let U_{i} be the domino tableau corresponding to P_{i}. By 4.1.2(d) we see that ch V = (sh U_{n}, sh U_{n−1}, …, sh U_{0}), so the shapes of successive domino tableaux U_{i} differ by dominos. Our goal shall be to describe the transition from U_{i−1} to U_{i}, which will be the insertion process for domino tableaux. Like in the case of the ordinary insertion procedure, it will be sufficient to establish the relationship between the shapes of U_{i−1}^{−}, U_{i−1}, U_{i}^{−} and U_{i}, possibly using the value of σ_{i} as well. We have sh U_{i} = sh P_{i}, sh U_{i}^{−} = sh P_{i}^{↓−}, and similarly with i − 1 in place of i; moreover P_{i} = σ_{−i} → P_{i−1} ← σ_{i}, and by (7) and 4.1.2(b) we have P_{i}^{↓−} = σ_{−i} → P_{i−1}^{↓−} ← σ_{i}, unless either σ_{i} > P_{i−1} or σ_{i} < P_{i−1}.

Let us consider those exceptional cases first. If σ_{i} > P_{i−1} then we have by 4.1.2(b) that P_{i}^{↓−} = (σ_{−i} → P_{i−1} ← σ_{i})^{↓−} = (P_{i−1} ← σ_{i})^{−} = P_{i−1} so that U_{i}^{−} = U_{i−1}; moreover it follows from 4.1.2(b) and P_{i−1} = S(P_{i−1}) that sh U_{i} = sh(σ_{−i} → P_{i−1} ← σ_{i}) = ρ^{+}(sh(σ_{−i} → P_{i−1})) = ρ^{+}(sh S(P_{i−1} ← σ_{i})) = ρ^{+}(ρ^{+}(sh(P_{i−1}))), so that U_{i} is obtained by attaching a horizontal domino in row 0 to U_{i−1}. By similar reasoning, if σ_{i} < P_{i−1} then U_{i} is obtained by attaching a vertical domino in column 0 to U_{i−1}. These are the cases where no recursive computation is necessary to determine U_{i}^{−}.

In the remaining cases we can find the relationship we wish to find between the shapes of U_{i−1}^{−}, U_{i−1}, U_{i}^{−}, and U_{i}, by reasoning about (some of) the shapes of the 16 tableaux that can be obtained by applying any combination of the operators ‘σ_{−i} → · ’, ‘ · ← σ_{i}’, ‘ ·^{↓}’, and ‘ ·^{−}’ (all of which commute among each other) to P_{i−1}. Set λ = sh P_{i−1}^{↓−} = sh U_{i−1}^{−}, which is the smallest of these shapes, then sh P_{i−1} = sh U_{i−1} and sh(σ_{−i} → P_{i−1}^{↓−} ← σ_{i}) = sh U_{i}^{−} are both obtained by adding a domino to λ, say sh U_{i−1} = λ + s + t and sh U_{i}^{−} = λ + x + y with s ∥ t and x ∥ y. We distinguish cases according to the overlap {s, t} ∩ {x, y}, which can be one of ∅, {s}, and {s, t}. In the first two cases sh U_{i} is completely determined by the fact that it can be obtained by adding a domino to either λ + s + t or λ + x + y: in the former case sh U_{i} = λ + s + t + x + y, in the latter case if s = x = (k, l) then {t, y} = {(k + 1, l), (k, l + 1)}, and with z = (k + 1, l + 1) we have sh U_{i} = λ + s + t + y + z (we leave it as an exercise to find these results by a more explicit computation, like we do for the remaining case). So assume that s = x ∥ t = y, and assume moreover that s and t lie in the same row. Let u and v be the first two squares outside Y (λ) in the row following s and t (u is a cocorner of λ + s, and v is a cocorner of λ + s + t + u). Now since sh P_{i−1}^{↓−} = λ and sh P_{i−1}^{−} = λ + s = sh(σ_{−i} → P_{i−1}^{↓−}), we have by 4.1.2(b) that sh(σ_{−i} → P_{i−1}^{−}) = ρ^{+}(λ + s, λ) = λ + s + u. Then from sh P_{i−1} = λ + s + t = sh(σ_{−i} → P_{i−1}^{↓−} ← σ_{i}) we get that sh(σ_{−i} → P_{i−1}) = λ + s + t + u = sh(σ_{−i} → P_{i−1}^{−} ← σ_{i}), and then finally, using (8), that sh(σ_{−i} → P_{i−1} ← σ_{i}) = ρ^{+}(λ + s + t + u, λ + s + u) = λ + s + t + u + v, which is the desired value of sh U_{i} (there are several alternative routes that lead to the same conclusion). Therefore, if U_{i−1} and U_{i}^{−} have the same shape μ that differs from λ by a horizontal domino, then sh U_{i} can be obtained by adding a horizontal domino in the next row to μ; similarly, if μ differs from λ by a vertical domino, then sh U_{i} can be obtained by adding a vertical domino in the next column to μ.

As in previous cases, we can now define a set of configurations that can occur, and which we can then use to define the actual insertion process. Like in the other cases, we include a class of trivial configurations to allow for sequences of partitions with repetitions.

4.2.1. Definition An arrangement of partitions ({κ \atop μ} {λ \atop ν}) with λ, μ ∈ (\{κ\} ∪ κ^{++}) ∩ (\{ν\} ∪ ν^{−−}) is called (i) a configuration of type G1 if κ = λ = μ and ν = ρ^{+}(ρ^{+}(λ)), (ii) a configuration of type G2 if κ = λ = μ and ν = τ^{+}(τ^{+}(λ)), (iii) a configuration of type G3 if λ = μ ∈ κ^{++} ∩ ν^{−−} and for the unique partitions κ′, ν′ with κ ⊂ κ′ ⊂

λ ⊂ ν′ ⊂ ν one has λ = τ^{+}(κ′, κ) = τ^{−}(ν′, ν) and ν′ = ρ^{+}(λ, κ′), (iv) a configuration of type G4 if λ = μ ∈ κ^{++} ∩ ν^{−−} and for the unique partitions κ′, ν′ with κ ⊂ κ′ ⊂

λ ⊂ ν′ ⊂ ν one has λ = ρ^{+}(κ′, κ) = ρ^{−}(ν′, ν) and ν′ = τ^{+}(λ, κ′),

(v) a configuration of type G5 if λ, μ ∈ κ^{++} ∩ ν^{−−} and for the unique partitions κ′, ν′ with κ ⊂ κ′ ⊂ λ ⊂ ν′ ⊂ ν one has λ = τ^{+}(κ′, κ) = τ^{−}(ν′, ν) and μ = ρ^{+}(κ′, κ) = ρ^{−}(ν′, ν),

(vi) a configuration of type G6 if λ, μ ∈ κ^{++} ∩ ν^{−−} and for the unique partitions κ′, ν′ with κ ⊂ κ′ ⊂

λ ⊂ ν′ ⊂ ν one has λ = ρ^{+}(κ′, κ) = ρ^{−}(ν′, ν) and μ = τ^{+}(κ′, κ) = τ^{−}(ν′, ν), (vii) a configuration of type G7 if λ, μ ∈ κ^{++}, κ = λ ∩ μ and ν = λ ∪ μ, (viii) a configuration of type G0 if κ = λ ∧ μ = ν or κ = μ ∧ λ = ν (possibly both).

Types G1–G2 correspond to adding a new domino in row 0 or column 0, types G2–G3 to moving a domino to the next row or column, and types G4–G5 to a pair of dominos within a 2 × 2 square, overlapping in one square. One may check that if we know that one of these configurations applies, then to determine ν uniquely it suffices to know the values of κ, λ, μ, and whether G1 or G2 or one of the remaining types applies; conversely, from λ, μ, ν we can always determine κ.

We are now ready to define the Robinson-Schensted correspondence for hyperoctahedral groups directly in terms of domino tableaux. When we are only considering elements of H_{n} (i.e., we do not view this group as embedded in some S_{m}), then there is no need to use a complete sequence (σ_{−n}, …, σ_{n}) to represent an element σ ∈ H_{n}; the sequence (σ_{1}, …, σ_{n}) is sufficient for this purpose, and we shall call such a sequence a signed permutation.

4.2.2. Definition Let a fixed number r ∈ N be given, and let c_{r} be the core partition (r, r−1, …, 1). For a signed permutation (σ_{1}, …, σ_{n}) representing σ ∈ H_{n}, a pair of normalised domino tableaux (U, V) = G_{r}(σ) is defined as follows. Construct a family of partitions λ^{[i,j]} for 0 ≤ i, j ≤ n satisfying the following conditions: λ^{[i,0]} = λ^{[0,j]} = c_{r} for all i, j, and for all i, j > 0 the arrangement ({λ^{[i−1,j−1]} \atop λ^{[i,j−1]}} {λ^{[i−1,j]} \atop λ^{[i,j]}} ) is of one of the types G0–G7, which moreover is type G1 if and only if σ_{i} = j, and is type G2 if and only if σ_{i} = −j. Then U, V are such that ch U = (λ^{[n,n]}, λ^{[n,n−1]}, …, λ^{[n,0]}) and ch V = (λ^{[n,n]}, λ^{[n−1,n]}, …, λ^{[0,n]}). Using the same conditions one can determine for each pair of normalised domino tableaux (U, V) of equal shape and of rank r the corresponding σ ∈ H_{n}, which defines the inverse operation G_{r}^{−1}.

Here is an illustration of the computation of G_{1}((5, 1, 7, 3, −6, −4, 2)) = (_{0} _{1} _{2}_{3}_{4} _{5}_{6}  _{7} , _{0} _{1}_{2}  _{3}_{4}_{5} _{6} _{7} ); we have

labelled each configuration of type Gi for i ≠ 0 with the number i.

0 1  2  3  4  5  6  7

0

1  _{1}
2  _{1}  _{3}
3  _{1}
4  _{1}  _{7}  _{3}
5  _{2}  _{7}
6  _{2}  _{5}  _{6}  _{7}
7  _{1}  _{3}  _{6}  _{4}  _{7}  _{5}

Note that to perform the steps of the inverse computation G_{r}^{−1}(U, V) it is not necessary to know the value of r, or even that U and V have the same core; indeed one can view the computation as an effective proof that any two domino tableaux of the same shape have the same core. ¿From the way in which we have derived the definition of G it is evident that we have the following.

4.2.3. Theorem. Let r ∈ {0, 1} and m = 2n + r. For any σ ∈ H_{n}, if σ̄ is the corresponding element of S_{m}, and G_{r}(σ) = (U, V), RS(σ̄) = (P, Q), then the domino tableaux U and V correspond to the self-dual tableaux P and Q respectively.

Remarks. The idea of defining a Robinson-Schensted algorithm for H_{n}, using a class of special Young tableaux, is first mentioned by D. Barbasch and D. Vogan in [BaVog, p.171]. They define a procedure that is essentially the inverse of the algorithm we gave for associating a self-dual tableau to a total domino tableau; it is used mainly as a criterion to recognise self-dual tableaux. However, they do not prove their claim that this class of tableaux corresponds via RS^{−1} to H_{n} as subgroup of S_{2n} or S_{2n+1}; their “proof” is merely a description of a method of computing RS^{−1}(P, Q) for self-dual P, Q, by alternatingly using I^{−1} and I^{−t} to produce numbers at either end of the sequence. The algorithms G_{0} and G_{1} and their inverses were introduced by D. Garfinkle [Garf, definitions 1.2.1, 1.2.11, and remark 1.2.14], in a manner that can be seen to be equivalent to our definition. She mentions in the introduction that the correspondence obtained between pairs of domino tableaux and elements of H_{n} is the same as that of Barbasch and Vogan (as stated in our theorem 4.2.3), but the paper contains no proof of such a statement; nonetheless it seems reasonable to assume that the algorithm was derived along much the same lines as our reasoning above. It should be noted that neither of the papers mentioned here concerns itself primarily with combinatorial questions. Indeed the algorithms G_{i} are used only as a first step towards generalising an interpretation of the Robinson-Schensted algorithm, concerning so-called primitive ideals in the enveloping algebra of simple Lie groups of type A_{n}, to the other classical types B_{n}, C_{n}, and D_{n}; another algorithmic operation (called S in [Garf]) is required to complete the classification for these other types. (These questions can also be formulated in terms of the cells in the corresponding Weyl groups, as defined for instance by means of the Kazhdan-Lusztig polynomials.) In this context it is also appropriate to mention the current author’s thesis [vLee1], in which a geometric interpretation of the Robinson-Schensted and Schützenberger algorithms, described in [Stb] and in [vLee3], is generalised from type A_{n} to the other classical types. In that instance too, the answer is not simply given by an algorithm G_{r}: in fact the generalisation (called ϕ_{2} in [vLee1]) of RS^{−1} for this problem is very similar, but not quite identical to the algorithms G_{r}^{−1}. (Despite the differences between ϕ_{2} and G_{r}^{−1}, it appears that their results never diverge very far from each other; as yet we have not been able to formulate their exact relationship, however.)

There exists a family of algorithmically defined bijections between pairs of equal shaped tableaux consisting of a fixed q-core to which n rim hooks of size q are added, and “q-coloured permutations of n” (i.e., sequences representing a permutation of n, in which each term has an additional attribute (colour) whose value lies in Z/q); it was first defined in [StWhi], and a succinct formulation appears in [FomSt]. For the special case q = 2, where rim hooks are dominos and q-coloured permutations can be identified with elements of H_{n}, the description of such an algorithm, inspired mainly by enumerative considerations, can already be found in [Stan1, §6] (see also [Oka1]). We would like to stress however that this is not the same bijection as defined by any G_{r}. In fact there is a bijection between q-rim hook tableaux of fixed core and q-tuples of Young tableaux (it is a direct generalisation of the bijection we sketched earlier for the case q = 2) under which the q-rim hook algorithm is transformed into q ordinary Robinson-Schensted algorithms running together, one for each colour, where each entry is inserted using the tableau pair of its own colour. For G_{r} on the other hand there can be no such factorisation, as we shall see below.

Using the language of differential posets, we can understand the relationship between these algorithms quite clearly. If we equip the set P with a partial order that is not ordinary inclusion, but rather is generated by removal of q-rim hooks, it becomes a q-differential poset, which means that one has identities corresponding to (1) with the number 1 replaced by q, and to (2). This poset splits into disjoint components corresponding the the different q-cores (each q-core is the minimal element of its component). Like for ordinary differential posets one can define a Robinson-Schensted-like correspondence for any component of a q-differential poset, in which q-coloured permutations replace ordinary permutations, provided one has basic bijections realising the modified equation (1). The q-rim hook algorithm gives such a Robinson-Schensted-like correspondence, where the basic bijections are derived from the isomorphism of any component with the product of q copies of the Young lattice via the bijection mentioned before. The correspondence defined by G_{r} is also of this type, but the basic bijections are not equal in this case to those for the 2-rim hook poset; instead they are related to the configurations of types G1–G4.

Although the configurations used to define the algorithms G_{r} are independent of r, the algorithms are certainly not all equivalent in any sense. For instance, the equivalence classes induced in H_{n} of elements corresponding to pairs of tableaux of one same shape are not the same for each r, as can already be seen for n = 2 and r = 0, 1 (yet, by our earlier counting argument, the number of such classes is independent of r). Contrarily, due to the factoring into separate ordinary Robinson-Schensted algorithms, the similar classes defined by the 2-rim hook algorithms for different cores are all the same; this also shows that a similar factoring cannot hold for all G_{r}. The existence of many non-equivalent algorithms G_{r} may serve as some explanation for the fact that these algorithms apparently do not give a complete answer to those problems from outside combinatorics where a generalisation of the Robinson-Schensted correspondence to hyperoctahedral groups has been sought for.

It is interesting to consider the limit of G_{r} for r → ∞. One easily sees that if r + 1 ≥ n, then the dominos in the tableaux of G_{r}(σ) will always be separated into a group of horizontal dominos at the right end of the core and a group of vertical dominos at the bottom of the core, and further increase of r will not essentially change anything. Moreover, shifting the lines in the former group of dominos so as to line up the leftmost dominos of each row, respectively shifting the columns of the latter group to line up the topmost dominos, we obtain arrangements that are just elongated versions of ordinary Young tableaux. This suggests that this limiting case is equivalent to the 2-rim hook correspondence; indeed if we transpose the “Young tableau” at the bottom of the core, we see that we have two independent ordinary Robinson-Schensted algorithms (configurations G5 and G6 do not occur). Therefore the algorithms G_{r} for small r may be viewed as deformations of the 2-rim hook algorithm; it would be interesting to study in detail the effect on G_{r}(σ) of small changes to r.

Considerations as these raise numerous interesting questions about the correspondences defined by the G_{r}, but we shall not pursue them here; there are however still a few obvious properties of G_{r} to be noted. First, G_{r} exhibits the same symmetry with respect to its argument as expressed by 3.2.1 for RS: if G_{r}(σ) = (U, V) then G_{r}(σ^{−1}) = (V, U). Second, if G_{r}(σ) = (U, V) then G_{r}(−σ) = (U^{t}, V^{t}), where the minus sign indicates multiplication by the central element of H_{n} (denoted by m̃ in the embedding into S_{m}). For r = 0 and r = 1 these facts can be deduced immediately via theorem 4.2.3 from theorem 3.2.1 and theorem 4.1.1 respectively, but from our definition it is clear that these properties hold for all r. Like for the proper Robinson-Schensted algorithm, one may handle the special case that σ is an involution in the group by computing the partitions λ^{[i,j]} only for i ≥ j; this leads to the following analogue of proposition 3.3.1.

4.2.4. Proposition. Let σ ∈ H_{n} be an involution, G_{r}(σ) = (U, U), and λ = sh U. Let k be the difference between the number of odd-length columns of λ and of the core (r, …, 1) of U (the latter number is \frac{r}{2} rounded upwards), and define l similarly for odd-length rows. Then k and l are non-negative even numbers, and the number of i > 0 with σ_{i} = i equals \frac{k}{2} , while the number of i > 0 with σ_{i} = −i equals \frac{l}{2}.

Via the indirect way of involutions in H_{n}, we obtain bijections t_{r,r′} between the sets of domino tableaux of ranks r and r′, for any r, r′ ∈ N, namely by setting t_{r,r′}(U) = U′ whenever G_{r}^{−1}(U, U) = G_{r′}^{−1}(U′, U′). These bijections do not always preserve equality of shape between tableaux, whence it cannot be generally true that G_{r}^{−1}(U, V) = G_{r′}^{−1}(t_{r,r′}(U), t_{r,r′}(V)), nor do the t_{r,r′} coincide with the bijections obtained via the isomorphisms of each of the components of the 2-rim hook lattice with P × P. The interesting question of giving a direct description of the t_{r,r′} is likely to require some techniques different from those used in this paper, since they do not commute with removal of the highest domino: while t_{0,1}( \begin{matrix}1 \\ 2 \end{matrix} ) = _{0} _{1}_{2} , we find that t_{0,1}( _{1}_{2} _{3} ) = _{0} _{1}_{2} _{3} . It seems that techniques similar to those in [Garf, §5] can be useful for answering this question and related ones.

§5. Glissement. In this section we shall discuss a different construction called glissement, defined by Schützenberger in [Schü3], where it is used for an independent approach to the Robinson-Schensted and Schützenberger algorithms. In that approach some fundamental properties of glissement are derived from results of Knuth [Kn1, Theorem 6] and Greene [Gre1, Theorem 3.1], and once these have been established, a connection can be made to the Robinson-Schensted and Schützenberger correspondences in their traditional form, from which the key properties of those correspondences, expressed by our theorems 2.2.1, 3.2.1, and 4.1.1, follow quite easily. We give here an opposite approach, by indicating how these basic facts about the traditional algorithms can be used to derive in a fairly simple way the fundamental properties of glissement, without using the results of Knuth and Greene. It is interesting to note that the facts we use were known long before the latter results were obtained.

First we generalise Young tableaux to to so-called skew tableaux. A skew diagram is a finite subset χ of Z × Z that is convex with respect to the natural ordering, i.e., for any pair of squares s, t ∈ χ we have p ∈ χ whenever s ≤ p ≤ t. A skew diagram is a Young diagram if and only if it is either empty or contains the origin as unique minimal element, and every skew diagram χ contained in N × N can be expressed as the difference set Y (λ) \ Y (μ) for some λ, μ ∈ P with μ ⊆ λ; note however that in general λ and μ are not uniquely determined by χ. A skew tableau of shape χ is an injective map φ : χ → Z that is increasing along rows and columns; more formally, it is an injective morphism of partially ordered sets χ → Z. Like Young tableaux, a skew tableau can be depicted by filling each square with its image in Z, which may look something like

4 10 13 7 8 11 6

(the lines to indicate the limits of N × N). For a skew tableau φ : χ → Z we define sh φ = χ. If χ = Y (λ) \ Y (μ), then one can associate to φ a saturated decreasing chain in P from λ to μ, but since λ and μ are not uniquely determined by φ, we cannot speak of the chain corresponding to φ. Nevertheless this will be a useful point of view, provided we can see that the operations we perform do not depend in an essential way on the choice of λ (or equivalently, of μ). Like for Young tableaux we define a similarity relation for skew tableaux of the same shape: for skew tableaux φ, φ′: χ → Z we say φ and φ′ are similar, written φ ∼ φ′, whenever φ′ = f ∘ φ for some monotonic function Z → Z. For instance, the skew tableau displayed above is similar to

1 5 7 3 4 6 2 .

One obvious way to obtain a skew tableau is to restrict a Young tableau T to the set of squares whose entries lie in a specified interval J of Z, which set is always a skew diagram; we shall call this the restriction to J of T, written T |_{J}. Every non-empty skew tableau φ whose shape is contained in N × N can be obtained as the restriction of some Young tableau T to an interval containing the highest entry of T; we call such a tableau T an extension of φ to a Young tableau. By restricting T to the complement of sh φ we obtain another Young tableau, which we shall denote as T \ φ. In [Schü3] the notion of glissement is defined in a uniform way for all skew tableaux, but because we want to emphasise the relation with the deflation procedure, we first define it only for skew tableaux whose shape is contained in N × N, and shall extend it by translation to all tableaux later.

5.1. Definition Let φ and φ′ be a skew tableaux whose shapes are contained in N × N, and with the same set of entries; φ′ is a glissement of φ, written as φ ▷ φ′, if there exists an extension T of φ to a Young tableau, say φ = T |_{J} such that φ′ = T^{↓···↓}|_{J} for some number of applications of ‘·^{↓}’ (this number cannot exceed | sh(T \ φ)|, lest entries of φ would be lost); T is called a witness for the relation φ ▷ φ′.

In terms of the family of partitions λ^{[i,j]} that we have used for the Schützenberger algorithm, this definition can be described as follows. In the computation of S(T) one has such a family for 0 ≤ i, j ≤ n and i + j ≤ n with ch T = (λ^{[0,0]}, λ^{[0,1]}, …, λ^{[0,n]}), and φ corresponds to an initial part of that chain, say to (λ^{[0,0]}, λ^{[0,1]}, …, λ^{[0,k]}). Then if the operator ‘·^{↓}’ was applied l times, we have k + l ≤ n, and φ′ corresponds to the chain (λ^{[l,0]}, λ^{[l,1]}, …, λ^{[l,k]}). The only relevant aspect of the choice of T \ φ is in determining the chain (λ^{[0,k]}, λ^{[1,k]}, …, λ^{[l,k]}), and it is always possible for given values of λ^{[0,0]}, λ^{[0,1]}, …, λ^{[0,k]}, λ^{[1,k]}, …, λ^{[l,k]} to choose an extension T that will lead to those values. If l = 1 we shall call φ′ a one-step glissement into square s of φ, written φ ▷_{s} φ′, where s = λ^{[0,k]} − λ^{[1,k]}. From the traditional definition of the deflation procedure it is obvious that if we apply a translation in the plane uniformly to each of φ, φ′, and s, such that the images lie in N × N, then the same relation will hold for those images. This allows us to define one-step glissement for arbitrary skew tableaux, by translating everything into N × N. It is obvious that whenever φ ▷ φ′, we can find a sequence φ ▷_{s_{1}} ⋯ ▷_{s_{k}} φ′, so we can define general glissement by repeated one-step glissement, provided that we can prove the following.

5.2. Lemma. For skew tableaux φ, φ′, φ′′ whose shapes are contained in N × N, and a square s, the relation φ ▷ φ′ ▷_{s} φ′′ implies φ ▷ φ′′.

Proof. Choosing an arbitrary witness for φ ▷ φ′ we get as indicated above values λ^{[0,0]}, λ^{[0,1]}, …, λ^{[0,k]}, λ^{[1,k]}, …, λ^{[l,k]} that describe the steps used to establish φ ▷ φ′. Now if s is a corner of λ^{[l,k]}, then we can set λ^{[l+1,k]} = λ^{[l,k]} − s, and choose a witness for φ ▷ φ′′ leading to these values. If on the other hand s is not a corner of λ^{[l,k]}, then Y (λ^{[l,k]}) contains some squares > s that are incomparable with sh φ′. If t is a maximal such square, it is a corner of λ^{[l,k]} and we can set λ^{[l+1,k]} = λ^{[l,k]} − t; this extended set of values still describes φ ▷ φ′, since φ′ ▷_{t} φ′. This process can be repeated (while increasing l) until finally s is a corner of λ^{[l,k]}, and then the case already handled provides a witness for φ ▷ φ′′.

As a corollary to the proof of the lemma we see that whenever φ ▷ φ′, we can find an witness P for φ ▷ φ′ which is of the minimal size possible (given sh φ), i.e., with sh P = λ where Y (λ) = { s | ∃t ∈ sh φ: s ≤ t } (extend φ to an arbitrary Young tableau of shape λ, which is a witness for the trivial relation φ ▷ φ; then use the given construction to successively add one-step glissements, which does not involve any squares outside Y (λ)); we call such a P a minimal witness for φ ▷ φ′.

For a skew tableau φ′ obtained from φ by a translation over (−x, −y) with x, y ∈ N we have φ ▷ φ′. To see this, it suffices to consider the case x = 0, y = 1. In each row that meets sh φ consider the square directly before the first square of sh φ; let s_{1}, …, s_{k} be the sequence of these squares ordered by decreasing row number. Now form the sequence φ = φ_{0} ▷_{s_{1}} φ_{1} ▷_{s_{2}} ⋯ ▷_{s_{k}} φ_{k}. One easily sees that the one-step glissement into s_{i} shifts the row of s_{i} one place to the left; consequently φ_{k} = φ′ so that φ ▷ φ′ as claimed. A skew diagram χ may be partitioned into connected components, which are equivalence classes for the equivalence relation generated by s ∥ t. The above argument may be extended to the case that φ′ is obtained from φ by applying possibly different translations to each of the connected components of sh φ, provided that no component is moved into or across rows or columns occupied by other components.

The following direct consequence of theorem 4.1.1 is our crucial connection between the algorithms discussed before, and glissements. It also justifies a claim made at the end of §2 concerning “almost self-dual tableaux with infinitesimal entries”.

5.3. Lemma. Let Q, Q′ be two Young tableaux of equal shape, which coincide with each other in the position of each of their k highest entries, for some k ∈ N. Then S(Q) and S(Q′) coincide with each other in the positions of each of their their k lowest entries.

Proof. Let λ = sh Q = sh Q′, and choose any fixed tableau P ∈ T_{λ}. Now compute the permutations σ = RS^{−1}(P, Q) and σ′ = RS^{−1}(P, Q′). From the definition of R it follows that the last k terms in the sequence of σ coincide with those of σ′, as the first k extractions proceed identically in both computations. Since the sequence of σñ is the reverse of that of σ, we find that σñ and σ′ñ coincide in their first k terms. Now by theorem 4.1.1, we have RS^{t}(σñ) = (P, Q^{∗}) and RS^{t}(σ′ñ) = (P, Q^{′∗}), with Q^{∗} ∼ S(Q) and Q^{′∗} ∼ S(Q′); the first k (column) insertions during these computations are identical, so S(Q) and S(Q′) must coincide in the positions of their k lowest entries.

Remark. We could also have used either of the other equivalences of theorem 4.1.1 to obtain a similar proof. Note that while the choice of P was necessary in the above computation, the entries of Q and Q′ other than the k highest of them need not even be inspected; one simply stops the computation of σ once the final k terms are determined, with which one can then perform the first k steps of the computation of RS^{t}(σñ), which already determine the required part of S(Q) and S(Q′).

We now come to the central fact in the theory of glissements.

5.4. Theorem. For any skew tableau φ with sh φ ⊆ N×N there is a unique Young tableau T with φ ▷ T.

Proof. Then existence of such T is obvious, so let T′ be another Young tableau with φ ▷ T′. Choose minimal witnesses Q and Q′ for φ ▷ T and φ ▷ T′, and let k = # sh φ; as Q and Q′ are both extensions of φ, they coincide in the positions of their k highest entries. We also have sh Q = sh Q′, so that lemma 5.3 applies, giving S(Q)|_{J} = S(Q′)|_{J}, where J is the interval containing the k lowest entries of S(T). From the definitions of S and of glissement it follows that S(Q)|_{J} = S(T) and similarly S(Q′)|_{J} = S(T′). From the invertibility of S it follows that T = T′.

The proof clearly indicates a connection between glissement and the Robinson-Schensted algorithm, which we shall now make more explicit. It can easily be deduced from 4.1.2(d), using theorem 3.2.1, that if the sequence σ′ is the result of removing the smallest term from σ, and RS(σ) = (P, Q), then RS(σ′) = (P^{↓}, Q′) for some Q′. Now the tableau T of theorem 5.4 can be constructed as follows. Choose an extension P of φ and any Q ∈ T_{| sh P |}, and compute σ = RS^{−1}(P, Q), which sequence contains the entries of φ interspersed with those of P \φ, where the former entries exceed all the latter ones. If we successively remove all entries of P \ φ from the sequence in increasing order, then we see that the corresponding left tableaux under the application of RS will be φ, φ^{↓}, …, φ^{↓···↓} = T, so T = ⊙ ← x_{1} ← ⋯ ← x_{k}, where x_{1}, …, x_{k} are the entries of φ taken in the order in which they occur in σ. By choosing Q in a special way, it can be achieved that the entries of P are extracted in a very orderly way to produce σ: if for each extraction I^{−1}(P_{i}, s) the square s it the corner of sh P_{i} in its last non-empty column, then the columns of P are successively marched out of the tableau from right to left, and σ will consist of a concatenation of the columns of P from left to right, where each column is read from bottom to top. The sequence x_{1}, …, x_{k} can therefore be be the one obtained by reading the entries of φ in a similar order. Using another equally orderly extraction order (beginning each extraction in the column before the previous one if possible, while starting each sweep in the last column), another sequence x_{1}, …, x_{k} can be obtained by concatenating the rows of φ from bottom to top. The following consequence is obvious.

5.5. Proposition. Let σ be a permutation, and φ(σ) a skew tableau such that sh φ(σ) ⊂ N × N and its connected components are all singletons, whose entries, listed by increasing column numbers, form the sequence for σ. Then in (P, Q) = RS(σ) the tableau P can be found as the unique Young with φ(σ) ▷ P; similarly, Q is determined by φ(σ^{−1}) ▷ Q.

There is also a description of the Schützenberger correspondence in terms of glissement. First consider a reversal operation on skew tableaux: for a skew diagram χ define −χ =^{def} { (−i, −j) | (i, j) ∈ χ }, which is again skew diagram, and for a skew tableau φ: χ → Z define a skew tableau \overline{φ}: −χ → Z by \overline{φ}(−i, −j) = −φ(i, j). It is easy to see that φ ▷_{s} φ′ is equivalent to \overline{φ′} ▷_{−s′} \overline{φ} where \{s\} ∪ sh φ = sh φ′ ∪ \{s′\}, and therefore that φ ▷ φ′ is equivalent to \overline{φ′} ▷ \overline{φ}. Now it is clear from theorem 4.1.1 and proposition 5.5 that if σ is a permutation and P the Young tableau with φ(σ) ▷ P, then φ(ñσñ) ▷ P^{∗} ∼ S(P). But we also have \overline{P} ▷ \overline{φ(σ)}, and up to a translation to bring its shape into N × N, the latter skew tableau is similar to φ(ñσñ), and has the same set of entries as S(P). So by transitivity of glissement, we get the following characterisation of S(P).

5.6. Proposition. For any Young tableau P, the Young tableau S(P) is the unique one that is a glissement of some translation of \overline{P} into N × N.

Calling a partition rectangular if all its non-zero parts are equal, we have in particular the following.

5.7. Proposition. For any Young tableau P of rectangular shape, S(P) is a translation of \overline{P}.

In the opinion of the author, this is the most amazing of all the remarkable facts about the Robinson-Schensted and Schützenberger algorithms, having such a simple formulation, yet apparently without a correspondingly simple proof. It means that in the computation of S(P) for rectangular P, by the original definition using the sequence of intermediate tableaux P^{↓···↓}, the position of the square where any of the deflation steps involved ends, is determined only by λ and the (original) position in P of the entry that is removed by that deflation step. Therefore that entry, while moving towards the origin in earlier deflation steps, has like magic managed to encode the information about its original position into the positions of the remaining entries, which moreover were simultaneously performing the same feat!

We end here our discussion of glissement, since our purpose was just to mention those aspects that are directly related to the Robinson-Schensted and Schützenberger algorithms. Let us remark however that the study of glissement becomes even more interesting when generalised to work with pictures instead of skew tableaux. With respect to skew tableaux, pictures have an additional symmetry in that squares are mapped to other squares rather than to numbers (subject to certain restrictions), so that the inverse of a picture is again a picture; it is then possible to form glissements both at the domain and image side of a picture. In this light proposition 5.5 becomes more symmetric, because rather than having to somewhat artificially construct the skew tableau φ(σ^{−1}) for the inverse permutation to obtain the tableau Q, it suffices to apply glissement at the image side of the picture analogue of φ(σ) itself. Moreover, it turns out that both forms of glissement commute with each other, and once this has been established, the main properties of glissement such as theorem 5.4 can be deduced while using neither the theorems of Knuth and Greene (as is done in [Schü3]), nor the central theorem 4.1.1 (as we have done here). We refer to [vLee4] for a description of this independent route leading to many of the results that were discussed in this paper.

References.

[BaVog] D. Barbasch and D. Vogan, “Primitive ideals and orbital integrals in complex classical groups”, Mathematische Annalen 259, (1982), 153–199.

[BeSt] G. Benkart and J. Stroomer, “Tableau and insertion schemes for spinor representations of the orthogonal Lie algebra 𝔰𝔬(2r + 1, C)”, J. Combin. Theory, Ser. A 57, (1991), 211–237.

[BeSoSt] G. Benkart, F. Sottile, J. Stroomer, Tableau switching: algorithms and applications, Preprint, submitted to J. Combin. Theory, Ser. A, (1993).

[Bere] A. Berele, “A Schensted-type correspondence for the symplectic group”, J. Combin. Theory, Ser. A 43, (1986), 320–328.

[Fom1] S. V. Fomin, “Finite partially ordered sets and Young tableaux”, Soviet Math. Dokl. 19, (1978), 1510– 1514.

[Fom2] S. V. Fomin, “Generalised Robinson-Schensted-Knuth correspondence”, Journal of Soviet Mathematics 41, (1988), 979–991. (Translation from ������� ������� ��������� ���� 155 (1986) 156–175; authorised translation available from the author).

[Fom3] S. Fomin, Dual graphs and Schensted correspondences, Proceedings of the 4th International conference on Formal power series and Algebraic combinatorics, Montreal, (1992).

[Fom4] S. Fomin, Schur operators and Knuth correspondences, Institut Mittag-Leffler report No. 17, (1991/92).

[Fom5] S. Fomin, “Duality of graded graphs”, J. Algebr. Combinatorics 3, (1994), 357–404.

[Fom6] S. Fomin, “Schensted algorithms for dual graded graphs”, J. Algebr. Combinatorics 4, (1995), 5–45.

[FoGr] S. Fomin and C. Greene, “A Littlewood-Richardson Miscellany”, Europ. J. Combinatorics 14, (1993), 191–212.

[FomSt] S. Fomin and D. Stanton, Rim hook lattices, Institut Mittag-Leffler report No. 23, (1991/92).

[FrSch] F. G. Frobenius and I. Schur, “Über die reellen Darstellungen der endlichen Gruppen”, Sitzungsberichte der Preussische Akademie, (1906), 186–208. Also in F. G. Frobenius: Gesammelte Abhandlungen (J.-P. Serre ed.), Springer Verlag (1968) 355–377.

[Garf] D. Garfinkle, “On the classification of primitive ideals for complex classical Lie Algebra’s, I”, Compositio Mathematica 75, (1990), 135–169.

[Gre1] C. Greene, “An extension of Schensted’s Theorem”, Advances in Mathematics 14, (1974), 254–265.

[Gre2] C. Greene, “Some partitions associated with a partially ordered set”, J. Combin. Theory, Ser. A 20, (1976), 69–79.

[Haim1] M. D. Haiman, “On mixed insertion, symmetry, and shifted Young tableaux”, J. Combin. Theory, Ser. A 50, (1989), 196–225.

[Haim2] M. D. Haiman, “Dual equivalence with applications, including a conjecture of Proctor”, Discrete Mathematics 99, (1992), 79–113.

[Hes] W. H. Hesselink, “A classification of the nilpotent triangular matrices”, Compositio Mathematica 55, (1985), 89–133.

[JaKer] G. James and A. Kerber, The representation theory of the symmetric group, Encyclopedia of mathematics and its applications (G.-C. Rota, ed.) Vol. 16, Addison-Wesley, Reading MA, 1981.

[Jos] A. Joseph, “Sur la classification des idéaux primitifs dans l’algèbre enveloppante d’une algèbre de Lie reductive”, Comptes rendus de l’Acad. Sciences, serie A 284 #8, (1977), 425–427.

[KaLu] D. Kazhdan and G. Lusztig, “Representations of Coxeter groups and Hecke algebras”, Inventiones Math. 53, (1979), 165–184.

[Kn1] D. E. Knuth, “Permutations, matrices and generalized Young tableaux”, Pacific Journal of Math. 34, (1970), 709–727.

[Kn2] D. E. Knuth, The art of Computer programming, Vol. III Sorting and Searching, pp. 48–72, Addison-Wesley, 1975.

[LaSch] A. Lascoux and M. P. Schützenberger, “Le monoïde plaxique”, Quad. Ricerca Scientifica C.N.R. 109, (1981), 129–156.

[vLee1] M. A. A. van Leeuwen, A Robinson-Schensted algorithm in the geometry of flags for Classical Groups, Thesis (Rijksuniversiteit Utrecht, the Netherlands), (1989).

[vLee2] M. A. A. van Leeuwen, The Robinson-Schensted and Schützenberger algorithms, Part I: New combinatorial proofs, CWI report AM-R9208, (1992). This report is also electronically available via

http://www.cwi.nl/cwi/publications/index.html#AM.

[vLee3] M. A. A. van Leeuwen, The Robinson-Schensted and Schützenberger algorithms, Part II: Geometric interpretations, CWI report AM-R9209, (1992). This report is also electronically available via

http://www.cwi.nl/cwi/publications/index.html#AM.

[vLee4] M. A. A. van Leeuwen, “Tableau algorithms defined naturally for pictures”, in Formal Power Series and Algebraic Combinatorics, Abstracts for FPSAC ’94, DIMACS, 1994. Full paper available electronically

at ftp://ftp.cwi.nl/pub/pictures/fullpaper.tex.gz.

[LiRi] D. E. Littlewood and A. R. Richardson, “Group characters and algebra”, Phil. Trans. A 233, (1934), 99–141.

[Littl] D. E. Littlewood, The theory of group characters, 2^{nd} edition, Oxford University Press, 1950.

[McL] T. McLarnan, Tableau recurrences and symmetric Schensted correspondences for ordinary, shifted, and oscillating tableaux, Thesis (UCSD), (1986).

[Oka1] S. Okada, “Wreath products by the symmetric groups and product posets of Young’s lattice”, J. Combin. Theory, Ser. A 55, (1990), 14–32.

[Oka2] S. Okada, “A Robinson-Schensted-type algorithm for SO(2n, C)”, Journal of Algebra 142, (1991), 334– 372.

[Pro] R. A. Proctor, “A Schensted algorithm which models tensor representations of the orthogonal group”, Canad. J. Math. 42, (1990), 28–49.

the electronic journal of combinatorics 3 (2) (1996), #R15 32

[Rob] G. de B. Robinson, “On the representations of the symmetric group”, American Journal of Math. 60, (1938), 745–760.

[Roby] T. W. Roby, Applications and extensions of Fomin’s generalization of the Robinson-Schensted correspondence to differential posets, Thesis (M. I. T.), (1991).

[Sag1] B. E. Sagan, “An analog of Schensted’s algorithm for shifted Young tableaux”, J. Combin. Theory, Ser. A 27, (1979), 10–18.

[Sag2] B. E. Sagan, “The ubiquitous Young tableau”, pp. 262–298 in Invariant theory and tableaux (D. Stanton, ed.), The IMA volumes in mathematics and its applications 19, Springer-Verlag, New York, 1990.

[SaSt] B. E. Sagan and R. P. Stanley, “Robinson-Schensted Algorithms for Skew Tableaux”, J. Combin. Theory, Ser. A 55, (1990), 161–193.

[Sche] C. Schensted, “Longest increasing and decreasing subsequences”, Canadian Journal of Math. 13, (1961), 179–191.

[Schü1] M. P. Schützenberger, “Quelques remarques sur une construction de Schensted”, Math. Scandinavica 12,

(1963), 117–128. [Schü2] M. P. Schützenberger, “Promotion des morphismes d’ensembles ordonnés”, Discrete Mathematics 2,

(1972), 73–94. [Schü3] M. P. Schützenberger, “La correspondence de Robinson”, pp. 59–113 in Combinatoire et Représentation

du Groupe Symétrique (D. Foata, ed.), Lecture Notes in Mathematics 579, 1976. [Schü4] M. P. Schützenberger, “Evacuations”, pp. 257–264 in Coll. Int. sulla Teorie Combinatorie, Tomo 1, Acad.

Nazion. dei Lincei, Roma, 1976.

[Shim] M. Shimozono, Littlewood-Richardson rules for ordinary and projective representations of symmetric groups, Thesis (UCSD), (1991).

[Stan1] R. P. Stanley, “Some aspects of groups acting on finite posets”, J. Combin. Theory, Ser. A 32, (1982), 132–161.

[Stan2] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986.

[Stan3] R. P. Stanley, “Differential posets”, Journal of the Am. Math. Soc. 1, (1988), 919–961.

[StWhi] D. W. Stanton and D. E. White, “A Schensted algorithm for rim hook tableaux”, J. Combin. Theory, Ser. A 40, (1985), 211–247.

[Stb] R. Steinberg, “An Occurrence of the Robinson-Schensted Correspondence”, Journal of Algebra 113, (1988), 523–528.

[Stem] J. R. Stembridge, “Rational tableaux and the tensor algebra of 𝔤𝔩_{n}”, J. Combin. Theory, Ser. A 46, (1987), 79–120.

[Sund1] S. Sundaram, On the combinatorics of representations of Sp(2n, C), Thesis (M. I. T.), (1986).

[Sund2] S. Sundaram, “Orthogonal tableaux and an insertion algorithm for SO(2n + 1)”, J. Combin. Theory, Ser. A 53, (1990), 239–256.

[Ter] I. Terada, A Robinson-Schensted-type correspondence for a dual pair on spinors, to appear in J. Combin. Theory, Ser. A.

[Thom1] G. P. Thomas, “On a construction of Schützenberger”, Discrete Mathematics 17, (1977), 107–118.

[Thom2] G. P. Thomas, “On Schensted’s construction and the multiplication of Schur functions”, J. Combin. Theory, Ser. A 32, (1982), 132–161.

[Vien] G. Viennot, “Une forme géométrique de la correspondance de Robinson-Schensted”, pp. 29–68 in Combinatoire et Représentation du Groupe Symétrique (D. Foata, ed.), Lecture Notes in Mathematics 579, 1976.

[Vog] D. Vogan, “A generalised τ-invariant for the primitive spectrum of a semisimple Lie-Algebra”, Mathematische Annalen 242, (1979), 209–224.

[Whi] D. White, “Some connections between the Littlewood-Richardson rule and the construction of Schensted”, J. Combin. Theory, Ser. A 30, (1981), 237–247.

[Zel] A. V. Zelevinsky, “A Generalisation of the Littlewood-Richardson Rule and the Robinson-Schensted-Knuth Correspondence”, Journal of Algebra 69, (1981), 82–94.