ROBINSON-SCHENSTED ALGORITHMS FOR SKEW TABLEAUX                                         by                                                          Bruce E. Sagan                                                Department of Mathematics                                         Michigan State University                                        East Lansing, MI 48824-1027                                                   and                                                      Richard P. Stanley                                              Department of Mathematics                                   Massachusetts Institute of Technology                                      Cambridge, MA 02139                       Keywords:  skew Young tableaux, Robinson-Schensted algorithm,            skew Schur functionAMS Subject Classification (1980):  05A15, 05A17, 68C05  Research supported in part by a Michigan State  All  Universtity Research Initiation Grant.   Research supported in part by a grant from the National Science Foundation                          \Proposed running head:                     SKEW SCHENSTED ALGORITHMS                    Send proofs to:                          Bruce E. Sagan                                               Department of Mathematics                                         Michigan State University                                        East Lansing, MI 48824-1027                                                ABSTRACT                                  We introduce several  analogs   of   the   Robinson-Schensted algorithm for skew Young tableaux.  These correspondences  provide combinatorial proofs of various  identities  involving  f   ,  the number of standard skew tableaux of shape l/m, and the skew  Schur functions s   (x).  For example we are able  to  show  bijectively that            f      q t /n! =              (1-q )and       s   (x)s   (y) =   s   (x)s   (y)   (1-x y )  .     It is then shown that these new algorithms enjoy some of  the same properties as  the  original.   In  particular  it  is  still true that replacing a permutation by its inverse exchanges the two output tableaux.  This fact permits us to derive a number of other identities as well.                 1.__INTRODUCTION_AND_DEFINITIONS                       The last few years have seen a  veritable  explosion  in  the production of various analogs of the Robinson-Schensted algorithm[Rob,Sch].  After Knuth's generalization to semistandard  tableaux [Knu] came  versions  for  rim  hook  tableaux  [SW],  oscillating tableaux [Ber,Sun,Pro], shifted tableaux  [Sag,Wor],  and  various others  [Tho,McL].   In  this  paper  we  present   several   new correspondences that apply to skew shapes.  They permit us to give combinatorial  derivations  of  a  plethora  of  identities   that heretofore had only algebraic proofs.  In particular we  are  able to bijectively  explain  formulae  originally  proved  by  Towber, Lascoux, Macdonald and  Zelivinsky  [Mac]  (using  the  theory  of symmetric functions) and by Stanley [Sta2] (using linear operators on partially ordered sets).     We assume familiarity  in  general  with  the   language   of tableaux  and  symmetric  functions  (see,  e.g.,  [Mac])  and  in particular with the Robinson-Schensted algorithm as  presented  in [Sch].  Any definitions not given below can be found in these  two sources.     We will let l = (l , ..., l ) stand for both a partition  and the corresponding Ferrers diagram displayed in "English"  notation with the longest part, l , in  the  top  row  and  no  zero  parts allowed.  The conjugate of l is the partition l' = (l',  ...,  l') where l' is the length of the j   column of l.  The  node  of  the diagram in row i and column j will be denoted v = (i,j) so v  e  l iff 1 < j < l .  If m c l then the corresponding skew shape l/m is the set {v |v e l, v m m}.  If |l/m| = n then we write l/m 9 n and say that l/m is a (skew) partition of n.     A Young tableau P of shape l/m is a labeling of the nodes  of l/m with an ordered alphabet so that  the  rows  and  columns  are weakly increasing.  The reader may assume that our  alphabet  will be the positive integers until stated otherwise.  The element of P labeling node v = (i,j) is denoted p  or p   so that k e P   means k = p   for some i,j.  A Young tableau is partial if its  elements are distinct, standard if it is partial  and  the  labels  are   1  through n  =  |l/m|,  and  generalized  if  the  columns  strictly increase.  For example, when l = (5,4,1) and m  =  (3,2)  possible tableaux of each of the three types are           P = p p 2 7   , p p 1 4   , and p p 2 2    .           The sets of partial, standard and generalized tableaux  of  shape l/m will be denoted PT(l/m), ST(l/m)  and  GT(l/m)  respectively.  Also let f    = | ST(l/m) | with the corresponding Schur  function in the infinite set of variables x = {x , x , ...} being given  by s   (x) =       x 1    x 2    ...  where n (P) is  the  number  of elements equal to k in P.     A biword, p, is a sequence  of  vertical  pairs  of  positive integers  p =             with i <i < ... <i .  We denote the  top and bottom lines of p by p = i  i  ... i  and p = j   j   ...  j .  The three types of biwords  that  we  will  consider  are  partial permutations of n where in each line the elements are distinct and of size at most n, permutations of n which are partial permutations with top line 1 2 ... n,  and  n  by  n  matrix  words  where  all elements are at most n with the pairs arranged  lexicographically: i  = i    implies j  < j   .  Examples of these  definitions  when n = 5 are           p =       ,           , and                  .          Note that there is a bijective correspondence between matrix words and n by n matrices M = (m  ) with non-negative  integral  entries where m   is the number of times the pair       appears in p.  The matrix corresponding to the matrix word above is                         M =   0 0 0 0 0 0                         The sets of partial permutations, permutations and n by n matrix words will be denoted PS , S , and  MAT   respectively.     In the next section, we present the  skew  Robinson-Schensted algorithm in its simplest form.  Next we  investigate  the  effect that inverting the partial permutation has on the output tableaux.  In Sections 4 and 5 we present two  different  generalizations  of the basic correspondence: one obtained by iteration and the  other by  using  tableaux  of  different  shapes.   Section  6   extends everything in the first five sections to tableaux and  words with repetitions; it contains the most general formulae  yet  presented (Corollaries  6.2,  6.5  and  6.12)  from  which   all   previous identities can be derived.  The skew dual and  skew  shifted  maps appear in the next two  sections.   Finally  we  close  with  some comments and open questions.                   2.__THE_FUNDAMENTAL_ALGORITHM                       The heart of any Robinson-Schensted algorithm is the  process of insertion.  For skew  tableaux  there  are  two  types  of  row insertion: external and internal.     External insertion is very  much  like  Schensted's  original procedure.  Initially one has a Young tableau P of shape l/m and an element m to be added to P.  To start, m replaces the smallest p   such that p   > m; in the case where m > p    for  all  j,  it  is placed at the row's right end.  If a p   was displaced  from   the first row then it is inserted into the second using the same rules as above.  This process continues until some element comes to rest at the end of a row.  The only need for caution in the  skew  case is when something is to be inserted into  row  i  which  is  empty (this can only happen at the begining or the end of an insertion).  If this happens, we must have l  = m  and we put  the  element  in cell (i,l +1).  If external row insertion of m into P yields P' we will write R (P)=P'.  For example the reader can verify that                                             .                         With internal row insertion, no new element is added  to  the tableau P.  Instead we start with an inner corner of the shape l/m of P: a cell (i,j) with (i,j) e l/m but (i-1,j),(i,j-1) m l/m.  To start the process p   is removed from row i  and  inserted,  using the usual rules, into row i + 1.  The insertion then continues  in a normal fashion, ending with an element settling at  the  end  of some row.  The internal row insertion operator  will  be  denoted R   .  This should cause no confusion with the  external  notation as the latter  has only a single subscript.  Note,  however,  that in the external case the subscript is the  element  while  in  the internal one we use the coordinates.  If we wish to hedge our bets as to which operator is being used we will merely write R.  As an example, we have                    R               =         .                        The original Robinson-Schensted algorithm gave a proof of the formula                               f  = n!                      (2.1) using a bijection p JL (P,Q) where p e S   and  P,Q  e  ST(l).  Using external and internal insertion we can give a skew analog of this correspondence and derive an equation similar to  (2.1).   In the sequel u denotes disjoint union.     Theorem_2.1.  Let n be a fixed positive integer and a a fixed partition (not necessarily of n).  Then there is a map                         (p,T,U) JL (P,Q)                         defined below which  is  a  bijection  between  p  e  PS   with T,U e PT(a/m) such that p u T = p u U = {1,2,...,n} on the one hand and P,Q e ST(l/a) such that l/a 9 n on the other.     Proof.  First, given (p,T,U) we construct (P,Q)  as  follows.  Let (P ,Q ) = (T,o ) where o  is the unique empty tableau of shape a/a, i.e., Q  is just the  Ferrers  diagram  for  a.   Iteratively construct (P ,Q ) for k = 1, 2, ..., n as  follows.   At  the  k   step, determine whether k e p or k e U.     In the former case, let m be the corresponding element  of  p and set P  = R (P   ).  In the latter, suppose  k  =  u  ,  whence (i,j) must be an inner corner of P    (all elements above  and  to the left have been removed by previous insertions).  Thus  we  can put P  = R   (P   ).  In either case Q  = Q    with  k  placed  in the cell where the corresponding  insertion  terminates.   Finally let (P,Q) = (P ,Q ).  An example of this procedure  can  be  found following the proof.     It is easy to see that at all times P   and  Q   are  partial Young tableaux with the shape of Q  being the same as the shape of the portion of P  outside of a.  Since after the n   step we  have removed all the elements inside a, it follows that P,Q e  SYT(l/a) for some l with l/a 9 n.     To show that this  map  is  a  bijection,  we  construct  its inverse.  The deletion process is exactly like that for the normalRobinson-Schensted algorithm except that at some point the element removed from row i+1 may be smaller than every element in  row  i.  In this case the deletion terminates by placing the element at the left end of the i   row  since  the  corresponding  insertion  was internal.     It should now be clear how  the  inverse  works:  start  with (P ,Q ) = (P,Q) and p = o.  To  obtain  (P ,Q )  from  (P   ,Q   ) locate the cell of k+1 in Q   ; say it's (i,j).  Then P  is  P    with its (i,j) entry removed by deletion and Q  is Q    with its(i,j) entry erased.  If the deletion was external then          is added to the left end of p, where m is the  element  removed  from the first row of P   , otherwise p stays the same.  P     As an example of this construction let n = 5,  a  =  (2,2,1), p =       , T = p 5 , and U = p 3 .  The  following  list  of  the pairs (P ,Q ) is in order of increasing k from left to right.     P :      ,       ,       ,       ,         ,         = P                                                                 (2.2)     Q :      ,       ,       ,       ,         ,         = Q          The analog of equation (2.1) can now be read off from Theorem 2.1.     Corollary_2.2.  Let n be a fixed positive integer and a be  a fixed partition.  Then                  f    =         k!    f    .  P                   Of course both Theorem 2.1 and Corollary 2.2  reduce  to  the original Robinson-Schensted results if a = o.               3._INVERTING_PERMUTATIONS_AND_TABLEAUX                   One of the many beautiful properties of Robinson-Schensted is that if  p JL (P,Q) then p   JL (Q,P).  Thus if p is an involution we have p = p   and  so  p  JL  (P,P)  JL  P.   The  corresponding identity is                             f  = Inv(n)                    (3.1) where Inv(n) is the number of  involutions  in  S .   The  skew algorithm introduced above enjoys similar properties, but first we must set up some additional definitions and notation.     The inverse of any biword p is constructed  by  interchanging the two lines and then lexicographically ordering the  pairs  with the new top line taking precedence.  If we compute the inverse  of the three example permutations of Section 1 in turn, we get          p   =       ,           , and                 .         Note that taking  the  inverse  of  a  matrix  word  is  the  same operation as taking the transpose of the corresponding matrix.     We will derive  our  result  about  inverse  words  from  the original theorem about inverse permutations.  In order to do so we will have to simulate skew insertion with  its  parent  algorithm.  To this end, introduce a new alphabet for tableaux:  {1    < 1    < 1    <...< 2    < 2    < 2    <...< 1 < 2 <...}  where the numbers j    will be used to fill up the  cells  of  the j   column of m in a tableau P of  shape  l/m.   The  result  will still be a Young tableau because only positive integers occur in P and these are greater than every new element of the alphabet.   In particular, let a, l, and m  be  partitions  with  both  a  and  l containing m.  Define a map [.]  : PT(a/m)  L  PT(a) taking P with entries > 1 and returning [P]  which agrees with P in the cells of a/m and has entries j  j , j  j   ,  ...,  j  j  j     reading  up the j   column of m (recall that the prime  denotes  conjugation).  If l = m then we simply write [P] for [P] .  For example, if   P =  p   p   2   7        then [P] =  1    2    2    7     .   while if l = (4, 3, 1) so that l' = (3, 2, 2, 1) then we have                   [P]  =  1    2    2    7                            We now define  a  bracketing  operation  on  the  triples  of Theorem 2.1 as follows.  We will denote the image  of  (p,T,U)  by [p,T,U] or more succinctly by [p] if  no  confusion  will  result.  [p] will be a biword with entries in the extended alphabet above.  The top line of this "permutation" will be  [p] = 1    1    ... 1  1  2    2    ... 2  2  ... 1 2 3 ... n.    To determine the element t e [p] paired with s e [p] there are three cases.     (i).  If s = j    then let t be the entry of [T]  which is in column j and b   from the bottom, i.e., the initial portion of [p] is the so-called column word of [T] .     (ii).  If s e p then let t be the corresponding element of  p so that pairs       e p are transferred to [p] unchanged.     (iii).  If s e  U,  say  s  is  in  column  j  and  b    from the bottom, then let t = j   .     To illustrate  this  somewhat  lengthy  definition,  one  can verify that for the triple (p,T,U) =           ,  p  5  ,  p  3    introduced after Theorem 2.1 we have   [p] =       [3]  [2]       [2]          [1]      [1] .   (3.2)      Note:  It will be useful for future reference to observe that for any j and b the  elements  j   ,  j     ,  ...,  j     form  a decreasing subsequence of [p].     The important property of the bracket operation  is  that  it commutes with the versions of Robinson-Schensted at our disposal.     Lemmma_3.1.  With the  same  notation  as  Theorem  2.1,  the following diagram commutes                                                                  where the top and bottom bijections  are  the  skew  and  ordinary Robinson-Schensted maps respectively.     Proof.  Let (P ,Q ).  ...,  (P ,Q )  be  the  tableaux  pairs constructed by applying skew Robinson-Schensted to (p,T,U).   Also let (P',Q'), ..., (P',Q'), where r = n + |a|, be the corresponding pairs for non-skew Robinson-Schensted applied to  p'  =  [p].   We must show that P' = [P ] and Q' = [Q ].  In fact we will show that for k = 0 to n we have P'     = [P ]  and similarly for  Q.   This will complete the proof because when k = n we have P  of shape l/a so that [P ] = [P ]  = P'     = P'.     The proof will proceed by induction on k.  When k = 0 we have inserted the first |a| elements of [p].  But by definition this is just the column word of [T]  where T = P ; hence P'   =  [P ]   as desired.  Also these elements enter column by column, each  column being filled by the corresponding entries of [p], so we also  have Q'   = [Q ]  where Q  is the empty skew tableau of shape a/a.     To show that the equations are  still  valid  after  the  k   step, we must consider whether k e p or k e U.  If k e p then  the pair       must appear in both p and [p].  Thus the skew insertion R (P   ) is external and hence exactly like ordinary insertion  of m into P'       (elements of the form j    will not  be  disturbed because m is positive).  It follows that k will be added to both Q tableaux in the same place so the induction holds in this case.     Now if k e U, say k = u  , then in [p] we have m = j    .  By induction and the note after the definition of [p] we see that the insertion of m into P'       will just push down  the  j    column until the first positive entry is displaced, which must be the one in row i by definition.  From this point on, the insertion process is exactly like the internal insertion R   (P   ) which  completes the proof of the induction step.  P     To continue our running example, consider again the triple (p,T,U)  =              ,  p  5  ,  p  3    .    Applying   normal Robinson-Schensted to [p] as computed in (3.2) we obtain  (P',Q'):  |   ,      | , | 1    , 1    | , | 1    , 1    | ,  | 1      , 1         | , | 1    5    , 1    2    | ,  | 1    5      , 1    2      | , | 1    4      , 1    2      | ,  | 1    2     , 1    2      |, | 1    2        , 1    2         |,          | 1    2          , 1    2          |                   Comparing these pairs from (P',Q') on with those computed in (2.2) illustrates the proof of Lemma 3.1.     We now must show  that  [.]  behaves  well  with  respect  to inversion of biwords and interchange of tableaux.     Lemma_3.2.  [p,T,U]   = [p  ,U,T].     Proof.  We must show that       e [p,T,U] if and only  if  we have       e [p  ,U,T].  Actually it suffices to  prove  only  the forward implication  since  both  sets  of  pairs  have  the  same cardinality.  In what follows (i), (ii) and (iii) refer  to  those parts of the definition of the bracket of a triple.     Consider first the case where s =  j     so  that  t  is  the element b   from the bottom in [T]  by (i).  If t is in  T  itself then t is a member of the second tableau of the triple (p,U,T) and by (iii),    [b]   appears in its bracket.  If t m T then t is  in cell (i,j) e m and we must have t = j    for some c.  Now becausei = a' - b + 1 = m' - (a' - c) we have                       b + c = 2a' - m' + 1.                (3.3) Also (i,j) m m iff a' - m' + 1 < b < a' which  is  equivalent,  by (3.3), to a' - m' + 1  <  c  <  a'.   Since  both  (3.3)  and  the accompanying boundary conditions are symmetric in b and c,    [b] will be in [p  ,U,T].     Now suppose s is a positive integer.  If t is  also  then  bythe definition of inverse       e p iff       e p    and  this  is also true of the bracket by (ii).  It t = j    then          is in [p  ,U,T] by an argument similar to that of the first  case  above with the roles of s and t reversed.  P     Combining the two lemmas we have  the  main  result  of  this section.     Theorem_3.3.  If (p,T,U) JL (P,Q) by skew  Robinson-Schensted then (p  ,U,T) JL (Q,P).     Proof.  This follows immediately from Lemmas 3.1 and 3.2  and the   fact   that   the   theorem   holds   for    the    ordinary Robinson-Schensted map.  P     Now suppose that p  is  an  involution,  i.e.,  p  =  p    as biwords.   By  the  preceeding  theorem  we  have  a  sequence  of bijections                  (p,T) JL (p,T,T) JL (P,P) JL P                  where the middle map is skew Robinson-Schensted.  We have proved:     Corollary_3.4.   If  p  is  an  involution  then  the   above composition of maps gives a bijection                            (p,T) JL P                            between p e PS  with T e PT(a/m) such that p u T =  {1,2,...,n} on the one hand and P e ST(l/a) such that l/a 9 n on the other.  P     Corollary_3.5.  Let n be a fixed positive integer and a be  a fixed partition.  Then                  f    =         Inv(k)    f    .  P                 A theorem of Schttzenberger [Sct2] states that  if  p  is  an involution and p JL P by normal Robinson-Schensted then the number of fixed points of p equals the number of  columns  of  P  of  odd length.  This fact generalizes to the skew case, but first we will introduce some notation.     If p is a biword let fix(p) be the number of fixed points  of p, i.e., the number of pairs       in p.  If l is a partition then we will denote the number of odd columns of l by  odd(l).   If  we have odd(l) = 0 then we say l' is even, meaning all of  the  parts of l' are even.     Corollary_3.6.  In the bijection of Corollary 3.4  we  always have                     fix(p) + odd(m) = odd(l).                    In particular, we still have a bijection when we restrict  to  the case where p is a fixed point free involution and m', l' are  both even.     Proof.  Let [p] = [p,T,T], then fix([p]) = fix(p)  +  odd(m) where the first summand takes care of all the pairs        in  [p] and the second counts fixed points of the form     [k]   .   Since the   shape   of   the   image   of   [p]   under   the   original Robinson-Schensted map is the same as the outer shape  of  P,  the theorem follows from Schttzenberger's result.  P     The equations arising from Corollary 3.6 are  best  described in terms of generating functions.  Let a be fixed and define               F (z,t) =       f    z         t /n!               and                F (z,t) =       f    z         t /n!              Also count involutions using                 Inv(z,t) =       z         t /n!                 where the sum is over all involutions p e S .   Thus  Corollary 3.5 merely states that F (1,t) = Inv(1,t) F (1,t) while  Corollary 3.6 translates as:     Corollary_3.7.  If a is  a  fixed  partition  then  with  the notation above F (z,t) = Inv(z,t) F (z,t).  In particular if n  is a fixed integer                   f    =          (2k-1)!!    f    .             where (2k-1)!! = 1W3W5 WWW (2k-1).  P                      4.__ITERATED_SKEW_MAPS                           Some of the formulae in this  and  subsequent  sections  were first derived by one of  us  [Sta2]  to  count  chains  in  Young's lattice (the lattice of partitions ordered by  containment).   The techniques used there were algebraic  and  one  of  the  principal motivations of the present work was to find  bijective  proofs  of these results.   In  all  future  identities,  sums  (respectively products) will  always  be  over  the  non-negative  (respectively positive) integers unless otherwise indicated.     One of the formulae which Stanley had demonstrated was            f      q t /n! =  e                 (1-q )       (4.1)which is reminiscent of Corollary 3.5, i.e., it was hoped  that  a Robinson-Schensted algorithm could be found that when  applied  to involutions would yield (4.1).  This lead Sagan to wonder what the corresponding identity would be for the same algorithm applied  to an arbitrary permutation and,  based  on  numerical  evidence,  he conjectured that            f      q t /n! =              (1-q )   .         (4.2)     To  prove  (4.2)  combinatorially  we  must  see   what   the coefficient of t /n! counts on  each  side.   In  both  cases  the objects enumerated will be weighted by a power of q.  On the  left we clearly have pairs (P,Q) with P,Q e SYT(l/m) with the weight of a pair being wt(P,Q) = q   .     The right side counts pairs (p,n) consisting of a permutation and a partition both given weights as follows.  From  the  product we see that wt(n) = q   .  The fraction in t permits each pair     in p to have weight q  for any non-negative integer k, giving  p itself total weight wt(p) =   wt      where the product  is  over all pairs in p.  To denote the fact that wt       =  q   we  will write the pair as    (k)  where the symbol (k) is omitted if  k  = 0.  So, for example, if                   p =  (4)  (2)      (7)  (2)                    then wt(p) = q  q  q  q  q  = q  .  Finally wt(p,n) = wt(p)  wt(n) so that with p as above and n = (4,3,1) 9 8 we have wt(p,n) = q  .     With these preliminaries we can provide a bijection to  prove (4.1) and (4.2) by iterating the skew  Robinson-Schensted  map  of Section 2.     Suppose (p,n) is given.  Let m be the  maximum  weight  of  a pair       e p.  We will construct a sequence  of  tableaux  pairs (P .Q ), 0 < k < m + 1, and let (P,Q) = (P   ,Q   ).     Initially (P ,Q ) = (o ,o ) both tableaux being empty Ferrers diagrams for n.  To construct the next pair after (P ,Q ), let  p  be the partial permutation consisting of all the pairs  of  weight m - k in p.  Now  apply  skew  Robinson-Schensted  to  the  triple (p ,P ,Q ) to obtain (P   ,Q   ).  Note that the elements of p get inserted in order of decreasing weight.     To see that the map is well defined, note first of  all  that since p e S  the final tableaux are certainly standard  with  n entries.  What about  the  weights?   We  start  with  a  pair  of tableaux of weight wt(n).  When an element of weight k is inserted externally from p it is at step m - k.  Thus this element will be internally inserted in the remaining k steps and so add exactly  k empty cells to n while  forming  m.   Hence  at  the  end  of  the procedure we have wt(P,Q) = wt(m) = wt(p) wt(n).     The   construction   of   the   inverse   correspondence   is straightforward and is left to the reader.  We have proved:     Theorem_4.1.  The map above is a weight preserving bijection                           (p,n) JL (P,Q)                          between pairs p e S  with n a partition and pairs P,Q e ST(l/m) where l/m 9 n.  P    By way of illustration, let p  =   (3)       (1)  (1)    and also n =     , then the  steps  of  the  above  algorithm  are  as follows:                   ,     ,       L         ,                                     o ,       ,         L         ,                                    ,       ,         L   p p p 4 , p p p 4            |     , p p p 4 , p p p 4 | L |           ,           | = (P,Q).      As advertised, this bijection gives us a combinatorial  proof of equation (4.2).     Corollary_4.2.               f      q t /n! =              (1-q )   .  P             It is an easy matter to see how  to  extend  our  results  on inverses of permutations to this setting.  If p is  weighted  then p   is the weighted permutation defined by    (k)  e p if and only if    (k)  e p  .  Of course p is an involution whenever p =  p  .  The following five corollaries now follow  immediately  from  the last five results  of  Section  3  and  the  fact  that  our  new algorithm is merely an iteration of the old one.     Corollary_4.3.   If  (p,n)  JL   (P,Q)   by   iterated   skew Robinson-Schensted then (p  ,n) JL (Q,P).  P     Corollary_4.4.  If p  is  a  weighted  involution,  then  the mapping of Theorem 4.1 restricts to a weight preserving bijection                            (p,n) JL P                            between p e S  with n a partition and P e ST(l/m) with l/m 9 n.  P     Corollary_4.5.               f      q t /n! =  e                 (1-q )  .  P          Corollary_4.6.  In the bijection of Corollary 4.4  we  always have               fix(p) + 2 odd(n) = odd(m) + odd(l).               In particular, we still have a bijection when we restrict  to  the case where p is a weighted fixed point free involution and  n',m', and l' are all even.  P     Corollary_4.7.            f    z                 q t /n!           =  e                   (1-z q    )(1-q  )     .         In particular if n is fixed                 f   q    =              (1-q  )  .  P                                5.__ANOTHER_GENERALIZATION                         In the skew Robinson-Schensted bijection of Section 2  it  is not necessary for both tableaux to have exactly  the  same  shape.  Note how the r[les of the partitions a and  b  change  in  passing from T,U to P,Q in the following theorem.     Theorem_5.1.  Let n and m be fixed integers and let a  and  b be fixed partitions (it is not necessary to have |a| = |b|).  Then the map                         (p,T,U) JL (P,Q)                         defined below is a bijection between partial permutations p with T e PT(a/m), U e PT(b/m) such that p u T = {1,2,...,n}, p  u  U  = {1,2,...,m} on the one hand and P e ST(l/b), Q e ST(l/a) such that l/b 9 n, l/a 9 m on the other.     Proof.  We will construct pairs (P ,Q ) for k = 0, 1, ...,  m starting with (P ,Q ) = (T,o ).  As before, at the k   step we see whether k e p or k e U.  If k e p or k = u    where  (i,j)  is  in P    then we proceed as in the original skew algorithm.     The only other possibility is that there  is  no  element  of P    in cell (i,j).  In this case  P   is  just  P     with  (i,j) adjoined but empty while Q   has  the  element  k  placed  in  the corresponding square.  It is easy to verify by induction that  the results will always be skew tableaux.     By the time we reach (P,Q) = (P ,Q ), the elements of U  will have forced us to empty every square of  P  inside  b  (either  by internal insertion or by addition of empty squares).  Thus P  will be of shape l/b for some l.  Also the Q's are formed  by  starting with the blank shape a and placing entries  so  that  the  "outer" shapes of P  and Q  always agree.  It follows that Q e ST(l/a)  as desired.     As usual, the construction of the inverse map will be left as an exercise.  P     Consider n = 4, m = 3, m = (2,1), a = (5,1), b =  (3,1),  and (p,T,U) =     ,            ,        .  Our construction yields       P :  p         , p p       ,p p 3     , p p 1     = P            Q :  p         , p 1       , p 1 2     , p 1 2     = Q.          The corresponding identity is     Corollary_5.2.  Let n, m be fixed integers  and  a,  b  fixed partitions.  Then              f   f    =               k!     f   f   .  P             It should also be noted that Theorem 3.3 continues to hold in this  setting,  although  "restriction  to  the  diagonal"  yields nothing new since T = U forces a = b.     As an application of the ideas of this section we  note  that Corollary 5.2 can be used to obtain a special case of a result of Stanley's  [Sta2, Theorem 3.7]    which    interpolates    between equations (2.1) and (3.1).     Corollary_5.3.  Let n and m be fixed integers.  Then                      f f    =       m! Inv(n-m).                      Proof.  In Corollary 5.2 let b = o and sum over all a.   This clearly gives the left hand side of 5.3.  On the  right  the  only surviving term is when m = o.  Hence k =  m  and  the  right  side reduces to                      m!     f  =       m! Inv(n-m)               by equation (3.1).  P     The extremal cases  m  =  n  and  m  =  0  of  Corollary  5.3 correspond to equations (2.1) and (3.1) respectively.     Zelevinsky  [private  communication]  noticed  the  following character-theoretic interpretation of Corollary 5.3.   Let  c   be the a   irreducible character of the corresponding symmetric group and consider c =    c .   Thus  the  induced  character  cIS   has dimension  equal  to  the  right  hand  side  of  the   corollary.  Decomposition into irreducibles yields cIS  =   m  c  where9              m  = <cIS ,c > = <c,c <S   > =     f                by Frobenius receprocity and the branching rule for the  symmetric group.  The equality of Corollary 5.3 follows.                 6.__THE_SKEW_KNUTH_CORRESPONDENCE                     Just as Knuth [Knu] was able to extend Robinson-Schensted  to tableaux with repetitions , we have an analog of Theorem  2.1  for matrix words and generalized tableaux.  Since the objects we  will be dealing with are now multisets (sets  with  repetition)  A,  B, etc., we will define A u B to be the multiset where the number  of repetitions of an element k is the sum of the number of copies  of k in A and B.     Theorem_6.1.  Let a be a fixed partition.  Then the map                         (p,T,U) JL (P,Q)                         defined  below  is  a  bijection  between  matrix  words  p   with T,U e GT(a/m) on the one hand and P,Q e GT(l/a) on the other  such that p u T = P and p u U = Q.     Proof.  Let the largest element of p u U  be  m.   The  pairs (P ,Q ), k = 0, 1, ..., m, are constructed by  starting  as  usual with (T,o ).  To obtain P , internally insert all the elements  of P    corresponding to k's in Q    followed by all the elements  of p paired with k's in p.  In both cases the insertions proceed from left to right.  Placing k's in the  appropriate  squares  of  Q    results in Q .     Note that when  inserting  an  element  in  a  row  it  still displaces the first entry strictly greater than  itself  and  that each insertion during step k begins in a row at least as  high  as the one just previous (if any).   Thus  in  constructing  P   each insertion comes to rest to the right of the preceeding one so that Q  remains a generalized tableaux.  This fact also makes  it  easy to define the inverse since we know we must  begin  deletion  with the square of the rightmost k in Q  and proceed to the left.  P     Example.  Let                  (p,T,U) =         ,     ,      .                 Then the output tableaux are                  (P,Q) = |         ,         |.                       Schur funtions count generalized tableaux, so we  immediately have a generalization of the famous Cauchy identitiy [Mac,p.33]:     Corollary_6.2.  Fix a partition a.  Then         s   (x)s   (y) =   s   (x)s   (y)   (1-x y )  .  P            We will now demonstrate that all of the results  of  sections 3,4 and 5 can be generalized to tableaux and biwords with repeated elements.     It is easy to show by standard techniques that the results of Section 3 all  have  analogs  in  this  setting.   In  particular, Theorem 3.3 holds for the skew Knuth map where p   is  the  biword of the transpose of the corresponding matrix.  Thus:     Corollary_6.3.  If p is a biword corresponding to a symmetric matrix then the mapping of Theorem 6.1 restricts to a bijection                            (p,T) JL P                            where T e GT(a/m) and P e GT(l/a) with a fixed and p u T = P.  P     The resultant identity is     Corollary_6.4.  Let a be a fixed partition.  Then           s   (x) =   s   (x)   (1-x x )     (1-x )  .  P             If M is the matrix corresponding to p in Corollary  6.3  then the trace of M counts fixed points of p and we always have                      tr(M) + odd(m) = odd(l)                     (cf. Corollary 3.6).  It follows that     Corollary_6.5.    s   (x) z       =   s   (x) z         (1-x x )     (1-zx )  . In particular                  s   (x) =   s   (x)   (1-x x )  .  P                 We can also  iterate  the  skew  Knuth  algorithm  to  obtain results about weighted matrices  and  generalized  tableaux.   The weights of partitions and skew tableaux are the  same  as  in  the case with distinct entries.     Now consider all copies of a pair       in a matrix  word  p.  Clearly the order in which these copies are weighted is immaterial since  only  the  weights  themselves  determine  when   otherwise identical elements are to be inserted.  So we make the  convention that among all pairs for fixed i,j the weights will be  listed  in weakly decreasing order.  This corresponds to  a  matrix  M  where each entry m   has been weighted by a partition l with at most m   parts, denoted M = (m  ).  For example the matrix word         p =    (2)  (2)  (1)            (3)  (3)                 corresponds to the matrix                     M =                     .                         The next theorem is proved in exactly the  same   manner   as Theorem 4.1.     Theorem_6.6.  The iteration of the  mapping  of  Theorem  6.1 produces a weight preserving bijection                          (p,n) JL (P,Q)                          between weighted matrix words p with a partition n on the one hand and pairs P,Q e GT(l/m) on the other where p = P  and  p  =  Q  as multisets.  P     Corollary_6.7.               s   (x)s   (y)   q  =                         .           Proof.  Clearly the left hand side of  this  equation  counts the pairs (P,Q) of weight k in Theorem 6.6.  The number of ways to weight a matrix entry m   with a partition of at most m   parts is           (x y ) /(1-q)(1-q )...(1-q ) =   (1-x y q   )          by a well-known identity of Euler [And, p. 19, Corollary 2.2].  P     Note that Corollary 6.7 is the special case of Theorem 5.1 of [Sta1] obtained by taking v =  (q,0,0,...)  and  replacing  x   by x /q.  We can also rederive Corollary 4.2 from 6.7 by  taking  the coefficient of x x ...x y y ...y  on  both  sides.     In fact 6.7 itself is a simple consequence of  Corollary  6.2 derived as follows.  Let L(x,y,q) and R(x,y,q) denote the left and right hand sides of 6.7 respectively.  Clearly R(x,y,q) is defined by the recurrence                R(q  x,y,q) = R(x,y,q)   (1-x y )                 together with the initial condition                      R(0,y,q) =   (1-q )  .                      One can now use 6.2 to  show  that  L(x,y,q)  satisfies  the  same recursion and boundary conditions thus proving that  L(x,y,q)  and R(x,y,q) are equal as desired.     Transposing weighted matrices presents no surprises.  If p is the word of the weighted matrix M = (m  ) then p   is the word of M  = (m  ) and we get:     Theorem_6.8.  If (p,n) JL (P,Q) is the  iterated  skew  Knuth map then (p  ,n) JL (Q,P).  Furthermore if the matrix M  of  p  is symmetric,  i.e.,  m    =  m  ,  then  restriction  of  the  above correspondence gives  a weight  preserving bijection                             (p,n) JL P                            with p = P as multisets.  P     Corollary_6.9.         s   (x) q  =                                      .  P        Keeping track of fixed points and odd column lengths gives:     Corollary_6.10.     s   (x) z             q            =                                                   .In particular             s   (x) q    =                          .  P              Corollaries 4.5 and 4.7 can be obtained  from  6.9  and  6.10 respectively by equating coefficients of  x x ...x y y ...y .   In their turn, 6.9 and 6.10 can  be  derived  from  6.4  and  6.5  by setting  up  appropriate  recurrences  (cf.  the  comments   after Corollary 6.7).     Finally we can use two different partitions a and b.     Theorem_6.11.  Let a and b be  fixed  partitions.   Then  the skew Knuth correspondence can be extended to a map                         (p,T,U) JL (P,Q)                         which is a bijection between matrix words p such that T e GT(a/m), U e GT(b/m) on the one hand and P e GT(l/b), Q e  GT(l/a)  on  the other with p u T = P and p u U = Q.  P     Corollary_6.12.  Fix partitions a and b.  Then         s   (x)s   (y) =   s   (x)s   (y)   (1-x y )  .  P            As usual, Corollary 5.2 can be reproved by taking square-free terms in 6.12.  It should also be noted that Corollaries 6.2,  6.4 and 6.12 as well as Corollaries 7.2 and 7.6 of  the  next  section were  proved  independently  by  Towber,  Lascoux,  Macdonald  and Zelevinsky using symmetric  function  techniques.   This  approach will appear in the second edition of [Mac].                         7.__THE_SKEW_DUAL                             Knuth [Knu] also discovered a dual to his  generalization  of Robinson-Schensted which mapped 0-1 matrices (m   = 0 or 1 for all i,j) to pairs of tableaux of conjugate shape.  One can do the same thing in the skew case.     Theorem_7.1.  Let a be a fixed partition.  Then  the map                         (p,T,U) J-L (P,Q)                         defined below is a bijection between 0-1 matrix words p such  that T e GT(a/m), U e GT(a'/m') on  the  one  hand  and  P  e  GT(l/a), Q e GT(l'/a') on the other with p u T = P and p u U = Q.     Proof.  We start with (P ,Q ) =  (T ,o  )  where  T   is  the transpose of the tableau T which now has strictly increasing rows.Since P  and Q  have the same shape a', we can proceed  with  the insertion process.  The one difference is that when an  element  m is inserted into a row, it replaces  the  smallest  entry  greater than or equal to m.  This preserves row-strictness of P , while the fact that p comes from a 0-1 matrix ensures  column-strictness  of Q .  If (P ,Q ) is the last pair then let P = P  and Q = Q .  P     Corollary_7.2.  Let the partition a be fixed.  Then        s   (x)s     (y) =   s   (x)s     (y)   (1+x y ).  P           The analogs of the results in Sections 4  and  5  follow  the same pattern as before so we will merely state them here.     Theorem_7.3.   Iteration  of  the  mapping  of  Theorem   7.1 produces a weight preserving bijection                          (p,n) J-L (P.Q)                         between 0-1 matrix words p with a partition n on the one hand andP e GT(l/m), Q e GT(l'/m') on the other such that p = P and p =  Q as multisets.  P     Corollary_7.4.          s   (x)s     (y)   q  =   (1-q )     (1+x y q   ).  P        Theorem_7.5.  Fix partitions  a  and  b.   Then  the  map  of Theorem 7.1 can be extended to a bijection                         (p,T,U) J-L (P,Q)                        between 0-1 matrix words p with T e GT(a/m), U e GT(b'/m') on  the one hand and P e GT(l/b), Q e GT(l'/a') on the other such that  we have p u T = P and p u U = Q.  P     Corollary_7.6.  Let a and b be fixed partitions.  Then        s   (x)s     (y) =   s   (x)s     (y)   (1+x y ).  P                           8.__SKEW_SHIFTED_TABLEAUX                         There is another family of arrays, the shifted tableaux, that exhibit many of the  nice  properties  of  their  "left-justified" cousins.   It  is  therefore  not  surprising  that  skew  shifted tableaux are relatively well behaved.  Below we will  outline  the necessary definitions and notation for this case.   Consult  [Sag] or [Wor] for a more detailed description.     A partition l = (l , ... ,l ) is strict if l  > l  > ... > l .Given a strict partition the corresponding shifted Ferrers diagram l  has row i shifted i-1 spaces to the right.  For example if  we have l = (5,4,2) then                           l  =   p p p p .                       The cells (i,i) e l  are called the diagonal; all other cells  are off-diagonal.  The number of diagonal cells is called  the  length of  l  and  denoted  l(l).   In  the  example  above  l(l)   =   3 corresponding to the diagonal squares (1,1), (2,2) and (3,3).     The definitions of skew shifted shape, as well as partial and standard skew shifted tableau, are the obvious analogs of those in Section 1.  To illustrate, if l is as above and m = (3,2) then one standard tableau of shape l /m  is                         P  =   p p 2 6 .                         As might be expected, the sets of  partial  and  standard  shifted tableaux of shape l /m  will be denoted  PT(l /m )  and  ST(l /m ) respectively.   In  addition  it  is  necessary  to  be  able   to distinguish certain elements of a shifted tableau P .  In previous papers [Sag,Wor] this was done by circling these elements.   Since this is not the most  convenient  convention  typographically,  we will underline numbers which are distinguished, e.g., k.  If we do not wish  to   commit  ourselves  as  to  whether  an  integer  is distinguished or not, we will write  k.   Of  particular  interest will be the  tableaux  where  only  off-diagonal  entries  can  be underlined.  Let PT (l /m ) and ST (l /m ) be  the  sets  of  such tableaux of the partial and standard varieties respectively, e.g., a shifted array P  e ST (l /m ) might look like                         P  =   p p 2 6 .                         Also let g    = |ST(l /m )| so that |ST (l /m )| = 2        gwhere l/m 9 n and l(l/m) = l(l) - l(m).     We must now modify the definitions of the insertion operators R  and R    from Section 2 to apply to a shifted tableau P .  If a diagonal element is never displaced during insertion then the  R's behave  as  before  and  the  insertion  is  called  a   Schensted insertion.  If, at  some  point,  p    is  displaced  then  it  is inserted into the i+1   column  (replacing  the  smallest  element larger than itself if one exists).  The process  continues  column by column until some entry comes to rest at the  lower  end  of  a column.  Since entries are moving  to  the  right  and  up  during column insertion, the diagonal will never  be  intersected  again.  An insertion of this type is called non-Schensted.  For example, a non-Schensted internal insertion might look like                 R       p p 2 6   =    p p 1 5   .               Finally we will wish to consider  internal  insertions  that  only displace entries by columns in P .  Let (i,j) be an  inner  corner of the shape l /m  of P .  C   (P ) will be the  tableau  obtained by removing p   from column j and inserting it in column j+1, etc. until an element comes to rest at the end of some column.  Such an operation will always be  considered  non-Schensted.   By  way  of illustration                 C       p p 2 6   =    p p 2 6   .                    One last bit of terminology before stating the main result of this section.  If A, B are sets of integers  some  of  which  have been underlined, we write A _ B to mean that A and B are the  same up to underlining, e.g., {1,3,4,5,7} _  {1,3,4,5,7}.   We  do  not permit a set A to have both k e A and k e A.  Thus we say A and  B are disjoint if A _ C and B _ D where C and D have  no  underlined elements and C n D =  o.   If  A  and  B  are  disjoint  then  the set A u B is defined as having every element which is in either  A or B with the underlining preserved (the fact that  the  sets  are disjoint makes the underlining of the union well-defined).     Theorem_8.1.  Let n be a fixed positive integer and a a fixed strict partition.  Then the map                       (p,T ,U ) JL (P ,Q )                       defined below is a bijection between p e PS , T   e  PT(a /m ), U  e PT (a /m ) such that p u T  = {1,2,...,n} _ p u U  on the one hand and P  e  ST(l /a ), Q  e ST (l /a ) on the other.     Proof.  We will construct (P ,Q ) = (T ,o *),  (P ,Q ),  ..., (P ,Q ) = (P ,Q ) as  follows.   At  the  k    step  we  determine whether k e p or k e U .     In the former case we have       in p and set P  =  R (P   ).  If the insertion is Schensted then we place k in the corresponding position of Q    to form Q .  However,  if  it  was  non-Schensted then k is put in that position.     Now suppose k e U  appearing, say, in cell (i,j).  If u   = kthen P  = R   (P   ) with Q  formed as before.  If instead u   = kthen P  = C   (P   ) with k being added to form Q .     Note that we will have  k  e  Q   if  and  only  if  the  k   insertion  was  non-Schensted,  i.e.,  step  k  ended  in   column insertion.  This guarantees that Q  has no underlined elements  on the diagonal.  It also  makes  construction  of  the  inverse  map possible by flagging which deletions are to be started by  columns rather than by rows.  P     The following  example  will  illustrate  all  five  possible insertions (Schensted and non-Schensted R  and  R     as  well  as C   ).  Let              (p,T ,U ) =       ,   p 1   ,   p 4    .             Then     (P ,Q ):      p 1   ,   p p     ,     p 1 4 ,   p p 1   ,              p 1 4   ,   p p 1     ,     p 1 3   ,   p p 1     ,          p p 1 3 ,   p p 1 4   ,     p p 1 3 ,   p p 1 4   = (P ,Q ).      Translating the bijection into an equation yields:     Corollary_8.2.   Let  the  positive  integer  n  and   strict partition a be fixed.  Then         2         g    =          k!     2           g   .  P         Composing this map with itself or  using  two  fixed   strict partitions produces the expected results which we  record  in  the next four corollaries.     Corollary_8.3.   Iteration  of  the  bijection  of   Theorem 8.1 produces a weight preserving bijection                         (p,n) JL (P ,Q )                         between weighted p e S  with n a strict partition and pairsP  e ST(l /m ), Q  e ST (l /m ) where l/m 9 n.  P     Corollary_8.4.             2         g      q t /n! =              (1+q ).  P        Corollary_8.5.   Let  positive  integers   n,m   and   strict partitions a, b be fixed.  Then the mapping of Theorem 8.1 can  be extended to a bijection                       (p,T ,U ) JL (P ,Q )                       between partial permutations p, T  e PT(a /m ),  U   e  PT (b /m ) such that p u T  = {1,2,...,n}, p u U  _ {1,2,...,m}  on  the  one hand and P  e ST(l /b ), Q  e ST (l /a ) such that l/b 9 n, l/a 9 m on the other.  P     Corollary_8.6.        2        g   g    =               k!    2          g   g   .  P     Shifted tableaux with repeated entries are  defined  somewhat differently  from  the  column-strict  arrays  of  Section  6.   A generalized shifted tableau of shape l /m  is an array,  P ,  with entries from the alphabet {1 < 1 < 2 < 2 < 3 < 3 < ...} such that     (i)  the rows and columns of P   are  weakly  increasing  (as with any Young tableau),     (ii)  for any k, there is at most one k in  any  row  and  at most one k in any column.For example,                      P  =                 .                           Note that conditions (i) and (ii) imply that the  k's  in  P  will form a union of skew hooks (a collection of cells  containing no diagram of the form     ).  Furthermore the underlining of  all k's in a given hook is completely determined by  (ii)  except  for the lower-leftmost one which can  be  either  underlined  or  not.  Since the elements on  the  diagonal  are  all  lower-leftmost  in their respective rim hooks, they may be underlined  or  not.   Let GT(l /m ) and  GT (l /m )  denote  the  sets  of  all  generalized tableaux and  generalized  tableaux  without  diagonal  underlines respectively.  The  corresponding  generating  functions  are  the Schur  Q-  and  P-functions  (which  are  special  cases  of   the Hall-Littlewood symmetric functions [Mac,p.104 and  ff.])  defined by           Q   (x)   =            x 1     x 2     ...  ,                     P   (x)   =             x 1     x 2     ...  ,          where n (P ) is the number of elements equal to k in P .   In  the example above x 1     x 2     ... = x  x  x  x  x  x .  Because of the relationship between the underlining  permitted  in  GT(l /m ) and GT (l /m ) discussed above we see that these two functions are multiples of each other: Q   (x) = 2       P   (x).     We will also permit underlining in our biwords.  An underlined matrix M is a  non-negative  integral  matrix  with  some  of  its positive entries underlined.  If  m    =  k  in  M   then  in  the corresponding underlined matrix word p, the first occurence of j in the k pairs        is  underlined  while  the  remaining  k-1  are ordinary integers.  To illustrate, let           M = | 2 1 0 | , then p =                   .                We can now describe  the  insertion  process.   Although  the rules may seem strange at first, they are forced on us in order to preserve  conditions  (i)  and  (ii)  in  the  definition   of   a generalized shifted tableau.  The options are as follows:     (a)  if k is being inserted in a row (respectively column) it displaces the smallest element greater than (respectively  greater than or equal to) itself,     (b)  if k is being inserted in a row (respectively column)  it displaces  the  smallest  element  greater  than   or   equal   to (respectively greater than) itself.It is convenient to record these possibilities in a table:                     _____|_______|_________| .                        The operators R , R    and C    are defined by iterating  (a) and  (b)  in  the  obvious  way,  with  two  exceptions.    Before considering the exceptional cases we will compute  the  effect  of applying R  to  the  example  tableau  P   above.   The  resulting tableau is                                          .                            The only modifications of the  above  insertion  rules  occur when a diagonal element is displaced:     (c)  if a k displaces p   = k then the incoming k loses  its underline after being inserted on the diagonal in row i,     (d)  if a k displaces p   = k then the outgoing k loses  its underline before being inserted (off the diagonal) in column i+1.These exceptions are illustrated by         R           =       , and R             =       .        Note that (c) and (d) do not apply to internal  insertions  of  the form R    since there is no incoming k in this case.     Finally everything is in place to prove:     Theorem_8.7.  Let a be a fixed strict  partition.   Then  the map                       (p,T ,U ) JL (P ,Q )                       defined below is a bijection between underlined  matrix  words  p, T  e GT(a /m ), U  e GT (a /m ) on the one hand and P  e GT(l /a ), Q  e GT (l /a ) on the other such that p u T  _ P  and p u U  _ Q  as multisets.     Note.  If A and B are multisets of underlined  integers  then their  disjoint  union  is  the  multiset  where  the  number   of repetitions of each k (respectively k) is the sum of the number of copies of k (respectively k) in A and B.     Proof.  The only thing that has not  been  specified  by  the above discussion is the order of the insertions at the  k    step, i.e., those corresponding to k's in p u U .  First we perform  the internal insertions that involve a k e  U   (all  C   's)  working from top to bottom in U .  Next the R   's corresponding to k's in U  are performed working from left to right.  Last  we  externally insert the elements below a k in p (remember: only k's  appear  in p).  P     It is an unfortunate historical accident of notation that the generating function for the P-tableaux in the above  bijection  is the Schur Q-function and  vice-versa.   However  this  should  not prevent us from writing down the correct identity.     Corollary_8.8.  Fix a strict partition a.  Then      Q   (x)P   (y) =   Q   (x)P   (y)   (1+x y )/(1-x y ).  P        The iterated analog of the shifted Knuth map carries over from the unshifted case mutatis mutandis.  The  only  point  that  might need clarification is the  definition  of  a  weighted  underlined matrix word:  for each i,j,k we permit only the first occurence of    (k)   to have an underlined j, e.g.,         p =    (2)  (2)  (1)            (3)  (3)          .      This ensures that the subword consisting of  all  pairs  of  fixed weight k is an underlined matrix word in the sense of Theorem 8.7.     Corollary_8.9.  Iteration of the map of Theorem 8.7 produces a weight preserving bijection                         (p,n) JL (P ,Q )                         between weighted  underlined  matrix  words  p  with  n  a  strict partition and pairs P  e GT(l /m ), Q  e GT (l /m ) where p _ P  and p _ Q  as multisets.  P     Corollary_8.10.        Q   (x)P   (y)  q  =   (1+q )   (1+x y q   )/(1-x y q   ). P     The two-partition case is disposed of with similar dispatch.     Corollary_8.11.  Let partitions a, b be fixed.  Then the  map of Theorem 8.7 can be extended to a bijection                       (p,T ,U ) JL (P ,Q )                       between underlined matrix words p, T  e GT(a /m ), U  e GT (b /m ) on the one hand and P  e GT(l /b ), Q  e GT (l /a ) on the  other such that p u T  _ P  and p u U  _ Q  as multisets.  P     Corollary_8.12.  Fix strict partitions a and b.  Then      Q   (x)P   (y) =   Q   (x)P   (y)   (1+x y )/(1-x y ).  P                     9.__COMMENTS_AND_OPEN_QUESTIONS                      The  amazingly  rich  structure  of  the  original  Robinson-Schensted algorithm suggests that we have only  begun  to  scratch the surface in the skew case.  Below we  outline  some  directions for future research.     (1)  One of Schensted's original results [Sch] was that when p JL (P,Q) (the case a = o of Theorem 2.1) then the length of  the longest increasing (respectively decreasing) subsequence of  p  is the length of the first row (respectively column) of P.  It is not at all clear what the analogous result is if a/m $  o..   In  fact Schensted proved that if one reverses the order of the elements of p then the P-tableau is  transposed.   A  generalization  of  this result to the skew case would be most welcome.     (2)  Viewing the biword p as an n by n matrix we can let  the dihedral group of the square act on p and ask what happens to  the output tableaux P,Q (with appropriate changes to the  accompanying tableaux T,U or partition n).  Exchanging p for p   or reversing p are special cases.  In fact the complete answer is known  for  the original algorithm for any symmetry of the square [Gan, Sct].     (3)  Two other important tools in tableau theory  whose  skew analogs are missing are  Schttzenberger's  jeu  de  taquin  [Sct1, Sct2] and the Knuth relations [Knu].  The jeu gives an alternative way to define the P-tableau and can be used to demonstrate various symmetric  function  identities  [Wor].    The   Knuth   relations characterize all biwords p which have the same P-tableau and  have been used, among other things, to generalize  Schensted's  theorem about increasing and decreasing subsequences [Gre].     (4)  Note that we did not derive any results about  inverting biwords in the shifted case.  This is because even when a = o  and p JL (P ,Q ) it is not true that inverting p will "interchange" P  and Q  in any reasonable sense of the term.  However Haiman  [Hai] has discovered another process,dubbed mixed insertion and  denoted m, such that p   J-L (Q ,P ).  It is an easy matter to find a skew analog of Haiman's algorithm, but it does not result  in  any  new identities and so has been omitted.     (5)    As   mentioned   in   the   previous   section,    the Hall-Littlewood symmetric functions P   (x;t)  specialize  to  the ordinary Schur functions or Schur P-functions when t is 0  or  -1 respectively.  In fact  one  can  algebraically derive  a  general formula for arbitrary t  that  has  Corollaries  6.2  and  8.8  as special  cases.  It would be interesting  to  obtain  a  Robinson- Schensted  type  proof  in  this   general   setting   using   the combinatorial definition of P   (x;t) given in [Mac, pp. 119-121].     (6)  Stanley [Sta2] was  led  to  identities  like  (4.1)  by counting chains in Young's lattice Y (the  lattice  of  partitions ordered by inclusion).  To see the connection,  merely  note  that f    is just the number of maximal chains from m to l in Y.   What is more, Stanley has shown  that  there  is  a  general  class  of partially ordered sets, called differential posets, where  similar equations hold.  However, the lattice of shifted partitions is not differential (which is not surprising since we have no  analog  of (4.1) in the shifted case).   Nonetheless,  we  can  still  derive identities like  Corollary  8.4  for  counting  pairs  of  maximal chains.  It seems probable that the techniques of  Stanley,  which involve solving certain partial differential equations,  can  also be applied to the shifted case.  Is there another class of  posets where analogous formulae can be proved?     (7)  Butler [But] has used a  different  approach  to  obtain generating functions for chains in Y  that  go  through  specified ranks.  Specifically she q-counts  linear  extensions  of  certain partially ordered sets to obtain her results.  Can the same  thing be done in the shifted lattice or  in  an  arbitrary  differential poset?  This enumeration problem is made harder because, as Butler has noted, the generating functions involved need not be  rational as they are for Y.     (8)  Oscillating tableaux are another family of  arrays  that are important in  combinatorics  and  representation  theory.   In particular there are a number of Robinson-Schensted algorithms for such tableaux [Ber,  McL,  Pro,  Sun]  and  formulae  for  certain oscillating chains in differential posets [Sta2].   This  suggests that a skew oscillating Robinson-Schensted map might be found.     (9)  Rim-hook tableaux appear in  the  determination  of  the ordinary and p-modular characters of the symmetric  group.   White [Whi] and  Stanton  and  White  [SW]  have  obtained  a  Robinson- Schensted correspondence in this case.  Furthermore the  poset  of all partitions with given p-core ordered by  rim-hook  removal  is differential.  These two facts point to the existence of a rim-hook version  of  our  algorithm.   This  matter  is  currently   under investigation by Sagan.                            REFERENCES                            [Ber]  A.  Berele,  A  Schensted-type   correspondence   for   the      symplectic group, J. Combin. Theory Ser. A 43 (1986), 320-328.[But]  L. M. Butler, Rational generating functions for enumerating      chains of partitions, preprint.[Gan]  E. Gansner, "Matrix Correspondences and the Enumeration  of      Plane Partitions," Ph.D. thesis, MIT, 1978.[Gre]  C. Greeene, An extension of Schensted's  theorem,  Adv.  in      Math. 14 (1974), 254-265.[Hai]  M. D. Haiman, On mixed  insertion,  symmetry,  and  shifted      Young tableaux, preprint.[Knu]  D. E. Knuth, Permutations, matrices and  generalized  Young      tableaux, Pacific J. Math. 34 (1970), 709-727.[Mac]   I.   G.   Macdonald,   "Symmetric   Functions   and   Hall      Polynomials," Oxford Univ. Press, Oxford, 1979.[McL]  T. J. McLarnan, "Tableau Recursions and Symmetric Schensted      Correspondences  for  Ordinary,   Shifted   and   Oscillating      Tableaux," Ph.D. thesis, UCSD, 1986.[Pro]  R. A. Proctor, A generalized Berele-Schensted algorithm and      conjectured  Young  tableaux  for   intermediate   symplectic      groups, preprint.[Rob]   G. de B. Robinson, On  representations  of  the  symmetric      group, Amer. J. Math. 60 (1934), 745-760.[Sag]  B. E. Sagan, Shifted tableaux,  Schur  Q-functions,  and  a      conjecture of R. Stanley, J. Combin. Theory Ser. A 45 (1987),      62-103.[Sch]    C.   Schensted,   Longest   increasing   and   decreasing      subsequences, Canad. J. Math. 13 (1961), 179-191.[Sct1]   M.-P.  Schttzenberger,   Quelques   remarques   sur   une      construction de Schensted, Math. Scand. 12 (1963), 117-128.[Sct2]  M.-P. Schttzenberger, La correspondence  de  Robinson,  in      "Combinatoire  et  Rwpresentation   du   Groupe   Symwtrique,      Strasbourg 1979," (D. Foata, ed.),  Lecture  Notes  in  Math.      Vol. 579, pp. 59-113, Springer, Berlin, 1977.[Sta1]  R. P. Stanley,  The stable behavior of some characters  of      SL(n,C), Linear and Multilinear Algebra 16 (1984), 3-27.[Sta2]  R. P. Stanley,  Differential posets, in preparation.[Sun]  S. Sundaram, "On the Combinatorics  of  Representations  of      Sp(2n,C)," Ph.D. thesis, MIT, 1986.[SW]  D. Stanton and D. White, A Schensted correspondence for  rim      hook tableaux, J. Combin. Theory Ser. A 40 (1985), 211-247.[Tho]   G.  P.  Thomas,   On  Schensted's  construction  and   the      multiplication of Schur functions, Adv. in Math.  30  (1978),      8-32.[Whi]   D.  White,   A  bijection  proving  orthogonality  of  the      characters of S ,  Adv. in Math. 50 (1983), 160-186.[Wor]  D. Worley, "A  Theory  of  Shifted  Young  Tableaux,"  Ph.D.      thesis, MIT, 1984.