\documentclass[12pt]{article}

\usepackage{epsfig,amsmath,amsfonts}
\input texdraw

\textwidth137mm
\textheight200mm

\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}

%Christian's texdraw definitions
\def\ldreieck{\bsegment
  \rlvec(0.866025403784439 .5) \rlvec(0 -1)
  \rlvec(-0.866025403784439 .5)  
  \savepos(0.866025403784439 -.5)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }
\def\rdreieck{\bsegment
  \rlvec(0.866025403784439 -.5) \rlvec(-0.866025403784439 -.5)  \rlvec(0 1)
  \savepos(0 -1)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }
\def\rhombus{\bsegment
  \rlvec(0.866025403784439 .5) \rlvec(0.866025403784439 -.5) 
  \rlvec(-0.866025403784439 -.5)  \rlvec(0 1)        
  \rmove(0 -1)  \rlvec(-0.866025403784439 .5) 
  \savepos(0.866025403784439 -.5)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }
\def\RhombusA{\bsegment
  \rlvec(0.866025403784439 .5) \rlvec(0.866025403784439 -.5) 
  \rlvec(-0.866025403784439 -.5) \rlvec(-0.866025403784439 .5) 
  \savepos(0.866025403784439 -.5)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }
\def\RhombusB{\bsegment
  \rlvec(0.866025403784439 .5) \rlvec(0 -1)
  \rlvec(-0.866025403784439 -.5) \rlvec(0 1) 
  \savepos(0 -1)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }
\def\RhombusC{\bsegment
  \rlvec(0.866025403784439 -.5) \rlvec(0 -1)
  \rlvec(-0.866025403784439 .5) \rlvec(0 1) 
  \savepos(0.866025403784439 -.5)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }
\def\RhombusAsh{\bsegment
  \rlvec(0.866025403784439 .5) \rlvec(0.866025403784439 -.5) 
  \rlvec(-0.866025403784439 -.5) \rlvec(-0.866025403784439 .5) 
  \lfill f:.8
  \savepos(0.866025403784439 -.5)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }
\def\RhombusBsh{\bsegment
  \rlvec(0.866025403784439 .5) \rlvec(0 -1)
  \rlvec(-0.866025403784439 -.5) \rlvec(0 1) 
  \lfill f:0.2
  \savepos(0 -1)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }
\def\RhombusCsh{\bsegment
  \rlvec(0.866025403784439 -.5) \rlvec(0 -1)
  \rlvec(-0.866025403784439 .5) \rlvec(0 1) 
  \savepos(0.866025403784439 -.5)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }
\def\hdSchritt{\bsegment
  \lpatt(.05 .13)
  \rlvec(0.866025403784439 -.5) 
  \savepos(0.866025403784439 -.5)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }
\def\vdSchritt{\bsegment
  \lpatt(.05 .13)
  \rlvec(0 -1) 
  \savepos(0 -1)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }

\def\odSchritt{\bsegment
  \lpatt(.05 .13)
  \rlvec(-0.866025403784439 -.5) 
  \savepos(-0.866025403784439 -.5)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }


\def\hdaSchritt{\bsegment
  \lpatt(.05 .13)
  \rlvec(-0.866025403784439 .5) 
  \savepos(-0.866025403784439 .5)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }
\def\vdaSchritt{\bsegment
  \lpatt(.05 .13)
  \rlvec(0 1) 
  \savepos(0 1)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }

\def\odaSchritt{\bsegment
  \lpatt(.05 .13)
  \rlvec(0.866025403784439 .5) 
  \savepos(0.866025403784439 .5)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }



\def\hhdSchritt{\bsegment
  \lpatt(.05 .13)
  \rlvec(0.4330127 -.25) 
  \savepos(0.4330127 -.25)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }

\def\hvdSchritt{\bsegment
  \lpatt(.05 .13)
  \rlvec(0 -.5) 
  \savepos(0 -.5)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }

\def\hodSchritt{\bsegment
  \lpatt(.05 .13)
  \rlvec(-0.4330127 -.25) 
  \savepos(-0.4330127 -.25)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }


\def\hhdaSchritt{\bsegment
  \lpatt(.05 .13)
  \rlvec(-0.4330127 .25) 
  \savepos(-0.4330127 .25)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }

\def\hvdaSchritt{\bsegment
  \lpatt(.05 .13)
  \rlvec(0 .5) 
  \savepos(0 .5)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }

\def\hodaSchritt{\bsegment
  \lpatt(.05 .13)
  \rlvec(0.4330127 .25) 
  \savepos(0.4330127 .25)(*ex *ey)
        \esegment
  \move(*ex *ey)
        }


\def\ringerl(#1 #2){\move(#1 #2)\fcir f:0 r:.1}

\def\bondA{\bsegment\ringerl(0 0)
\rlvec(0.57735 0) \ringerl(0.57735 0)
\esegment}
\def\bondB{\bsegment\ringerl(0 0)
\rlvec(0.2886751347 0.5) \ringerl(0.2886751347 0.5)
\esegment}
\def\bondC{\bsegment\ringerl(0 0)
\rlvec(-0.2886751347 0.5) \ringerl(-0.2886751347 0.5)
\esegment}

\def\hex{\bsegment
	\rlvec(0.5773502693 0)  
        \rlvec(0.2886751347 -.5) \rlvec(-0.2886751347 -.5)
	\rlvec(-0.5773502693 0) \rlvec(-0.2886751347 .5) 
        \rlvec(0.2886751347 .5)
	\savepos(0.8660254040 -.5)(*ex *ey)
	 \esegment
	\move(*ex *ey)
}

\def\shex{\bsegment 
	\lpatt(.05 .13)
	\rlvec(1 0)  \rlvec(.5 -.866025403784439) \rlvec(-.5 -.866025403784439)
	\rlvec(-1 0) \rlvec(-.5 .866025403784439) \rlvec(.5 .866025403784439)
	\savepos(1.5 -.866025403784439)(*ex *ey)
	 \esegment
	\move(*ex *ey)
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%               PATHS.TEX: Begonnen am 16. Juli 1993                       %
% Dieses kleine Macropaket soll einfache Befehle zum Zeichnen von Gittern  %
% und Gitterpunktwegen einfuehren. (Fuer AMSLaTeX!)                        %
% Wesentlich ueberarbeitet und gestrafft am 1. Mai 1994.                   %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Fonts:                                                                   %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\font\scalefont = cmti8
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Basic parameters:                                                        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\unitlength = 5mm					% instead of 4 mm
\thicklines

\newcount\xmin                % coordinates of extremal points of the grid
\newcount\xmax
\newcount\ymin
\newcount\ymax

\newcount\gridwidth
\newcount\gridheight

\newcount\nofxpoints          % number of points in horizontal direction
\newcount\nofypoints          % number of points in vertical direction

\newcount\dcnta               % dummy-counter A
\newcount\dcntb               % dummy-counter B

% Special macros for drawing a grid with lower left corner (xmin, ymin)
% and upper right corner (xmax, ymax):
\def\begingrid#1#2#3#4{			% arguments: xmin, ymin, xmax, ymax
	\global\xmin = #1
	\global\ymin = #2
	\global\xmax = #3
	\global\ymax = #4
	% simple test:
	\ifnum\xmin > \xmax\errmessage{PATHS: \xmin > \xmax|}\fi
	\ifnum\ymin > \ymax\errmessage{PATHS: \ymin > \ymax|}\fi
	% computation of heigth and width
	\gridwidth = \xmax
	\gridheight = \ymax
	\advance\gridwidth by -\xmin
	\advance\gridheight by -\ymin
	\nofxpoints = \gridwidth
	\advance\nofxpoints by 1
	\nofypoints = \gridheight
	\advance\nofypoints by 1
	% adjust some space around the picture
	\advance\gridwidth by 4
	\advance\gridheight by 4
	\advance\xmin by -2
	\advance\ymin by -2
	% LaTeX's picture command
	\begin{picture}(\gridwidth, \gridheight)(\xmin, \ymin)
	% restore correct the lengths
	\advance\gridwidth by -4
	\advance\gridheight by -4
	\advance\xmin by 2
	\advance\ymin by 2
	% for debugging
	% \message{PATHS: width \number\gridwidth, height \number\gridheight; %
	% at (\number\xmin, \number\ymin)}
	% draw gridpoints:
	\global\dcnta = \ymin
	\loop\ifnum\dcnta<\ymax
		\makegridline\dcnta	% do inner loop in a separate macro
		\global\advance\dcnta by 1
	\repeat
	\makegridline\ymax
}
 
% inner loop of grid-drawing procedure
\def\makegridline#1{
   \begingroup
   \global\dcntb = \xmin
   \loop\ifnum\dcntb<\xmax
      \put(\dcntb, #1){\circle*{0.1}}
      \global\advance\dcntb by 1
   \repeat
   \put(\xmax, #1){\circle*{0.1}}
   \endgroup
}
 
% draw axes
\def\makexaxis{\thinlines
        \dcnta = \gridwidth
        \advance\dcnta by 1
        \put(\xmin, 0){\vector(1,0){\dcnta}}
        \thicklines
}
\def\makeyaxis{\thinlines
        \dcntb = \gridheight
        \advance\dcntb by 1
        \put(0, \ymin){\vector(0,1){\dcntb}}
        \thicklines
}
\def\makeaxes{\thinlines
        \dcnta = \gridwidth
        \advance\dcnta by 1
        \put(\xmin, 0){\vector(1,0){\dcnta}}
        \dcntb = \gridheight
        \advance\dcntb by 1
        \put(0, \ymin){\vector(0,1){\dcntb}}
        \thicklines
}
 
% scaling on axes
\def\makexscale{
   \dcnta = \xmin
	\ifnum\dcnta<-9\dcnta=-9\fi
   \loop\ifnum\dcnta<0
		\put(\dcnta,0){\line(0,-1){0.2}}
      \put(\dcnta,-0.5){\makebox(0,0){
		{\scalefont\number\dcnta}}}
      \advance\dcnta by 1
  \repeat
  \dcnta = 1
  \dcntb=\xmax
  \ifnum\dcntb>9\dcntb=9\fi
  \loop\ifnum\dcnta<\dcntb
      \put(\dcnta,0){\line(0,-1){0.2}}
      \put(\dcnta, -0.5){\makebox(0,0){
		{\scalefont\number\dcnta}}}
      \advance\dcnta by 1
  \repeat
  \put(\dcntb,0){\line(0,-1){0.2}}
  \put(\dcntb, -0.4){\makebox(0,0){{\scalefont\number\dcntb}}}
}
\def\makeyscale{
   \dcnta = \ymin
   \loop\ifnum\dcnta<0
      \put(0,\dcnta){\line(-1,0){0.2}}
      \put(-0.4, \dcnta){\makebox(0,0){
		{\scalefont\number\dcnta}}}
      \advance\dcnta by 1
   \repeat
   \dcnta = 1
   \loop\ifnum\dcnta<\ymax
      \put(0,\dcnta){\line(-1,0){0.2}}
      \put(-0.4, \dcnta){\makebox(0,0){
		{\scalefont\number\dcnta}}}
      \advance\dcnta by 1
   \repeat
   \put(-0.4, \ymax){\makebox(0,0){{\scalefont\number\ymax}}}
}

% macros for drawing skew dotted lines
\newsavebox{\skewdowndottedbox}
\newsavebox{\skewupdottedbox}
\savebox{\skewdowndottedbox}(1,1)[lb]{
	\put(0.2,-0.2){\circle*{0.01}}
   \put(0.4,-0.4){\circle*{0.01}}
 	\put(0.6,-0.6){\circle*{0.01}}
	\put(0.8,-0.8){\circle*{0.01}}
}
\savebox{\skewupdottedbox}(1,1)[lb]{
	\put(0.2,0.2){\circle*{0.01}}
   \put(0.4,0.4){\circle*{0.01}}
 	\put(0.6,0.6){\circle*{0.01}}
	\put(0.8,0.8){\circle*{0.01}}
}
\def\downskewline#1#2#3{
	\multiput(#1,#2)(1,-1){#3}{\usebox{\skewdowndottedbox}}
}
\def\upskewline#1#2#3{
	\multiput(#1,#2)(1,1){#3}{\usebox{\skewupdottedbox}}
}

% Special macros for drawing lattice paths:
\newsavebox{\hplainbox}
\savebox{\hplainbox}{\put(0,0){\line(1,0){1}}}
\newsavebox{\hdottedbox}
\savebox{\hdottedbox}(1,0)[bl]{
	\put(0.2,0){\circle*{0.01}}
	\put(0.4,0){\circle*{0.01}}
	\put(0.6,0){\circle*{0.01}}
	\put(0.8,0){\circle*{0.01}}
}
\newsavebox{\vplainbox}
\savebox{\vplainbox}{\put(0,0){\line(0,1){1}}}
\newsavebox{\vdottedbox}
\savebox{\vdottedbox}(0,1)[bl]{
	\put(0,0.2){\circle*{0.01}}
	\put(0,0.4){\circle*{0.01}}
	\put(0,0.6){\circle*{0.01}}
	\put(0,0.8){\circle*{0.01}}
}
\newsavebox{\vplaindownbox}
\savebox{\vplaindownbox}{\put(0,0){\line(0,-1){1}}}
\newsavebox{\vdotteddownbox}
\savebox{\vdotteddownbox}(0,1)[bl]{
	\put(0,-0.2){\circle*{0.01}}
	\put(0,-0.4){\circle*{0.01}}
	\put(0,-0.6){\circle*{0.01}}
	\put(0,-0.8){\circle*{0.01}}
}
\newsavebox{\skewupbox}
\savebox{\skewupbox}{\put(0,0){\line(1,1){1}}}
\newsavebox{\skewdownbox}
\savebox{\skewdownbox}{\put(0,0){\line(1,-1){1}}}
\newsavebox{\hstep}		% horizontal step
\newsavebox{\vstep}		% vertical step
\newsavebox{\sstep}		% skew step
\newcount\updownincrement
\def\uppath#1#2#3{
	\savebox{\hstep}{\usebox{\hplainbox}}
	\savebox{\vstep}{\usebox{\vplainbox}}
	\savebox{\sstep}{\usebox{\skewupbox}}
	\updownincrement=1
	\dcnta=#1
	\dcntb=#2
	\thickpoint{\dcnta}{\dcntb}
	\dosteplist#3\endList
	\thickpoint{\dcnta}{\dcntb}
}
\def\updottedpath#1#2#3{
	\savebox{\hstep}{\usebox{\hdottedbox}}
	\savebox{\vstep}{\usebox{\vdottedbox}}
	\savebox{\sstep}{\usebox{\skewupdottedbox}}
	\updownincrement=1
	\dcnta=#1
	\dcntb=#2
	\thickcircle{\dcnta}{\dcntb}
	\dosteplist#3\endList
	\thickcircle{\dcnta}{\dcntb}
}
\def\downpath#1#2#3{
	\savebox{\hstep}{\usebox{\hplainbox}}
	\savebox{\vstep}{\usebox{\vplaindownbox}}
	\savebox{\sstep}{\usebox{\skewdownbox}}
	\updownincrement=-1
	\dcnta=#1
	\dcntb=#2
	\thickpoint{\dcnta}{\dcntb}
	\dosteplist#3\endList
	\thickpoint{\dcnta}{\dcntb}
}
\def\downdottedpath#1#2#3{
	\savebox{\hstep}{\usebox{\hdottedbox}}
	\savebox{\vstep}{\usebox{\vdotteddownbox}}
	\savebox{\sstep}{\usebox{\skewdowndottedbox}}
	\updownincrement=-1
	\dcnta=#1
	\dcntb=#2
	\thickcircle{\dcnta}{\dcntb}
	\dosteplist#3\endList
	\thickcircle{\dcnta}{\dcntb}
}
%\def\endList{\endList}
\def\dosteplist{\afterassignment\handlenextstep\let\next=}
\def\handlenextstep{
	\ifx\next\endList
   	\let\next=\relax
	\else
		\ifx\next-
			\put(\dcnta,\dcntb){\usebox{\hstep}}
			\advance\dcnta by 1
		\else
			\ifx\next|
				\put(\dcnta,\dcntb){\usebox{\vstep}}
				\advance\dcntb by\updownincrement
			\else
				\ifx\next/
					\put(\dcnta,\dcntb){\usebox{\sstep}}
					\advance\dcnta by 1
					\advance\dcntb by\updownincrement
				\else
					\errmessage{PATHS: Wrong symbol path argument.}
				\fi
			\fi
		\fi
		\let\next=\dosteplist
	\fi
	\next
}
 
% draw thick point:
\def\thickpoint#1#2{\put(#1, #2){\circle*{0.4}}}

% draw thick circle
\def\thickcircle#1#2{\put(#1, #2){\circle{0.4}}}

% label thick point above or below:
\def\labelpointal#1#2#3{							% above, to the left
	\put(#1,#2){
		\begin{picture}(1,1)(0,0)
			\put(-0.85,0.35){$\scriptstyle #3$}
		\end{picture}
	}
}

\def\labelpointar#1#2#3{							% above, to the right
	\put(#1,#2){
		\begin{picture}(1,1)(0,0)
			\put(-0.15,0.35){$\scriptstyle #3$}
		\end{picture}
	}
}

\def\labelpointbl#1#2#3{							% below, to the left
	\put(#1,#2){
		\begin{picture}(1,1)(0,0)
			\put(-0.85,-0.8){$\scriptstyle #3$}
		\end{picture}
	}
}

\def\labelpointbr#1#2#3{							% below, to the right
	\put(#1,#2){
		\begin{picture}(1,1)(0,0)
			\put(-0.15,-0.8){$\scriptstyle #3$}
		\end{picture}
	}
}

% label horizontal steps
\def\hlabel#1#2#3{\put(#1,#2){\makebox(1,0.6){\scalefont #3}}}
 
\def\endgrid{\end{picture}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  TABLEAUX.TEX: Begonnen am 20. Juli 1993                                 %
% Dieses kleine Macropaket soll einfache Befehle zur Darstellung von       %
% Tableaux  einfuehren. (Nur fuer AMSLaTeX|)                               %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcount\rowcount
\newcount\columncount

\def\begintableau#1#2{									% rows, columns
\global\rowcount=#1
\begin{picture}(#2,#1)(0,0)
\linethickness{0.1pt}
% \put(0,0){\line(0,1){#1}}
% \put(0,#1){\line(1,0){#2}}
}

\def\endtableau{\end{picture}}

\def\row#1{
	\global\advance\rowcount by -1
	\global\columncount=0
	\dorowlist#1\endList
}

%\def\endList{\endList}

\def\dorowlist{\afterassignment\handlenextentry\let\next=}

\def\handlenextentry{
	\ifx\next\endList
		\let\next=\relax
	\else
		\ifx\next o
			\put(\columncount,\rowcount){\framebox(1,1){\space}}
			\global\advance\columncount by 1
		\else
			\ifx\next-
				% \put(\columncount,\rowcount){\framebox(1,1){\space}}
				\global\advance\columncount by 1
			\else
				\put(\columncount,\rowcount){\framebox(1,1){$\next$}}
				\global\advance\columncount by 1
			\fi
		\fi
		\let\next=\dorowlist
	\fi
	\next
}

\newcount\ca
\newcount\cb
\def\printrow#1#2{
	\global\ca=0
	\global\cb=#1
	\doprintrowlist#2\endList
}

\def\doprintrowlist{\afterassignment\handlenextprintentry\let\next=}

\def\handlenextprintentry{
	\ifx\next\endList
		\let\next=\relax
	\else
		\put(\ca,\cb){\makebox(1,1){$\scriptstyle\next$}}
		\global\advance\ca by 1
		\let\next=\doprintrowlist
	\fi
	\next
}



%%%@@@ end input from tableaux
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Input-Datei zum Erzeugen von Gitterpunktwegen.%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%LaTeX-Version%
%%%%%%%%%%%%%%%
%entering a path: 
%  \Pfad(x-coordinate of starting point,y-coordinate of starting point),path
%  as 1-2-3-4-5-6-7-8-word\endPfad
%(1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, 4=downward diagonal step)
%(5=step in negative x-direction, 6=step in negative y-direction, 7=downward left diagonal step, 8=upward left diagonal step)
%
%entering a dotted path: 
%  \SPfad(x-coordinate of starting point,y-coordinate of starting point),path
%  as 1-2-3-4-5-6-7-8-word\endSPfad
%(1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, 4=downward diagonal step)
%(5=step in negative x-direction, 6=step in negative y-direction, 7=downward left diagonal step, 8=upward left diagonal step)
%
%coordinate-axes:
%  \Koordinatenachsen(length of positive x-axes, length of positive y-axes)(length of negative x-axes, length of negative y-axes)
%The length of negative axes are entered as negative numbers.
%
%lattice:
%  \Gitter(number of points in positive x-direction, number of points in positive y-direction)(number of points in negative x-direction, number of points in negative y-direction)
%
%diagonal lines:
%  \Diagonale(x-coordinate of SW-most point,y-coordinate of SW-most point)length of the projection on the x-axes
%
%antidiagonal lines:
%  \AntiDiagonale(x-coordinate of NW-most point,y-coordinate of NW-most point)length of the projection on the x-axes
%
%labelling of points:
%  \Label[location?]{[label]}(x-coordinate,y-coordinate)
%where:
%  [location?]=\l,\lo,\lu,\r,\ro,\ru,\o,\u
%and l=left, r=right, u=bottom, o=top.
%In addition, if by \Einheit?cm the basic unit is changed, there exist
%\llo,\loo,\llu,\luu,\rro,\roo,\rru,\ruu.
%
%The basic unit can be changed by entering
%  \Einheit=?cm
%The default is \Einheit=0.5cm.
%
%The thickness of the paths can be changed by entering
%     \PfadDicke{?cm}
%The default is \PfadDicke=1pt.
%
%The following point sizes are available:
%\DuennPunkt, \NormalPunkt, \DickPunkt. Syntax:
%  \DickPunkt(x-coordinate,y-coordinate), etc.
%
%Besides, a circle is available by \Kreis. Syntax:
%  \Kreis(x-coordinate,y-coordinate)
%
\catcode`\@=11
\font\tenln    = line10
\font\tenlnw   = linew10

\thinlines
\newskip\Einheit \Einheit=0.6cm
\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\scriptsize$\bullet$\hss}}}
\def\DuennPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-2.5pt\hbox to0pt{\hss\normalsize$\bullet$\hss}\hss}}
\def\NormalPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-3pt\hbox to0pt{\hss\large$\bullet$\hss}\hss}}
\def\DickPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-4pt\hbox to0pt{\hss\Large$\bullet$\hss}\hss}}
\def\Kreis(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-4pt\hbox to0pt{\hss\Large$\circ$\hss}\hss}}
\def\Diagonale(#1,#2)#3{\unskip\leavevmode
  \xcoord#1\relax \ycoord#2\relax
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,1){#3}\hss}}
\def\AntiDiagonale(#1,#2)#3{\unskip\leavevmode
  \xcoord#1\relax \ycoord#2\relax \advance\xcoord by -0.05\relax
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,-1){#3}\hss}}
\def\Pfad(#1,#2),#3\endPfad{\unskip\leavevmode
  \xcoord#1 \ycoord#2 \thicklines\ZeichnePfad#3\endPfad\thinlines}
\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\ifnum#1=2
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
        \hbox{\hskip-\PfadD@cke\vrule height1 \Einheit width\PfadD@cke depth0pt}\hss}%
      \advance\ycoord by 1
    \else\ifnum#1=3
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,1){1}\hss}
      \advance\xcoord by 1
      \advance\ycoord by 1
    \else\ifnum#1=4
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,-1){1}\hss}
      \advance\xcoord by 1
      \advance\ycoord by -1
    \else\ifnum#1=5
      \advance\xcoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \vrule height\Pfadd@cke width1 \Einheit depth\Pfadd@cke\hss}%
    \else\ifnum#1=6
      \advance\ycoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
        \hbox{\hskip-\PfadD@cke\vrule height1 \Einheit width\PfadD@cke depth0pt}\hss}%
    \else\ifnum#1=7
      \advance\xcoord by -1
      \advance\ycoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,1){1}\hss}
    \else\ifnum#1=8
      \advance\xcoord by -1
      \advance\ycoord by +1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,-1){1}\hss}
    \fi\fi\fi\fi
    \fi\fi\fi\fi
  \fi\next}
\def\hSSchritt{\leavevmode\raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit}
\def\vSSchritt{\vbox{\baselineskip.2\Einheit\lineskiplimit0pt
\hbox{.}\hbox{.}\hbox{.}\hbox{.}\hbox{.}}}
\def\DSSchritt{\leavevmode\raise-.4pt\hbox to0pt{%
  \hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.2\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.4\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.6\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.8\Einheit\hbox to0pt{\hss.\hss}\hss}}
\def\dSSchritt{\leavevmode\raise-.4pt\hbox to0pt{%
  \hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.2\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.4\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.6\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.8\Einheit\hbox to0pt{\hss.\hss}\hss}}
\def\SPfad(#1,#2),#3\endSPfad{\unskip\leavevmode
  \xcoord#1 \ycoord#2 \ZeichneSPfad#3\endSPfad}
\def\ZeichneSPfad#1{\ifx#1\endSPfad\let\next\relax
  \else\let\next\ZeichneSPfad
    \ifnum#1=1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \hSSchritt\hss}%
      \advance\xcoord by 1
    \else\ifnum#1=2
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
        \hbox{\hskip-2pt \vSSchritt}\hss}%
      \advance\ycoord by 1
    \else\ifnum#1=3
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \DSSchritt\hss}
      \advance\xcoord by 1
      \advance\ycoord by 1
    \else\ifnum#1=4
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \dSSchritt\hss}
      \advance\xcoord by 1
      \advance\ycoord by -1
    \else\ifnum#1=5
      \advance\xcoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \hSSchritt\hss}%
    \else\ifnum#1=6
      \advance\ycoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
        \hbox{\hskip-2pt \vSSchritt}\hss}%
    \else\ifnum#1=7
      \advance\xcoord by -1
      \advance\ycoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \DSSchritt\hss}
    \else\ifnum#1=8
      \advance\xcoord by -1
      \advance\ycoord by 1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \dSSchritt\hss}
    \fi\fi\fi\fi
    \fi\fi\fi\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\llo{\advance\xdim by-.25cm \advance\ydim by.5 \Einheit}%
  \def\loo{\advance\xdim by-.5 \Einheit \advance\ydim by.25cm}%
  \def\o{\advance\ydim by.25cm}%
  \def\ro{\advance\xdim by.5 \Einheit \advance\ydim by.5 \Einheit}%
  \def\rro{\advance\xdim by.25cm \advance\ydim by.5 \Einheit}%
  \def\roo{\advance\xdim by.5 \Einheit \advance\ydim by.25cm}%
  \def\l{\advance\xdim by-.30cm}%
  \def\r{\advance\xdim by.30cm}%
  \def\lu{\advance\xdim by-.5 \Einheit \advance\ydim by-.6 \Einheit}%
  \def\llu{\advance\xdim by-.25cm \advance\ydim by-.6 \Einheit}%
  \def\luu{\advance\xdim by-.5 \Einheit \advance\ydim by-.30cm}%
  \def\u{\advance\ydim by-.30cm}%
  \def\ru{\advance\xdim by.5 \Einheit \advance\ydim by-.6 \Einheit}%
  \def\rru{\advance\xdim by.25cm \advance\ydim by-.6 \Einheit}%
  \def\ruu{\advance\xdim by.5 \Einheit \advance\ydim by-.30cm}%
  #1\raise\ydim\hbox to0pt{\hskip\xdim
     \vbox to0pt{\vss\hbox to0pt{\hss$#2$\hss}\vss}\hss}%
}
\catcode`\@=12

\def\Line(#1,#2)(#3,#4)#5{\unskip\leavevmode
  \xcoord#1\relax \ycoord#2\relax
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
  \line(#3,#4){#5}\hss}
  }
\def\Arrow(#1,#2)(#3,#4)#5{\unskip\leavevmode
  \xcoord#1\relax \ycoord#2\relax
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
  \vector(#3,#4){#5}\hss}
  }

\let\vv\v
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\Ga{\Gamma}
\def\de{\delta}
\def\la{\lambda}
\def\et{\eta}
\def\si{\sigma}
\def\A{{\mathcal A}}
\def\B{{\mathcal B}}
\def\C{{\mathcal C}}
\def\D{{\mathcal D}}
\def\P{{\mathcal P}}
\def\Bau{\mathcal B}
\def\Rel{\mathcal R}
\def\Monomer{\mathcal M}
\def\Dimer{\mathcal D}
\def\({\left(}
\def\){\right)}
\def\fix{\operatorname{fix}}
\def\sgn{\operatorname{sgn}}
\def\Pf{\operatorname{Pf}}
\def\GF{\operatorname{GF}}

\begin{document}

\title{Combinatorics}
\author{C. Krattenthaler}
\date{}

\maketitle


\section{Introduction} \label{sec:Intro}

Combinatorics is a vast field which enters particularly in a crucial
way in Statistical Physics. There, it is particularly enumerative
problems which are of importance. Therefore, in this article, we shall
mainly concentrate on the enumerative aspects of Combinatorics.
Section~\ref{sec:basic} will recall the basic terminology, 
in particular the basic combinatorial objects and numbers,
together with the simplest facts about them.
The next six sections will then provide introductions into
the most important techniques of enumeration:
the generating function technique (see Section~\ref{sec:GF}),
Redfield--P\'olya theory (see Section~\ref{sec:Polya}),
methods of solving functional equations of combinatorial origin
(see Section~\ref{sec:kernel}), methods of asymptotic enumeration
(see Section~\ref{sec:GFasy}), the theory of heaps
(see Section~\ref{sec:heaps}), and the transfer matrix
method (see Section~\ref{sec:transfer}).
The subsequent sections then discuss specific problem circles 
with relation to Statistical Physics more closely.
Section~\ref{sec:paths} discusses lattice path problems,
Section~\ref{sec:Kast} explains Kasteleyn's method of enumerating
perfect matchings and tilings, Section~\ref{sec:nonint} presents
the fundamental theorems on non-intersecting paths,
and Sections~\ref{sec:PP} and \ref{sec:ASM} provide an introduction
into the research field involving 
vicious walkers, plane partitions, rhombus tilings, 
alternating sign matrices, six vertex configurations,
and fully packed loop configurations.
Finally, in Section~\ref{sec:binomial}, it is explained how
one should treat binomial and hypergeometric series, which frequently arise
in enumeration problems.

\section{Basic combinatorial terminology} \label{sec:basic}

In this section we review basic combinatorial notions and facts.
The reader finds a more detailed treatment and further results, 
for example, in \cite[Ch.~1]{StanAP}.

The basic combinatorial choice problems, and their solutions, are:
There are $2^n$ subsets of an $n$-element set. There are $\binom nk$
$k$-element subsets of an $n$-element set. 
Given an alphabet $\mathcal A=\{a_1,a_2,\dots\}$, a {\it word\/} is a
(finite or infinite) sequence of elements of $\mathcal A$. Usually, a
finite word is written in the form $w_1w_2\dots w_n$ (with $w_i\in\mathcal A$).
Out of the letters $\{1,2,\dots,k\}$, 
one can build $k^n$ words of length $n$. 
Out of the letters $\{1,2,\dots,k\}$, 
one can build $\binom {n+k-1}n$ increasing sequences of length $n$.
The number of permutations of an $n$-element set is $n!$.
The set of permutations of $\{1,2,\dots,n\}$ is denoted by $\mathfrak S_n$.
The number of permutations of an $n$-element set with exactly $k$ cycles is the 
{\it Stirling number of the first kind} $s(n,k)$. These
numbers are given as
the expansion coefficients of falling factorials,
$$x(x-1)\cdots(x-n+1)=
\sum _{k=0} ^{n}(-1)^{n-k}s(n,k)\,x^k,$$
or in form of the double (formal) power series
$$
\sum _{n,k\ge0} ^{}s(n,k)x^k\frac {y^n} {n!}=(1+y)^x.$$
A {\it partition of a set} is a collection of pairwise disjoint
subsets the union of which is the complete set. The subsets in the
collection are called the {\it blocks} of the partition.
The total number of
partitions of an $n$-element set is the {\it Bell number} $B_n$. These
numbers are given by
$$
\sum _{n\ge0} ^{}B_n\frac {x^n} {n!}=e^{e^x-1}.$$
The number of partitions of an $n$-element set into exactly $k$ blocks
is the {\it Stirling number of the second kind} $S(n,k)$. 
These numbers are given by
$$
\sum _{n,k\ge0} ^{}S(n,k)x^k\frac {y^n} {n!}=e^{x(e^y-1)},$$
or, explicitly, by
$$S(n,k)=\frac {1} {k!}
\sum _{j=0} ^{k}(-1)^{k-j}\binom kjj^n.$$
A {\it composition} of a positive integer $n$ is a representation of
$n$ as a sum $n=s_1+s_2+\dots+s_k$ of other positive integers $s_i$,
where the order of the summands matters.
The total number of compositions of $n$ is $2^{n-1}$.
The number of compositions of $n$ with exactly $k$ summands is $\binom
{n-1}{k-1}$. A {\it partition} of a positive integer $n$ is
a representation of $n$ as a sum $n=\la_1+\la_2+\dots+\la_k$ of other
positive integers $\la_i$, where the order of the summands {\it does}
matter. Thus, we may assume that the summands are ordered,
$\la_1\ge\la_2\ge\dots\ge\la_k>0$. This is the motivation to write
partitions most often in the form of tuples
$(\la_1,\la_2,\dots,\la_k)$ the entries of which are weakly decreasing.
The summands of a partition 
are called the {\it parts} of the partition.
Let $p(n)$ denote the number of
partitions of $n$. These numbers are given by
$$
\sum _{n=0} ^{\infty}p(n)\,x^n=\frac {1} {
\prod _{i=1} ^{\infty}(1-x^i)}.$$
If $p(n,k)$ denotes the number of partitions of $n$ into at most $k$
parts, then we have
$$
\sum _{n=0} ^{\infty}p(n,k)x^n=\frac {1} {
\prod _{i=1} ^{k}(1-x^i)}.$$
Finally, if $p(n,k,m)$ denotes the number of partitions of $n$ into
at most $k$ parts, all of which are at most $m$, then
$$
\sum _{n\ge0} ^{}p(n,k,m)\,x^n=\frac
{(1-x^{k+m})(1-x^{k+m-1})\cdots(1-x^{m+1})} 
{(1-x^k)(1-x^{k-1})\cdots(1-x)}.$$
The expression on the right-hand side is called {\it $q$-binomial
coefficient\/}, and is denoted by $\left[\begin{smallmatrix}
k+m\\k\end{smallmatrix}\right]_x$. 

Partitions are frequently encoded in terms of their {\it Ferrers
diagrams}. The {\em Ferrers
diagram} of a partition $\lambda=(\la_1,\la_2,\dots,\la_\ell)$
is an array of cells with $\ell$ left-justified rows and $\lambda_i$
cells in row $i$. For example, the diagram in Figure~\ref{fig:Ferrers}
is the Ferrers diagram of the partition $(3,3,2)$.
%The {\em conjugate of\/} $\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 Ferrers board of
%$\lambda$.

\newbox\figbox
\setbox\figbox\hbox{\small 
A Ferrers diagram}

\begin{figure}[h]
$$
\Einheit1cm
\Pfad(0,0),112122555666\endPfad
\Pfad(0,1),1122\endPfad
\Pfad(0,2),111\endPfad
\Pfad(1,0),222\endPfad
\hbox{\hskip3cm}
$$
\caption{\unhbox\figbox}
\label{fig:Ferrers}
\end{figure}

A {\it lattice path} $P$ in $\mathbb Z^d$
(where $\mathbb Z$ denotes the set of integers) is a path in the $d$-dimensional
integer lattice $\mathbb Z^d$ which uses only points of the lattice,
that is, it is a sequence $(P_0,P_1,\dots,P_l)$, where $P_i\in \mathbb
Z^d$ for all $i$. The vectors
$\overrightarrow {P_0P_1},\overrightarrow {P_1P_2}, \dots, \overrightarrow
{P_{l-1}P_{l}}$ are called the {\em steps} of $P$. The number of
steps, $l$, is called the {\em length} 
of $P$. Figure~\ref{fig1a} shows a lattice path
in $\mathbb Z^2$ of length $11$. 

\newbox\figbox
\setbox\figbox\hbox{\small 
A Motzkin path}

\begin{figure}[h]
$$
\Gitter(12,5)(-1,0)
\Koordinatenachsen(12,5)(-1,0)
\Pfad(0,0),33141133444\endPfad
\DickPunkt(0,0)
\DickPunkt(11,0)
\PfadDicke{.5pt}
%\Pfad(-2,4),11111111111111\endPfad
%\Label\l{y=R-2}(-3,4)
\hbox{\hskip6.5cm}
$$
\caption{\unhbox\figbox}
\label{fig1a}
\end{figure}

A {\it Dyck path\/} is a lattice path in the integer plane $\mathbb
Z^2$ consisting of
up-steps $(1,1)$ and down-steps $(1,-1)$, which starts at the origin,
never passes below the $x$-axis, and ends on the $x$-axis. See
Figure~\ref{fig:Dyck} for an example.

\newbox\figbox
\setbox\figbox\hbox{\small 
A Dyck path}

\begin{figure}[h]
$$
\Gitter(12,5)(-1,0)
\Koordinatenachsen(12,5)(-1,0)
\Pfad(0,0),343343343444\endPfad
\DickPunkt(0,0)
\DickPunkt(12,0)
\PfadDicke{.5pt}
\hbox{\hskip6.5cm}
$$
\caption{\unhbox\figbox}
\label{fig:Dyck}
\end{figure}

The number of Dyck paths of length $2n$ is the {\it Catalan number}
$C_n=\frac {1} {n+1}\binom {2n}n$. The generating function
(see Section~\ref{sec:GF} for an introduction into the theory of
generating functions) for these
numbers is
\begin{equation} \label{eq:CatGF} 
\sum _{n=0} ^{\infty}C_n\,x^n=\frac
{1-\sqrt{1-4x}} {2x}. 
\end{equation}
The reader is referred to Exercise~6.19 in \cite{StanBI} for countless
occurrences of the Catalan numbers.

A {\it Motzkin path\/} is a lattice path in the integer plane $\mathbb
Z^2$ consisting of
up-steps $(1,1)$, level steps $(1,0)$, and down-steps $(1,-1)$, 
which starts at the origin,
never passes below the $x$-axis, and ends on the $x$-axis. The path
in Figure~\ref{fig1a} is in fact a Motzkin path. The 
number of Motzkin paths of length $n$ is the {\it Motzkin number}
$M_n=
\sum _{k\ge0} ^{}\frac {1} {k+1}\binom {2k}k\binom n{2k}$. 
The generating function for these
numbers is
\begin{equation} \label{eq:MotzGF} 
\sum _{n=0} ^{\infty}M_n\,x^n=\frac
{1-x-\sqrt{1-2x-3x^2}} {2x^2}. 
\end{equation}
The reader is referred to Exercise~6.38 in \cite{StanBI} for numerous
occurrences of the Motzkin numbers.

A {\it Schr\"oder path\/} is a lattice path in the integer plane $\mathbb
Z^2$ consisting of
horizontal steps $(1,0)$ and vertical steps $(0,1)$, 
which starts at the origin,
never passes below the diagonal $x=y$, and ends on the diagonal $x=y$.
See Figure~\ref{fig:Sch} for an example. 

\newbox\figbox
\setbox\figbox\hbox{\small 
A Schr\"oder path}

\begin{figure}[h]
$$
\Gitter(9,9)(-1,0)
\Koordinatenachsen(9,9)(-1,0)
\Pfad(0,0),23132213211\endPfad
\thinlines
\Pfad(0,0),33333333\endPfad
\DickPunkt(0,0)
\DickPunkt(7,7)
\PfadDicke{.5pt}
\hbox{\hskip4cm}
$$
\caption{\unhbox\figbox}
\label{fig:Sch}
\end{figure}


The 
number of Schr\"oder paths of length $n$ is the (large) {\it
Schr\"oder number}
$S_n=
\sum _{k\ge0} ^{}\frac {1} {k+1}\binom {2k}k\binom {n+k}{2k}$. 
The generating function for these
numbers is
\begin{equation} \label{eq:SchGF} 
\sum _{n=0} ^{\infty}S_n\,x^n=\frac
{1-x-\sqrt{1-6x+x^2}}{2x}.
\end{equation}
The reader is referred to Exercise~6.39 in \cite{StanBI} for numerous
occurrences of the Schr\"oder numbers.

There is another famous sequence of numbers which we did not touch yet,
the {\it Fibonacci numbers} $F_n$. They are given by
$$F_n=\frac {1} {\sqrt5}\(\frac {1+\sqrt5}
{2}\)^{n+1},
$$
with generating function
\begin{equation} \label{eq:FibGF} 
\sum _{n=0} ^{\infty}F_n\,x^n=\frac {1} {1-x-x^2}.
\end{equation}
They also occur in numerous places. For example, the number $F_n$ 
counts all paths on the integers $\mathbb Z$ from $0$ to $n$ with steps
$(1,0)$ and $(2,0)$.

An {\it undirected graph} $G$ consists of {\it vertices} and {\it
edges}. An edge is a
2-element subset of the vertices, which, however, is thought of 
a line or curve connecting the two vertices. See
Figure~\ref{fig:graph}.a for an example.
The usual notation for a graph $G$ is $G=(V,E)$, where
$V$ is the set of vertices and where $E$ is the set of edges of $G$.
A graph is {\it planar} if it is embedded in the plane (sphere)
in such a way that the curves which mark the edges do not intersect
in their interiors. There can be several different ways to embed
the same graph in the plane (or in another surface). When we speak of
a {\it planar graph\/} then we assume the graph already be embedded in
a given way. For example, the graph in Figure~\ref{fig:graph} is not
a planar graph, by its drawing. However, there is a different
embedding which {\it is} planar (namely, all embeddings which put the vertex
$v_3$ above the vertex $v_5$ and leave the other vertices as they are).
A {\it tree} is a graph without any cycles.

\newbox\figbox
\setbox\figbox\hbox{\small 
A graph}

\begin{figure}[h]
$$
\DickPunkt(0,0)
\DickPunkt(0,4)
\DickPunkt(6,1)
\DickPunkt(4,4)
\DickPunkt(2,6)
\Label\lu{v_1}(0,0)
\Label\lo{v_2}(0,4)
\Label\r{v_3}(6,1)
\Label\ro{v_4}(4,4)
\Label\o{v_5}(2,6)
\Line(0,0)(1,1)5
\Line(0,0)(0,1)5
\Line(0,4)(1,1){2.6}
\Line(0,4)(2,-1){7.3}
\Line(2,6)(1,-1){2.6}
\Line(4,4)(2,-3){2.4}
\hbox{\hskip6cm}
\DickPunkt(0,0)
\DickPunkt(0,4)
\DickPunkt(6,1)
\DickPunkt(4,4)
\DickPunkt(2,6)
%\Label\lu{v_1}(0,0)
%\Label\lo{v_2}(0,4)
%\Label\r{v_3}(6,1)
%\Label\ro{v_4}(4,4)
%\Label\o{v_5}(2,6)
\Arrow(0,0)(1,1){4.7}
\Arrow(0,0)(0,1){4.6}
\Arrow(0,4)(1,1){2.3}
\Arrow(0,4)(2,-1){7.0}
\Arrow(2,6)(1,-1){2.3}
\Arrow(4,4)(2,-3){2.3}
\hbox{\hskip4cm}
$$
\centerline{\small 
a. An undirected graph\quad \quad \quad \quad \quad b. A directed graph}
\caption{}
\label{fig:graph}
\end{figure}

A {\it directed graph} (or {\it digraph}) 
$G$ consists of {\it vertices} and {\it arcs} (which are sometimes also called
{\it directed edges}). An arc is a
pair of vertices, which, however, is thought of 
an arrow pointing from the first vertex of the pair to the second. See
Figure~\ref{fig:graph}.b for an example.
The usual notation for a directed graph $G$ is again $G=(V,E)$, where
$V$ is the set of vertices and where $E$ is the set of arcs of $G$.
All other notions explained for undirected graphs have analogous
meanings for directed graphs.

Graphs can be {\it labelled\/}, in which case each vertex is assigned
a label, or {\it unlabelled\/}. The (undirected) graph in
Figure~\ref{fig:graph}.a is labelled, whereas the (directed) graph
in Figure~\ref{fig:graph}.b is unlabelled.

\section{Generating functions} \label{sec:GF}

Generating functions are the very basic tools of enumeration.
For introductions into this technique, from different points
of view, the reader is referred to
\cite{BeLLAA}, \cite[Ch.~1]{FlSeAA}, \cite[Ch.~1]{StanAP},
and \cite[Ch.~4]{StanBI}.

Let $\A$ be a set of (unlabelled) objects. Each object $a$ in $\A$ has
a certain size, $\vert a\vert$, which is a non-negative integer.
Let us also assume that there is only a finite number of objects from
$\A$ of a given size. Let $a_n$ be the number of objects from $\A$ of
size $n$. The (ordinary) 
{\it generating function} for $\A$ is the {\it formal
power series} 
$$F_\A(x)=
\sum _{a\in \A} ^{}x^{\vert a\vert}=\sum _{n=0} ^{\infty}a_nx^n.$$ 
(``Formal" means that $x$ is
just an indeterminate, not a real or complex number. 
One can compute with formal power
series in the same way as with analytic series, only that convergence
issues do not arise, respectively that ``convergence" has a different
meaning; cf.\ \cite[Sec.~1.1]{StanAP}.) 
Typical examples are 
{\tt Sets} (the collection containing all ``unlabelled sets",
that is all objects of the form
$\{\bullet,\bullet,\dots,\bullet\}$, including the empty set,
where the size of $\{\bullet,\bullet,\dots,\bullet\}$ is the number
of $\bullet$'s)
{\tt Sequences} (the collection containing all ``unlabelled sequences",
that is all objects of the form
$(\bullet,\bullet,\dots,\bullet)$, including the empty sequence), 
{\tt Cycles} (unlabelled cycles), with respective generating function
\begin{equation}  
F_{\text{\tt Sets}}(x)=
F_{\text{\tt Sequences}}(x)=\frac {1} {1-x},\quad 
F_{\text{\tt Cycles}}(x)=\frac {x} {1-x},
\end{equation}
or {\tt Trees} (unlabelled trees).

If $\A$ and $\B$ are two sets of objects, 
one can define several other sets of objects using them.
The {\it union} of $\A$ and $\B$, written $\A\cup\B$, has as a
groundset the {\it disjoint} union of $\A$ and $\B$, and the size of
an element from $\A$ is its size in $\A$, while the size of
an element from $\B$ is its size in $\B$. We have
\begin{equation} \label{eq:und} 
F_{\A\cup \B}(x)=F_\A(x)+F_\B(x).
\end{equation}
The {\it product} of $\A$ and $\B$, written $\A\times\B$, has as a
groundset the set of pairs $\A\times\B$, and the size of
an element $(a,b)$ from $\A\times\B$ is the sum of the sizes of $a$
(in $\A$) and of $b$ (in $\B$). We have
\begin{equation} \label{eq:mal} 
F_{\A\times \B}(x)=F_\A(x)\cdot F_\B(x).
\end{equation}
The substitution of two sets $\A$ and $\B$ of objects can only be
defined in certain circumstances, and only in certain more restrictive
circumstances the generating function for the substitution can be
computed by substituting the generating functions for $\A$ and
$\B$. 
Let us assume that any object $a$ from $\A$ of size $n$, by its
structure, has $n$ atoms (nodes). For example, if $\A$ is a certain
set of trees, where the size of a tree is the number of leaves in the
tree, then we may take as the atoms the leaves of the tree. In this
situation, the {\it substitution of $\B$ in $\A$}, denoted by
$\A(\B)$, is the set of
objects which arises by replacing the atoms
of objects from $\A$ by objects from $\B$ in all possible ways.
The size of an object from $\A(\B)$ is the sum of the sizes of the
objects from $\B$ that it contains. In order that $\A(\B)$ contains
only a finite number of objects of a given size, we must assume that
$\B$ contains no elements of size $0$.
If, in addition, the atoms of any element $a$ from $\A$ inherit an
order (for example, if $\A$ is a set of binary trees, then the leaves
of a binary tree are ordered in a natural way from ``left" to
``right"), then we have
\begin{equation} \label{eq:comp} 
F_{\A(\B)}(x)=F_\A(F_\B(x)).
\end{equation}
However, this equation is not true in general. 
The general formula comes out of Redfield--P\'olya theory (see
\eqref{eq:unlabel} and \eqref{eq:compC}) 
and requires the notion of {\it cycle index
series}. For example, if $\B$ is the set of connected (unlabelled)
graphs, $\A$ is {\tt Sets}, so that $\A(\B)$ is the set of {\it all\/}
(connected and disconnected) graphs, then \eqref{eq:comp} is not true,
but what is true is
\begin{equation} \label{eq:setcomp} 
F_{{\tt Sets}(\B)}=\exp\(F_\B(x)+\frac {1} {2}F_\B(x^2)+\frac {1}
{3}F_\B(x^3)+\cdots\).
\end{equation}
This holds, in fact, for any set $\B$ of unlabelled objects.
(This is seen by combining \eqref{eq:compC}, \eqref{eq:CISets}, 
and \eqref{eq:unlabel}.)

\medskip
Next we deal with the enumeration of {\it labelled\/} objects.
Let $\A$ be a set of labelled objects, again, each object $a$ 
with a certain size $\vert a\vert$ which is a non-negative integer.
``Labelled" means that each object of size $n$, by its
structure, comes with $n$ atoms (nodes) which are labelled
$1,2,\dots,n$. For example, $\A$ may be the set of all labelled
graphs, where the size of a graph is the number of its vertices, and
where the vertices are labelled $1,2,\dots,n$.
Again, we
assume that there is only a finite number of objects from
$\A$ of a given size. Let $a_n$ be the number of objects from $\A$ of
size $n$. The 
{\it exponential generating function} for $\A$ is the {\it formal
power series} 
$$E_\A(x)=
\sum _{a\in \A} ^{}\frac {x^{\vert a\vert}} {\vert a\vert!}
=\sum _{n=0} ^{\infty}a_n\frac {x^n}{n!}.$$ 
Typical examples are 
{\tt Sets} (the collection containing all ``labelled sets",
that is all objects of the form
$\{1,2,\dots,n\}$, including the empty set),
{\tt Permutations}, {\tt Cycles} (labelled cycles),
with respective generating functions
\begin{align}
E_{\text{\tt Sets}}(x)&=\exp(x),\\
E_{\text{\tt Permutations}}(x)&=\frac {1} {1-x},\\
E_{\text{\tt Cycles}}(x)&=\log\frac {1} {1-x},
\end{align}
or {\tt Trees} (labelled trees).
The explicit form of the generating function for {\tt Trees} is
discussed in Section~\ref{sec:kernel}.

If $\A$ and $\B$ are two sets of objects, 
one defines again several other sets of objects using them.
The {\it union} of $\A$ and $\B$, written $\A\cup\B$, has as a
groundset the {\it disjoint} union of $\A$ and $\B$, and the size of
an element from $\A$ is its size in $\A$, while the size of
an element from $\B$ is its size in $\B$. We have
\begin{equation} \label{eq:undE} 
E_{\A\cup \B}(x)=E_\A(x)+E_\B(x).
\end{equation}
To define the {\it product} of $\A$ and $\B$, written $\A\times\B$, 
we cannot simply take $\A\times\B$ as a groundset, we must also say
something about the labelling of the objects. So, as a groundset we
take all pairs $(a,b)$ with $a\in \A$ and $b\in \B$, 
but labelled in all possible ways
by $1,2,\dots,\vert a\vert+\vert b\vert$ such that the order of labels
assigned to $a$ respects the original order of labels of $a$, and the
same for $b$. The size of such an
element $(a,b)$ is again the sum of the sizes of $a$
(in $\A$) and of $b$ (in $\B$). 
We have
\begin{equation} \label{eq:malE} 
E_{\A\times \B}(x)=E_\A(x)\cdot E_\B(x).
\end{equation}
Since, in the labelled world, objects come automatically with atoms, 
the substitution of two sets $\A$ and $\B$ of objects can now always
be defined. The {\it substitution of $\B$ in $\A$}, denoted by
$\A(\B)$, is the set of
objects which arises by replacing the atoms
of objects from $\A$ by objects from $\B$ in all possible ways,
and labelling the substituted objects in all possible ways by
$1,2,\dots,\sum _{b} ^{}\vert b\vert$ (the sum being over the objects
from $\B$ which were put in the places of the atoms) that
are consistent with the original labellings of the objects from $\B$.
The size of an object from $\A(\B)$ is the sum of the sizes of the
objects from $\B$ that it contains.
In order that $\A(\B)$ contains
only a finite number of objects of a given size, we must assume that
$\B$ contains no elements of size $0$.
Then we have
\begin{equation} \label{eq:compE} 
E_{\A(\B)}(x)=E_\A(E_\B(x)).
\end{equation}
An example of a composition is 
$$\text{\tt Permutations}=\text{\tt Sets}( \text{\tt Cycles}).$$
Thus, from \eqref{eq:compE} we have
$$E_{\text{\tt Permutations}}(x)=E_{\text{\tt Sets}}(E_{\text{\tt Cycles}}(x)),
$$
corresponding to the identity
$$
\frac {1} {1-x}=\exp\left(\log 1/(1-x)\right).$$
Another manifestation of the composition rule is for example the fact
(which is sometimes called the ``exponential principle") that, if
one takes the $\log$ of the partition function for some maps, the
result is the partition function for the connected maps among them.

All of the above can be generalized to a weighted setting.
Namely, if $\A$ is a set of objects (labelled or unlabelled), and if
$w:\A\to R$ is a {\it weight function} from $\A$ into some ring $R$,
then all of the above remains true, if we replace the definitions
of $F_\A(x)$ and $E_\A(x)$ above by the
weighted sums 
$$F_\A(x)=
\sum _{a\in \A} ^{}w(a)\,x^{\vert a\vert}$$ 
and
$$E_\A(x)=
\sum _{a\in \A} ^{}w(a)\frac {x^{\vert a\vert}} {\vert a\vert!},
$$
respectively, if in the definition of the union of $\A$ and $\B$ we define the
weight of an object to be its weight in $\A$, respectively $\B$,
if in the definition of the product of $\A$ and $\B$
we define the weight of an object
$(a,b)$ to be the product of the weights of $a$ and $b$, and if in the
definition of the substitution we define the weight of an object in
$\A(\B)$ as the product of the weights of the objects from $\B$ that
were put in place of the atoms.

%??inclusion-exclusion

\section{Redfield--P\'olya theory of coloured enumeration} \label{sec:Polya}

The natural and uniform environment for the separate treatment
of generating functions for unlabelled and labelled objects 
in Section~\ref{sec:GF} is the theory for counting coloured objects
founded by Redfield and P\'olya, in the modern treatment through cycle
index series due to Joyal. We refer the reader to
\cite[App.~1]{BeLLAA}, \cite{BruiAA} 
and \cite[Ch.~7]{StanBI} for further reading.

Let $\A$ be a set of labelled objects with the constraint that there
is only a finite number of objects of a given size. The {\it cycle
index series} for $\A$ is the formal multivariable series
\begin{equation} \label{eq:cycind}
Z_\A(x_1,x_2,\dots)=
\sum _{n=0} ^{\infty}\frac {1} {n!}
\sum _{\si\in\mathfrak S_n} ^{}\fix_\si (\A)\,x_1^{c_1(\si)}
x_2^{c_2(\si)}x_3^{c_3(\si)}\cdots, 
\end{equation}
where $\fix_\si(\A)$ is the number of objects $a$ from $\A$ which
remain invariant when the labels are permuted according to the
permutation $\si$ (in particular, if $\si\in\mathfrak S_n$, the size 
of $a$ must be $n$ in order that $\si$ can be applied to the labels),
and where $c_i(\si)$ denotes the number of cycles of length $i$ of
$\si$. 

In most cases it is difficult to obtain compact expressions for the
cycle index series. However, for our familiar families of objects,
compact expressions are available:
\begin{align} \label{eq:CISets}
Z_{\text{\tt Sets}}(x_1,x_2,\dots)&=\exp\left(x_1+\frac {x_2} {2}+\frac
{x_3} {3}+\cdots\right),\\
Z_{\text{\tt Permutations}}(x_1,x_2,\dots)&=
\prod _{i=1} ^{\infty}\frac {1} {1-x_i},\\
Z_{\text{\tt Cycles}}(x_1,x_2,\dots)&=
\sum _{i=1} ^{\infty}\frac {\Phi(i)} {i}\log\frac {1} {1-x_i},
\end{align}
where $\Phi(i)$ is the {\it Euler totient function}
(the number of positive integers $j\le i$ relatively prime to $i$).

What makes the cycle index series so fundamental is the fact that
the generating functions from Section~\ref{sec:GF} are specializations
of it. Namely,
the exponential generating function for $\A$ is equal to
\begin{equation} \label{eq:label} 
E_\A(x)=Z_\A(x,0,0,\dots).
\end{equation}
If, given the set of labelled objects $\A$, we produce a set of
unlabelled objects $\tilde\A$ by taking all the objects from $\A$ but
forgetting the labels, then the ordinary generating function for $\tilde\A$
is another specialization of the cycle index series,
\begin{equation} \label{eq:unlabel} 
F_{\tilde\A}(x)=Z_\A(x,x^2,x^3,\dots).
\end{equation}

The cycle index series satisfies the following properties with respect
to union, product and composition of sets of objects:
\begin{align} \label{eq:undC} 
Z_{\A\cup \B}(x_1,x_2,\dots)&=Z_\A(x_1,x_2,\dots)+Z_\B(x_1,x_2,\dots),\\
\label{eq:malC}
Z_{\A\times \B}(x_1,x_2,\dots)&=Z_\A(x_1,x_2,\dots)\cdot Z_\B(x_1,x_2,\dots),\\
Z_{\A(\B)}(x_1,x_2,\dots)&=Z_\A(Z_\B(x_1,x_2,x_3,\dots),
Z_\B(x_2,x_4,x_6\dots),\notag\\
\label{eq:compC}
&\kern4cm
Z_\B(x_3,x_6,x_9,\dots),\dots).
\end{align}

Similar to the theory of generating functions surveyed in
Section~\ref{sec:GF}, one can also develop a weighted version of the
cycle index series. Given a set of labelled objects $\A$, where each
object $a$ is assigned a weight $w(a)$, one changes the definition
\eqref{eq:cycind} insofar as $\fix_\si(\A)$ gets replaced
by the weighted sum $
\sum _{\si(a)=a} ^{}w(a)$, where $\si(a)$ means the object arising
from $a$ by permuting the labels according to $\si$. Then all the
above formulas remain true in this weighted setting.

Cycle index series are instrumental in the enumeration of {\it
coloured\/} objects. The basic situation is that we have given a set
$\tilde\A$ of unlabelled objects so that every object of size $n$
comes with $n$ atoms (nodes). For example, we may think of $\tilde\A$ as the
set of cycles.  We are now going to colour each atom by a colour from
the set of colours $C$. The question that we pose is: {\it how many
different coloured objects of a given size are there?} In our example, if $C$
consists of the two colours ``black" and ``white", then we are asking
the question of how many necklaces one can make out of
$n$ pearls that can be black or white. In terms of generating
functions, we want to compute
$$\Ga_{\tilde\A}(x)=
\sum _{c} ^{}x^{\vert c\vert},$$
where the sum is over all coloured objects $c$ that one can obtain
by colouring the objects from $\tilde\A$.

The central result of Redfield--P\'olya theory is that, 
if $\A$ is the set of labelled objects that one obtains
from $\tilde\A$ by labelling the objects of $\tilde\A$ in all possible
ways, then
$$\Ga_{\tilde\A}(x)=Z_{\A}(\vert C\vert x,\vert C\vert x^2,\vert C\vert
x^3,\dots ).$$

There is again a weighted version. One allows the objects $a$ from
$\tilde\A$ to have weight $w(a)\in R$. Moreover, one assumes a weight
function $f:C\to R$ on the colours with values in the ring $R$.
One defines the weight of a coloured object obtained by colouring the
atoms of $a$ to be $w(a)$ multiplied by the product of all $f(\gamma)$,
where $\gamma$ ranges over all the colours of the atoms (including
repetitions of colours). Let $\Ga_{\tilde\A}(w,f)$ denote the sum of
all the weights of all coloured objects obtained from $\tilde\A$. Then
$$\Ga_{\tilde\A}(w,f)=Z_{\A}\(
\sum _{c\in C} ^{}f(c),\sum _{c\in C} ^{}f(c)^2,\sum _{c\in C} ^{}f(c)^3,
\dots \).$$

We remark that these results cover also the case of enumeration
of objects under a group action. This includes the enumeration of
objects on which we impose certain symmetries. 
See \cite[App.~1]{BeLLAA}, \cite{BruiAA} 
and \cite[Ch.~7]{StanBI} for more details.
The enumeration of asymmetric objects is the subject of an ongoing
research program (cf.\ \cite{LaLaAA}).

\section{Solving equations for generating functions:
the Lagrange inversion formula and the kernel method} \label{sec:kernel}

In this section, we describe two methods to solve functional equations
for generating functions. The Lagrange inversion makes it possible
(in some situations) to
find explicit expressions for the coefficients of an implicitly given
series. The kernel method (and its extensions), on the other hand, is
a powerful method to obtain an explicit expression for an implicitly
given function. We refer the reader to \cite[Sec. VII.5]{FlSeAA} 
for further reading.

In many situations it will happen that, when we apply the methods
from Sections~\ref{sec:GF}, we end up with a functional equation
for the generating function $f(x)=
\sum _{n=0} ^{\infty}f_n x^n$ that we wanted to compute.
For example, if $t_n$ denotes the number of labelled rooted trees with
$n$ nodes, and if we write $T(x)=
\sum _{n=1} ^{\infty}t_n x^n/n!$, then, by applying a straight-forward
decomposition of a tree into its root and its set of subtrees attached to the
root, we obtain the equation
\begin{equation} \label{eq:tree} 
T(x)=x\exp(T(x)).
\end{equation}

How does one solve such an equation?
As a matter of fact, for $T(x)$, there is no expression in terms of
known functions. However, the {\it Lagrange inversion formula} enables
one to find the {\it coefficients} $t_n/n!$ of $T(x)$ explicitly.
The theorem reads as follows.

{\it Let $g(x)$ be a formal Laurent series containing only a finite
number of negative powers of $x$, and let $f(x)$ be a 
formal power series without constant term. If we expand 
$g(x)$ in powers of $f(x)$,
\begin{equation} \label{eq:g-f} 
g(x)=\sum _{k} ^{}c_kf^k(x),
\end{equation}
then the coeffizients $c_n$ are given by
\begin{equation} \label{eq:Lagr1} 
c_n=\frac {1} {n}[{x^{-1}}]g'(x)f^{-n}(x) \quad \text {for }n\ne0,
\end{equation}
or, alternatively, by
\begin{equation} \label{eq:Lagr2} 
c_n=[{x^{-1}}]g(x)f'(x)f^{-n-1}(x).
\end{equation}
Here, $[x^n]h(x)$ denotes the coefficient of $x^n$ in the power series
h(x).}

With this theorem in hand, the equation \eqref{eq:tree} is easy to
solve. We write it in the form,
\begin{equation} \label{eq:T} 
T(x)\exp(-T(x))=x.
\end{equation}
We want to know the coefficients in the expansion $T(x)=
\sum _{n=0} ^{\infty}t_n\,x^n/n!$. Since, by \eqref{eq:T}, $T(x)$ is
the compositional inverse of $x\exp(-x)$, substitution of
$x\exp(-x)$ instead of $x$ gives
$$x=
\sum _{n=0} ^{\infty}\frac {t_n} {n!}\,(x\exp(-x))^n.$$
This equation is in the form \eqref{eq:g-f} with $f(x)=x\exp(-x)$ and
$g(x)=x$. Hence, by \eqref{eq:Lagr1}, we obtain
$$
\frac {t_n} {n!}=\frac {1} {n}[{x^{-1}}](x\exp(-x))^{-n}
=\frac {1} {n}[{x^{n-1}}]\exp(nx)
=\frac {n^{n-1}} {n!},
$$
and, thus, $t_n=n^{n-1}$.

\medskip
The second method to solve functional equations which we explain in
this section is the {\it kernel method}. We illustrate
the method by an example.
Let us consider the problem of counting Dyck paths of length $2n$
(see Section~\ref{sec:basic}). Rather than attempting to arrive at
a solution of the problem directly, we consider the more general
problem of counting the number $a_{n,k}$ of paths consisting of steps
$(1,1)$ and $(1,-1)$, which start at the origin, never drop below
$y=0$, have length $n$ and end at height $k$. We then form the
bivariate generating function $F(u,x)=
\sum _{n,k\ge0} ^{}a_{n,k}x^nu^k$. We then have the functional equation
\begin{equation} \label{eq:func} 
F(u,x)=1+xuF(u,x)+\frac {x} {u}(F(u,x)-F(0,x)),
\end{equation}
since a path can be empty (this explains the term $1$), it
can end by a step $(1,1)$ (this explains the term $xuF(u)$), or it can
end by a step $(1,-1)$. The latter can only happen if the path before
that last step did not end at height $0$. The generating function for
these paths is $F(u,x)-F(0,x)$, and this explains the third term in the
equation \eqref{eq:func}. In fact, we may replace \eqref{eq:func} by
\begin{equation} \label{eq:func1} 
F(u,x)=1+xuF(u,x)+\frac {x} {u}(F(u,x)-F_1(x)),
\end{equation}
because \eqref{eq:func1} {\it implies} that $F_1(x)=F(0,x)$.

The idea of the kernel method is to get rid of the unknown series
$F(u,x)$. 
This is possible because $F(u,x)$ occurs linearly
in \eqref{eq:func1}, which can be rewritten as
\begin{equation} \label{eq:func2} 
F(u,x)\(1-xu-\frac {x} {u}\)=1-\frac {x} {u}F_1(x).
\end{equation}
We simply equate the coefficient of $F(u,x)$ in this equation to zero,
$$1-xu-\frac {x} {u}=0,$$
solve this for $u$,
$$u=\frac {1-\sqrt{1-4x^2}} {2x},$$
(the other solution for $u$ makes no sense in \eqref{eq:func1})
and substitute this back in \eqref{eq:func2}, to obtain
$$F_1(x)=\frac {1-\sqrt{1-4x^2}} {2x^2},$$
the familiar generating function \eqref{eq:CatGF} for the Catalan
numbers. Now, by substituting this result in \eqref{eq:func1}, we can
even compute the full series $F(u,x)$.

While this was certainly a complicated, and unusual, way to compute the
Catalan numbers, this approach generalizes when one considers paths
with different step sets (see \cite[Sec.~VII.5]{FlSeAA}). 
In a more general
situation, one has a functional equation
\begin{equation} \label{eq:Func} 
P(F(u,x),F_1(x),\dots,F_k(x),x,u)=0,
\end{equation}
where $F(u,x)$ appears linearly, as well as the unknown series
$F_1(x)$, \dots, $F_k(x)$, whereas $x$ and $u$ appear rationally.
It is clear that one can apply the same technique, namely collecting
all the terms involving $F(u,x)$, equating the coefficient of $F(u,x)$ to
zero, solving for $u$ and substituting back in \eqref{eq:Func}. If
there is more than one function $F_i(x)$, then this will only give
one equation for the $F_i(x)$. However, when equating the coefficient
of $F(u,x)$, which was a polynomial equation, there can be more
solutions. (That was actually also the case in our example, although
only one solution could be used.) All these solutions can be
substituted in \eqref{eq:Func} to give many more equations for the
$F_i(x)$. The kernel method will work if we have enough equations
to determine the unknown functions $F_i(x)$. See \cite[Sec.~VII.5]{FlSeAA}
for further details. In the variant of the ``obstinate kernel method",
more equations are produced in more sophisticated ways.
The method has been largely extended 
by Bousquet--M\'elou and co-workers to cover
equations of the form \eqref{eq:Func} where $P$ is a {\it polynomial} 
such that equation \eqref{eq:Func} determines all involved series uniquely.
This extension covers in particular the so-called {\it quadratic
method\/} due to Brown, which is of
great significance in the work of Tutte on the enumeration of maps. We refer the reader to \cite{BoJeAA}
and the references given there for these extensions.

\section{Extracting asymptotic information from generating functions} 
\label{sec:GFasy}

There is powerful machinery available to extract the asymptotic
behaviour of the coefficients of a power series out of analytic
properties of the power series. We describe the corresponding
methods, {\it singularity analysis} and the {\it saddle point method}
in this section. The survey \cite{Odly} and the book
\cite{FlSeAA} are excellent sources for further reading, which, in
particular, contain several other methods which we cannot cover here
for reasons of limited space.

Let us suppose that we are interested
in the asymptotic behaviour of the sequence $(f_n)_{n\ge0}$ of
real (or complex) numbers as $n$
tends to infinity. Let us suppose that the power series $
f(z)=\sum _{n=0} ^{\infty}f_n\,z^n$ converges in some neighbourhood of the
origin. (If this series converges only at $z=0$, then
either one has to try to scale, that is, for example, look at 
the power series
$f(z)=
\sum _{n=0} ^{\infty}f_n\,z^n/n!$ instead, or one must apply
methods other than singularity analysis or the saddle point
method. In the latter case, depending on the nature of the
coefficients $f_n$, this may be the {\it Euler--Maclaurin} or the {\it
Poisson summation formulas}, the {\it Mellin transform technique},
or other direct methods. The reader is referred to \cite{FlSeAA,Odly}.)
The idea is then to consider $f(z)$ as a complex function in
$z$ (and extend the range of $f$ beyond the disk of convergence
about the origin), and to study the singularities of $f(z)$.
(The point at infinity can also be a singularity.)
The upshot is that the singularities of $f(z)$ with smallest modulus
dictate the asymptotic behaviour of the coefficients $f_n$.
These singularities of smallest modulus are called the
{\it dominating} singularities.

If there is an infinite number of dominant singularities, then one has to try 
the {\it circle method}. We refer the reader to
\cite{AndrAF,AyouAA} for details of this method.

If there is a finite number of dominant singularities,
then there can be again two different situations, depending on
whether these are ``small" or ``large" singularities.
Roughly speaking, a singularity is small if the function $f(z)$ grows
at most polynomially when $z$ approaches the singularity, 
otherwise it is ``large". A typical example of a small singularity is
$z=1/4$ in $(1-4z)^{-1/2}$, whereas a typical example of a large
singularity is $z=\infty$ in $\exp(x)$ or
$z=1$ in $\exp(1/(1-z))$.

The method to apply for small singularities is
the method of {\it singularity analysis}
as developed by Flajolet and Odlyzko.
(Singularity analysis implies {\it Darboux's method}, 
which occurs frequently in the literature, and, thus, supersedes it.)
For the sake of simplicity, we consider first only the case of a unique
dominant singularity. We shall address the issue of several dominant
singularities a little bit later. Furthermore, we assume 
the singularity to be $z=1$, again for the sake
of simplicity of presentation. The general result can then be obtained
by rescaling $z$.

The basic idea is the transfer principle
\begin{equation} \label{eq:transfer} 
\text{If }f(z)\underset{z\to1}=\si(z)+O(\tau(z))\quad
\text{then}\quad f_n\underset{n\to\infty}=\si_n+O(\tau_n), 
\end{equation}
where $\si(z)=
\sum _{n=0} ^{\infty}\si_n\,z^n$ is a linear combination of
standard functions of the
form $(1-z)^{-\al}$, or logarithmic variants, and $\tau(z)=
\sum _{n=0} ^{\infty}\tau_n\,z^n$ also lies in the scale.
(See \cite[Sec.~VI.3,4]{FlSeAA} for the exact statement.)
The expansion for $f(z)$ in \eqref{eq:transfer} is called the {\it
singular expansion} of $f(z)$.
For the above mentioned standard functions, we have
\begin{multline} \label{eq:standard}
[z^n](1-z)^{-\al}\(\frac {1} {z}\log\frac {1} {1-z}\)^\be
\\\sim \frac {n^{\al-1}} {\Ga(\al)}(\log n)^\be
\(1+\frac {C_1} {1!}\frac {\be} {\log n}+\frac {C_2} {2!}\frac
{\be(\be-1)} {(\log n)^2}+\cdots\),
\end{multline}
where $[z^n]g(z)$ denotes the coefficient of $z^n$ in $g(z)$, and
where
$$C_k=\Ga(\al)\frac {d^k} {ds^k}\frac {1} {\Ga(s)}\bigg\vert_{s=\al}.$$ 
If $\al$ is a non-positive integer, then this expansion has to
be taken with care (cf.\ \cite[Sec.~VI.2]{FlSeAA}).

To see how this works, consider the example $f_n=
\sum _{k=0} ^{n}\binom {2k}k$. We have
$$
\sum _{n=0} ^{\infty}f_n\,z^n=\frac {1} {(1-z)\sqrt{1-4z}}.$$
The function on the right-hand side is meromorphic in all of $\mathbb C$
(where $\mathbb C$ denotes the complex numbers), with singularities at
$z=1$ and $z=1/4$. The dominant singularity is $z=1/4$. We determine
the singular expansion of $f(z)$ about $z=1/4$,
$$f(z)={\frac {4}{3}}(1-4z)^{-1/2}
-{\frac {4}{9}} (1- 4 z )^{1/2} +{\frac
{4}{27}} ( 1-4 
 z ) ^{3/2}+O\((1- 4 z ) ^{5/2}\).
$$
(We stopped the expansion after $3$ terms. The farther we go,
the more terms can we compute of the asymptotic expansion for $f_n$.)
Hence, we obtain
\begin{align*}
f_n&=4^n\bigg({\frac {4}{3}}\frac {n^{-1/2}} {\Ga(1/2)}\(1-\frac {1}
{8n}+\frac {1} {128n^2}\)
-{\frac {4}{9}} \frac {n^{-3/2}} {\Ga(-1/2)}\(1+\frac {3} {8n}\)\\
&\kern6cm
+{\frac
{4}{27}} \frac {n^{-5/2}} {\Ga(-3/2)}
+O\(n ^{-7/2}\)\bigg)\\
&=\frac {4^n} {\sqrt {\pi n}}\(\frac {4} {3}+\frac {1} {18n}+\frac
{11} {288n^2} +O\(\frac {1} {n^3}\)\).
\end{align*}

If there is several small dominant singularities (but only a finite
number of them), then one simply applies the above procedure for all of
them and, to obtain the desired asymptotic expansion, 
one adds up the corresponding contributions.

\medskip
The method to apply for large singularities is
the {\it saddle point method}. For the following considerations
we assume that $f(z)$ is analytic in $\vert z\vert<R\le\infty$.
At the heart of the saddle point method lies Cauchy's formula
\begin{equation} \label{eq:Cauchy}
f_n=[z^n]f(z)=\frac {1} {2\pi i}\int _{\mathcal C} ^{}\frac {f(z)} {z^{n+1}}dz 
\end{equation}
for writing the $n$-th coefficient in the power series expansion of
$f(z)$. Here, $\mathcal C$ is some simple closed contour around the
origin that stays in the range $\vert z\vert<R$. The idea is to
exploit the fact that we are free to deform the contour. The aim is to
choose a contour such that the main contribution to the integral in
\eqref{eq:Cauchy} comes from a very tiny part of the contour, whereas
the contribution of the rest is negligible. This will be possible if
we put the contour through a saddle point of the integrand
$f(z)/z^{n+1}$. Under suitable conditions, the main contribution will
then come from the small passage of the path through the saddle point,
and the contribution of the rest will be negligible.

In practice, the the saddle point method is not
always straight-forward to apply, but has to be
adapted to the specific properties of
the function $f(z)$ that we are encountering. 
I refer the reader to the corresponding chapters in \cite{FlSeAA,Odly}
for more details.
There is one important exception though, namely the {\it Hayman admissible
functions}. I shall not reproduce the definition of Hayman
admissibility because it is cumbersome (cf.\
\cite[Sec.~VIII.5]{FlSeAA} and \cite[Def.~12.4]{Odly}).
However, in many applications it is not even necessary to go back to it
because of the closure properties of Hayman admissible functions.
Namely, it is known (cf.\ \cite[Theorem~12.8]{Odly}) that
$\exp(p(z))$ is Hayman admissible in $\vert z\vert<\infty$ 
for any polynomial $p(z)$ with real coefficients 
as long as the coefficients $a_n$ of the
Taylor series of 
$\exp(p(z))$ are positive for all sufficiently large $n$ (thus,
$\exp(z)$ is Hayman admissible, for example),
and it is known that, if $f(z)$ and $g(z)$
are Hayman admissible in $\vert z\vert<R\le \infty$, then $\exp(f(z))$
and $f(z)g(z)$ are also (thus, $\exp(\exp(z)-1)$ 
is Hayman admissible, for example). 

The central result of Hayman's theory is the
following: {\it If $f(z)=\sum_{n\ge0}f_nz^n$ is Hayman admissible in $\vert
z\vert<R$, then
\begin{equation}
   f_n\sim\frac{f(r_n)}{r_n^n\sqrt{2\pi b(r_n)}}\quad\text{as $n\to\infty$},
   \label{eq:Hayman}
\end{equation}
where $r_n$ is the unique solution for large $n$ of the equation
$a(r)=n$ in $(R_0,R)$, 
with $a(r)=rf'(r)/f(r)$, $b(r)=ra'(r)$, and a suitably chosen constant
$R_0>0$.}

This result covers only the first term in the asymptotic expansion.
There is an even more sophisticated theory due to Harris and
Schoenfeld which allows one to also find a complete asymptotic
expansion. We refer the reader to \cite[Sec.~VIII.5]{FlSeAA} and
\cite[pp.~1180ff]{Odly} for more details.

\medskip
Methods for the asymptotic analysis of multivariable generating
functions are also available, see the corresponding
chapters in \cite{FlSeAA,Odly}, and the recent important development
surveyed in \cite{PeWiAD}. 
We add that both the method of singularity analysis and
Hayman's theory of admissible functions have been made largely
automatic, and that this has been implemented in the {\sl Maple} program {\tt
gdev}.\footnote{The program is available at {\tt
http://algo.inria.fr/libraries/libraries.html\#gdev}.}

\section{The theory of heaps} \label{sec:heaps}

The {\it theory of heaps}, developed by Viennot, 
is a geometric rendering of the theory of the
partial commutation monoid of Cartier and Foata, which
is now most often called the {\it Cartier--Foata monoid}. 
Its importance stems from the fact that several objects which appear
in statistical physics, such as Motzkin paths, animals,
respectively polyominoes, or
Lorentzian triangulations (see 
\cite{ViJaAA} and the references therein),
are in bijection with heaps.

Informally, a {\em heap} is what we would imagine. We take a
collection of
``pieces," say $B_1,B_2,\dots$, and put them one upon the other,
sometimes also sideways, to form a ``heap," see Figure~\ref{F3.14}.

\begin{figure}
\unitlength1cm
\begin{picture}(10,5)
\thicklines
\put(5.2,1){\oval(2,1)}
\put(9.5,1){\oval(2,1)}
\put(10,2){\oval(1,1)}
\put(3,2){\oval(4.5,1)}
\put(6,2){\oval(1,1)}
\put(3,3){\oval(2,1)}
\put(5.2,3){\oval(2,1)}
\put(4,4){\oval(3,1)}
\put(5.1,.9){$B_2$}
\put(9.4,.9){$B_7$}
\put(9.9,1.9){$B_6$}
\put(2.9,1.9){$B_4$}
\put(5.9,1.9){$B_5$}
\put(2.9,2.9){$B_3$}
\put(5.1,2.9){$B_2$}
\put(3.9,3.9){$B_1$}
\put(0,0.5){\line(1,0){11}}
\end{picture}
\caption{\small A heap of pieces}
\label{F3.14}
\end{figure}

There, we imagine that pieces can only move vertically, so that the heap in
Figure~\ref{F3.14} would indeed form a stable arrangement. Note that
we allow several copies of a piece to appear in a heap. (This
means that they differ only by a vertical translation.) For
example, in Figure~\ref{F3.14} there appear two copies of $B_2$.
Under these assumptions, there are pieces which can move past each
other, and others which cannot. For example, in Figure~\ref{F3.14},
we can move the piece $B_6$ higher up, thus moving it higher than
$B_1$ if we wish. However, we cannot move $B_7$ higher than $B_6$,
because $B_6$ blocks the way. On the other hand, we can move $B_7$
past $B_1$ (thus taking $B_6$ with us). 
Thus, a rigorous way to introduce heaps is by beginning with a set
$\Bau$ of pieces (in our example, $\Bau=\{B_1,B_2,\dots,B_7\}$), and
we declare which pieces can be moved past another and which cannot. We
indicate this by a symmetric relation $\Rel$: we write $a\Rel b$ to
indicate that $a$ {\it cannot\/} move past $b$ (and vice versa). 
When we
consider a word $a_1a_2\dots a_n$ of pieces, $a_i\in\Bau$, we think of
it as putting first $a_1$, then putting $a_2$ on top of it (and, possibly,
moving it past $a_1$), then putting $a_3$ on top of what we already
have, etc. We declare two words to be equivalent if one arises from
the other by commuting adjacent letters which are not in relation.
A heap is then an equivalence class of words under this
equivalence relation. What we have described just now is indeed the
original definition of Cartier and Foata.

The class of heaps which occurs most frequently in applications
is the class of heaps of 
{\em monomers} and {\em dimers}, which we
now introduce.
Let $\Bau=M\cup D$, where $\Monomer=\{m_0,m_1,\dots\}$ is the set of
monomers and $\Dimer=\{d_1,d_2,\dots\}$ is the set of
dimers. We think of a monomer $m_i$ as a point, symbolized by a
circle, with $x$-coordinate $i$, see Figure~\ref{F3.16}.
We think of a dimer $d_i$ as two points, symbolized by 
circles, with $x$-coordinates $i-1$ and $i$ which are connected by an edge, 
see Figure~\ref{F3.16}.
We impose the relations $m_i\Rel m_i$, $m_i\Rel d_i$, $m_i\Rel
d_{i+1}$, $i=0,1,\dots$, $d_i\Rel d_j$, $i-1\le j\le i$, and extend
$\Rel$ to a symmetric relation. Figure~\ref{F3.17} shows two heaps of
momomers and dimers.

\begin{figure}
$$
\Einheit1cm
\Pfad(-1,0),111111111\endPfad
\SPfad(0,0),222222\endPfad
\SPfad(1,0),222222\endPfad
\SPfad(2,0),222222\endSPfad
\SPfad(3,0),222222\endSPfad
\SPfad(4,0),222222\endSPfad
\SPfad(5,0),222222\endSPfad
\SPfad(6,0),222222\endSPfad
\SPfad(7,0),222222\endSPfad
\Kreis(0,1)
\Kreis(1,1)
\Kreis(2,1)
\Kreis(3,1)
\Kreis(4,1)
\Kreis(5,1)
\Kreis(6,1)
\Kreis(7,1)
\Label\u{m_0}(0,1)
\Label\u{m_1}(1,1)
\Label\u{m_2}(2,1)
\Label\u{m_3}(3,1)
\Label\u{m_4}(4,1)
\Label\u{m_5}(5,1)
\Label\u{m_6}(6,1)
\Label\u{m_7}(7,1)
\Kreis(0,2)
\Kreis(1,2)
\Kreis(1,3)
\Kreis(2,3)
\Kreis(2,4)
\Kreis(3,4)
\Kreis(3,5)
\Kreis(4,5)
\Pfad(0,2),1\endPfad
\Pfad(1,3),1\endPfad
\Pfad(2,4),1\endPfad
\Pfad(3,5),1\endPfad
\Label\ro{d_1}(0,2)
\Label\ro{d_2}(1,3)
\Label\ro{d_3}(2,4)
\Label\ro{d_4}(3,5)
\Label\u{0}(0,0)
\Label\u{1}(1,0)
\Label\u{2}(2,0)
\Label\u{3}(3,0)
\Label\u{4}(4,0)
\Label\u{5}(5,0)
\Label\u{6}(6,0)
\Label\u{7}(7,0)
\hskip7cm
$$
\vskip10pt
\caption{\small Monomers and dimers}
\label{F3.16}
\end{figure}

\begin{figure} 
$$
\Einheit.35cm
\Pfad(-2,0),111111111111111111\endPfad
\SPfad(0,0),22222\endPfad
\SPfad(2,0),22222\endPfad
\SPfad(4,0),22222\endSPfad
\SPfad(6,0),22222\endSPfad
\SPfad(8,0),22222\endSPfad
\SPfad(10,0),22222\endSPfad
\SPfad(12,0),22222\endSPfad
\SPfad(14,0),22222\endSPfad
\Label\u{0}(0,0)
\Label\u{1}(2,0)
\Label\u{2}(4,0)
\Label\u{3}(6,0)
\Label\u{4}(8,0)
\Label\u{5}(10,0)
\Label\u{6}(12,0)
\Label\u{7}(14,0)
\Kreis(0,2)
\Kreis(0,3)
\Kreis(2,1)
\Kreis(2,2)
\Kreis(4,1)
\Kreis(8,1)
\Kreis(10,2)
\Kreis(12,1)
\Kreis(12,2)
\Kreis(14,1)
\Pfad(0,2),11\endPfad
\Pfad(2,1),11\endPfad
\Pfad(10,2),11\endPfad
\hbox{\hskip7cm}
\Pfad(-2,0),111111111111111111\endPfad
\SPfad(0,0),22222\endPfad
\SPfad(2,0),22222\endPfad
\SPfad(4,0),22222\endSPfad
\SPfad(6,0),22222\endSPfad
\SPfad(8,0),22222\endSPfad
\SPfad(10,0),22222\endSPfad
\SPfad(12,0),22222\endSPfad
\SPfad(14,0),22222\endSPfad
\Label\u{0}(0,0)
\Label\u{1}(2,0)
\Label\u{2}(4,0)
\Label\u{3}(6,0)
\Label\u{4}(8,0)
\Label\u{5}(10,0)
\Label\u{6}(12,0)
\Label\u{7}(14,0)
\Kreis(2,2)
\Kreis(4,1)
\Kreis(4,2)
\Kreis(4,3)
\Kreis(6,1)
\Kreis(6,2)
\Kreis(8,2)
\Kreis(10,1)
\Pfad(2,2),11\endPfad
\Pfad(4,1),11\endPfad
\Pfad(6,2),11\endPfad
\hskip5cm
$$
\vskip10pt
\caption{\small Two heaps of monomers and dimers}
\label{F3.17}
\end{figure}

For example, Motzkin paths are in bijection with heaps
of monomers and dimers. To see this, given a Motzkin
path, we read the steps of the path from the beginning to the end.
Whenever we read a level-step at height $h$, we make it into a
monomer with $x$-coordinate $h$, whenever we read a down-step from height $h$ to
height $h-1$, we make it into a dimer whose end points have
$x$-coordinates $h-1$ and $h$. Up-steps are ignored. 
Figure~\ref{F3.20} shows an example.
In the figure, the heap is not in ``standard" fashion, in the sense
that the $x$-axis is not shown as a horizontal line but as a vertical
line (compare with Figure~\ref{F3.16}). But it could be easily
transformed into ``standard" fashion by a simple reflection with
respect to a line of slope $1$.

\begin{figure} 
$$
\Einheit.7cm
\Pfad(0,0),3134133444134\endPfad
\PfadDicke{.5pt}
\Pfad(0,0),1111111111111\endPfad
\DickPunkt(0,0)
\DickPunkt(1,1)
\DickPunkt(2,1)
\DickPunkt(3,2)
\DickPunkt(4,1)
\DickPunkt(5,1)
\DickPunkt(6,2)
\DickPunkt(7,3)
\DickPunkt(8,2)
\DickPunkt(9,1)
\DickPunkt(10,0)
\DickPunkt(11,0)
\DickPunkt(12,1)
\DickPunkt(13,0)
\kern1.5pt
\Pfad(3,2),4\endPfad
\Pfad(7,3),444\endPfad
\Pfad(12,1),4\endPfad
\hbox{\hskip9.5cm}
\raise.7cm\hbox{$\longrightarrow$\hskip.8cm}
\Einheit.35cm
\Pfad(0,-2),2222222222\endPfad
\SPfad(0,0),11111111\endSPfad
\SPfad(0,2),11111111\endSPfad
\SPfad(0,4),11111111\endSPfad
\SPfad(0,6),11111111\endSPfad
\Kreis(1,2)
\Kreis(2,2)
\Kreis(2,4)
\Kreis(3,2)
\Kreis(3,4)
\Kreis(3,6)
\Kreis(4,2)
\Kreis(4,4)
\Kreis(5,0)
\Kreis(5,2)
\Kreis(6,0)
\Kreis(7,0)
\Kreis(7,2)
\Pfad(2,2),22\endPfad
\Pfad(3,4),22\endPfad
\Pfad(4,2),22\endPfad
\Pfad(5,0),22\endPfad
\Pfad(7,0),22\endPfad
\Label\l{0}(0,0)
\Label\l{1}(0,2)
\Label\l{2}(0,4)
\Label\l{3}(0,6)
\hskip3.5cm
$$
\caption{\small Bijection between Motzkin paths and heaps of monomers and
dimers}
\label{F3.20}
\end{figure}

{\it Lattice animals} on the triangular lattice and on the quadratic lattice
are also in bijection with heaps, this time with heaps consisting entirely
out of dimers. Given an animal, one simply replaces each vertex of
the animal by a dimer, see Figures~\ref{fig:animal} and
\ref{fig:animal2}. While in the case of animals on the triangular
lattice this gives a constraint-less bijection (see
Figure~\ref{fig:animal}), in the case of the quadratic lattice this
sets up a bijection with heaps of dimers {\it in which two dimers
of the same type can never be placed directly one over the other} (see
Figure~\ref{fig:animal2}). For example, two dimers $d_5$, one
placed directly over the other (as they occur in
Figure~\ref{fig:animal}), are forbidden under this rule.

\begin{figure} 
$$
\Einheit1cm
\Pfad(0,0),\endPfad
\PfadDicke{.5pt}
\Pfad(0,0),3333\endPfad
\Pfad(0,1),333\endPfad
\Pfad(0,2),33\endPfad
\Pfad(0,3),3\endPfad
%\Pfad(0,5),33333\endPfad
\Pfad(4,0),8888\endPfad
\Pfad(3,0),888\endPfad
\Pfad(2,0),88\endPfad
\Pfad(1,0),8\endPfad
\Pfad(1,0),333\endPfad
\Pfad(2,0),33\endPfad
\Pfad(3,0),3\endPfad
%\Pfad(5,0),3\endPfad
\Pfad(4,1),888\endPfad
\Pfad(4,2),88\endPfad
\Pfad(4,3),8\endPfad
\Pfad(0,0),2222\endPfad
%\Pfad({0.5},0),2222\endPfad
\Pfad(1,0),2222\endPfad
%\Pfad({1.5},0),2222\endPfad
\Pfad(2,0),2222\endPfad
%\Pfad({2.5},0),2222\endPfad
\Pfad(3,0),2222\endPfad
%\Pfad({3.5},0),2222\endPfad
\hbox{\hskip.5\Einheit}
\Pfad(0,0),2222\endPfad
\Pfad(1,0),2222\endPfad
\Pfad(2,0),2222\endPfad
\Pfad(3,0),2222\endPfad
\hbox{\hskip-.5\Einheit}
\Pfad(4,0),2222\endPfad
\DickPunkt(2,2)
\DickPunkt(2,1)
\DickPunkt({1.5},{2.5})
\DickPunkt({2.5},{2.5})
\DickPunkt({2.5},{0.5})
\hbox{\hskip5cm}
\raise1.7cm\hbox{$\longrightarrow$\hskip.8cm}
\Einheit.35cm
\Pfad(-2,0),111111111111111111\endPfad
\SPfad(0,0),22222\endPfad
\SPfad(2,0),22222\endPfad
\SPfad(4,0),22222\endSPfad
\SPfad(6,0),22222\endSPfad
\SPfad(8,0),22222\endSPfad
\SPfad(10,0),22222\endSPfad
\SPfad(12,0),22222\endSPfad
\SPfad(14,0),22222\endSPfad
\SPfad(16,0),22222\endSPfad
\Label\u{0}(0,0)
\Label\u{1}(2,0)
\Label\u{2}(4,0)
\Label\u{3}(6,0)
\Label\u{4}(8,0)
\Label\u{5}(10,0)
\Label\u{6}(12,0)
\Label\u{7}(14,0)
\Label\u{8}(16,0)
\Kreis(10,1)
\Kreis(12,1)
\Kreis(8,2)
\Kreis(10,2)
\Kreis(8,3)
\Kreis(10,3)
\Kreis(6,4)
\Kreis(8,4)
\Kreis(10,4)
\Kreis(12,4)
\Pfad(10,1),11\endPfad
\Pfad(8,2),11\endPfad
\Pfad(8,3),11\endPfad
\Pfad(6,4),11\endPfad
\Pfad(10,4),11\endPfad
\hskip6cm
$$
\caption{\small Bijection between animals and heaps of dimers}
\label{fig:animal}
\end{figure}

\begin{figure} 
$$
\Einheit1cm
\Pfad(0,0),\endPfad
\PfadDicke{.5pt}
\Pfad(0,0),3333\endPfad
\Pfad(0,1),333\endPfad
\Pfad(0,2),33\endPfad
\Pfad(0,3),3\endPfad
%\Pfad(0,5),33333\endPfad
\Pfad(4,0),8888\endPfad
\Pfad(3,0),888\endPfad
\Pfad(2,0),88\endPfad
\Pfad(1,0),8\endPfad
\Pfad(1,0),333\endPfad
\Pfad(2,0),33\endPfad
\Pfad(3,0),3\endPfad
%\Pfad(5,0),3\endPfad
\Pfad(4,1),888\endPfad
\Pfad(4,2),88\endPfad
\Pfad(4,3),8\endPfad
\DickPunkt(2,2)
\DickPunkt(2,1)
\DickPunkt({1.5},{1.5})
\DickPunkt({2.5},{1.5})
\DickPunkt({2.5},{0.5})
\hbox{\hskip5cm}
\raise.7cm\hbox{$\longrightarrow$\hskip.8cm}
\Einheit.35cm
\Pfad(-2,0),111111111111111111\endPfad
\SPfad(0,0),22222\endPfad
\SPfad(2,0),22222\endPfad
\SPfad(4,0),22222\endSPfad
\SPfad(6,0),22222\endSPfad
\SPfad(8,0),22222\endSPfad
\SPfad(10,0),22222\endSPfad
\SPfad(12,0),22222\endSPfad
\SPfad(14,0),22222\endSPfad
\SPfad(16,0),22222\endSPfad
\Label\u{0}(0,0)
\Label\u{1}(2,0)
\Label\u{2}(4,0)
\Label\u{3}(6,0)
\Label\u{4}(8,0)
\Label\u{5}(10,0)
\Label\u{6}(12,0)
\Label\u{7}(14,0)
\Label\u{8}(16,0)
\Kreis(10,1)
\Kreis(12,1)
\Kreis(8,2)
\Kreis(10,2)
\Kreis(8,4)
\Kreis(10,4)
\Kreis(6,3)
\Kreis(8,3)
\Kreis(10,3)
\Kreis(12,3)
\Pfad(10,1),11\endPfad
\Pfad(8,2),11\endPfad
\Pfad(8,4),11\endPfad
\Pfad(6,3),11\endPfad
\Pfad(10,3),11\endPfad
\hskip6cm
$$
\caption{\small Bijection between animals and heaps of dimers}
\label{fig:animal2}
\end{figure}

Next we make heaps into a {\em monoid\/} by introducing a
{\em composition} of heaps. (A monoid is a
set with a binary operation which is associative.) Intuitively, given
two heaps $H_1$ and $H_2$, the composition of $H_1$ and $H_2$, 
the heap $H_1\circ H_2$, is the heap which
results by putting $H_2$ on top of $H_1$. In terms of words, the
composition of two heaps is the equivalence class of the concatenation
$uw$, where $u$ is a word from the equivalence class of $H_1$, and
$w$ is a word from the equivalence class of $H_2$.


The composition of the two heaps in Figure~\ref{F3.17} is shown in
Figure~\ref{F3.18}.

\begin{figure} 
$$
\Einheit.35cm
\Pfad(-2,0),11111111111111111111\endPfad
\SPfad(0,0),22222\endPfad
\SPfad(2,0),22222\endPfad
\SPfad(4,0),22222\endSPfad
\SPfad(6,0),22222\endSPfad
\SPfad(8,0),22222\endSPfad
\SPfad(10,0),22222\endSPfad
\SPfad(12,0),22222\endSPfad
\SPfad(14,0),22222\endSPfad
\SPfad(16,0),22222\endSPfad
\Label\u{0}(0,0)
\Label\u{1}(2,0)
\Label\u{2}(4,0)
\Label\u{3}(6,0)
\Label\u{4}(8,0)
\Label\u{5}(10,0)
\Label\u{6}(12,0)
\Label\u{7}(14,0)
\Label\u{8}(16,0)
\Kreis(0,2)
\Kreis(0,3)
\Kreis(2,1)
\Kreis(2,2)
\Kreis(2,3)
\Kreis(4,1)
\Kreis(4,2)
\Kreis(4,3)
\Kreis(4,4)
\Kreis(6,2)
\Kreis(6,3)
\Kreis(8,1)
\Kreis(8,3)
\Kreis(10,2)
\Kreis(10,3)
\Kreis(12,1)
\Kreis(12,2)
\Kreis(14,1)
\Pfad(0,2),11\endPfad
\Pfad(2,1),11\endPfad
\Pfad(2,3),11\endPfad
\Pfad(4,2),11\endPfad
\Pfad(6,3),11\endPfad
\Pfad(10,2),11\endPfad
\hskip5.6cm
$$
\vskip10pt
\caption{\small The composition of the heaps in Figure~\ref{F3.17}}
\label{F3.18}
\end{figure}


Given pieces $\Bau$ with relation $\Rel$,
let \glossary{$\mathcal H(\Bau, \Rel)$}$\mathcal H(\Bau, \Rel)$ 
be the set of all heaps consisting of pieces
from $\Bau$, including the empty heap, the latter 
denoted by $\emptyset$. It is easy
to see that the composition makes $(\mathcal H(\Bau,\Rel),\circ)$
into a monoid with unit $\emptyset$.

\medskip
For the statement of the main theorem in the theory of heaps, we need
two more terms. A {\em
trivial heap} is a heap consisting of pieces all of which are
pairwise unrelated. 
Figure~\ref{F3.19}.a shows a trivial heap consisting of
monomers and dimers. 
A {\em pyramid\/} is a heap with exactly one
maximal (=~top-most) element.
Figure~\ref{F3.19}.a shows a pyramid consisting of
monomers and dimers. Finally, if $H$ is a heap, then we write $\vert{H}\vert$
for the number of pieces in $H$.

\begin{figure} 
$$
\Einheit.35cm
\Pfad(-2,0),111111111111111111\endPfad
\SPfad(0,0),22222\endPfad
\SPfad(2,0),22222\endPfad
\SPfad(4,0),22222\endSPfad
\SPfad(6,0),22222\endSPfad
\SPfad(8,0),22222\endSPfad
\SPfad(10,0),22222\endSPfad
\SPfad(12,0),22222\endSPfad
\SPfad(14,0),22222\endSPfad
\Label\u{0}(0,0)
\Label\u{1}(2,0)
\Label\u{2}(4,0)
\Label\u{3}(6,0)
\Label\u{4}(8,0)
\Label\u{5}(10,0)
\Label\u{6}(12,0)
\Label\u{7}(14,0)
\Kreis(2,1)
\Kreis(4,1)
\Kreis(8,1)
\Kreis(10,1)
\Kreis(12,1)
\Kreis(14,1)
\Pfad(2,1),11\endPfad
\Pfad(10,1),11\endPfad
\hbox{\hskip7cm}
\Pfad(-2,0),1111111111111111\endPfad
\SPfad(0,0),2222222\endPfad
\SPfad(2,0),2222222\endPfad
\SPfad(4,0),2222222\endSPfad
\SPfad(6,0),2222222\endSPfad
\SPfad(8,0),2222222\endSPfad
\SPfad(10,0),2222222\endSPfad
\SPfad(12,0),2222222\endSPfad
\Label\u{0}(0,0)
\Label\u{1}(2,0)
\Label\u{2}(4,0)
\Label\u{3}(6,0)
\Label\u{4}(8,0)
\Label\u{5}(10,0)
\Label\u{6}(12,0)
\Kreis(0,2)
\Kreis(2,1)
\Kreis(2,2)
\Kreis(2,3)
\Kreis(4,1)
\Kreis(4,2)
\Kreis(4,3)
\Kreis(4,4)
\Kreis(6,2)
\Kreis(6,3)
\Kreis(8,1)
\Kreis(8,3)
\Kreis(10,2)
\Kreis(10,3)
\Kreis(12,1)
\Kreis(12,2)
\Kreis(8,4)
\Kreis(10,4)
\Kreis(6,4)
\Kreis(8,5)
\Kreis(6,6)
\Kreis(8,6)
\Pfad(0,2),11\endPfad
\Pfad(2,1),11\endPfad
\Pfad(2,3),11\endPfad
\Pfad(4,2),11\endPfad
\Pfad(6,3),11\endPfad
\Pfad(10,2),11\endPfad
\Pfad(8,4),11\endPfad
\Pfad(4,4),11\endPfad
\Pfad(6,6),11\endPfad
\hskip5cm
$$
\vskip10pt
\caption{\small a. A trivial heap\hskip5cm b. A pyramid}
\label{F3.19}
\end{figure}

In applications, heaps will have weights, which are defined by
introducing a weight $w(B)$ for each piece $B$ in $\Bau$, and by
extending the weight $w$ to all heaps $H$ by letting $w(H)$ denote
the product of all weights of the pieces in $H$ (multiplicities of
pieces included). 

Let $\mathcal M$ be a subset of the pieces $\Bau$. Then, 
the generating function for all heaps with maximal pieces
contained in $\mathcal M$ is given by
\begin{equation} \label{e3.37}
\underset{\text {maximal pieces }\subseteq\mathcal M}
{\sum _{H\in \mathcal H(\Bau,\Rel)} ^{}}\kern-15pt w(H)=
\frac {\sum _{T\in \mathcal T(\Bau\backslash\mathcal M,\Rel)} 
^{}(-1)^{\vert{T}\vert}w(T)}
{\sum _{T\in \mathcal T(\Bau,\Rel)} ^{}(-1)^{\vert{T}\vert}w(T)},
\end{equation}
where $\mathcal T(\Bau,\Rel)$ denotes the set of all trivial heaps
with pieces from $\Bau$.
In particular, the generating function for {\it all\/} heaps is given by
\begin{equation} \label{e3.38}
{\sum _{H\in \mathcal H(\Bau,\Rel)} ^{}}w(H)=
\frac {1} {\sum _{T\in \mathcal T(\Bau,\Rel)} ^{}(-1)^{\vert{T}\vert}w(T)}.
\end{equation}



%It is not difficult to see that this sets up a bijection between
%Motzkin paths starting at the origin and returning to the $x$-axis
%which stay below the line $y=k$ and pyramids of monomers
%$\{m_0,m_1,\dots,m_k\}$ and dimers $\{d_1,d_2\dots,d_k\}$
%with maximal piece being either $m_0$ (a monomer with $x$-coordinate
%$0$) or $d_1$ (a dimer whose end points have $x$-coordinates $0$ and
%$1$). In particular, the set of pieces is
%$\Bau=\{m_0,m_1,\dots,m_k,d_1,d_2,\dots,d_k\}$, with relation $\Rel$. 

Furthermore, if $\mathcal P(\Bau,\Rel)$ denotes the set of all pyramids
with pieces from $\Bau$, then
\begin{equation} \label{eq:pyr} 
{\sum _{P\in \mathcal P(\Bau,\Rel)} ^{}}\frac {w(P)} {\vert P\vert}=
\log\bigg({\sum _{H\in \mathcal H(\Bau,\Rel)} ^{}}w(H)\bigg),
\end{equation}
where $\vert P\vert$ is the number of pieces of $P$. (As the reader
will have guessed, this is a consequence of the ``exponential
principle" mentioned in Section~\ref{sec:GF}.)

\section{The transfer matrix method} \label{sec:transfer}

The transfer matrix method
(cf.\ \cite[Ch.~4]{StanAP} for further
reading) applies whenever we are able to build the
combinatorial objects that we are interested in by moving on a finite
number of states in a step-by-step
fashion, where the current step does not depend on the previous ones.
(In statistical language, we are considering a {\it finite
state Markov chain}.) For example, Motzkin paths which are constrained
to stay between two parallel lines, say between $y=0$ and $y=K$, can
be described in such a way: the states are the heights $0,1,\dots,K$,
and, if we are in state $h$, then in the next step we are allowed to
move to states $h+1$, $h$, or $h-1$, except that from state $0$ we
cannot move to $-1$ (there is no state $-1$), and when we are in state
$K$ we cannot move to $K+1$ (there is no state $K+1$).

For describing the general situation,
let $G=(V,E)$ be a directed graph with vertex set $V$ and edge set
$E$. Let $w_n(u,v)$ denote the number of walks from vertex $u$ to
vertex $v$ along edges of $G$. To compute these numbers, we
consider the {\it adjacency matrix} of $G$, $A(G)$. By definition,
using our notation, $A(G)=(w_1(u,v))_{u,v\in V}$. Obviously,
$(w_n(u,v))_{u,v\in V}=(A(G))^n$. Thus,
$$\(
\sum _{n=0} ^{\infty}w_n(u,v)\,x^n\)_{u,v\in V}=
\sum _{n=0} ^{\infty}(A(G))^n\,x^n=\(I_n-A(G)x\)^{-1},$$
where $I_n$ is the $n\times n$ identity matrix.
In other words, the generating functions $\sum _{n=0}
^{\infty}w_n(u,v)\,x^n$ for the walk numbers between $u$ and $v$ form
the entries of a matrix which is the inverse matrix of $I_n-A(G)x$.
By elementary linear algebra,
\begin{equation} \label{eq:uv} 
\sum _{n=0} ^{\infty}w_n(u,v)\,x^n=
\frac {(-1)^{\#u+\#v}\det(I_n-A(G)x)_{v,u}} {\det(I_n-A(G)x)},
\end{equation}
where $\det(I_n-A(G)x)_{v,u}$ is the minor of $I_n-A(G)x$ with the
row indexed by $v$ and the column indexed by $u$ omitted, and where
$\#u$ denotes the row number of $u$ and similarly for $\#v$.
A weighted version could also be developed in the same way, where
we put a weight $w(e)$ on each edge, and the weight of a walk is the
product of the weights of all its edges.

In particular, the expression \eqref{eq:uv} 
is a {\it rational function} in $x$. 
Then, by the basic theorem on rational generating functions
(cf.\ \cite[Sec.~4.1]{StanAP}), the number $w_n(u,v)$ can be expressed
as a sum $\sum _{i=1} ^{d}P_i(n)\ga_i^n$, where the $\ga_i$'s are
the different roots of the polynomial $\det(xI_n-A(G))$, and $P_i(n)$
is a polynomial of degree less than the multiplicity of the root
$\ga_i$. (The $P_i(n)$'s depend on $u$ and $v$, whereas the $\ga_i$'s
do not.) If there exists a unique root $\ga_j$ with maximal modulus,
then this implies that, asymptotically as $n\to\infty$,
$w_n(u,v)\sim P_j(n)\ga_j^n$.


\section{Lattice paths} \label{sec:paths}

Recall from Section~\ref{sec:basic}, that
a {\it lattice path} $P$ in $\mathbb Z^d$ is a path in the $d$-dimensional
integer lattice $\mathbb Z^d$ which uses only points of the lattice,
that is, it is a sequence $(P_0,P_1,\dots,P_l)$, where $P_i\in \mathbb
Z^d$ for all $i$. The vectors
$\overrightarrow {P_0P_1},\overrightarrow {P_1P_2}, \dots, \overrightarrow
{P_{l-1}P_{l}}$ are called the {\em steps} of $P$. The number of
steps, $l$, is called the {\em length} 
of $P$.

%\newbox\figbox
%\setbox\figbox\hbox{\small 
%A lattice path}
%
%\begin{figure}[h]
%$$
%\Gitter(12,5)(-1,0)
%\Koordinatenachsen(12,5)(-1,0)
%\Pfad(0,1),13141133444\endPfad
%\DickPunkt(0,1)
%\DickPunkt(11,0)
%\PfadDicke{.5pt}
%\Pfad(-2,4),11111111111111\endPfad
%\Label\l{y=R-2}(-3,4)
%\hbox{\hskip6.5cm}
%$$
%\caption{\unhbox\figbox}
%\label{fig1}
%\end{figure}

The enumeration of lattice paths has always been an intensively
studied topic in statistics, because of their importance in the
study of {\it random walks}, of
{\it rank order statistics} for {\it non-parametric testing}, and
of {\it queueing processes}. The reader is referred to \cite{FellAA}
and particularly 
Mohanty's book \cite{MohaAE}, which is a rich source for enumerative
results on lattice paths, albeit in a statistical language.
We review the most important results in this section.
Most of these concern 2-dimensional lattice paths, i.e., the case $d=2$. 

To begin with, we consider paths in the integer plane $\mathbb Z^2$
consisting of horizontal and vertical
unit steps in the positive direction.
Clearly, the number of all (unrestricted) paths from the origin to
$(n,m)$ is the binomial coefficient $\binom {n+m}n$. By the {\it
reflection principle}, which is commonly attributed to D.~Andr\'e
(see e.g.\ \cite[p.~22]{ComtAA}), it
follows that the number of paths from the origin to $(n,m)$ which do
not pass above the line $y=x+t$, where $m\le n+t$, is given 
by\footnote{Roughly, the reflection principle
sets up a bijection between the paths from the origin to $(n,m)$
which {\it do pass above} the line $y=x+t$ and {\it all\/} paths from
$(-t-1,t+1)$ to $(n,m)$, by reflecting the path portion between the
origin and the last touching point on $y=x+t+1$ in this latter
line. Thus, the result of the enumeration problem is the number of
{\it all\/} paths from $(0,0)$ to $(n,m)$, which is given by the
binomial coefficient $\binom {n+m}n$, minus the number of {\it all\/}
paths from $(-t-1,t+1)$ to $(n,m)$, which is given by the binomial
coefficient $\binom {n+m}{n+t+1}$, whence the formula \eqref{eq:ref1}.}
\begin{equation} \label{eq:ref1}
\binom {n+m} {n} -
\binom {n+m}{n+t+1}. 
\end{equation}

If one considers more generally paths bounded by the line
$my=nx+t$, no compact formula is known.
It seems that the most
conceptual way to approach this problem is through the
so-called {\it kernel method} (see Section~\ref{sec:kernel}), which, in
combination with the saddle point method, allows one also to obtain
strong asymptotic results.
There is one special instance, however, which has a ``nice"
formula. The number of all lattice paths from the origin to
$(n,m)$ which never pass above $x=\mu y$, where $\mu$ is a positive
integer, is given by
\begin{equation} \label{e1.8}
\frac {n-\mu m+1} {n+m+1}\binom
{n+m+1} {m}  .
\end{equation}
The most elegant way to prove this formula is by means of the {\it
cycle lemma} of Dvoretzky and Motzkin (see
\cite[p.~9]{MohaAE}, where the cycle lemma occurs under the name of
``penetrating analysis"). 

Iteration of the reflection principle shows that the 
number of paths from the origin to $(n,m)$ which stay
between the lines $y=x+t$ and $y=x+s$ (being allowed to touch them), 
where $t\ge 0\ge s$ and $n+t\ge m\ge n+s$, is given by the finite (!) sum
(see e.g.\ \cite[p.~6]{MohaAE})
\begin{equation} \label{eq:ref2}
\sum _{k\in\mathbb Z} ^{}\left(\binom
{n+m} {n-k(t-s+2)}-\binom {n+m}{n-k(t-s+2)+t+1}\right).
\end{equation}

\medskip
The enumeration of lattice paths restricted to regions bounded by hyperplanes
has also been considered for other regions, such as quadrants, octants, 
and rectangles, as well as in higher dimensions.
A general result due to Gessel and Zeilberger, and Biane,
independently, on the number of lattice 
paths in a chamber (alcove) of an (affine) reflection group 
(see \cite{KratBT} for the corresponding
references and pointers to further results) shows
how far one can go when one uses the reflection principle. In particular,
this result covers \eqref{eq:ref1} and \eqref{eq:ref2}, the
enumeration of lattice paths in quadrants, octants, rectangles, and many other
results that have appeared (before and after) in the literature.
We present a particularly elegant (and frequently occurring) special
case. (In reflection group language, it corresponds to the
reflection group of ``type $A_{n-1}$". See \cite{HumpAC} for
terminology and information on reflection groups.)

{\em
Let $A=(a_1,a_2,\dots,a_d)$ and $E=(e_1,e_2,\dots,e_d)$ be points in
$\mathbb Z^d$ with $a_1\ge a_2\ge\dots\ge a_d$ and $e_1\ge e_2\ge\dots\ge
e_d$. The number of all paths from $A$ to $E$ in the integer lattice
$\mathbb Z^d$, which consist of
positive unit steps and which stay in the region
$x_1\ge x_2\ge\dots\ge x_d$, equals
\begin{equation} \label{e7.2} 
\Big(\sum _{i=1}
^{d}(e_i-a_i)\Big)! 
\det_{1\le i,j\le d}\left(\frac {1} {(e_i-a_j-i+j)!}\right).
\end{equation}}

The counting problem of the theorem is equivalent to numerous other counting
problems. It has been originally formulated as an $n$-candidate 
ballot problem, but it is as well equivalent to counting the
number of standard Young tableaux of a given shape. 
In the case that all $a_j$'s are equal, the
determinant does in fact evaluate into a closed form product.
In Young tableaux theory a particular way to write the result is known as the 
{\it hook-length formula} (see e.g.\ \cite[Cor.~7.21.6]{StanBI}).

\medskip
We return to lattice paths in the plane, mentioning 
some more closely related results. The first is a
result of Mohanty \cite[Sec.~4.2]{MohaAE}, which
expresses the number of all lattice paths from the origin to $(n,m)$
which touch the line $y=x+t$ {\it exactly} $r$ times, never
crossing it, as the difference
\begin{equation} \label{eq:touch}
\binom {n+m-r}{n+t-1}-\binom {n+m-r}{n+t},\quad \quad r\ge1. 
\end{equation}

Not forbidding that the paths cross the bounding line, we arrive at
the problem of counting the lattice paths from the origin to $(n,m)$, which
cross the main diagonal $y=x$ exactly $r$ times, the answer being
\begin{equation} \label{} 
\begin{cases} %\displaystyle
\frac {m-n+2r+1} {m+n+1}\binom {m+n+1}{n-r}&\text{if }m>n,\\
%\displaystyle
\frac {2r+2} {n}\binom {2n}{n-r-1}&\text{if }m=n.
\end{cases}
\end{equation}
Next, we give the number of lattice paths from the
origin to $(n,n)$ which have $2r$ steps on one side of the line $y=x$, as
\begin{equation} \label{} 
\binom {2r}r\binom {2n-2r}{n-r},
\end{equation}
a result due to Sparre Andersen.
We refer the reader to \cite[Ch.~3]{MohaAE} for further results in
this direction.

\medskip
Enumerating lattice paths with a fixed number of maximal straight
pieces (which correspond to runs), 
is intimately connected to another basic enumeration problem
concerning lattice paths: the enumeration of lattice paths having 
a fixed number
of {\it turns}. An effective way to attack the latter problem is by
means of {\it two-rowed arrays}, see the survey article \cite{KratBL},
where in particular analogues of the reflection principle for
two-rowed arrays are developed. These imply formulas for the number
of lattice paths with fixed starting and end points and a fixed 
number of {\it north-east} (respectively {\it east-north}) {\it
turns}, for unrestricted paths, as well as for paths
bounded by lines. (A north-east turn in a lattice path is a point where
the direction changes from ``north" to ``east." An east-north turn is
defined analogously.)
In particular, analogues of \eqref{eq:ref1}--\eqref{eq:ref2} 
are known when the number of north-east (respectively
east-north) turns is fixed.

These formulas imply for example (see again \cite[Sec.~3.5]{KratBL}) that the
number of lattice paths from the origin to $(n,n)$ which never pass
above the line $y=x+t$ and have exactly $2r$ maximal straight pieces
is given by
\begin{equation} \label{eq:D+R}
2{\binom{n-1}{r-1}}^2-
{\binom {n+t-1}{r-2}}{\binom{n-t-1}{r}} -
{ \binom{n+t-1}{r-1}}{\binom{n-t-1}{r-1}},
\end{equation}
with a similar result for the case of $2r+1$ maximal straight 
pieces.\footnote{If $t=0$, the numbers in \eqref{eq:D+R} become
$\frac {1} {n}\binom nr\binom n{r-1}$, and they are known as the 
{\it Narayana numbers}.}
Furthermore, they imply that the
number of lattice paths from the origin to $(n,n)$ which never pass
above the line $y=x+t$ and never below the line $y=x-t$ and have 
exactly $2r$ maximal straight pieces is given by
\begin{multline} \label{eq:DR}
\sum _{k=-\infty}^{\infty}
\Bigg\{2{\binom{n-2kt-1}{r+k-1}}{\binom{n+2kt-1}{r-k-1}}\\-
{\binom {n-2kt+t-1}{r+k-2}}{\binom{n+2kt-t-1}{r-k}}\\
 \qquad -
{ \binom{n-2kt+t-1}{r+k-1}}{\binom{n+2kt-t-1}{r-k-1}}\Bigg\},
\end{multline}
with a similar result for the case of $2r+1$ maximal straight pieces. 

\medskip
The most general boundary for lattice paths that one can
imagine is the restriction that it stays between two given (fixed)
paths. Let us assume that the horizontal steps of the upper (fixed) path
are at heights $a_1\le a_2\le \dots\le a_n$, whereas the 
horizontal steps of the lower (fixed) path are at heights 
$b_1\le b_2\le \dots\le b_n$, $a_i\ge b_i$, $i=1,2,\dots,n$.
Then the number of all
paths from $(0,b_1)$ to $(n,a_n)$ satisfying the property that 
for all $i=1,2,\dots,n$ the height of the $i$-th horizontal step is
between $b_i$ and $a_i$ is given by the determinant
\begin{equation} \label{e1.30}
\det_{1\le i,j\le n}\left(\binom {a_i-b_j+1}{j-i+1}\right). 
\end{equation}
In the statistical literature, this formula is often known as 
``Steck's formula", but it is actually a special case of a
much more general theorem due to Kreweras.
A generalization of \eqref{e1.30} to higher dimensional paths was
given by Handa and Mohanty (see \cite[Sec.~2.4]{MohaAE}. 

Next, we consider three-step 
lattice paths in the integer plane $\mathbf Z^2$, that is, paths
consisting of up-steps $(1,1)$, level steps $(1,0)$, and down-steps
$(1,-1)$. 
The particular problem that we are interested in is to count
such three-step paths
starting at $(0,r)$ and ending at $(\ell,s)$, which do
not pass below the $x$-axis and do not pass above the horizontal line
$y=K$. Furthermore, we assign the weight 1 to an
up-step, the
weight $b_h$ to a level-step at height $h$, and the weight $\lambda_h$
to a down-step from height $h$ to $h-1$. The weight $w(P)$
of a path $P$ is defined as the product of the weights of all its
steps. Then we have the following result, which can be obtained
by the transfer matrix method described in Section~\ref{sec:transfer}.

{\em
Define the sequence $(p_n(x))_{n\ge0}$ of polynomials
by
\begin{equation} \label{A.2} 
xp_{n}(x)=p_{n+1}(x)+b_np_n(x)+\lambda_{n}p_{n-1}(x),\quad \quad 
\text{ for } n\geq 1,
\end{equation}
with initial conditions $p_0(x)=1$ and $p_1(x)=x-b_0$.
Furthermore, define\break $(Sp_n(x))_{n\ge0}$ to be the sequence of
polynomials which arises from the sequence $(p_n(x))$ by replacing $\lambda_i$ by
$\lambda_{i+1}$ and $b_i$ by $b_{i+1}$, $i=0,1,2,\dots$, everywhere in
the three-term recurrence \eqref{A.2} and in the initial
conditions. Finally, given a polynomial $p(x)$ of degree $n$, we
denote the corresponding reciprocal polynomial
$x^np(1/x)$ by $p^*(x)$.

With the weight $w$ defined as before, the generating function $\sum
_{P} ^{}w(P)x^{\ell(P)}$, where the sum is over all
three-step paths $P$ which start at $(0,r)$, terminate at height $s$,
do not pass below the $x$-axis,
and do not pass above the line $y=K$,
and where $\ell(P)$ denotes the length of $P$, is given by
\begin{equation} \label{eq:gf} 
\begin{cases} \dfrac {x^{s-r}p^*_r(x)S^{s+1}p_{K-s}^*(x)} {p_{K+1}^*(x)}
&r\le s,\\
\lambda_r\cdots\lambda_{s+1}\dfrac {x^{r-s}p^*_s(x)S^{r+1}p_{K-r}^*(x)}
{p_{K+1}^*(x)}
&r\ge s.
\end{cases}
\end{equation}}

The sequence of polynomials $(p_n(x))_{n\ge0}$
is in fact a sequence of {\it orthogonal polynomials}
(cf.\ \cite{KoSwAA,SzegOP}).

We remark that in the case that $r=s=0$ there is also an elegant
expression for the generating function due to Flajolet (see \cite[Sec.~V.2]{FlSeAA})
in terms of a continued fraction.

In order to solve our problem, we just have to extract the coefficient
of $x^\ell$ in \eqref{eq:gf}. By a partial fraction expansion, 
a formula of the type
\begin{equation} \label{eq:part} 
\sum _{m} ^{}c_m\xi_m^\ell,
\end{equation}
results, where the $\xi_m$'s are the zeroes of $p_{K+1}(x)$, and the
$c_m$'s are some coefficients, only a finite number of them being non-zero.

It should be noted that, because of the many available parameters (the
$b_n$'s and $\lambda_n$'s), by appropriate specializations one can also
obtain numerous results about enumerating three-step paths according
to various statistics, such as the number of touchings on the bounding
lines, etc. 

There are two important special cases, in which a completely explicit
solution in terms of elementary functions can be given. 

The first case occurs for $b_i=0$ and $\lambda_i=1$ for all $i$.
In this case, the polynomials
$p_n(x)$ defined by the three-term recurrence \eqref{A.2} are Chebyshev
polynomials of the second kind,\footnote{The Chebyshev polynomial of
the second kind $U_n(x)$ is defined by $U_n(\cos t)=\sin((n+1)t)/\sin
t$ (see \cite{KoSwAA} for almost exhaustive 
information on these polynomials and,
more generally, on hypergeometric orthogonal polynomials).}
$p_n(x)=U_n(x/2)$. The result which is then obtained from the
general theorem
(clearly, the zeroes of
$U_n(x)$ are $x=\cos(2k\pi/(n+1))$, $k=1,2,\dots,n$, and therefore the
partial fraction expansion of \eqref{eq:gf} is easily determined)
is that the number of lattice paths from $(0,r)$ to $(\ell,s)$ with
only up- and down-steps, which always stay between the $x$-axis and the
line $y=K$, is given by (see also \cite[Ch.~XIV, Eq.~(5.7)]{FellAA})
\begin{equation} \label{sincos1}
\frac {2} {K+2}\sum _{k=1} ^{K+1}
\left(2\cos \frac {\pi k} {K+2}\right)^\ell\cdot
\sin\frac {\pi k(r+1)} {K+2}\cdot \sin\frac
{\pi k(s+1)} {K+2},
\end{equation}
a formula which goes back to Lagrange.

The second case occurs for $b_i=1$ and $\lambda_i=1$ for all $i$.
In this case, the polynomials
$p_n(x)$ defined by the three-term recurrence \eqref{A.2} are again Chebyshev
polynomials of the second kind,
$p_n(x)=U_n((x-1)/2)$. The result which is then obtained from 
the general theorem
is that the number of three-step lattice paths from $(0,r)$ to $(\ell,s)$,
which always stay between the $x$-axis and the
line $y=K$, is given by
\begin{equation} \label{sincos2}
\frac {2} {K+2}\sum _{k=1} ^{K+1}
\left(2\cos \frac {\pi k} {K+2}+1\right)^\ell\cdot
\sin\frac {\pi k(r+1)} {K+2}\cdot \sin\frac
{\pi k(s+1)} {K+2}. 
\end{equation}





\section{Perfect matchings and tilings} \label{sec:Kast}

In this section we consider the problem of counting the perfect
matchings of a graph. For an introduction into the problem, and into
methods to solve it, as well as for a report on recent developments,
we refer the reader to \cite{PropAH}.

Let $G=(V,E)$ be a finite loopless graph with vertex set $V$ and edge set $E$.
A {\it matching} (also called {\it $1$-factor} in graph theory) 
is a subset of the edges with the property that no
two edges share a vertex. A matching is {\it perfect} if it covers all
the edges. Let $M(G)$ denote the number of perfect matchings of the
graph $G$. More generally, we could assign a weight $w(e)$ to each
edge $e$ of the graph and define the weight of a matching to be the
product of the weights of all its edges. Let $M_w(G)$ denote the sum
of all weights of all matchings of the graph $G$.

Kasteleyn's method for determining $M(G)$, respectively
$M_w(G)$, makes use of determinants and Pfaffians. Recall that the
{\it Pfaffian} $\Pf(A)$ of a triangular array $A=(a_{i,j})_{1\le
i<j\le 2n}$ is defined by
\begin{equation} \label{eq:Pf} 
\Pf(A)=
\sum _{m} ^{}(\sgn m)
\prod _{\{i,j\}\in m} ^{}a_{i,j},
\end{equation}
where the sum is over all perfect matchings of the complete graph
on vertices $\{1,2,\dots,2n\}$, and where the product is over all
edges $\{i,j\}$, $i<j$, of $m$. The sign $\sgn m$ of $m$ is 
$(-1)^{\#\text{crossings of }m}$, where a crossing is a pair
$(\{i,j\},\{k,l\})$ of edges such that $i<k<j<l$.
Usually, one extends the triangular array $A$ to a 
matrix by setting $a_{j,i}=-a_{i,j}$, $i<j$, and $a_{i,i}=0$ for all
$i$. Then, abusing notation, we identify the triangular array with 
the skew-symmetric matrix $A=(a_{i,j})_{1\le i,j\le 2n}$. The Pfaffian
satisfies the following useful properties:
$$\Pf(B^tAB)=\det(B)\Pf(A)$$
and
\begin{equation} \label{eq:Pfdet} 
\Pf(A)^2=\det(A).
\end{equation}
The latter equality shows in particular that Pfaffians are very close
to determinants. They do, in fact, generalize determinants since
\begin{equation} \label{eq:Pfdet2} 
\Pf\begin{pmatrix} \hphantom{-}0 &B\\-B &0\end{pmatrix}=\det B,
\end{equation}
for any square matrix $B$.

Thus, given a graph with vertices $v_1,v_2,\dots,v_{2n}$,
specializing $a_{i,j}$ to the weight of the edge between $v_i$
and $v_j$ if it exists and setting $a_{i,j}=0$ otherwise
in the definition of the Pfaffian, we obtain almost $M_w(G)$, the only
difference is that there could be signs in front of the individual
terms of the sum, whereas in $M_w(G)$ the sign in front of each term
must be $+$. (The object which one obtains by omitting the sign
in \eqref{eq:Pf} is called {\it Hafnian}. Unfortunately, in contrast
to the Pfaffian, it does not have any nice properties and it is
therefore extremely difficult to compute.) Kasteleyn's idea is to
circumvent this problem by orienting the edges of the graph, defining 
signed weights of the edges, in such a way that the Pfaffian of the
array with signed weights produces exactly $M_w(G)$.

More precisely, given a (weighted) graph $G$ with vertices
$v_1,v_2,\dots,v_{2n}$, 
we make it into an oriented (weighted) graph
$\overrightarrow G$. That is, if there is an edge between $v_i$ and
$v_j$, $e_{i,j}$ say, we orient it either from $v_i$ to $v_j$ or the
other way.
Now we define the {\it signed adjacency matrix}
$A(\overrightarrow G)$ of $\overrightarrow G$ by letting its
$(i,j)$-entry to be $+w(e_{i,j})$ if there is an edge from $v_i$ to
$v_j$ oriented that way, $-w(e_{i,j})$ if there is an edge from $v_j$ to
$v_i$ oriented that way, and $0$ if there is no edge between $v_i$ and
$v_j$. Such an orientation is called {\it Pfaffian} if
$$\Pf(A(\overrightarrow G))=\pm M_w(G).$$

Clearly, the question remains whether a Pfaffian orientation can be
found for a given graph. In general, this is an open question.
However, Kasteleyn shows that for {\it planar} graphs such a Pfaffian
orientation can always be found. Moreover, he shows that any
orientation of a planar graph which has the property that around any
face bounded by $4k$ edges an odd number of edges is oriented in
either direction and that around any
face bounded by $4k+2$ edges an even number of edges is oriented in
either direction is Pfaffian.

For {\it bipartite} graphs (that is, for graphs in which the set of
vertices can be split into two disjoint sets such that all the edges
connect the vertex of one of these sets to a vertex of the other), the
situation is even nicer. This is because for a bipartite graph $G$
in which both parts of the bipartition of the vertices are of the same
size (otherwise there is no perfect matching),
any signed adjacency matrix $A(\overrightarrow G)$ has the block form
of the matrix on the left-hand side of \eqref{eq:Pfdet2} and, hence,
the Pfaffian reduces to a determinant. More precisely, let
$G$ be a bipartite graph with vertex set $V=U\cup W$,
$U=\{u_1,u_2,\dots, u_n\}$ and $W=\{w_1,w_2,\dots, w_n\}$,
with edges connecting some $u_i$ to some $w_j$.
Given a Pfaffian orientation $\overrightarrow G$, 
we build the {\it signed bipartite adjacency matrix}
$B(\overrightarrow G)=(b_{i,j})_{1\le i,j\le n}$ of $\overrightarrow
G$ by setting $b_{i,j}=+w(e_{i,j})$ if there is an edge from $u_i$ to
$w_j$ oriented that way, $-w(e_{i,j})$ if there is an edge from $u_j$ to
$w_i$ oriented that way, and $0$ if there is no edge between $u_i$ and
$w_j$. Then we have
$$\det(B(\overrightarrow G))=\pm M_w(G).$$
In particular, this holds for any bipartite {\it planar} graph.
See \cite{RoSTAA} for a structural description which 
(not necessarily planar) bipartite graphs
admit a Pfaffian orientation.

Kasteleyn's construction in the planar case
has been generalized to graphs on surfaces of
any genus $g$ in \cite{DoMSAA,GaLoAA,TeslAF}, independently.
As predicted by Kasteleyn,
the solution is in terms of a linear combination of $4^g$ Pfaffians.

With the help of his method, Kasteleyn 
computed the number of dimer coverings of an $m\times n$ rectangle.
(A dimer is a $2\times 1$ rectangle. Thus, this is equivalent to
counting the number of perfect matchings on the $m\times n$ grid graph.
The formula was independently found by Temperley and Fisher.) 
The result is
$$
\prod _{i=1} ^{m}
\prod _{j=1} ^{n}\(2\cos\frac {\pi i} {m+1}+2\sqrt{-1}\cos\frac {\pi
j} {n+1}\).$$
For even $m$ and $n$, the formula can be rewritten as
$$
\prod _{i=1} ^{m/2}
\prod _{j=1} ^{n/2}\(4\cos^2\frac {\pi i} {m+1}+4\cos^2\frac {\pi j}
{n+1}\).$$
There is a similar rewriting if one of $m$ and $n$ is odd.
(If both $m$ and $n$ are odd, there is no dimer covering.)

For further reading and references see \cite{KupeAG}.

\section{Non-intersecting paths} \label{sec:nonint}

Let $G=(V,E)$ be a directed acyclic graph with vertices $V$ and directed
edges $E$. 
Furthermore, we are given a function $w$ which assigns a
weight $w(x)$ to every vertex or edge $x$. Let us define the weight
$w(P)$ of a walk $P$ in the graph by $\prod _{e} ^{}w(e)\prod _{v}
^{}w(v)$, where the first product is over all edges $e$ of the walk
$P$ and the second product is over all vertices $v$ of $P$. 
We denote the set of all walks in $G$ from $u$ to $v$ by $\P(u\to
v)$, and the set of all families $(P_1,P_2,\dots,P_n)$ of walks,
where $P_i$ runs from $u_i$ to $v_i$, $i=1,2,\dots,n$, by $\P(\mathbf
u\to\mathbf v)$, with $\mathbf u=(u_1,u_2,\dots,u_n)$ and 
$\mathbf v=(v_1,v_2,\dots,v_n)$. The symbol $\P^+(\mathbf
u\to\mathbf v)$ stands for the set of all families $(P_1,P_2,\dots,P_n)$ 
in $\P(\mathbf u\to\mathbf v)$ with the additional property that no two
walks share a vertex. We call such families of walk(er)s {\it ``vicious
walkers"} or, alternatively, {\it ``non-intersecting paths"}. 
The weight $w(\mathbf P)$ of a family $\mathbf
P=(P_1,P_2,\dots,P_n)$ of walks is defined as the product $\prod
_{i=1} ^{n}w(P_i)$ of all the weights of the walks in the family.
Finally, given a set $M$ with weight function $w$, we write 
$\GF(\mathcal M;w)$ for the generating function $\sum
_{x\in\mathcal M} ^{}w(x)$. 

We need two further notations before we are able to state the
{\it Lindstr\"om--Gessel--Viennot theorem}.
(For referennces and historical remarks,
we refer the reader to Footnote~5 in \cite{KratBW}.)
As earlier, the symbol $\mathfrak S_n$
denotes the symmetric group of order $n$. Given a permutation $\si\in
\mathfrak S_n$, we write $\mathbf u_\si$ for
$(u_{\si(1)},u_{\si(2)},\dots,u_{\si(n)})$. Then
\begin{equation} \label{eq:Lindallg} 
\sum _{\si\in \mathfrak S_n} ^{}(\sgn\si) \cdot\GF(\P^+(\mathbf u_\si\to \mathbf
v);w)
=\det_{1\le i,j\le n}\big(\GF(\P(u_{j}\to v_i);w)\big).
\end{equation}

Most often, this theorem is applied in the case where the only permutation
$\si$ for which vicious walks exist is the identity
permutation, so that the sum on the left-hand side reduces to a
single term which counts all families $(P_1,P_2,\dots,P_n)$ of 
vicious walks, the $i$-th walk $P_i$ running from $A_i$
to $E_i$, $i=1,2,\dots,n$. This case occurs for example if for any
pair of walks $(P,Q)$ with $P$ running from $u_a$ to $v_d$ and $Q$
running from $u_b$ to $v_c$, $a<b$ and $c<d$, it is true that $P$ and
$Q$ must have a common vertex. Explicitly, in that case we have
\begin{equation} \label{eq:Lind} 
\GF(\P^+(\mathbf u\to \mathbf v);w)=
\det_{1\le i,j\le n}\big(\GF(\P(u_{j}\to v_i);w)\big).
\end{equation}


If the starting points or/and the end points
are not fixed, then the corresponding number is given by a Pfaffian, a
result obtained by Okada and Stembridge
(see \cite{BresAO} for references).
For a set $\mathcal A$ of starting points, let 
$\P^+(\mathcal A\to \mathbf v)$ denote the set 
of all families $(P_1,P_2,\dots,P_{2n})$ of non-intersecting lattice
paths, where $P_i$ runs from some point of $\mathcal A$ to $v_i$,
$i=1,2,\dots,2n$. Furthermore, let us suppose that the elements of
$\mathcal A=\{u_1,u_2,\dots\}$ are ordered in such a way that for any 
pair of walks $(P,Q)$ with $P$ running from $u_a$ to $v_d$ and $Q$
running from $u_b$ to $v_c$, $a<b$ and $c<d$, it is true that $P$ and
$Q$ must have a common vertex. (This is the same condition as the
one which makes \eqref{eq:Lind} valid, with the only difference
that, here, the number of $u_i$'s could be larger than the number
of $v_i$'s.) Then,
\begin{multline} \label{eq:Okada} 
\GF(\P^+(\mathcal A\to \mathbf v);w)\\=
\underset{1\le i,j\le 2n}\Pf\bigg(
\sum _{a<b} ^{}\big(\GF(\P(u_{a}\to v_i);w)\GF(\P(u_{b}\to
v_j);w)\\-
\GF(\P(u_{b}\to v_i);w)\GF(\P(u_{a}\to v_j);w)\big)\bigg).
\end{multline}
If the number of paths is odd, then one can use the same formula
by adding an artificial point to the end points and to the set of
starting points $\mathcal A$. 
There is also a theorem by Okada and Stembridge 
which covers the
case that starting {\it and\/} end points vary.
Refinements when the number of turns is fixed can be found in \cite{KratBL}.


\section{Vicious walkers, plane partitions, rhombus tilings, 
and fully packed loop
configurations} \label{sec:PP}

In this section we describe the interrelations between four
frequently appearing objects in statistical mechanics and combinatorics:
vicious walkers, plane partitions, rhombus tilings, 
and fully packed loop configurations.

Given a lattice, {\it vicious walkers}, as introduced by Fisher \cite{FIS},
are particles which move on lattice sites
in such a way that two particles never occupy the
same lattice site. Models of vicious walkers have been the object of
numerous studies from various points of view.
Rather than accomplishing the impossible task of providing a
complete overview of references, the reader is referred to
the basic reference \cite{FIS} and to \cite{KratBW} for further
pointers to the literature.

Most of the known results apply for vicious walkers on the line.
There are in fact two different models: in the 
{\it random turns vicious walker model},
$n$ walkers move on the integral points of the real line in such a way
that at each tick of the clock {\it exactly one} walker moves to
the right or to the left, whereas in the
{\it lock step vicious walker model} 
$n$ walkers move on the integral points of the real line in such a way
that at each tick of the clock {\it each} walker moves to
the right or to the left.

The first model is equivalent to a model of one walker in $\mathbb
Z^n$ ($\mathbb Z$ denoting the set of integers) which at each tick of
the clock moves a positive or negative unit step in direction of one of
the coordinate axes, always staying in the wedge $x_1>x_2>\dots>x_n$.
This point of view was already put forward in \cite{FIS}. 
However, this problem belongs to the problem of counting paths
in chambers of reflection groups discussed in Section~\ref{sec:paths}.

The second model could also be realized as a single walker model
(cf.\ \cite{KratBT}). However, most often it is realized as a model
of $n$ paths in the plane consisting of steps $(1,1)$ and $(1,-1)$
with the property that no two paths have a point in common. 
In this picture, the $x$-axis becomes the time line, the $k$-th path
doing an up-step $(1,1)$ from $(t-1,y)$ to $(t,y+1)$ meaning that
the $k$-th particle moves to the left at time $t$, whereas 
the $k$-th path
doing a down-step $(1,-1)$ from $(t-1,y)$ to $(t,y-1)$ meaning that
the $k$-th particle moves to the right at time $t$.

\begin{figure}[t]
$$
        \Gitter(7,13)(0,-1)
        \Koordinatenachsen(7,13)(0,-1)
        \Pfad(0,0),343443\endPfad
        \Pfad(0,2),334434\endPfad
        \Pfad(0,4),333434\endPfad
        \Pfad(0,6),333334\endPfad
        \DickPunkt(0,0)
        \DickPunkt(0,2)
        \DickPunkt(0,4)
        \DickPunkt(0,6)
        \DickPunkt(6,0)
        \DickPunkt(6,2)
        \DickPunkt(6,6)
        \DickPunkt(6,10)
        \Label\r{\mathit 2}(1,1)
        \Label\r{\mathit 4}(3,1)
        \Label\r{\mathit 5}(4,0)
        \Label\r{\mathit 3}(2,4)
        \Label\r{\mathit 4}(3,3)
        \Label\r{\mathit 6}(5,3)
        \Label\r{\mathit 4}(3,7)
        \Label\r{\mathit 6}(5,7)
        \Label\r{\mathit 6}(5,11)
        \Label\l{A_1}(0,0)
        \Label\l{A_2}(0,2)
        \Label\l{A_3}(0,4)
        \Label\l{A_4}(0,6)
        \Label\r{E_1}(6,0)
        \Label\r{E_2}(6,2)
        \Label\r{E_3}(6,6)
        \Label\r{E_4}(6,10)
\begin{picture}(15,5)(0,0)
\put(12,4){
        \begintableau{3}{4}
        \row{2346}
        \row{446}
        \row{56}
        \endtableau
}
\put(13,2){\small b. A tableau}
\put(3,-3){\small a. Vicious walkers}
\end{picture}
$$
\vskip.3cm
\caption{}
\label{F1}
\end{figure}

The reader should consult Figure~\ref{F1}.a for an example.
(The labellings should be ignored at this point.)
Clearly, what we encounter here is a particular instance of the
non-intersecting paths of Section~\ref{sec:nonint}.
Therefore, for fixed starting and end points, Formula~\eqref{eq:Lind}
applies, whereas if the starting points vary and the end
points are fixed, it is Formula~\eqref{eq:Okada} which applies.

At this point, the links to the other objects, semistandard
tableaux and plane partitions (cf.\ \cite{BresAO}), emerge. 
A filling
of the cells of the Ferrers diagram of $\lambda$ with elements of
the set $\{1,2,\dots\}$
which is {\em weakly increasing\/} along rows and {\em strictly increasing\/}
along columns
is called a ({\em semistandard}) {\em tableau of shape $\lambda$\/}.
Figure~\ref{F1}.b shows such a semistandard tableau of shape
$(4,3,2)$. 
In fact, vicious walkers and semistandard tableaux are equivalent
objects. To see this,
first label down-steps by the $x$-coordinate of their
end point, so that a step from $(a-1,b)$ to $(a,b-1)$ is labelled by
$a$, see Figure~\ref{F1}.a. Then, out of the labels of the $j$-th
path, form the $j$-th column of the corresponding tableau,
see Figure~\ref{F1}.b. The
resulting array of numbers is indeed a semistandard tableau. This can
be readily seen, since the entries are
trivially strictly increasing along columns, and they are weakly
increasing along rows because the paths do not touch each other.
Thus, problems of enumerating vicious walkers can be translated
into tableau enumeration problems, and vice versa. 

The significance of semistandard
tableaux lies particularly in the representation
theory for classical groups. Namely, the irreducible characters for
$GL(n,\mathbb C)$ and $SL(n,\mathbb C)$, the {\it Schur functions},
are generating functions for semistandard tableaux of a given shape.
If the entries of the $i$-th row of a semistandard tableau are required
to be at least $2i-1$, then one speaks of {\it symplectic tableaux},
and the irreducible characters for $Sp(2n,\mathbb C)$ are generating functions 
for symplectic tableaux of a given shape.
We refer the reader to \cite{KrGVAA} for more information
on these topics.

Objects which are very close to semistandard tableaux are
{\it plane partitions}. According to MacMahon,
a plane partition of shape $\la$ is a filling of the Ferrers diagram
of $\la$ with non-negative integers
which is {\em weakly decreasing\/} along rows and columns.
See Figure~\ref{fig:PP}.b for an example of a plane partition
of shape $(3,3,3)$.
In particular, semistandard tableaux and plane partitions of
rectangular shape are actually equivalent. For, let $T$ be a
semistandard tableau of rectangular shape. Then, from each element of 
the $i$-th row we subtract $i$. Finally, the obtained array is rotated
by $180^\circ$. As a result, we obtain a plane partition.
See Figure~\ref{fig:PP} for a semistandard tableau and a plane
partition which correspond to each other under these transformations.

\begin{figure}[h]
$$
\begin{matrix} 1&1&2\\3&3&3\\4&5&5\end{matrix}
\hskip3cm
\begin{matrix} 2&2&1\\1&1&1\\1&0&0\end{matrix}
$$
\centerline{\small 
a. A semistandard tableau\quad \quad b. A plane partition}
\caption{}
\label{fig:PP}
\end{figure}

On the other hand, plane partitions can also be realized as 3-dimensional
objects, by interpreting each entry in the array as a pile uf unit
cubes of the size of the entry. For example, the plane partition in
Figure~\ref{fig:PP} corresponds to the pile of cubes in
Figure~\ref{fig:PP2}.a. But then, forgetting the 3-dimensional view,
by embedding the picture in a minimally bounding hexagon, and by
filling the emerging empty regions by rhombi of unit length in the
unique way this is possible, we obtain a {\it rhombus tiling}
of a hexagon in which opposite sides have the same length,
see Figure~\ref{fig:PP2}.b.

\begin{figure} 
\centertexdraw{
\drawdim truecm \linewd.1
\RhombusA \RhombusA \RhombusB \RhombusA \RhombusB 
\move(-.866025 -1.5)
\RhombusA \RhombusA \RhombusA \RhombusB
\move(-1.7305 -2)
\RhombusA \RhombusB %\RhombusA \RhombusA 
\move(0 0)
\RhombusC 
\move(0 -2)
\RhombusC \RhombusC
\move(-1.7305 -2)
\RhombusC
%\move(2.596 -.5)
%\RhombusC

\move(7 0)
\bsegment
\RhombusA \RhombusA \RhombusB \RhombusA \RhombusB 
\move(-.866025 -.5)
\RhombusB \RhombusA \RhombusA \RhombusA \RhombusB
\move(-1.7305 -1)
\RhombusB \RhombusA \RhombusB \RhombusA \RhombusA 
\move(0 0)
\RhombusC 
\move(0 -2)
\RhombusC
\move(-1.7305 -2)
\RhombusC
\move(2.596 -.5)
\RhombusC
\esegment
}
\centerline{\small
a. A plane partition, 3-dimensional\quad\quad  b. A rhombus tiling}
\caption{}
\label{fig:PP2}
\end{figure}

From the rhombus tiling, there is then again an elegant way to
go to nointersecting paths: 
we mark the mid-points of the edges along two opposite
sides, see Figure~\ref{fig:rhombus}.a. Now we draw lattice paths 
which connect points on different sides, 
by ``following" along the other lozenges, as is indicated in
Figure~\ref{fig:rhombus}.a by the dashed lines. 
Clearly, the resulting
paths are nonintersecting, i.e., no two paths have a common vertex. 
If we slightly distort
the underlying lattice, we get orthogonal paths with
horizontal and vertical steps in the positive direction, see
Figure~\ref{fig:rhombus}.b.

\begin{figure} 
\btexdraw
\drawdim truecm \linewd.1
\RhombusA \RhombusA \RhombusB \RhombusA \RhombusB 
\move(-.866025 -.5)
\RhombusB \RhombusA \RhombusA \RhombusA \RhombusB
\move(-1.7305 -1)
\RhombusB \RhombusA \RhombusB \RhombusA \RhombusA 
\move(0 0)
\RhombusC 
\move(0 -2)
\RhombusC
\move(-1.7305 -2)
\RhombusC
\move(2.596 -.5)
\RhombusC

\linewd.05
\move(1.29904 .25)
\odSchritt \vdSchritt \odSchritt \odSchritt \vdSchritt
\move(2.165 -.25)
\odSchritt \vdSchritt \odSchritt \vdSchritt \odSchritt 
\move(3.031 -.75)
\vdSchritt \odSchritt \odSchritt \vdSchritt \odSchritt
\ringerl(1.29904 .25)
\ringerl(2.165 -.25)
\ringerl(3.031 -.75)
\ringerl(-1.29904 -3.25)
\ringerl(-.433012 -3.75)
\ringerl(.433012 -4.25)
\etexdraw
\vskip-6cm
$$
\hbox{\hskip6cm}
\Einheit=.7cm
\Gitter(7,6)(0,0)
\Koordinatenachsen(7,6)(0,0)
\Pfad(0,2),21121\endPfad
\Pfad(1,1),12121\endPfad
\Pfad(2,0),12112\endPfad
\DickPunkt(0,2) \DickPunkt(3,4)
\DickPunkt(1,1) \DickPunkt(4,3)
\DickPunkt(2,0) \DickPunkt(5,2)
\hskip4cm
$$
\vskip1cm
\centerline{\small
a. A rhombus tiling\quad \quad \quad\quad  
b. A family of non-intersecting paths}
\caption{}
\label{fig:rhombus}
\end{figure}

Rhombus tilings, on their part, are equivalent to perfect matchings
of hexagonal graphs. To see this, one places the tiling on the
underlying triangular grid, see Figure~\ref{fig:hex}.a.
Then one places a bond into each rhombus, so that it connects the
mid-points of the two triangles out of which the rhombus is composed,
see Figure~\ref{fig:hex}.b. Finally, one forgets the contour
of the tiling, but instead one introduces all the other edges
which connect mid-points of adjacent triangles of the triangular
grid, see Figure~\ref{fig:hex}.c. Thus, one arrives at a perfect
matching of the hexagonal graph consisting of the edges connecting
mid-points of triangles.

\begin{figure} 
\centertexdraw{
\drawdim truecm \linewd.1
\RhombusA \RhombusA \RhombusB \RhombusA \RhombusB 
\move(-.866025 -.5)
\RhombusB \RhombusA \RhombusA \RhombusA \RhombusB
\move(-1.7305 -1)
\RhombusB \RhombusA \RhombusB \RhombusA \RhombusA 
\move(0 0)
\RhombusC 
\move(0 -2)
\RhombusC
\move(-1.7305 -2)
\RhombusC
\move(2.596 -.5)
\RhombusC
\linewd.02
\move(0 0)
\rhombus \rhombus \rhombus 
\move(-.866025 -.5)
\rhombus \rhombus \rhombus \rhombus \ldreieck
\move(-1.7305 -1)
\rhombus \rhombus \rhombus \rhombus \rhombus 
\move(-1.7305 -1)
\rdreieck \rhombus \rhombus \rhombus \ldreieck 
\move(-1.7305 -2)
\rdreieck \rhombus \rhombus \rhombus 

\linewd.1
\move(7 0)
\bsegment
\RhombusA \RhombusA \RhombusB \RhombusA \RhombusB 
\move(-.866025 -.5)
\RhombusB \RhombusA \RhombusA \RhombusA \RhombusB
\move(-1.7305 -1)
\RhombusB \RhombusA \RhombusB \RhombusA \RhombusA 
\move(0 0)
\RhombusC 
\move(0 -2)
\RhombusC
\move(-1.7305 -2)
\RhombusC
\move(2.596 -.5)
\RhombusC
\linewd.02
\move(0 0)
\rhombus \rhombus \rhombus 
\move(-.866025 -.5)
\rhombus \rhombus \rhombus \rhombus \ldreieck
\move(-1.7305 -1)
\rhombus \rhombus \rhombus \rhombus \rhombus 
\move(-1.7305 -1)
\rdreieck \rhombus \rhombus \rhombus \ldreieck 
\move(-1.7305 -2)
\rdreieck \rhombus \rhombus \rhombus 

\linewd.05
\move(0.5773502694 0)
\bondA
\move(1.443375673 -0.5)
\bondA
\move(-0.2886751347 -1.5)
\bondA
\move(0.5773502694 -2)
\bondA
\move(1.443375673 -2.5)
\bondA
\move(2.309401077 -2)
\bondA
\move(-0.2886751347 -3.5)
\bondA
\move(-1.154700539 -2)
\bondA
\move(0.5773502694 -4)
\bondA

\move(-0.5773502694 -1)
\bondB
\move(2.020725943 -1.5)
\bondB
\move(2.886751347 -3)
\bondB
\move(-1.443375673 -1.5)
\bondB
\move(-0.5773502694 -3)
\bondB
\move(2.020725943 -3.5)
\bondB

\move(0.5773502694 -1)
\bondC
\move(1.443375673 -1.5)
\bondC
\move(3.175426481 -1.5)
\bondC
\move(0.5773502694 -3)
\bondC
\move(1.443375673 -3.5)
\bondC
\move(-1.154700539 -3)
\bondC
\esegment

\linewd.1
\move(3.5 -4.5)
\bsegment

\linewd.1
\move(0.5773502694 0)
\bondA
\move(1.443375673 -0.5)
\bondA
\move(-0.2886751347 -1.5)
\bondA
\move(0.5773502694 -2)
\bondA
\move(1.443375673 -2.5)
\bondA
\move(2.309401077 -2)
\bondA
\move(-0.2886751347 -3.5)
\bondA
\move(-1.154700539 -2)
\bondA
\move(0.5773502694 -4)
\bondA

\move(-0.5773502694 -1)
\bondB
\move(2.020725943 -1.5)
\bondB
\move(2.886751347 -3)
\bondB
\move(-1.443375673 -1.5)
\bondB
\move(-0.5773502694 -3)
\bondB
\move(2.020725943 -3.5)
\bondB

\move(0.5773502694 -1)
\bondC
\move(1.443375673 -1.5)
\bondC
\move(3.175426481 -1.5)
\bondC
\move(0.5773502694 -3)
\bondC
\move(1.443375673 -3.5)
\bondC
\move(-1.154700539 -3)
\bondC

\linewd.02
\move(0.5773502693 0)
\hex \hex \hex
\move(-0.2886751347 -0.5)
\hex \hex \hex \hex
\move(-1.154700539 -1)
\hex \hex \hex \hex
\move(-1.154700539 -2)
\hex \hex \hex
\esegment
}
\vskip-4cm
\centerline{\small
a. A rhombus tiling\hskip5cm  b. Bonds in rhombi}
\vskip4cm
\centerline{\small
c. A perfect matching of a hexagonal graph}
\caption{}
\label{fig:hex}
\end{figure}

Because of these various connections, enumeration problems for
vicious walkers, plane partitions, tableaux, rhombus tilings can be
approached by the different methods which are available for
the various objects: the determinant theorem from
Section~\ref{sec:nonint}, together with determinant evaluation
techniques (cf.\ the survey \cite{KratBZ}), apply,
as well as the ``Kasteleyn method" from Section~\ref{sec:Kast},
and also methods from character theory for the classical groups.
And all of them have been applied extensively
(see the surveys \cite{KenyAF,PropAH} and \cite{KrGVAA}), the first
and third more
frequently for exact enumeration, while the second particularly
for asymptotic studies. It should be noted that methods from random
matrix theory also apply in certain situations, see
\cite{JohaAB}. 

We missed in fact to mention a further object, from
statistical physics, which in some cases is equivalent to vicious
walkers, etc.: {\it fully packed loop configurations}. 
(Fully packed loop configurations are in bijection with six vertex
configurations, see Section~\ref{sec:ASM}.)
If one imposes certain ``connectivity constraints" on fully packed
loop configurations, then one can construct bijections with rhombus
tilings and, hence, with nonintersecting paths and with the other
objects discussed in this section. The reader is referred to
\cite{FrZZAA} and the references therein.

After having explained the various connections,
we cite some fundamental results in the area.
(We refer the reader to \cite{BresAO} and \cite[Ch.~7]{StanBI}.) 
MacMahon proved that
the number of all plane partitions contained in an $a\times b\times c$
box (when viewed in 3 dimensions) is equal to
\begin{equation} \label{eq:MacMahon} 
\prod_{i=1}^a\prod_{j=1}^b\prod_{k=1}^c\frac{i+j+k-1}{i+j+k-2}.
\end{equation}
Thus, the number of rhombus tilings of a hexagon with side lengths
$a,b,c,a,\break b,c$ is given by the same number, as well as
the number of all vicious walkers $(P_1,P_2,\dots,P_a)$, where
$P_i$ runs from $(0,2i)$ to $(b+c,b-c+2i)$, $i=1,2,\dots,a$.
More generally, the number of semistandard tableaux of shape $\la$
with entries at most $m$ is given by the {\it hook-content formula}
\begin{equation} \label{eq:hook-content} 
\prod _{u\in \la} ^{}\frac {c(u)+m} {h(u)},
\end{equation}
where $u$ ranges over all the cells of the Ferrers diagram of $\la$,
with $c(u)$ being the {\it content} of $u$, defined as the difference
of the column number and the row number of $u$, and with $h(u)$ being the
{\it hook length\/} of $u$, defined as the number of cells in the {\it
hook} of $u$, the latter consisting of 
the cells to the right of $u$ in the same row
and below $u$ in the same column, including $u$.
Thus, this gives also a formula for
the number of all vicious walkers $(P_1,P_2,\dots,P_a)$, where
$P_i$ runs from $(0,2i)$ to $(N,h_i)$. See
\cite[Sec.~2]{KrGVAA} for details.
There it is also explained that a Schur function summation formula,
together with an analogue of the hook-content formula for {\it special
orthogonal characters}, proves that the number of all
the number of all vicious walkers $(P_1,P_2,\dots,P_a)$, where
$P_i$ runs from $(0,2i)$ for $N$ steps is given by
\begin{equation} \label{e10}
\prod _{1\le i\le j\le N} ^{}\frac {a+i+j-1} {i+j-1}.
\end{equation}

The reader is referred to the references given in this section for
many more results, in particular, on the enumeration of plane
partitions with symmetry, the enumeration of rhombus tilings of
regions other than hexagons, and the enumeration of vicious walkers
with various starting and end points, under various constraints.

\section{Six vertex model and alternating sign matrices} \label{sec:ASM}

An alternating sign matrix is a square matrix of $0$'s, $1$'s and $-1$'s
for which  
the sum of entries in each row and in each column is $1$ and the
non-zero entries of each row and  
of each column alternate in sign. For instance, 
$$
\left(
\begin{array}{rrrrr}
0 & 0 & \hphantom{-}1 & \hphantom{-}0 & 0 \\
1 & 0 & -1 & \hphantom{-}1& 0 \\
0 & 1 & \hphantom{-}0 & -1 & 1 \\
0 & 0 & \hphantom{-}1 & \hphantom{-}0 & 0 \\
0 & 0 &  \hphantom{-}0 & \hphantom{-}1 & 0
\end{array}
\right)
$$
is a $5\times 5$ 
alternating sign matrix. Zeilberger proved that the
number of $n \times n$ alternating sign matrices is given by
\begin{equation}
\label{asmformula}
\prod_{i=0}^{n-1} \frac{(3i+1)!}{(n+i)!},
\end{equation}
and he went on to prove the finer version that the
number of $n \times n$ alternating sign matrices with the 
(unique) $1$ in the
first row in position $j$ is given by
\begin{equation}
\label{refined}
\frac{\binom {n+j-2}{n-1}\binom {2n-j-1}{n-1}} {\binom {3n-2}{n-1}} \prod\limits_{i=0}^{n-1} \frac{(3i+1)!}{(n+i)!}.
\end{equation}
The first number is also equal to the number of totally symmetric
self-complementary plane partitions contained in the
$(2n)\times(2n)\times(2n)$ box,
but there is no intrinsic explanation why this is so.
We refer the reader to \cite{BresAO} for an exposition of
these results, and for pointers to the literature
containing further unexplained connections between alternating
sign matrices and plane partitions.

While the first result was achieved by a brute force constant term
approach, the second result is based on the observation, 
that alternating sign matrices are in bijection with
configurations in the six vertex model on the square grid 
under domain wall boundary conditions. This then allowed one
to use a formula due to Izergin for the partition
function for these six vertex configurations. Similar formulas
for variations of the model have been found by Kuperberg,
and by Razumov and Stroganov (see \cite{RaStAG} and the 
references therein).

\begin{figure}
\begin{center}{\resizebox*{10cm}{!}{\includegraphics{6Knoten.eps}}}
\end{center}
$$
\hbox to0pt{\hss $0$\hss}\kern50pt
\hbox to0pt{\hss $0$\hss}\kern50pt
\hbox to0pt{\hss $0$\hss}\kern50pt
\hbox to0pt{\hss $0$\hss}\kern50pt
\hbox to0pt{\hss $-1$\hss}\kern50pt
\hbox to0pt{\hss $1$\hss}
$$
\caption{}
\label{fig:6v}
\end{figure}

A configuration in the six vertex model is an orientation of edges of
a 4-regular graph (that is, at each vertex there meet exactly $4$
edges) such that at each vertex two edges are oriented towards the
vertex and two edges are oriented away from the vertex. 
Thus, there are six possible vertex configurations, giving the name of
the model, see Figure~\ref{fig:6v}.
To go from one object to
the other one uses the translation between local configurations at a
vertex and entries in alternating sign matrices indicated in
the figure. An example of the correspondence can be found
in Figure~\ref{fig:ASM-6v}.

\begin{figure}
\begin{picture}(40,6)(0,0)
\put(5,3){$
\begin{pmatrix}
0 & \hphantom{-}1 & 0 \\
1 & -1 & 1 \\
0 & \hphantom{-}1 & 0
\end{pmatrix}$}
%\put(10,1){$\leftrightarrow$}
\put(16,0){\resizebox*{3cm}{!}{\includegraphics{Konfig.eps}}}
\end{picture}
\centerline{\small a. An alternating sign matrix\quad \quad \quad 
b. A six vertex configuration}
\caption{}
\label{fig:ASM-6v}
\end{figure}

Another manifestation of alternating sign matrices and six vertex
configurations are {\it fully packed loop configurations}.
A fully packed loop configuration on a graph is a collection of edges
such that each vertex is incident to exactly two edges.
One obtains a fully packed loop configuration out of a
six vertex configuration by dividing the square lattice into its even and odd
sublattice denoted by $A$ and $B$ respectively. Instead of arrows, only those
edges are drawn that on sublattice $A$ point inward and on sublattice $B$
point outward. I refer to \cite{degier,FrZZAA} for further reading.

The story of alternating sign matrices and its connection to the
six vertex model is given a vivid account in \cite{BresAO},
with further important results by Kuperberg, Okada,
Razumov and Stroganov, referenced in \cite{RaStAG}.

Fully packed loop configurations seem to play an important role
in the explicit form of the groundstate vectors of certain 
Hamiltonians in the dense
$O(1)$ loop model. The corresponding conjectures are
surveyed in \cite{degier}. There is important progress on these
conjectures by Di Francesco and Zinn--Justin
(cf.\ \cite{FrZiAG} and the references cited therein).

%\section{Theory of partitions} \label{sec:partitions}

%\section{Maps} \label{sec:maps}

%\section{Animals} \label{sec:animal}

\section{Binomial sums and hypergeometric series} \label{sec:binomial}

When dealing with enumerative problems, it is inevitable to deal with
{\it binomial sums}, that is, sums in which the summands are
products/quotients of binomial coefficients and factorials, 
such as, for example,
$$\sum _{k=0} ^{n}\binom {2k}k\binom {2n-2k}{n-k}.$$
In most cases,
the right environment in which one should work is the theory of
(generalized) {\it hypergeometric series}. These are defined as
follows: 
\def\po#1#2{(#1)_#2}
\begin{equation*}  % \label{eq:hyper}
{}_r F_s\!\left[\begin{matrix} a_1,\dots,a_r\\ b_1,\dots,b_s\end{matrix}; 
z\right]=\sum _{k=0} ^{\infty}\frac {\po{a_1}{k}\cdots\po{a_r}{k}}
{\po{b_1}{k}\cdots\po{b_s}{k}} \frac {z^k}{k!}\ ,
\end{equation*}
where
$(\alpha)_k  =  \alpha(\alpha+1)(\alpha+2)\cdots (\alpha+k-1)$ for
$k>0$, and $(\alpha)_0  = 1$. The symbol
$(\alpha)_k$ is called the 
{\it Pochhammer symbol\/} or {\it shifted factorial}.
For in-depth treatments of the subject,
we refer the reader to \cite{AAR,GaRaAA,SlatAC}.

Hypergeometric series can be characterized as series in which the
quotient of the $(k+1)$-st by the $k$-th summand is a rational
function in $k$. This is also the way to convert binomial sums into
their hypergeometric form (respectively to see if this is possible; in
most cases it is): form the quotient  
of the $(k+1)$-st by the $k$-th summand and read off the parameters
$a_1,\dots,a_r$, $b_1,\dots,b_s$, and the argument $z$ from the
factorization of the numerator and the denominator polynomials of the
rational function, out of these form the corresponding hypergeometric
series, and multiply the series by the summand for $k=0$. 
This is, in fact, a completely routine task, and,
indeed, computer algebra programs such as {\sl
Maple} and {\sl Mathematica} do this automatically.

The reason why hypergeometric series are much more fundamental than
the binomial sums themselves is that there are hundreds of ways to
write the same sum using binomial coefficients and factorials,
whereas there is {\it just one} hypergeometric form, that is, 
hypergeometric series are a kind of {\it normal form} for binomial
sums. In particular, given a specific binomial sum,
it is a hopeless enterprise to scan through all the identities
available in the literature 
for this sum. There may be an identity for it, but perhaps
written in a different way. On the contrary, given a specific
hypergeometric series, the list of available identities which apply to
this series is usually not large, and tables of such identities can be
set up in a systematic way. This has been done (cf.\ \cite{SlatAC};
the most comprehensive table available to this date 
is contained in the manual of the {\sl Mathematica}
package HYP\footnote{\label{foot:HYP}available at
{\tt http://www.mat.univie.ac.at/\~{}kratt}}),
and scanning through these tables is largely facilitated by the use
of the {\sl Mathematica} package HYP$^{\text{\ref{foot:HYP}}}$.

We give here some of the most important identities for hypergeometric
series. Aside from the binomial theorem, the most important {\it
summation formulas} are {\it Gau{\ss}' $_2F_1$-summation formula}
$${}_2 F_1\!\left[\begin{matrix} a,b\\ c\end{matrix}; 
1\right]=\frac {\Ga(c)\,\Ga(c-a-b)} {\Ga(c-a)\,\Ga(c-b)},
$$
provided $\Re(c-a-b)>0$,
the {\it Pfaff--Saalsch\"utz summation formula}
$$
{} _{3} F _{2} \!\left [ \begin{matrix} { a, b, -n}\\ { c, 1 + a + b - c -
   n}\end{matrix} ; {\displaystyle 1}\right ]  =
  {\frac{({ \textstyle c-a}) _{n}  \,({ \textstyle c-b}) _{n} }
    {({ \textstyle c}) _{n} \, ({ \textstyle c-a-b}) _{n} }},
$$
provided $n$ is a non-negative integer, and {\it Dougall's summation
formula}
\begin{multline*} 
{} _{7} F _{6} \!\left [ \begin{matrix} {\displaystyle 
a, a/2+1, b, c, d, 1 + 2 a - b - c - d + n, -n}\\
{a/2,1+a-b,1+a-c,1+a-d,-a+b+c+d-n,a+1+n}\end{matrix};
   {\displaystyle 1} \right]\\
=  {\frac{({ \textstyle 1 + a}) _{n}  \,
      ({ \textstyle 1 + a - b - c}) _{n} \, ({ \textstyle 1 + a - b - d}) _{n}  
\,      ({ \textstyle 1 + a - c - d}) _{n} } 
    {({ \textstyle 1 + a - b}) _{n}  \,({ \textstyle 1 + a - c}) _{n} 
\,  ({ \textstyle 1 + a - d}) _{n}  \,({ \textstyle 1 + a - b - c - d}) _{n} }
    },
\end{multline*}
provided $n$ is a non-negative integer.

Some of the most important {\it transformation formulas} are
{\it Euler's transformation formula}
$$
{} _{2} F _{1} \!\left [ \begin{matrix} { a, b}\\ { c}\end{matrix} ; {\displaystyle
   z}\right ]  = {{\left( 1 - z \right) }^{c-a-b}} 
   {} _{2} F _{1} \!\left [ \begin{matrix} { c-a, c-b}\\ { c}\end{matrix} ;
    {\displaystyle z}\right ] ,
$$
provided $\vert z\vert<1$, {\it Kummer's transformation formula}
$$
{} _{3} F _{2} \!\left [ \begin{matrix} { a, b, c}\\ { d, e}\end{matrix} ;
   {\displaystyle 1}\right ]  =
   \frac{\Ga( e)\,\Ga(  d + e-a - b - c)} {\Ga(  e-a)\,\Ga ( d +
    e-b - c)}
  {} _{3} F _{2} \!\left [ \begin{matrix} { a,  d-b,  d-c}\\ { d,  d +
    e-b - c}\end{matrix} ; {\displaystyle 1}\right ]  ,
$$
provided both series converge, and
{\it Whipple's transformation formula}
\begin{multline} \label{eq:Whipple1}
{} _{4} F _{3} \!\left [ \begin{matrix} { a, b, c, -n}\\ { e, f, 1 + a + b + c - e -
   f - n}\end{matrix} ; {\displaystyle 1}\right ] =
{\frac{({ \textstyle  e-a)_n\,(  f-a}) _{n}} {({ \textstyle e)_n\,( f})
_{n}}}\\
\times
  {} _{4} F _{3} \!\left [ \begin{matrix} { -n, a, 1 + a + c - e - f - n, 1 + a + b -
    e - f - n}\\ { 1 + a + b + c - e - f - n, 1 + a - e - n, 1 + a - f -
    n}\end{matrix} ; {\displaystyle 1}\right ]   
\end{multline}
where $n$ is a non-negative integer, and 
\begin{multline} \label{eq:Whipple2}
{} _{7} F _{6} \!\left [ \begin{matrix} { a, 1 + \frac{a}{2}, b, c, d, e, -n}\\ {
    \frac{a}{2}, 1 + a - b, 1 + a - c, 1 + a - d, 1 + a - e, 1 + a +
    n}\end{matrix} ; {\displaystyle 1}\right ]  \\=
    \frac {({ \textstyle 1 + a)_n\,( 1 + a - d - e}) _{n}} {({ \textstyle 1 + a -
     d)_n\,( 1 + a - e}) _{n}}
   {} _{4} F _{3} \!\left [ \begin{matrix} { 1 + a - b - c, d, e, -n}\\ { 1 + a -
     b, 1 + a - c, -a + d + e - n}\end{matrix} ; {\displaystyle 1}\right ] ,
\end{multline}
provided $n$ is a non-negative integer.

Since about 1990, for the {\it verification} of binomial and
hypergeometric series, there are {\it automatic tools} available.
The book \cite{PeWZAA} is an excellent introduction into these aspects.
The philosophy is as follows. Suppose we are given a binomial or
hypergeometric series $S(n)=
\sum _{k} ^{}F(n,k)$. The 
{\it Gosper--Zeilberger algorithm}\footnote{Computer implementations 
written by Doron
Zeilberger are available from {\tt
http://www.math.rutgers.edu/\~{}zeilberg}, {\sl Mathematica} implementations 
written by Peter Paule and Markus Schorn are available 
from {\tt
http://www.risc.uni-linz.ac.at/research/combinat/risc/software}.}
(cf.\ \cite{PeWZAA}; a simplified version was presented in
\cite{ZeilAZ}) will find a linear recurrence 
\begin{equation} \label{eq:Rek}
A_0(n)S(n)+A_1(n)S(n+1)+\dots+A_d(n)S(n+d)=C(n)
\end{equation}
for some $d$,
where the coefficients $A_i(n)$ are polynomials in $n$, and where
$C(n)$ is a certain function in $n$, {\it with proof\/}!

If, for example, we suspected that $S(n)=RHS(n)$, where $RHS(n)$ is
some closed form expression, then we just have to verify that $RHS(n)$
satisfies the recurrence \eqref{eq:Rek} and check $S(n)=RHS(n)$ for
sufficiently many initial values of $n$ to have a proof for the
identity $S(n)=RHS(n)$ {\it for all\/} $n$. 
On the other hand, if $RHS(n)$ was a different
sum, then we would apply the algorithm to find a recurrence for
$RHS(n)$. If it turns out to be the same recurrence then, again, a
check of $S(n)=RHS(n)$ for a few initial values will provide a full proof
of $S(n)=RHS(n)$ {\it for all\/} $n$.

Even in the case that we do not have a conjectured expression
$RHS(n)$, this is not the end of the story. Given a recurrence of the
type \eqref{eq:Rek}, the {\it Petkov\vv sek algorithm}\footnote{A {\sl
Mathematica} implementation by Marko Petkov\vv sek is available at 
{\tt http://www.fmf.uni-lj.si/\~{}petkovsek}.} (cf.\ \cite{PeWZAA}) is
able to find a closed form solution (where ``closed form" has a
precise meaning, see \cite{PeWZAA}), respectively tell that there is
no closed form solution.

The fascinating point about both algorithms is that neither do we have to
know what the algorithm does internally nor do we have to check that.
For the Petkov\vv sek algorithm this is obvious anyway because, once the
computer says that a certain expression is a 
solution of \eqref{eq:Rek}, it is a routine matter to check that.
This is less obvious for the Gosper--Zeilberger algorithm.
However, what the Gosper--Zeilberger algorithm does is, for a given
sum $S(n)=
\sum _{k} ^{}F(n,k)$, to find polynomials $A_0(n),A_1(n),\dots,A_d(n)$
{\it and\/} an expression $G(n,k)$ (which is in fact a rational
multiple of $F(n,k)$), such that
\begin{equation} \label{eq:Rek1}
A_0(n)F(n,k)+A_1(n)F(n+1,k)+\dots+A_d(n)F(n+d,k)=G(n,k+1)-G(n,k),
\end{equation}
for some $d$. Because of the properties of $F(n,k)$ and $G(n,k)$, which
are part of the theory, this is an identity which can be {\it directly}
verified by clearing all common factors and checking the remaining
identity between rational functions in $n$ and $k$. However, we may
now sum both sides of \eqref{eq:Rek1} over $k$ to obtain a recurrence
of the form \eqref{eq:Rek}.

Algorithms for multiple sums are also available\footnote{{\sl
Mathematica} implementations by Axel Riese and Kurt 
Wegschaider are available at
{\tt
http://www.risc.uni-linz.ac.at/research/combinat/risc/software}.}.
They follow ideas by Wilf and Zeilberger \cite{WiZeAC} (of which a
simplified version is presented in \cite{MoZeAA}),
however they run more quickly in capacity problems.
Schneider \cite{SchnAA} is currently developing a very promising new
algorithmic approach to the automatic treatment of multisums.


%\section{Graph Polynomials} \label{sec:graphpoly}


\footnotesize

\begin{thebibliography}{10}

\bibitem{AndrAF}
G. E. Andrews, {\em The theory of
partitions}, Encyclopedia of Math.\ and its Applications, Vol.~2,
Addison--Wesley, Reading, 1976; reprinted by Cambridge University
Press, Cambridge, 1998.   

\bibitem{AAR} G.~E.~Andrews, R.~A.~Askey et R.~Roy, {\em Special
Functions},
The Encyclopedia of Mathematics and Its Applications, vol.~71,
G.-C.~Rota, ed., Cambridge University Press, Cambridge, 1999.

\bibitem{AyouAA}
R. Ayoub, {\em An introduction to the analytic theory of numbers},
Mathematical Surveys, No.~10,
Amer.\ Math.\ Soc., Providence, R.I., 1963.

%\bibitem{BaFlAA}
%C.    Banderier and P. Flajolet,
%{\em Basic analytic combinatorics of directed lattice paths},
%Theoret.\ Computer Science {\bf 281} (2002), 37--80.

\bibitem{BeLLAA}
F. Bergeron, G. Labelle and P. Leroux, {\em Combinatorial species and
tree-like structures}, Cambridge University Press, Cambridge, 1998.

%\bibitem{BianAD} P.    Biane,
%{\it Minuscule weights and random
%walks on lattices}, in: Quantum probability \& related topics,
%L.~Accardi, ed., World Sci.\ Publ., River Edge, NJ, 1992, pp.~51--65.

%\bibitem{BoViAA}
%M. Bousquet-M\'elou and X. Viennot, {\em Empilements de segments et
%$q$-\'enum\'eration de polyominos
%convexes dirig\'es},
%J. Combin.\ Theory Ser.~A 60 (1992), 196--224.

%\bibitem{BMR}
%M. Bousquet-M\'elou and A. Rechnitzer, {\em Lattice animals
%and heaps 
%of dimers}, Discrete Math.\ {\bf 258} (2002), 235--274.

\bibitem{BoJeAA}
M.    Bousquet-M\'elou and A. Jehanne,
{\em Polynomial equations with one catalytic variable, algebraic
series, and map enumeration}, preprint; {\tt ar$\chi$iv:math.CO/0504018}.

\bibitem{BresAO}
D. M. Bressoud, {\em Proofs and confirmations --- The story of the 
alternating sign matrix conjecture}, Cambridge University Press,
Cambridge, 1999.

\bibitem{BruiAA}
N. G. de Bruijn, {\em P\'olya's theory of counting}, in: Applied
Combinatorial Mathematics, E.~.F.~Beckenbach, ed., Wiley, New York,
1964; reprinted by Krieger, Malabar, Florida, 1981.

%\bibitem{CaFoAA}
%P. Cartier and D. Foata,
%{\em Probl\`emes combinatoires de commutation et r\'earrangements}, 
%Lecture Notes in Mathematics, No.~85,
%Springer--Verlag, Berlin, New York, 1969.

\bibitem{ComtAA}
L.~Comtet, {\em Advanced {C}ombinatorics}, D.~Reidel, Dordrecht,
Holland, 1974. 

\bibitem{DoMSAA}
N. P. Dolbilin, A. S. Mishchenko, M. A. Shtan'ko, M. I. 
Shtogrin and Yu.~M.~Zinoviev,
{\em Homological properties of dimer configurations for lattices on surfaces}
Funct. Anal. Appl. {\bf 30} (1996), 163--173.

%\bibitem{ElKLAB}
%M.    Elkies, G. Kuperberg, M. Larsen and J. Propp,
%{\it Alternating sign matrices and domino tilings, II},
%J. Alg.\ Combin.\ {\bf 1} (1992), 219--234.

\bibitem{FellAA} W.    Feller, {\it An introduction to
probability theory and its applications}, vol.~1, 2nd ed., Wiley,
New York,  1957.

\bibitem{FIS}
M. E. Fisher,
{\it Walks, walls, wetting and melting},
J. Stat.\ Phys.\ {\bf 34} (1984), 667-729.

%\bibitem{FlajAA} P.    Flajolet, {\it Combinatorial
%aspects of continued fractions}, Discrete Math.\ {\bf 32} (1980),
%125--161.

%\bibitem{FlOdAA}
%P.    Flajolet and A. Odlyzko,
%{\em Singularity analysis of generating functions},
% SIAM J. Discrete Math. {\bf 3} (1990), 216--240.

\bibitem{FlSeAA}
P.    Flajolet and R. Sedgewick,
{\em Analytic Combinatorics},
book project, available at {\tt 
http://algo.inria.fr/flajolet/Publications/books.html}.

%\bibitem{DGL}
%P. Di Francesco and E. Guitter, {\em Critical and multicritical
%semi-random $(1+d)$-dimensional lattices and hard objects in $d$
%dimensions}, J. Phys.\ A: Math.\ Gen.\ {\bf 35} (2002) 897--927.

\bibitem{FrZZAA}
P. Di Francesco, P. Zinn-Justin and J.-B. Zuber, {\em Determinant
Formulae for some Tiling Problems and Application to Fully Packed
Loops}, preprint; {\tt ar$\chi$iv:math-ph/0410002}.

\bibitem{FrZiAG}
P. Di Francesco and P. Zinn-Justin, 
{\em Quantum Knizhnik-Zamolodchikov equation, generalized
Razumov-Stroganov sum rules and extended Joseph polynomials}, 
preprint; {\tt ar$\chi$iv:math-ph/0508059}.

%\bibitem{FrGuAC}
%P. Di Francesco and E. Guitter, {\em Integrability of graph
%combinatorics via random walks and heaps of dimers}, preprint;
%{\tt ar$\chi$iv:math.CO/0506542}.

\bibitem{GaLoAA}
A. Galluccio and M. Loebl, {\em On the theory of Pfaffian
orientations I. Perfect matchings and permanents},
Electron.\ J. Combin.\ {\bf 6}  (1999), Article~\#R6, 18~pp. 

\bibitem{GaRaAA}
G.~Gasper and M.~Rahman, {\em Basic hypergeometric series},
2nd edition, Encyclopedia of Mathematics And Its Applications 96, Cambridge
University Press, Cambridge, 2004.

%\bibitem{GeViAA}
%I. M. Gessel and X. Viennot,
%{\em Binomial determinants, paths, and hook length formulae},
%Adv.\ in Math.\ {\bf 58} (1985), 300--321.

%\bibitem{GeZeAA} I. M. Gessel and D. Zeilberger,
%{\it Random walk in a Weyl chamber}, Proc.\ Amer.\ Math.\ Soc.\
%{\bf 115} (1992), 27--31.

\bibitem{degier}J. de Gier, {\em Loops, matchings and alternating-sign
matrices},
{Discr.\ Math.}, to appear. {\tt ar$\chi$iv:math.CO/0211285}.

%\bibitem{GoJaAQ}I. P. Goulden and J. M. Jackson, {\em Combinatorial
%enumeration}, John Wiley \& Sons, New York, 1983.

%\bibitem{GrabAD} D. J. Grabiner,
%{\em Random walk in an alcove of an affine Weyl group, and non-colliding
%random walks on an interval}, J. Combin.\ Theory Ser.~A {\bf 97} 
%(2002), 285--306.

%\bibitem{HaMoAB} B. R. Handa and S. G. Mohanty,
%{\it Enumeration of higher-dimensional paths under restrictions},
%Discrete Math.\ {\bf 26} (1979), 119--128.

\bibitem{HumpAC}
J. E. Humphreys, {\it Reflection groups
and Coxeter groups}, Cambridge University Press,
Cambridge, 1990.

%\bibitem{IzerAA}
%A. G. Izergin, {\em Partition function of the six-vertex model in a
%finite volume}, Soviet Phys.\ Dokl.\ {\bf 32} (1987), 878--879.

\bibitem{JohaAB}
K. Johansson, {\em Non-intersecting paths, random tilings and random
matrices},  Probab.\ Theory Related Fields {\bf 123}  (2002),
225--280. 

%\bibitem{JoyaAA}
%A.    Joyal, {\em Une combinatoire des
%s\'eries formelles}, Adv.\ in Math.\ {\bf 42} (1981), 1--82.

%\bibitem{KastAB}
%P. W. Kasteleyn, {\em The statistics of dimers on a lattice 1. The
%number of dimer arrangements on a quadratic lattice}, Physica {\bf 27}
%(1961), 1209-1225.

%\bibitem{KastAA}
%P. W. Kasteleyn, {\it Graph theory and
%crystal physics}, in: Graph Theory and Theoretical Physics,
%F.~Harary, ed., Academic Press, San Diego, 1967, pp.~43--110.

\bibitem{KenyAF}
R. Kenyon, {\em An introduction to the dimer model},
lecture notes for a short course at the ICTP, 2002; 
{\tt ar$\chi$iv:math.CO/0310326}.

\bibitem{KoSwAA}
R.    Koekoek and R. F. Swarttouw,
{\em The Askey--scheme of hypergeometric orthogonal polynomials and 
its $q$-analogue}, TU Delft, The Netherlands, 1998; on the WWW:
{\tt http://aw.twi.tudelft.nl/\~{}koekoek/askey.html}.

%\bibitem{KratAS}
%C.    Krattenthaler, {\it HYP},
%Manual for a {\sl Mathematica} package for handling hypergeometric
%series, 1993--2005; available at
%{\tt http://www.mat.univie.ac.at/\~{}kratt}.

\bibitem{KratBL} C.    Krattenthaler, {\em The enumeration of lattice 
paths with respect to their number of turns}, in: Advances in 
Combinatorial Methods and Applications to Probability and Statistics,
N.~Balakrishnan, ed., Birkh\"auser, Boston, 1997, pp.~29--58.

%\bibitem{KratBN}
%C.    Krattenthaler, {\em Advanced determinant calculus},
%S\'eminaire Lotharingien Combin.\ {\bf 42} (1999)
%(``The Andrews Festschrift"), Article~B42q, 67~pp.

%\bibitem{KratBP} C.    Krattenthaler,
%{\it Permutations
%with restricted patterns and Dyck paths}, Adv.\ Appl.\ Math.\
%{\bf 27} (2001), 510--530.

\bibitem{KratBT}
C.    Krattenthaler, {\em Asymptotics for random walks in alcoves of
affine Weyl groups}, preprint. {\tt ar$\chi$iv:math.CO/0301203}.

\bibitem{KratBW}
C.    Krattenthaler, {\em Watermelon configurations with
wall interaction: exact and asymptotic results}, preprint.
{\tt ar$\chi$iv:math.CO/0506323}.

\bibitem{KratBZ} C.    Krattenthaler, {\em Advanced
determinant calculus: a complement}, Linear Algebra Appl.\ (to
appear); {\tt ar$\chi$iv:math.CO/0503507}.

\bibitem{KrGVAA} 
C. Krattenthaler, A. J. Guttmann and X. G. Viennot,
{\em Vicious walkers, friendly walkers and Young tableaux II: with a
wall}, J. Phys.\ A: Math.\ Gen.\ {\bf 33} (2000), 8835--8866.

%\bibitem{KupeAD}
%G.    Kuperberg, {\em Another proof of the alternating sign matrix 
%conjecture}, Math.\ Research Lett.\ {\bf 3} (1996), 139--150.

\bibitem{KupeAG}
G.    Kuperberg, {\em An exploration of the permanent-determinant
method}, Electron.\ J. Combin.\ {\bf 5} (1998), Article~\#R46, 34~pp.

%\bibitem{KupeAH}
%G.    Kuperberg, {\em Symmetry classes of alternating-sign matrices
%under one roof}, Ann.\ Math.\ {\bf 156} (2002), 835--866.

\bibitem{LaLaAA} G. Labelle and C. Lamathe, {\em A shifted asymmetry
index series},  Adv.\ Appl.\ Math.\ {\bf 32} (2004), 576--608.

%\bibitem{LindAA} B.    Lindstr\"om,
%{\it On the vector representations of induced matroids},
%Bull.\ London Math.\ Soc.\ {\bf 5} (1973), 85--90.

%\bibitem{MacMahon}
%P.~A.~MacMahon, {\em Combinatory Analysis\/}, vol.~2, Cambridge University
%Press, 1916; reprinted by Chelsea, New York, 1960.

%\bibitem{MiRRAB}
%W. H. Mills, D. H. Robbins and H. Rumsey,
%{\em Alternating sign matrices and descending plane partitions},
%J. Combin.\ Theory Ser.~A {\bf 34} (1983), 340--359. 

\bibitem{MoZeAA}
M. Mohammed and D. Zeilberger, {\em Multi-variable Zeilberger and
Almkvist--Zeilberger algorithms and the sharpening of Wilf-Zeilberger
theory}, preprint; available at
{\tt http://www.math.rutgers.edu/\~{}zeilberg}.

%\bibitem{MohaAB} S. G. Mohanty,
%{\it On some generalization 
%of a restricted random walk}, Stud.\ Sci.\ Math.\ 
%Hungarica {\bf 3} (1968), 225--241.

\bibitem{MohaAE} S. G. Mohanty,
{\it Lattice Path Counting and Applications},  Academic
Press, New York, 1979.

\bibitem{Odly} A. M. Odlyzko, Asymptotic enumeration methods, in:
``Handbook of Combinatorics," 
vol.~2, R.~L.~Graham, M.~Gr\"otschel, L.~Lov\'asz, eds., Elsevier,
Amsterdam, 1995, pp.~1063--1229.

%\bibitem{OkadAA}
%S.    Okada, {\em On the generating functions for certain classes of 
%plane partitions}, J. Combin.\ Theory A {\bf 51} (1989), 1--23.

%\bibitem{OkadAJ}
%S. Okada, {\em Enumeration of symmetry classes of alternating sign
%matrices and characters of classical groups}, preprint. 
%{\tt ar$\chi$iv:math.CO/0408234}. 

\bibitem{PeWiAD}
R. Pemantle and M. C. Wilson, {\em Twenty combinatorial examples of
asymptotics derived from multivariate generating functions}, preprint;
available at 
{\tt http://www.cs.auckland.ac.nz/\~{}mcw}.

\bibitem{PeWZAA} M.    Petkov\vv sek, H. Wilf and D. Zeilberger,
{\em A=B}, A.~K.~Peters, Wellesley, 1996.

\bibitem{PropAH}
J.~Propp, {\em Enumeration of matchings: Problems and progress},
in: "New Perspectives in Algebraic
 Combinatorics", L.~Billera, A.~Bj\"orner, C.~Greene, R.~Simion, and
R.~P.~Stanley, eds.,
 Mathematical Sciences Research Institute Publications, vol.~38, 
Cambridge University Press, 1999, pp.~255--291.

%\bibitem{RaStAF}
%A. V. Razumov and Y. G. Stroganov, {\em Enumeration of half-turn
%symmetric alternating-sign matrices of odd order}, 
%preprint; {ar$\chi$iv:math-ph/0504022}.

\bibitem{RaStAG}
A. V. Razumov and Y. G. Stroganov, {\em Enumeration of quarter-turn
symmetric alternating-sign matrices of odd order}, 
preprint; {ar$\chi$iv:math-ph/0507003}.

\bibitem{RoSTAA}
N. Robertson, P. D. Seymour and R. Thomas, {\em Permanents, Pfaffian
orientations, and even directed circuits},  Ann.\ Math.\ (2) {\bf 150}
(1999), 929--975.

%\bibitem{gdev} B. Salvy, {\tt gdev}, a {\it Maple} package for
%series expansions and limits; available at {\tt
%http://algo.inria.fr/libraries/libraries.html\#gdev}.

\bibitem{SchnAA}
C. Schneider, {\em A new {S}igma approach to multi-summation}, 
Adv.\ Appl.\ Math.\ {\bf 34}(4) (2005), 740--767.

\bibitem{SlatAC}
L.~J.~Slater,
{\em Generalized Hypergeometric Functions\/},
Cambridge University Press, Cambridge, 1966.

\bibitem{StanAP}
R. P. Stanley, {\em Enumerative Combinatorics}, Vol.~1, 
Wadsworth \& Brooks/Cole, Pacific Grove, California, 1986; reprinted
by Cambridge University Press, Cambridge, 1998.

\bibitem{StanBI} R.~P.~Stanley, 
{\em Enumerative Combinatorics}, vol.~2,
Cambridge University Press, Cambridge, 1999. 

%\bibitem{StemAE}
%J.~R.~Stembridge, {\em Nonintersecting paths, pfaffians and plane partitions\/}, 
%Adv.\ in Math.\ {\bf 83} (1990),
%96--131.

\bibitem{SzegOP}
G.~Szeg\H o,
{\em Orthogonal polynomials\/},
American Mathematical Society Colloquium Publications Vol.~XXIII, 
New York, 1959.

%\bibitem{TeFiAA}
%H. N. V. Temperley and M. E. Fisher, 
%{\em Dimer problem in statistical mechanics --- an exact result},
%Philos.\ Mag.\ (8) {\bf 6} (1961), 1061--1063.

\bibitem{TeslAF}
G.    Tesler, {\em Matchings in graphs on non-oriented surfaces},
J. Combin.\ Theory Ser.~B {\bf 78} (2000), 198--231.

%\bibitem{VienAE}
%X.~Viennot,
%{\em  Une th\'eorie combinatoire des polyn\^omes orthogonaux g\'en\'eraux},
%UQAM, Montreal, Qu\'ebec, 1983.

%\bibitem{VienAF}
%X. G. Viennot,
%{\em Heaps of pieces. I. Basic definitions and combinatorial lemmas},
%Lecture Notes in Math., 1234, Springer, Berlin, 1986, pp.~ 321--350.

\bibitem{ViJaAA}
X. Viennot and W. James,
{\em Heaps of segments, q-Bessel functions in square lattice
enumeration and applications in quantum gravity},  
preprint.

\bibitem{WiZeAC}
H. S. Wilf and D. Zeilberger, {\em An
algorithmic proof theory for hypergeometric (ordinary and ``$q$")
multisum/integral identities}, Invent.\ Math.\ {\bf 108} (1992),
575--633.

%\bibitem{ZeilBD} 
%D.    Zeilberger, {\em Proof of the
%alternating sign matrix conjecture}, Electron.\ J. Combin. \{\bf 3}
%(no.~2, ``The Foata Festschrift") (1996), \#R13, 84~pp.

%\bibitem{ZeilAO}
%D.    Zeilberger, {\em Proof of the
%refined alternating sign matrix conjecture}, New York J. Math.\
%{\bf 2} (1996), 59--68.

\bibitem{ZeilAZ}
D. Zeilberger, {\em Deconstructing the Zeilberger algorithm},
J. Difference Equations Appl.\ (to appear).

\end{thebibliography}

\end{document}

