%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 Verfgung: %\DuennPunkt, \NormalPunkt, \DickPunkt. Eingabe: % \DickPunkt(x-Koordinate,y-Koordinate), etc. % %Weiters steht mit \Kreis ein Kreis zur Verfgung. 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 $(