%AmS-TeX file for a 9 page paper



\def\StWhAB{13}
\def\SagaAB{11}
\def\MacdAB{9}
\def\LaScAE{8}
\def\ZeilAE{14}
\def\StanAB{12}
\def\RemmAD{10}
\def\HiGrAA{7}
\def\GrNWAA{6}
\def\GeViAB{5}
\def\GeViAA{4}
\def\GaMiAB{3}
\def\FbZeAA{2}
\def\FrRTAA{1}

\input amstex
\documentstyle{amsppt}
\magnification1200
\hsize15.6truecm
\vsize22.8truecm
\catcode`\@=11
\font@\twelverm=cmr10 scaled\magstep1
\font@\twelveit=cmti10 scaled\magstep1
\font@\twelvei=cmmi10 scaled\magstep1
\font@\twelvesy=cmsy10 scaled\magstep1
\font@\twelveex=cmex10 scaled\magstep1

\newtoks\twelvepoint@
\def\twelvepoint{\normalbaselineskip15\p@
 \abovedisplayskip15\p@ plus3.6\p@ minus10.8\p@
 \belowdisplayskip\abovedisplayskip
 \abovedisplayshortskip\z@ plus3.6\p@
 \belowdisplayshortskip8.4\p@ plus3.6\p@ minus4.8\p@
 \textonlyfont@\rm\twelverm \textonlyfont@\it\twelveit
 \textonlyfont@\sl\twelvesl 
 \textonlyfont@\smc\twelvesmc \textonlyfont@\tt\twelvett
%Erg�nzung des fetten Small-Capitals-Fonts:
%
 \ifsyntax@ \def\big##1{{\hbox{$\left##1\right.$}}}%
  \let\Big\big \let\bigg\big \let\Bigg\big
 \else
  \textfont\z@=\twelverm  \scriptfont\z@=\tenrm  \scriptscriptfont\z@=\sevenrm
  \textfont\@ne=\twelvei  \scriptfont\@ne=\teni  \scriptscriptfont\@ne=\seveni
  \textfont\tw@=\twelvesy \scriptfont\tw@=\tensy \scriptscriptfont\tw@=\sevensy
  \textfont\thr@@=\twelveex \scriptfont\thr@@=\tenex
        \scriptscriptfont\thr@@=\tenex
  \textfont\itfam=\twelveit \scriptfont\itfam=\tenit
        \scriptscriptfont\itfam=\tenit
\scriptfont\bffam=\tenbf
        \scriptscriptfont\bffam=\sevenbf
  \setbox\strutbox\hbox{\vrule height10.2\p@ depth4.2\p@ width\z@}%
  \setbox\strutbox@\hbox{\lower.6\normallineskiplimit\vbox{%
        \kern-\normallineskiplimit\copy\strutbox}}%
 \setbox\z@\vbox{\hbox{$($}\kern\z@}\bigsize@=1.4\ht\z@
 \fi
 \normalbaselines\rm\ex@.2326ex\jot3.6\ex@\the\twelvepoint@}

\font@\fourteenrm=cmr10 scaled\magstep2
\font@\fourteenit=cmti10 scaled\magstep2
\font@\fourteensl=cmsl10 scaled\magstep2
\font@\fourteensmc=cmcsc10 scaled\magstep2
\font@\fourteentt=cmtt10 scaled\magstep2
\font@\fourteeni=cmmi10 scaled\magstep2
\font@\fourteensy=cmsy10 scaled\magstep2
\font@\fourteenex=cmex10 scaled\magstep2
\font@\fourteenmsa=msam10 scaled\magstep2
\font@\fourteeneufm=eufm10 scaled\magstep2
\font@\fourteenmsb=msbm10 scaled\magstep2
\newtoks\fourteenpoint@
\def\fourteenpoint{\normalbaselineskip15\p@
 \abovedisplayskip18\p@ plus4.3\p@ minus12.9\p@
 \belowdisplayskip\abovedisplayskip
 \abovedisplayshortskip\z@ plus4.3\p@
 \belowdisplayshortskip10.1\p@ plus4.3\p@ minus5.8\p@
 \textonlyfont@\rm\fourteenrm \textonlyfont@\it\fourteenit
 \textonlyfont@\sl\fourteensl 
 \textonlyfont@\smc\fourteensmc \textonlyfont@\tt\fourteentt
%Erg�nzung des fetten Small-Capitals-Fonts:
%
 \ifsyntax@ \def\big##1{{\hbox{$\left##1\right.$}}}%
  \let\Big\big \let\bigg\big \let\Bigg\big
 \else
  \textfont\z@=\fourteenrm  \scriptfont\z@=\twelverm  \scriptscriptfont\z@=\tenrm
  \textfont\@ne=\fourteeni  \scriptfont\@ne=\twelvei  \scriptscriptfont\@ne=\teni
  \textfont\tw@=\fourteensy \scriptfont\tw@=\twelvesy \scriptscriptfont\tw@=\tensy
  \textfont\thr@@=\fourteenex \scriptfont\thr@@=\twelveex
        \scriptscriptfont\thr@@=\twelveex
  \textfont\itfam=\fourteenit \scriptfont\itfam=\twelveit
        \scriptscriptfont\itfam=\twelveit
        \scriptscriptfont\bffam=\tenbf
  \setbox\strutbox\hbox{\vrule height12.2\p@ depth5\p@ width\z@}%
  \setbox\strutbox@\hbox{\lower.72\normallineskiplimit\vbox{%
        \kern-\normallineskiplimit\copy\strutbox}}%
 \setbox\z@\vbox{\hbox{$($}\kern\z@}\bigsize@=1.7\ht\z@
 \fi
 \normalbaselines\rm\ex@.2326ex\jot4.3\ex@\the\fourteenpoint@}

\font@\seventeenrm=cmr10 scaled\magstep3
\font@\seventeenit=cmti10 scaled\magstep3
\font@\seventeensl=cmsl10 scaled\magstep3
\font@\seventeensmc=cmcsc10 scaled\magstep3
\font@\seventeentt=cmtt10 scaled\magstep3
\font@\seventeeni=cmmi10 scaled\magstep3
\font@\seventeensy=cmsy10 scaled\magstep3
\font@\seventeenex=cmex10 scaled\magstep3
\font@\seventeenmsa=msam10 scaled\magstep3
\font@\seventeeneufm=eufm10 scaled\magstep3
\font@\seventeenmsb=msbm10 scaled\magstep3
\newtoks\seventeenpoint@
\def\seventeenpoint{\normalbaselineskip18\p@
 \abovedisplayskip21.6\p@ plus5.2\p@ minus15.4\p@
 \belowdisplayskip\abovedisplayskip
 \abovedisplayshortskip\z@ plus5.2\p@
 \belowdisplayshortskip12.1\p@ plus5.2\p@ minus7\p@
 \textonlyfont@\rm\seventeenrm \textonlyfont@\it\seventeenit
 \textonlyfont@\sl\seventeensl \textonlyfont@\bf\seventeenbf
 \textonlyfont@\smc\seventeensmc \textonlyfont@\tt\seventeentt
%Erg�nzung des fetten Small-Capitals-Fonts:
%
 \ifsyntax@ \def\big##1{{\hbox{$\left##1\right.$}}}%
  \let\Big\big \let\bigg\big \let\Bigg\big
 \else
  \textfont\z@=\seventeenrm  \scriptfont\z@=\fourteenrm  \scriptscriptfont\z@=\twelverm
  \textfont\@ne=\seventeeni  \scriptfont\@ne=\fourteeni  \scriptscriptfont\@ne=\twelvei
  \textfont\tw@=\seventeensy \scriptfont\tw@=\fourteensy \scriptscriptfont\tw@=\twelvesy
  \textfont\thr@@=\seventeenex \scriptfont\thr@@=\fourteenex
        \scriptscriptfont\thr@@=\fourteenex
  \textfont\itfam=\seventeenit \scriptfont\itfam=\fourteenit
        \scriptscriptfont\itfam=\fourteenit
  \textfont\bffam=\seventeenbf \scriptfont\bffam=\fourteenbf
        \scriptscriptfont\bffam=\twelvebf
  \setbox\strutbox\hbox{\vrule height14.6\p@ depth6\p@ width\z@}%
  \setbox\strutbox@\hbox{\lower.86\normallineskiplimit\vbox{%
        \kern-\normallineskiplimit\copy\strutbox}}%
 \setbox\z@\vbox{\hbox{$($}\kern\z@}\bigsize@=2\ht\z@
 \fi
 \normalbaselines\rm\ex@.2326ex\jot5.2\ex@\the\seventeenpoint@}

\catcode`\@=13

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Input-Datei zum Erzeugen von Gitterpunktwegen.%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Pfad-Eingabe: 
%  \Pfad(x-Koordinate des Anf.Punkts,y-Koordinate des Anf.Punkts),Pfad
%  als 1-2-Wort\endPfad
%(1=Schritt in x-Richtung, 2=Schritt in y-Richtung)
%
%Koordinatenachsen:
%  \Koordinatenachsen(L�nge der x-Achse, L�nge der y-Achse)
%
%Gitter:
%  \Gitter(Anzahl der Punkte in x-Richtung, Anzahl der Punkte in x-Richtung)
%
%Bezeichnung von Punkten:
%  \Label[wo?]{[Bezeichnung]}(x-Koordinate,y-Koordinate)
%wobei:
%  [wo?]=\l,\lo,\lu,\r,\ro,\ru,\o,\u
%und l=links, r=rechts, u=unten, o=oben.
%
%Die Einheit kann durch Eingabe von
%  \Einheit=?cm
%ver�ndert werden.
%
%Die Dicke der Pfade kann durch Eingabe von
%     \PfadDicke{?cm}
%ver�ndert werden.
%
%Es stehen die folgenden Punktgr��en zur Verf�gung:
%\DuennPunkt, \NormalPunkt, \DickPunkt. Eingabe:
%  \DickPunkt(x-Koordinate,y-Koordinate), etc.
%
%Weiters steht mit \Kreis ein Kreis zur Verf�gung. Eingabe:
%  \Kreis(x-Koordinate,y-Koordinate)
%
\catcode`\@=11
\newskip\Einheit \Einheit=0.5cm
\newcount\xcoord \newcount\ycoord
\newdimen\xdim \newdimen\ydim \newdimen\PfadD@cke \newdimen\Pfadd@cke
\PfadD@cke1pt \Pfadd@cke0.5pt
\def\PfadDicke#1{\PfadD@cke#1 \divide\PfadD@cke by2 \Pfadd@cke\PfadD@cke
 \multiply\PfadD@cke by2}
\long\def\LOOP#1\REPEAT{\def\BODY{#1}\ITERATE}
\def\ITERATE{\BODY \let\next\ITERATE \else\let\next\relax\fi \next}
\let\REPEAT=\fi
\def\Punkt{\hbox{\raise-2pt\hbox to0pt{\hss$\ssize\bullet$\hss}}}
\def\DuennPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-2.5pt\hbox to0pt{\hss$\bullet$\hss}\hss}}
\def\NormalPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-3pt\hbox to0pt{\hss\twelvepoint$\bullet$\hss}\hss}}
\def\DickPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-4pt\hbox to0pt{\hss\fourteenpoint$\bullet$\hss}\hss}}
\def\Kreis(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-4pt\hbox to0pt{\hss\fourteenpoint$\circ$\hss}\hss}}
\def\Pfad(#1,#2),#3\endPfad{\unskip\leavevmode
  \xcoord#1 \ycoord#2 \ZeichnePfad#3\endPfad}
\def\ZeichnePfad#1{\ifx#1\endPfad\let\next\relax
  \else\let\next\ZeichnePfad
    \ifnum#1=1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \vrule height\Pfadd@cke width1 \Einheit depth\Pfadd@cke\hss}%
      \advance\xcoord by 1
    \else
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
        \hbox{\hskip-1pt\vrule height1 \Einheit width\PfadD@cke
 depth0pt}\hss}%
      \advance\ycoord by 1
    \fi
  \fi\next}
\def\Koordinatenachsen(#1,#2){\unskip
 \hbox to0pt{\hskip-.5pt\vrule height#2 \Einheit width.5pt depth1 \Einheit}%
 \hbox to0pt{\hskip-1 \Einheit \xcoord#1 \advance\xcoord by1
    \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}}
\def\Koordinatenachsen(#1,#2)(#3,#4){\unskip
 \hbox to0pt{\hskip-.5pt \ycoord-#4 \advance\ycoord by1
    \vrule height#2 \Einheit width.5pt depth\ycoord \Einheit}%
 \hbox to0pt{\hskip-1 \Einheit \hskip#3\Einheit 
    \xcoord#1 \advance\xcoord by1 \advance\xcoord by-#3 
    \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}}
\def\Gitter(#1,#2){\unskip \xcoord0 \ycoord0 \leavevmode
  \LOOP\ifnum\ycoord<#2
    \loop\ifnum\xcoord<#1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}%
      \advance\xcoord by1
    \repeat
    \xcoord0
    \advance\ycoord by1
  \REPEAT}
\def\Gitter(#1,#2)(#3,#4){\unskip \xcoord#3 \ycoord#4 \leavevmode
  \LOOP\ifnum\ycoord<#2
    \loop\ifnum\xcoord<#1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}%
      \advance\xcoord by1
    \repeat
    \xcoord#3
    \advance\ycoord by1
  \REPEAT}
\def\Label#1#2(#3,#4){\unskip \xdim#3 \Einheit \ydim#4 \Einheit
  \def\lo{\advance\xdim by-.5 \Einheit \advance\ydim by.5 \Einheit}%
  \def\o{\advance\ydim by.5 \Einheit}%
  \def\ro{\advance\xdim by.5 \Einheit \advance\ydim by.5 \Einheit}%
  \def\l{\advance\xdim by-.5 \Einheit}%
  \def\r{\advance\xdim by.5 \Einheit}%
  \def\lu{\advance\xdim by-.5 \Einheit \advance\ydim by-.5 \Einheit}%
  \def\u{\advance\ydim by-.5 \Einheit}%
  \def\ru{\advance\xdim by.5 \Einheit \advance\ydim by-.5 \Einheit}%
  #1\raise\ydim\hbox to0pt{\hskip\xdim
     \vbox to0pt{\vss\hbox to0pt{\hss$#2$\hss}\vss}\hss}%
}
\catcode`\@=13

\def\LL{\leavevmode\setbox0=\hbox{L}\hbox to\wd0{\hss\char'40L}}
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\de{\delta}
\def\ep{\varepsilon}
\def\ze{\zeta}
\def\et{\eta}
\def\th{\theta}
\def\vt{\vartheta}
\def\io{\iota}
\def\ka{\kappa}
\def\la{\lambda}
\def\rh{\rho}
\def\si{\sigma}
\def\ta{\tau}
\def\ph{\varphi}
\def\ch{\chi}
\def\ps{\psi}
\def\om{\omega}
\def\Ga{\Gamma}
\def\De{\Delta}
\def\Th{\Theta}
\def\La{\Lambda}
\def\Si{\Sigma}
\def\Ph{\Phi}
\def\Ps{\Psi}
\def\Om{\Omega}
\def\row#1#2#3{#1_{#2},\ldots,#1_{#3}}
\def\rowup#1#2#3{#1^{#2},\ldots,#1^{#3}}
\def\x{\times}
\def\crf{}            %used for crossreferencing, Tex should ignore.
\def\rf{}             %used for refencing (section-numbers)
\def\rfnew{}          %used for new-section numbers
\def\P{{\Bbb P}}
\def\R{{\Bbb R}}
\def\X{{\Cal X}}
\def\C{{\Bbb C}}
\def\Mf{{\Cal Mf}}
\def\FM{{\Cal F\Cal M}}
\def\F{{\Cal F}}
\def\G{{\Cal G}}
\def\V{{\Cal V}}
\def\T{{\Cal T}}
\def\A{{\Cal A}}
\def\N{{\Bbb N}}
\def\Z{{\Bbb Z}}
\def\Q{{\Bbb Q}}
\def\ddt{\left.\tfrac \partial{\partial t}\right\vert_0}
\def\dd#1{\tfrac \partial{\partial #1}}
\def\today{\ifcase\month\or
 January\or February\or March\or April\or May\or June\or
 July\or August\or September\or October\or November\or December\fi
 \space\number\day, \number\year}
\def\nmb#1#2{#2} %zum Nummerieren
\def\totoc{} % f\"ur Inhaltsverzeichnung
\def\dfrac#1#2{{\displaystyle{#1\over#2}}}
\def\tfrac#1#2{{\textstyle{#1\over#2}}}
\def\iprod#1#2{\langle#1,#2\rangle}
\def\pder#1#2{\frac{\partial #1}{\partial #2}}
\def\iint{\int\!\!\int}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\supp{\operatorname{supp}}
\def\Df{\operatorname{Df}}
\def\dom{\operatorname{dom}}
\def\Ker{\operatorname{Ker}}
\def\Tr{\operatorname{Tr}}
\def\Res{\operatorname{Res}}
\def\Aut{\operatorname{Aut}}
\def\kgV{\operatorname{kgV}}
\def\ggT{\operatorname{ggT}}
\def\diam{\operatorname{diam}}
\def\Im{\operatorname{Im}}
\def\Re{\operatorname{Re}}
\def\ord{\operatorname{ord}}
\def\rang{\operatorname{rang}}
\def\rng{\operatorname{rng}}
\def\grd{\operatorname{grd}}
\def\inv{\operatorname{inv}}
\def\maj{\operatorname{maj}}
\def\des{\operatorname{des}}
\def\varmaj{\operatorname{\overline{maj}}}
\def\vardes{\operatorname{\overline{des}}}
\def\pvarmaj{\operatorname{\overline{maj}'}}
\def\pmaj{\operatorname{maj'}}
\def\ln{\operatorname{ln}}
\def\der{\operatorname{der}}
\def\Hom{\operatorname{Hom}}
\def\tr{\operatorname{tr}}
\def\Span{\operatorname{Span}}
\def\grad{\operatorname{grad}}
\def\div{\operatorname{div}}
\def\rot{\operatorname{rot}}
\def\Sp{\operatorname{Sp}}
\def\sgn{\operatorname{sgn}}
\def\liml{\lim\limits}
\def\supl{\sup\limits}
\def\bigcupl{\bigcup\limits}
\def\bigcapl{\bigcap\limits}
\def\limsupl{\limsup\limits}
\def\liminfl{\liminf\limits}
\def\intl{\int\limits}
\def\suml{\sum\limits}
\def\maxl{\max\limits}
\def\minl{\min\limits}
\def\prodl{\prod\limits}
\def\tg{\operatorname{tan}}
\def\ctg{\operatorname{cot}}
\def\arctg{\operatorname{arctan}}
\def\arccot{\operatorname{arccot}}
\def\arcctg{\operatorname{arccot}}
\def\tgh{\operatorname{tanh}}
\def\ctgh{\operatorname{coth}}
\def\arcsinh{\operatorname{arcsinh}}
\def\arccosh{\operatorname{arccosh}}
\def\arctgh{\operatorname{arctanh}}
\def\arcctgh{\operatorname{arccoth}}
\def\3{\ss}
\catcode`\@=11
\def\dddot#1{\vbox{\ialign{##\crcr
      .\hskip-.5pt.\hskip-.5pt.\crcr\noalign{\kern1.5\p@\nointerlineskip}
      $\hfil\displaystyle{#1}\hfil$\crcr}}}

\newif\iftab@\tab@false
\newif\ifvtab@\vtab@false
\def\tab{\bgroup\tab@true\vtab@false\vst@bfalse\Strich@false%
   \def\\{\global\hline@@false%
     \ifhline@\global\hline@false\global\hline@@true\fi\cr}
   \edef\l@{\the\leftskip}\ialign\bgroup\hskip\l@##\hfil&&##\hfil\cr}
\def\endtab{\cr\egroup\egroup}
\def\vtab{\vtop\bgroup\vst@bfalse\vtab@true\tab@true\Strich@false%
   \bgroup\def\\{\cr}\ialign\bgroup&##\hfil\cr}
\def\endvtab{\cr\egroup\egroup\egroup}
\def\stab{\D@cke0.5pt\null 
 \bgroup\tab@true\vtab@false\vst@bfalse\Strich@true\Let@@\vspace@
 \normalbaselines\offinterlineskip
  \openup\spreadmlines@
 \edef\l@{\the\leftskip}\ialign
 \bgroup\hskip\l@##\hfil&&##\hfil\crcr}
\def\endstab{\crcr\egroup
 \egroup}
\newif\ifvst@b\vst@bfalse
\def\vstab{\D@cke0.5pt\null
 \vtop\bgroup\tab@true\vtab@false\vst@btrue\Strich@true\bgroup\Let@@\vspace@
 \normalbaselines\offinterlineskip
  \openup\spreadmlines@\bgroup}
\def\endvstab{\crcr\egroup\egroup
 \egroup\tab@false\Strich@false}

\newdimen\htstrut@
\htstrut@8.5\p@
\newdimen\htStrut@
\htStrut@12\p@
\newdimen\dpstrut@
\dpstrut@3.5\p@
\newdimen\dpStrut@
\dpStrut@3.5\p@
\def\openup{\afterassignment\@penup\dimen@=}
\def\@penup{\advance\lineskip\dimen@
  \advance\baselineskip\dimen@
  \advance\lineskiplimit\dimen@
  \divide\dimen@ by2
  \advance\htstrut@\dimen@
  \advance\htStrut@\dimen@
  \advance\dpstrut@\dimen@
  \advance\dpStrut@\dimen@}
\def\Let@@{\relax\iffalse{\fi%
    \def\\{\global\hline@@false%
     \ifhline@\global\hline@false\global\hline@@true\fi\cr}%
    \iffalse}\fi}
\def\matrix{\null\,\vcenter\bgroup
 \tab@false\vtab@false\vst@bfalse\Strich@false\Let@@\vspace@
 \normalbaselines\openup\spreadmlines@\ialign
 \bgroup\hfil$\m@th##$\hfil&&\quad\hfil$\m@th##$\hfil\crcr
 \Mathstrut@\crcr\noalign{\kern-\baselineskip}}
\def\endmatrix{\crcr\Mathstrut@\crcr\noalign{\kern-\baselineskip}\egroup
 \egroup\,}
\def\smatrix{\D@cke0.5pt\null\,
 \vcenter\bgroup\tab@false\vtab@false\vst@bfalse\Strich@true\Let@@\vspace@
 \normalbaselines\offinterlineskip
  \openup\spreadmlines@\ialign
 \bgroup\hfil$\m@th##$\hfil&&\quad\hfil$\m@th##$\hfil\crcr}
\def\endsmatrix{\crcr\egroup
 \egroup\,\Strich@false}
\newdimen\D@cke
\def\Dicke#1{\global\D@cke#1}
\newtoks\tabs@\tabs@{&}
\newif\ifStrich@\Strich@false
\newif\iff@rst

\def\Stricherr@{\iftab@\ifvtab@\errmessage{\noexpand\s not allowed
     here. Use \noexpand\vstab!}%
  \else\errmessage{\noexpand\s not allowed here. Use \noexpand\stab!}%
  \fi\else\errmessage{\noexpand\s not allowed
     here. Use \noexpand\smatrix!}\fi}
\def\format{\ifvst@b\else\crcr\fi\egroup\iffalse{\fi\ifnum`}=0 \fi\format@}
\def\format@#1\\{\def\preamble@{#1}%
 \def\Str@chfehlt##1{\ifx##1\s\Stricherr@\fi\ifx##1\\\let\Next\relax%
   \else\let\Next\Str@chfehlt\fi\Next}%
 \def\c{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi\iftab@\else$\m@th\fi\the\hashtoks@\iftab@\else$\fi\hfil}%
 \def\r{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi\iftab@\else$\m@th\fi\the\hashtoks@\iftab@\else$\fi}%
 \def\l{\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi\iftab@\else$\m@th\fi\the\hashtoks@\iftab@\else$\fi\hfil}%
 \def\s{\ifStrich@\ \the\tabs@\vrule width\D@cke\the\hashtoks@%
          \fi\the\tabs@\ }%
 \def\sa{\ifStrich@\vrule width\D@cke\the\hashtoks@%
            \the\tabs@\ %
            \fi}%
 \def\se{\ifStrich@\ \the\tabs@\vrule width\D@cke\the\hashtoks@\fi}%
 \def\cd{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi$\dsize\m@th\the\hashtoks@$\hfil}%
 \def\rd{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi$\dsize\m@th\the\hashtoks@$}%
 \def\ld{\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi$\dsize\m@th\the\hashtoks@$\hfil}%
 \ifStrich@\else\Str@chfehlt#1\\\fi%
 \setbox\z@\hbox{\xdef\Preamble@{\preamble@}}\ifnum`{=0 \fi\iffalse}\fi
 \ialign\bgroup\span\Preamble@\crcr}
\newif\ifhline@\hline@false
\newif\ifhline@@\hline@@false
\def\hlinefor#1{\multispan@{\strip@#1 }\leaders\hrule height\D@cke\hfill%
    \global\hline@true\ignorespaces}
\def\Item "#1"{\par\noindent\hangindent2\parindent%
  \hangafter1\setbox0\hbox{\rm#1\enspace}\ifdim\wd0>2\parindent%
  \box0\else\hbox to 2\parindent{\rm#1\hfil}\fi\ignorespaces}
\def\ITEM #1"#2"{\par\noindent\hangafter1\hangindent#1%
  \setbox0\hbox{\rm#2\enspace}\ifdim\wd0>#1%
  \box0\else\hbox to 0pt{\rm#2\hss}\hskip#1\fi\ignorespaces}
\def\item"#1"{\par\noindent\hang%
  \setbox0=\hbox{\rm#1\enspace}\ifdim\wd0>\the\parindent%
  \box0\else\hbox to \parindent{\rm#1\hfil}\enspace\fi\ignorespaces}
\let\plainitem@\item
\catcode`\@=13



\def\Bullet{\hbox{\fourteenpoint $\bullet$}}
\def\mc{\operatorname{comaj}}
\def\HG{\operatorname{HG}}
\def\SP{\operatorname{SP}}
\def\bT{{\bar T}}
\def\bS{{\bar S}}
\def\bU{{\bar U}}
\def\bO{{\bar O}}
\def\bX{{\bar X}}
\def\bi{{\bar i}}
\def\tU{{U'}}
\def\0{{\bold 0}}

\topmatter 
\title Bijective proofs of the hook formulas for the number of
standard Young tableaux, ordinary and shifted
\endtitle 
\author C.~Krattenthaler\footnote"$^\dagger$"{Supported in part by EC's Human
Capital and Mobility Program, grant CHRX-CT93-0400 and the\linebreak 
\hbox{Austrian Science Foundation FWF, grant P10191-PHY}}
\endauthor 
\affil 
Institut f\"ur Mathematik der Universit\"at Wien,\\
Strudlhofgasse 4, A-1090 Wien, Austria.\\
\endaffil
%\email KRATT\@Pap.Univie.Ac.At\endemail
%\dedicatory \enddedicatory
\dedicatory Submitted: February 20, 1995; Accepted: July 9, 1995\enddedicatory
%\thanks \endthanks
\subjclass Primary 05A15;
 Secondary 05A17, 05A30, 05E10,\linebreak 05E15, 11P81
\endsubjclass
\keywords Standard Young tableaux, shifted standard tableaux, hook formula, 
Hillman--Grassl algorithm, $(P,\om)$-partition theorem, involution principle
\endkeywords
\abstract 
Bijective proofs of the hook formulas for the number of ordinary
standard Young tableaux and for the number of shifted standard Young
tableaux are given. They are formulated in a uniform manner, and in
fact prove $q$-analogues of the ordinary and shifted hook formulas.
The proofs proceed by combining the ordinary, respectively shifted,
Hillman--Grassl algorithm and Stanley's $(P,\om)$-partition theorem
with the involution principle of Garsia and Milne.
\endabstract
\endtopmatter

\font\smcp=cmcsc8
\headline={\ifnum\pageno>1 {\smcp the electronic journal of  
combinatorics 2 (1995), \#R13\hfill\folio} \fi}

\document

\subhead 1. Introduction\endsubhead
A few years ago there had been a lot of interest in finding a
bijective proof of Frame, Robinson and Thrall's \cite{\FrRTAA} 
hook formula for the number of standard Young
tableaux of a given shape.
This resulted in the discovery of three
different such proofs \cite{\FbZeAA, \RemmAD, \ZeilAE}, none of them
is considered to be really satisfactory. Closest to being
satisfactory is probably the proof by Franzblau and Zeilberger
\cite{\FbZeAA}. However, while the description of their algorithm is
fairly simple, it is rather difficult to show that it really works.
Also, it does not portray the nice row-column symmetry of the hooks. 
Remmel's proof \cite{\RemmAD} is the
most complicated. It uses the involution principle of Garsia and
Milne \cite{\GaMiAB}. However, Remmel bases his proof on
``bijectivization" of recurrence relations, which is not the most
direct route to attack the problem. Finally, Zeilberger's proof
\cite{\ZeilAE}, translating the beautiful probabilistic proof
\cite{\GrNWAA} by Greene, Nijenhuis and Wilf into a bijection,
actually sets up a bijection between larger sets than one desires.

So, it is still considered to be the case that
the best proof of the hook formula is
to use the Hillman--Grassl algorithm \cite{\HiGrAA} and Stanley's
$(P,\om)$-partition theorem \cite{\StanAB}, and then to apply a limit
argument (this is the non-bijective part). In view of this it is
somehow surprising that there are 
half-combinatorial proofs of the hook formula that
were translated into bijective proofs, such as the Gessel--Viennot
method \cite{\GeViAA, \GeViAB} of nonintersecting lattice paths in
Remmel's proof \cite{\RemmAD}, and the probabilistic proof
\cite{\GrNWAA} by Greene, Nijenhuis and Wilf in Zeilberger's proof
\cite{\ZeilAE}, but that it was never tried to translate what is
still considered to be the best (but only half-combinatorial) proof into a
bijective proof. This omission is made up for in this paper. In fact, it
turns out to be pretty simple. Besides, this new bijective proof has
two advantages. First, it actually proves a natural $q$-analogue of
the hook formula (see the Theorem in section~4) 
which all the other proofs do not. Secondly, the
same idea also works to provide a bijective proof of the hook formula
for the number of {\it shifted\/} standard Young tableaux (and its
$q$-analogue; see the Theorem in section~4). 
No bijective proof for the shifted hook formula has
been given before. On the other hand, our proofs are still
not satisfactory in that they involve the involution principle.

The outline of the paper is as follows. In the next section we review
all relevant definitions. Then, in section~3, we explain briefly what
the Hillman--Grassl algorithm, Stanley's $(P,\om)$-partition theorem
and the involution principle of Garsia and Milne are about. Finally,
in section~4 we state the two hook formulas and
present our bijective proofs of them, 
in a unified fashion. In section~5 we explain where the
involutions of section~4 come from.

\subhead 2. Definitions\endsubhead
A {\it partition\/} of a positive integer $n$ is a sequence
$\la=(\la_1,\la_2,\dots,\mathbreak\la_r)$ with $\la_1+\la_2+\dots+\la_r=n$ and 
$\la_1\ge \la_2\ge\dots\ge\la_r>0$,
for some $r$. The components of $\la$ are called the {\it parts\/} of
$\la$. The integer $n$, the sum of all the parts of $\la$, is called
the {\it norm\/} of $\la$ and is denoted by $n(\la)$.
The {\it \rm(\it ordinary\rm) \it Ferrers
diagram\/} of $\lambda$
is an array of cells with $r$ left-justified rows and $\lambda_i$
cells in row $i$. Figure~1.a shows the Ferrers
diagram corresponding to $(4,3,3,1)$. If $\la$ is a partition with
distinct parts then the {\it shifted Ferrers
diagram\/} of $\lambda$
is an array of cells with $r$ rows, each row indented by one cell to
the right with respect to the previous row, and $\lambda_i$
cells in row $i$. Figure~1.b shows the shifted Ferrers
diagram corresponding to $(5,4,2,1)$. We shall frequently use the
same symbols for things which may have an
``ordinary" or ``shifted" interpretation. It will always be clear
which interpretation is meant. In particular, if a partition $\la$
appears in the shifted context then it is always assumed that $\la$
is a partition with distinct parts.

The {\it conjugate\/} of a partition $\lambda$ is the partition 
$(\lambda^\prime_1, \dots, \lambda^\prime_{\lambda_1})$ where
$\lambda_j'$ is the length of the $j$-th column in the ordinary
Ferrers diagram of
$\lambda$. 

\eightpoint
\vskip10pt
\vbox{
$$
\gather
\smatrix \format \sa\c\quad \s\c\quad \s\c\quad \s\c\quad \se\\
\hlinefor9\\
&\vphantom{f}&& && && &\\
\hlinefor9\\
&\vphantom{f}&& && &\\
\hlinefor7\\
&\vphantom{f}&& && &\\
\hlinefor7\\
&\vphantom{f} &\\
\hlinefor3
\endsmatrix
\hskip0.8cm
\smatrix \format \sa\c\quad \s\c\quad \s\c\quad \s\c\quad \s\c\quad \se\\
\hlinefor{11}\\
&\vphantom{f}&& && && && &\\
\hlinefor{11}\\
\omit&\omit&&\vphantom{f}&& && && &\\
\omit&\omit&\hlinefor9\\
\omit&\omit&\omit&\omit&&\vphantom{f}&& &\\
\omit&\omit&\omit&\omit&\hlinefor5\\
\omit&\omit&\omit&\omit&\omit&\omit&&\vphantom{f} &\\
\omit&\omit&\omit&\omit&\omit&\omit&\hlinefor3
\endsmatrix
\hskip0.8cm
\smatrix \format \sa\c\s\c\s\c\s\c\quad \se\\
\hlinefor9\\
&\vphantom{f}&& && && &\\
\hlinefor9\\
&\hskip1pt\Bullet\hskip1pt&&\hskip1pt\Bullet\hskip1pt &&\hskip1pt\Bullet\hskip1pt &\\
\hlinefor7\\
&\Bullet&& && &\\
\hlinefor7\\
&\Bullet &\\
\hlinefor3
\endsmatrix
\hskip0.8cm
\smatrix \format \sa\c\quad \s\c\s\c\s\c\s\c\se\\
\hlinefor{11}\\
&\vphantom{f}&&\hskip1pt\Bullet\hskip1pt &&\hskip1pt\Bullet\hskip1pt &&\hskip1pt\Bullet\hskip1pt &&\hskip1pt\Bullet\hskip1pt &\\
\hlinefor{11}\\
\omit&\omit&&\Bullet\vphantom{f}&& && && &\\
\omit&\omit&\hlinefor9\\
\omit&\omit&\omit&\omit&&\Bullet\vphantom{f}&&\Bullet &\\
\omit&\omit&\omit&\omit&\hlinefor5\\
\omit&\omit&\omit&\omit&\omit&\omit&&\vphantom{f} &\\
\omit&\omit&\omit&\omit&\omit&\omit&\hlinefor3
\endsmatrix
\\
\smallmatrix\format\l\\
 \text{\eightpoint a. Ferrers diagram\hskip0.7cm
b. shifted Ferrers\hskip1.5cm
c. hook\hskip1.9cm
d. shifted hook}\\%
\text{\eightpoint \hphantom{a. Ferrers diagram\hskip0.7cm
b. }\hbox to0pt{diagram\hss}%
\hphantom{shifted Ferrers\quad \quad
c. } }
\endsmallmatrix
\endgather
$$
\centerline{\eightpoint Figure 1}
}
\vskip10pt
\tenpoint

We label the cell in the $i$-th row and $j$-th column of
the ordinary, respectively shifted,
Ferrers diagram of $\la$ by the pair $(i,j)$. Also, if we write
$\rh\in\la$ we mean `$\rh$ is a cell of $\la$'. The {\it hook\it} of 
a cell $\rh$ of the {\it ordinary\/} Ferrers diagram of $\la$ 
is the set of cells that are either in
the same row as $\rh$ and to the right of $\rh$, or in the same column
as $\rh$ and below $\rh$, $\rh$ included. 
The dots in Figure~1.c indicate the hook of the cell $(2,1)$.
The {\it hook\/} of 
a cell $\rh$ of the {\it shifted\/} Ferrers diagram of $\la$ 
again includes all cells that are either in
the same row as $\rh$ and to the right of $\rh$, or in the same column
as $\rh$ and below $\rh$, $\rh$ included, but if this set contains a
cell on the main diagonal, cell $(j,j)$ say, then
also all the cells of the $(j+1)$-st row belong to the hook of $\la$.
The dots in Figure~1.d indicate the hook of the cell $(1,2)$.
The {\it hook length\/} 
$h_\rh$ (in the ordinary, respectively 
shifted sense) of a cell $\rh$ of $\la$ is the number of cells in the
{\it hook\/} of $\rh$.

\eightpoint
\vskip10pt
\vbox{
$$
\gather
\smatrix \format\sa\c\s\c\s\c\s\c\se\\
\hlinefor9\\
&\hbox to10pt{\hss 1\hss}&&\hbox to10pt{\hss 3\hss}&&\hbox to10pt{\hss
4\hss}&&\hbox to10pt{\hss 4\hss}&\\
\hlinefor9\\
&5&&5&&7&\\
\hlinefor7\\
&5&&6&&7&\\
\hlinefor7\\
&8&\\
\hlinefor3
\endsmatrix
\hskip0.6cm
\smatrix \format \sa\c \s\c \s\c \s\c \s\c \se\\
\hlinefor{11}\\
&\hbox to10pt{\hss 2\hss}&& \hbox to10pt{\hss 2\hss}&& \hbox to10pt{\hss
5\hss}&& \hbox to10pt{\hss 6\hss}&& \hbox to10pt{\hss 6\hss}&\\
\hlinefor{11}\\
\omit&\omit&&4&& 5&& 7&& 9&\\
\omit&\omit&\hlinefor9\\
\omit&\omit&\omit&\omit&&5&& 8&\\
\omit&\omit&\omit&\omit&\hlinefor5\\
\omit&\omit&\omit&\omit&\omit&\omit&&8 &\\
\omit&\omit&\omit&\omit&\omit&\omit&\hlinefor3
\endsmatrix
\hskip0.6cm
\smatrix \format\sa\c\s\c\s\c\s\c\se\\
\hlinefor9\\
&\hbox to10pt{\hss 1\hss}&&\hbox to10pt{\hss 2\hss}&&\hbox to10pt{\hss
3\hss}&&\hbox to10pt{\hss 4\hss}&\\
\hlinefor9\\
&5&&6&&9&\\
\hlinefor7\\
&7&&8&&\!10\!&\\
\hlinefor7\\
&\!11\!&\\
\hlinefor3
\endsmatrix
\hskip0.6cm
\smatrix \format \sa\c \s\c \s\c \s\c \s\c \se\\
\hlinefor{11}\\
&\hbox to10pt{\hss 1\hss}&& \hbox to10pt{\hss 2\hss}&& \hbox to10pt{\hss
4\hss}&& \hbox to10pt{\hss 7\hss}&& \hbox to10pt{\hss 8\hss}&\\
\hlinefor{11}\\
\omit&\omit&&3&& 5&& 9&& \!12\!&\\
\omit&\omit&\hlinefor9\\
\omit&\omit&\omit&\omit&&6&& \!10\!&\\
\omit&\omit&\omit&\omit&\hlinefor5\\
\omit&\omit&\omit&\omit&\omit&\omit&&\!11\! &\\
\omit&\omit&\omit&\omit&\omit&\omit&\hlinefor3
\endsmatrix
\\
\smallmatrix\format\l\\
 \text{\eightpoint a. reverse plane\hskip0.7cm
b. shifted reverse\hskip0.9cm
c. standard Young\hskip1cm
d. shifted standard}\\%
\text{\eightpoint \hphantom{a. }\hbox to0pt{partition\hss}%
\hphantom{reverse plane\hskip0.7cm
b. }\hbox to0pt{plane partition\hss}%
\hphantom{shifted reverse\hskip0.9cm
c. }\hbox to0pt{tableau\hss}%
\hphantom{standard Young\hskip1cm
d. }Young tableau}
\endsmallmatrix
\endgather
$$
\centerline{\eightpoint Figure 2}
}
\vskip10pt
\tenpoint

Given a partition $\la=(\la_1,\la_2,\dots,\la_r)$, a {\it reverse plane
partition of shape\/} $\la$ (in the ordinary or shifted sense) 
is a filling $P$ of the cells of $\la$
with nonnegative integers such that the entries along rows and along columns are
weakly increasing. Figure~2.a displays an ordinary reverse plane
partition of shape $(4,3,3,1)$, Figure~2.b displays a shifted reverse plane
partition of shape $(5,4,2,1)$. 
We write $P_\rh$ for the entry in cell $\rh$ of $P$. Also here, we
call the sum of all the entries of a reverse plane partition $P$ the
{\it norm\/} of $P$, and denote it by $n(P)$. Given a partition $\la$
of $n$, a {\it standard Young
tableau of shape\/} $\la$ (in the ordinary or shifted sense) 
is a reverse plane partition whose set of entries is
$\{1,2,\dots,n\}$. Figure~2.c displays an ordinary standard Young
tableau of shape $(4,3,3,1)$, Figure~2.d displays a shifted standard
Young tableau of shape $(5,4,2,1)$.

\eightpoint
\vskip10pt
\vbox{
$$
\smatrix \format\sa\c\s\c\s\c\s\c\se\\
\hlinefor9\\
&\hbox to10pt{\hss \!11\!\hss}&&\hbox to10pt{\hss \!10\!\hss}&&\hbox to10pt{\hss
9\hss}&&\hbox to10pt{\hss 8\hss}&\\
\hlinefor9\\
&7&&6&&5&\\
\hlinefor7\\
&4&&3&&2&\\
\hlinefor7\\
&1&\\
\hlinefor3
\endsmatrix
\hskip2cm
\smatrix \format \sa\c \s\c \s\c \s\c \s\c \se\\
\hlinefor{11}\\
&\hbox to10pt{\hss \!12\!\hss}&& \hbox to10pt{\hss \!11\!\hss}&& \hbox to10pt{\hss
\!10\!\hss}&& \hbox to10pt{\hss 9\hss}&& \hbox to10pt{\hss 8\hss}&\\
\hlinefor{11}\\
\omit&\omit&&7&& 6&& 5&& 4&\\
\omit&\omit&\hlinefor9\\
\omit&\omit&\omit&\omit&&3&& 2&\\
\omit&\omit&\omit&\omit&\hlinefor5\\
\omit&\omit&\omit&\omit&\omit&\omit&&1 &\\
\omit&\omit&\omit&\omit&\omit&\omit&\hlinefor3
\endsmatrix
$$
\centerline{\eightpoint Figure 3}
}
\vskip10pt
\tenpoint

For the rest of the paper we fix the following {\it total order\/} of the
cells of an (ordinary or shifted) Ferrers diagram $\la$. 
A cell $\rh_1$ comes before cell $\rh_2$ if $\rh_1$ is in a lower row
than $\rh_2$ or if both are in the same row but $\rh_1$ is to the
right of $\rh_2$. In other words, to obtain the total order one
starts with the right-most cell in the last row and reads each row
from right to left, beginning with the bottom row and continuing up
to the first row. We write $\#\rh$ for the number of the cell $\rh$ in this
total order. Figure~3 displays the values $\#\rh$ for the ordinary
diagram $(4,3,3,1)$ and the shifted diagram $(5,4,2,1)$.


Next we define a statistics on (ordinary or
shifted) standard Young tableaux, which is similar to charge
(see \cite{\LaScAE; 
\MacdAB, p.~129} for the
definition of charge). Given a standard Young tableau $Y$ with $n$
entries, we define
$\mc(Y)$ to be the sum $\sum _{} ^{}(n-i)$, where the sum is over all
$i$ that have the property that $i+1$ is located strictly above $i$ in $Y$.
For example, $\mc(.)=3$ for the standard Young
tableau in Figure~2.c and $\mc(.)=9+6+1=16$ for that in Figure~2.d.


We call an {\it arbitrary\/} filling of the cells of $\la$ (ordinary
or shifted) with
nonnegative integers a {\it tabloid of shape\/} $\la$. 
Also here, by $n(T)$ we mean the sum of all the entries of $T$, and
by $T_\rh$ we mean the entry in cell $\rh$ of $T$. Furthermore,
we define the {\it hook weight\/} $w_h(T)$ of a tabloid $T$ of
shape $\la$ by $\sum _{\rh\in\la} ^{}T_\rh\cdot h_\rh$, where $h_\rh$
has to be understood in the ordinary or shifted sense, depending on
whether the shape $\la$ is understood in the ordinary or shifted
sense.
Finally, we introduce some special tabloids to be used in the
course of the following bijections. 
We call a tabloid
$T$ of shape $\la$ a {\it $(<h)$-tabloid\/} if $T_\rh<h_\rh$ for all
cells $\rh\in\la$, and we call $T$ a {\it $(0\text{--}h)$-tabloid\/}
if $T_\rh$ equals $0$ or $h_\rh$, for all cells $\rh\in\la$.
Similarly, we call a tabloid
$T$ of shape $\la$ a {\it $(<\#)$-tabloid\/} if $T_\rh<\#\rh$ for all
cells $\rh\in\la$, and we call $T$ a {\it $(0\text{--}\#)$-tabloid\/}
if $T_\rh$ equals $0$ or $\#\rh$, for all cells $\rh\in\la$. 
The sign
$\sgn(T)$ of a $(0\text{--}h)$-tabloid or $(0\text{--}\#)$-tabloid 
is always defined to be
$(-1)^{\text{number of nonzero entries in $T$}}$.

\subhead 3. Preliminaries\endsubhead
In this section we briefly explain the basic ingredients of our
bijections in the next section: the ordinary and shifted
Hillman--Grassl algorithm, a bijection that comes from Stanley's
$(P,\om)$-partition theory, and the involution principle of Garsia
and Milne.

Let $\la$ be a partition of $n$. The ordinary Hillman--Grassl
algorithm \cite{\HiGrAA} sets up a bijection, $\HG$ say, between
reverse plane partitions $P$ of (ordinary) shape $\la$ and tabloids
$S=\HG(P)$ of (ordinary) shape $\la$, such that
$$n(P)=w_h(S),\tag3.1$$
where the hook weight $w_h$ is read in the ordinary sense.
Sagan's shifted Hillman--Grassl algorithm \cite{\SagaAB, sec.~3,4} 
does the same for reverse plane partitions of shifted shape $\la$ and tabloids
of shifted shape $\la$, provided that the hook weight $w_h$ in (3.1)
is now read in the shifted sense.

The second bijection that we need is a bijection, $\SP$ say, between reverse
plane partitions $P$ of shape $\la$ (ordinary, respectively shifted) and
pairs $(Y,\ta)$, where $Y$ is a standard Young tableau of shape $\la$
(ordinary, respectively shifted), and $\ta$ is a partition with at
most $n$ parts. It comes from
\cite{\StanAB, sec.~6}. Given the reverse plane partition $P$, the standard
Young tableaux $Y$ is given by the numbering of the cells of
$\la$ that is determined by reading the entries of $P$
according to size, starting with the smallest entry and going up to
the largest entry, if two entries are equal the one in the higher row
comes first, and if two equal entries are in the same row, the left
entry comes first.
See the examples below. 
The partition $\ta$ is formed in the following way. Consider the entries
of $P$ in the order just described. At
the very beginning (i.e\. when considering the entry in cell
$(1,1)$), $0$ is subtracted from the considered entry. 
Suppose that we subtracted $s$ from the entry considered last. Then
we subtract $s$ from the next
entry to be considered if it is located weakly below the previously
considered entry, otherwise we subtract $s+1$. The partition $\ta$ is
the sequence of all the obtained integers, in reverse order, and
disregarding all $0$'s. For example, under this mapping the reverse
plane partition in Figure~2.a is mapped to $(\text
{Figure~2.c},76665554431)$, and the reverse
plane partition in Figure~2.b is mapped to $(\text
{Figure~2.d},666544444422)$. It is not difficult to check that this
correspondence satisfies
$$n(P)=n(\ta)+\mc(Y).\tag3.2$$

Finally we recall the
involution principle of Garsia and Milne \cite{\GaMiAB} (see also
\cite{\StWhAB, sec.~4.6}). Let $X$ be a finite set with a signed
weight function $w$ defined on it. Furthermore, let $X_L$ and $X_R$ be
subsets of $X$, both of which containing elements with positive sign
only. Suppose that there is a sign-reversing and weight-preserving
involution $i_L$ on $X$ that fixes $X_L$ and a sign-reversing and
weight-preserving involution $i_R$ on $X$ that fixes $X_R$. Then there
must be a weight-preserving bijection between $X_L$ and $X_R$. And such
a bijection can be constructed explicitly by mapping $x\in X_L$ to
$(i_L\circ i_R)^m(x)$ where $m$ is the least integer such that
$(i_L\circ i_R)^m(x)$ is in $X_R$.


\subhead 4. The hook formulas and their bijective proofs\endsubhead
The hook formulas that we are going to prove are the following.
\proclaim{Theorem}Let $\la$ be a partition of $n$. Then, in the
ordinary or shifted sense, there holds
$$\underset \text {shape }\la\to{\sum _{Y\text { a SYT of}}
^{}}q^{\mc(Y)}=\frac {[n][n-1]\cdots[1]} {\prod _{\rh\in\la}
^{}[h_\rh]},\tag4.1$$
where by definition $[k]:=1+q+q^2+\dots+q^{k-1}$. (SYT is short for
`standard Young tableau'.)
\endproclaim
\demo{Proof}Since the formula and all other things that are needed
are stated uniformly for the ordinary {\it and\/} shifted case, also
the proof can be formulated uniformly, i.e\. the following can be
read in the ordinary context or in the shifted context.

First we rewrite (4.1)  in the form
$$[n][n-1]\cdots[1]=
\bigg(\underset \text {shape }\la\to{\sum _{Y\text { a SYT of}}
^{}}q^{\mc(Y)}\bigg)\prod _{\rh\in\la}
^{}[h_\rh].\tag4.2$$
We prove (4.2) by setting up a bijection between the set $O_L$ of all
$(<\#)$-tabloids $T$ of shape $\la$, the generating function $\sum
_{T} ^{}q^{n(T)}$ for which being evidently the left-hand side in
(4.2), and the set $O_R$ of pairs $(Y,\tU)$, where $Y$ is a standard
Young tableau of shape $\la$ and $\tU$ is a $(<h)$-tabloid of shape
$\la$, the generating function $\sum _{(Y,\tU)} ^{}q^{\mc(Y)}q^{n(\tU)}$
for which being evidently the right-hand side of (4.2). We do this by
using the involution principle. Hence, we have to say which choices 
we take for the set $X$, the signed weight $w$, the subsets
$X_L$ and $X_R$, and the involutions $i_L$ and $i_R$. Of course, $O_L$
and $O_R$ should
correspond to $X_L$ and $X_R$, respectively, the latter being subsets of the
bigger set $X$, that has to be described next.

We define $X$ to be the set of all triples $(S,T,U)$, where $S$ is an
arbitrary tabloid of shape $\la$, where $T$ is a $(<\#)$-tabloid of
shape $\la$, and where $U$ is a $(0\text {--}h)$-tabloid of shape
$\la$. The signed weight $w$ on $X$ is defined by
$$w\big((S,T,U)\big)=\sgn (U)\,q^{w_h(S)+n(T)+n(U)}.\tag 4.3$$

We define the set $X_L$ to be the subset of $X$ consisting of all
triples $(\0,T,\0)$, where $\0$ denotes the filling of $\la$ with $0$
in each cell, and where $T$ is an arbitrary $(<\#)$-tabloid of shape
$\la$. Note in particular that the sign of $w\big((\0,T,\0)\big)$
for all these triples is $\sgn(\0)=1$, which is positive. Trivially,
$X_L$ is in bijection with $O_L$.

What the set $X_R$ is going to be is better explained in the course
of the description of the involution $i_R$.

However, first we define the involution $i_L$ that fixes $X_L$. Let
$(S,T,U)$ be a triple in $X$ that is not in $X_L$, i.e\. at least one
of $S$ and $U$ is different from $\0$. Pick the least cell $\rh$ (in
the total order of the cells defined in section~2) in $\la$ such that
$S_\rh\ne0$ or $U_\rh\ne0$. If $U_\rh\ne0$, i.e\. $U_\rh=h_\rh$, then
replace $U_\rh$ by $0$, thus obtaining $\bU$, and add $1$ to $S_\rh$,
thus obtaining $\bS$. If $U_\rh=0$ then
replace $U_\rh$ by $h_\rh$, thus obtaining $\bU$, and subtract $1$
from $S_\rh$, thus obtaining $\bS$. We define $i_L\big((S,T,U)\big)$
to be $(\bS,T,\bU)$. By construction we have
$w\big((S,T,U)\big)=-w\big((\bS,T,\bU)\big)$, as required. It is
obvious that $i_L$ is an involution on $X\backslash X_L$.

Next we define the involution $i_R$. As promised before, the
definition of the set $X_R$ that is fixed by $i_R$ will naturally
appear in the course of the definition of $i_R$.

We partition the set $X$ into two disjoint subsets $X^1$ and $X^2$.
By definition, the set $X^1$ consists of all triples $(S,T,U)$ where
there exists a cell $\rh$ in $\la$ such that
$$h_\rh\le T_\rh+U_\rh<\#\rh.\tag4.4$$
The set $X^2$ is defined to be the complement $X\backslash X^1$. 

Now we define $i_R$ on the subset $X^1$. Let $(S,T,U)$ be a triple in
$X^1$, i.e\. there exists a cell $\rh$ such that (4.4) is satisfied.
We assume that $\rh$ is the least such cell (in the total order
explained in section~2). If $U_\rh=0$ then we replace $U_\rh$ by
$h_\rh$, thus obtaining $\bU$, and we replace $T_\rh$ by
$T_\rh-h_\rh$, thus obtaining $\bT$. If $U_\rh=h_\rh$ then we replace $U_\rh$ by
$0$, thus obtaining $\bU$, and we replace $T_\rh$ by
$T_\rh+h_\rh$, thus obtaining $\bT$. We define $i_L\big((S,T,U)\big)$
to be $(S,\bT,\bU)$. It is obvious that in both cases $(S,\bT,\bU)$
is in $X^1$ again. Besides, there holds
$w\big((S,T,U)\big)=-w\big((S,\bT,\bU)\big)$, as required. Clearly,
$i_R$ thus defined on $X^1$ is an involution on $X^1$.

Next we consider the set $X^2$. Instead of directly working with
these triples, it is more convenient to map them in an intermediate
step by a sign-preserving and weight-preserving bijection, $\ph$ say,
to another set, $\bX^2$ say. By definition, $\bX^2$ is the set of all
quadruples $(Y,\pi,T',U')$, where $Y$ is a standard Young tableau of
shape $\la$, $\pi$ is a partition with all its parts being at most
$n$, $T'$ is a $(0\text {--}\#)$-tabloid, and where $U'$ is a
$(<h)$-tabloid. The signed weight on $\bX^2$ is defined by
$$w\big((Y,\pi,T',U')\big)=\sgn
(T')\,q^{\mc(Y)+n(\pi)+n(T')+n(U')}.\tag4.5$$
The bijection between $X^2$ and $\bX^2$ is defined in the following
way. Let $(S,T,U)$ be an element of $X^2$, i.e\. for all cells $\rh$
in $\la$ the relation (4.4) does not hold. Denote the image of
$(S,T,U)$ under the mapping $\ph$ to be defined by $(Y,\pi,T',U')$.
The pair $(Y,\pi)$ is obtained
by applying first the inverse of the Hillman--Grassl algorithm to the
tabloid $S$, thus obtaining a reverse plane partition $P$, then applying
the map $\SP$ explained in section~3 to this reverse plane partition,
thus obtaining a pair $(Y,\ta)$ consisting of a standard Young tableau
$Y$ and a
partition $\ta$ with at most $n$ parts, and finally mapping the partition
$\ta$
to its conjugate $\pi$, thus obtaining the pair $(Y,\pi)$ consisting
of the standard Young tableau $Y$ and a partition $\pi$ all of
whose parts are at most $n$. Because of (3.1) and (3.2) we have
$$w_h(S)=n(P)=\mc(Y)+n(\ta)=\mc(Y)+n(\pi).\tag4.6$$
Now we turn to the construction of $T'$ and $U'$. $T'$
and $U'$ are obtained by doing the following operation on $T$ and
$U$ for each cell $\rh$ in $\la$. If $U_\rh=0$, then,
since (4.4) does not hold, we must have $T_\rh<h_\rh$. Then we replace
$U_\rh$ by $T_\rh$, and we replace $T_\rh$ by
$0$. If $U_\rh=h_\rh$, then 
we must have $T_\rh+h_\rh=T_\rh+U_\rh\ge\#\rh$. Then
we replace $U_\rh$ by $T_\rh+h_\rh-\#\rh$, and
we replace $T_\rh$ by $\#\rh$. 
It is immediate
from the construction and from (4.6) that this mapping from $X^2$ to $\bX^2$ is
weight-preserving and sign-preserving. Besides, because our
particular total order of the cells implies $h_\rh\le\#\rh$, 
the mapping can be inverted, as is easily checked. Hence it is a bijection.

Now, finally, we are able to say what the set $X_R$ is. It is defined
to be the inverse image (under the mapping $\ph$ from $X^2$ to $\bX^2$
just described) of the set of all quadruples $(Y,\emptyset,\0,U')$,
where $Y$ is a standard Young tableau of shape $\la$, 
$\emptyset$ denotes the empty partition, and where $U'$ is a
$(<h)$-tabloid. Let us denote the latter subset of $\bX^2$ by
$\bO_R$. Observe that the sign of $w\big((Y,\emptyset,\0,U')\big)$ 
for all quadruples
in $\bO_R$ is $\sgn(\0)=1$, which is
positive. Clearly, the set $O_R$ of right-hand side objects of (4.2)
is in bijection with $\bO_R$, and, hence, with $X_R$.

So all what remains is to define a sign-reversing and
weight-preserving involution, $\bi_R$ say, on $\bX^2$ that fixes
$\bO_R$. This is because $i_R$ is then defined as it is on $X^1$, and
on $X^2$ by $\ph^{-1}\circ \bi_R\circ \ph$. Let $(Y,\pi, T',U')$ be
an element of $\bX^2\backslash \bO_R$, i.e\. $\pi$ is a nonempty
partition or $T'$ is nonzero. Let $i$ be the least (positive) integer
such that $i$ occurs as a part in $\pi$ or such that the cell $\rh$
with $\#\rh=i$ has a nonzero entry in $T'$. If $T'_\rh$ is nonzero,
i.e\. $T'_\rh=\#\rh=i$, then we replace $T'_\rh$ by $0$, thus obtaining
$\bT'$, and we add one part of size $i$ to $\pi$, thus obtaining
$\bar \pi$. If $T'_\rh=0$, then we replace $T'_\rh$ by $i=\#\rh$, thus obtaining
$\bT'$, and we remove one part of size $i$ from $\pi$, thus obtaining
$\bar \pi$. We define $\bi_R\big((Y,\pi,T',U')\big)$ to be
$(Y,\bar\pi,\bT',U')$. By construction we have
$w\big((Y,\pi,T',U')\big)=-w\big((Y,\bar\pi,\bT',U')\big)$, as
required. It is easy to check that $\bi_R$ is a sign-reversing and
weight-preserving involution on $\bX^2\backslash \bO_R$. 

This
completes the bijective proof(s) of the hook formula(s) (4.1).
\quad \quad \qed
\enddemo


\subhead 5. The algebra behind\endsubhead
Here we explain where the operations $i_L,i_R,\ph$ of the previous
section come from.

First, it should be observed that the generating function $\sum _{}
^{}\sgn(U)q^{w_h(S)+n(T)+n(U)}$ for all triples $(S,T,U)$ in $X$ is given by
$$\prod _{\rh\in\la} ^{}\frac {1} {1-q^{h_\rh}}\prod _{i=1} ^{n}[i]
\prod _{\rh\in\la} ^{}(1-q^{h_\rh}).\tag5.1$$
Evidently, the involution $i_L$ just models combinatorially 
the cancellation of the two products in (5.1). (What survives after
the cancellation is the
left-hand side of (4.2).)

Next we may rewrite (5.1) as 
$$\prod _{\rh\in\la} ^{}\frac {1} {1-q^{h_\rh}}\prod _{i=1}
^{n}(1-q^i)
\prod _{\rh\in\la} ^{}[h_\rh].\tag5.2$$
What the map $i_R$ on $X^1$ and the subsequent transformation of
$(T,U)$ to $(T',U')$ in the mapping $\ph$ do, is exactly the
combinatorial modelling of the transition from (5.1) to (5.2).

Now, by the Hillman--Grassl algorithm(s) we know that the first product
in (5.2) is the generating function $\sum _{} ^{}q^{n(P)}$ for all
reverse plane partitions $P$ of shape $\la$. Moreover, by Stanley's
$(P,\om)$-partition theorem \cite{\StanAB, Cor.~5.3+7.2} we know that
the same generating function can be written as 
$$\dsize\frac {\dsize\sum _{Y\text { a SYT of shape }\la} ^{}q^{\mc(Y)}} 
{\dsize\prod
_{i=1} ^{n}(1-q^i)}.\tag5.3$$
Substituting this into (5.2) gives that the generating
function\linebreak 
$\sum
_{} ^{}\sgn(U)q^{w_h(S)+n(T)+n(U)}$ for all triples $(S,T,U)$ in $X$ can also
be written as 
$$\underset \text {of shape }\la\to{\sum _{Y\text { a SYT}}} ^{}q^{\mc(Y)}
\prod _{i=1} ^{n}\frac {1} {(1-q^i)}
\prod _{i=1} ^{n}(1-q^i)\prod _{\rh\in\la}
^{}[h_\rh].\tag5.4$$
The
transformation of $S$ into $(Y,\pi)$ in the mapping $\ph$, 
of course, exactly models 
combinatorially the transition from (5.2) to (5.4).
Finally, it is evident that the map $\bi_R$ on $\bX^2\backslash \bO_R$
just models combinatorially 
the cancellation of the second and third factor in (5.4).
(What survives after the cancellation is the right-hand side of
(4.2).)

\remark{Acknowledgement} This work was carried out while the author
visited the University of California at San Diego. He thanks the
University of California and in particular Adriano Garsia for making
this visit possible. Besides, he is indebted to Adriano Garsia for
drawing his attention to the problem of finding ``nice" combinatorial
proofs of hook formulas, and to Jeff Remmel who suggested
that the above ideas should also work for the shifted hook formula.
\endremark

\vskip10pt
\noindent\eightpoint\it e-mail: KRATT\@Pap.Univie.Ac.At
\vskip10pt

\Refs

\ref\no \FrRTAA\by J. S. Frame, G. B. Robinson and R. M. Thrall \yr 1954 
\paper The hook graphs of the symmetric group
\jour Canad\. J. Math\.\vol 6
\pages 316--325\endref

\ref\no \FbZeAA\by D. S. Franzblau and D.    Zeilberger \yr 1982 
\paper A bijective proof of the hook-length formula
\jour J. Algorithms\vol 3
\pages 317--343\endref

\ref\no \GaMiAB\by A. M. Garsia and S. C. Milne \yr 1981 
\paper Method for constructing bijections for classical partition identities
\jour Proc\. Nat\. Acad\. Sci\. U.S.A.\vol 78
\pages 2026--2028\endref

\ref\no \GeViAA\by I. M. Gessel and X. Viennot \yr 1985 
\paper Binomial determinants, paths, and hook length formulae
\jour Adv\. in Math\. \vol 58
\pages 300---321\endref

\ref\no \GeViAB\by I. M. Gessel and X. Viennot \yr 1989 
\paper Determinants, paths, and plane partitions 
\paperinfo preprint\endref

\ref\no \GrNWAA\by C.    Greene, A. Nijenhuis and H. S. Wilf \yr 1979 
\paper A probabilistic proof of a formula for the number of Young tableaux of a given shape
\jour Adv\. in Math\.\vol 31
\pages 104--109\endref

\ref\no \HiGrAA\by A. P. Hillman and R. M. Grassl \yr 1976 
\paper Reverse plane partitions and tableau hook numbers
\jour J. Combin\. Theory Ser.~A\vol 21
\pages 216--221\endref

\ref\no \LaScAE\by A.    Lascoux and M.-P. Sch\"utzenberger \yr 1981 
\paper Le mono\"ide plaxique
\inbook Noncommutative structures in algebra and geometric combinatorics\ed A.~de Luca
\publ Quaderni della Ricerca Scientifica del C.~N.~R.
\publaddr Roma
\pages 129--156\endref

\ref\no \MacdAB\by I. G. Macdonald \yr 1979 
\book Symmetric Functions and Hall Polynomials 
\publ Oxford University Press
\publaddr New York/Lon\-don\endref

\ref\no \RemmAD\by J. B. Remmel \yr 1982 
\paper Bijective proofs of formulae for the number of standard Young tableaux
\jour Linear and Multilinear Alg\.\vol 11
\pages 45--100\endref

\ref\no \SagaAB\by B. E. Sagan \yr 1982 
\paper Enumeration of partitions with hooklengths
\jour Europ\. J. Combin\.\vol 3
\pages 85--94\endref

\ref\no \StanAB\by R. P. Stanley \yr 1972 
\book Ordered structures and partitions 
\bookinfo Mem\. Amer\. Math\. Soc\. No.~119
\publ American Mathematical Society
\publaddr Providence, R.~I.\endref

\ref\no \StWhAB\by D.    Stanton and D. White \yr 1986 
\book Constructive Combinatorics
\bookinfo Undergraduate Texts in Math\.
\publ Sprin\-ger--Ver\-lag
\publaddr New York, Berlin Heidelberg, Tokyo\endref

\ref\no \ZeilAE\by D.    Zeilberger \yr 1984 
\paper A short hook-lengths bijection inspired by the Greene--Nijenhuis--Wilf proof
\jour Discrete Math\.\vol 51
\pages 101--108\endref

\endRefs
\enddocument
