%% This document created by Scientific Word (R) Version 2.5


\documentclass[12pt,thmsa]{article}
\usepackage{amssymb}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{sw20lart}

%TCIDATA{TCIstyle=article/art4.lat,lart,article}

%TCIDATA{Created=Sun Nov 17 09:41:53 1996}
%TCIDATA{LastRevised=Sun Mar 09 10:04:00 1997}
%TCIDATA{Language=American English}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Input-Datei zum Erzeugen von Gitterpunktwegen.%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%LaTeX-Version%
%%%%%%%%%%%%%%%
%entering a path: 
%  \Pfad(x-coordinate of starting point,y-coordinate of final %point),path
%  as 1-2-3-4-word\endPfad
%(1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, 4=downward diagonal step)
%
%entering a dotted path: 
%  \SPfad(x-coordinate of starting point,y-coordinate of starting point),path
%  as 1-2-3-4-word\endSPfad
%(1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, 4=downward 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
    \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
    \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



\input{tcilatex}
\begin{document}

\author{Christian Krattenthaler and Heinrich Niederhausen \\
%EndAName
Universitaet Wien \hfill Florida Atlantic University}
\title{Lattice Paths with Weighted Left Turns Above a Parallel to the Diagonal\\
D\ R\ A\ F\ T, March 1997}
\maketitle

\begin{abstract}
classification (both primary and secondary), and Keywords.
\end{abstract}

\section{Introduction}

A lattice path is a sequence of unit steps in the North $\uparrow $ and East 
$\rightarrow $ direction, starting at the origin. In a (left) weighted
lattice path every left turn $\stackrel{\quad \;\uparrow }{\rightarrow \circ 
}$ gets the multiplicative weight $\mu $. 
\[
\begin{tabular}{l}
$
\begin{array}{cccccccc}
&  &  &  &  &  &  & \uparrow \\ 
& \circ & \rightarrow & \circ & \rightarrow & \circ & \rightarrow & \mu \\ 
& \uparrow &  &  &  &  &  &  \\ 
\rightarrow & \mu &  &  &  &  &  & 
\end{array}
$ \\ 
Lattice Path with Weight $\mu ^{2}$%
\end{tabular}
\]
The total weight $s_{n}(m)$ of all paths reaching the point $(n,m)$ equals 
\begin{equation}
s_{n}(m)=\sum_{d\ge 0}\binom{m}{d}\binom{n}{d}\mu ^{d}  \label{unrestricted}
\end{equation}
In Section \ref{SSsymmetry} we show why this kind of weighted path is a very
``natural'' generalization of the ordinary lattice path (where $\mu =1$).

A \emph{ballot path} stays strictly above a parallel to the diagonal, $y=x-K$%
, say, where $K$ is a nonnegative integer. In an ordinary ($\mu =1$) ballot
path we can switch the two types of steps and obtain a path below $y=x+K$.
Hence counting ordinary ballot paths above is equivalent to counting paths
below corresponding boundaries. However, this is no longer true for weighted
paths, because switching the steps moves the weight from left to right turns.

\[
\begin{tabular}{|llllll|ll|}
\hline
& $\mathbf{0}$ & \multicolumn{1}{|l}{$2\mu +3\mu ^{2}$} & $4\mu +9\mu
^{2}+\mu ^{3}$ & $6\mu +18\mu ^{2}+4\mu ^{3}$ & $\dots $ & $\leftarrow
t_{3}(u)$ &  \\ \cline{2-2}
$\mathbf{0}$ & \multicolumn{1}{|l}{$2\mu $} & $4\mu +\mu ^{2}$ & $6\mu +3\mu
^{2}$ & $8\mu +6\mu ^{2}$ & $\dots $ & $\leftarrow t_{K}(u)$ &  \\ 
\cline{1-1}
$1$ & $1+\mu $ & $1+2\mu $ & $1+3\mu $ & $1+4\mu $ & $\dots $ & $\leftarrow
t_{1}(u)$ &  \\ 
$1$ & $1$ & $1$ & $1$ & $1$ & $\dots $ & $\leftarrow t_{0}(u)$ &  \\ 
\cline{1-7}
$u=0$ & $u=1$ & $u=2$ & $u=3$ & $u=4$ & $\dots $ & degree $v\uparrow $ &  \\ 
\hline
\multicolumn{8}{|c|}{Total weights$\text{ of paths with weighted left turns
below }y=x+2$} \\ \hline
\end{tabular}
\]
The total weight $t_{v}(u)$ of the ballot paths to $\left( u,v\right) $
below $y=x+K$ is easily obtained via symmetric Sheffer sequences as 
\begin{equation}
t_{v}(u)=\sum_{l\ge 0}\left( \binom{u}{l}\binom{v}{l}-\binom{u+K}{l}\binom{%
v-K}{l}\right) \mu ^{l}  \label{TotalBelow}
\end{equation}
for all $0\le v\le u+K$ (Corollary \ref{CorBelow}). It follows that for $%
K\le v\le u+K$ there are $\binom{u+K}{l}\binom{v-K}{l}$ paths with $l$ left
turns, ending at $(u,v)$ and reaching the line $y=x+K$ somewhere.
%Christian
Theorem~\ref{T1}
shows a different proof for this result, using 2-rowed plane partitions.
Suppose $m>n-K\ge 0$. With the same approach it is shown in
%Christian
Theorem~\ref{T2} that $%
\binom{n-K+2}{l+1}\binom{m+K-2}{l-1}$ paths with $l$ left turns end at $(n,m)
$ above the line $y=x-K$ after reaching it somewhere.

\[
\begin{tabular}{|llllll|l|}
\hline
$1$ & $1+3\mu $ & $1+5\mu +3\mu ^{2}$ & $\mathbf{1+6\mu +6\mu }^{2}\mathbf{%
+\mu }^{3}$ & $\mathbf{1+6\mu +6\mu }^{2}\mathbf{+\mu }^{3}$ & 
\multicolumn{1}{|l|}{$\dots $} & $m=3$ \\ \cline{5-5}
$1$ & $1+2\mu $ & $\mathbf{1+3\mu +\mu }^{2}$ & $\mathbf{1+3\mu +\mu }^{2}$
& \multicolumn{1}{|l}{} &  & $m=2$ \\ \cline{4-4}
$1$ & $\mathbf{1+\mu }$ & $\mathbf{1+\mu }$ & \multicolumn{1}{|l}{} &  &  & $%
m=1$ \\ \cline{3-3}
$1$ & $1$ & \multicolumn{1}{|l}{} &  &  &  & $m=0$ \\ \hline
$r_{0}(m)$ & $r_{1}(m)\uparrow $ & $r_{K}(m)\uparrow $ & $r_{3}(m)\uparrow $
& $r_{4}(m)\uparrow $ & $\dots $ & $\leftarrow $ degree $n$ \\ \hline
\multicolumn{7}{|c|}{$\text{Total weights of paths with weighted left turns
above }m=n-2$} \\ \hline
\end{tabular}
\]

In order to find the weight $r_{n}(m)$ of the ballot paths above the line $%
y=x-K$ in terms of Sheffer sequences it is no longer admissible to use the
initial value $r_{n}(n-K)=0$ for all $n\ge K$. Instead, we must work with
the initial condition $r_{n}(n-K+1)=r_{n-1}(n-K+1)$ for all $n\ge K$ (bold
entries in the table above). We say that the initial values are \emph{%
recursively defined}; the polynomial $r_{n}(x)$ gets an initial value from
its predecessor $r_{n-1}(x)$. In Theorem \ref{ThSkewed} we show that 
\[
r_{n}(m)=\sum_{l\ge 0}\left( \binom{n}{l}\binom{m}{l}-\binom{n-K+2}{l+1}%
\binom{m+K-2}{l-1}\right) \mu ^{l}
\]
as a special case ($k=1$) of a result for skew-symmetric Sheffer sequences.
More general results on Sheffer sequences with recursively defined initial
values will be shown in a forthcoming paper.

\section{Sheffer Sequences}

For the following we need a few definitions from the Unmral Calculus \cite
{Rota}. A \emph{Sheffer sequence} $\left\{ p_{n}(x)\right\} $ is a sequence
of polynomials such that $\deg p_{n}=n$ and 
\[
\sum_{n\ge 0}p_{n}(x)t^{n}=p(t)e^{x\beta (t)} 
\]
where $s(t)=\sum_{n\ge 0}s_{n}(0)t^{n}$ and $\beta (t)$ are formal power
series of order $0$ and $1$, respectively. Let $B(t)$ be the formal inverse
of $\beta (t)$, and $D$ be the derivative operator on the algebra of
polynomials. The linear operator $B(D)$ is called the \emph{delta operator}
for $\left\{ p_{n}\right\} $, and for all $n\ge 0$%
\[
Bp_{n}=p_{n-1} 
\]

$\left\{ \binom{n+x}{n}\right\} $ is an example for a Sheffer sequence with
associated delta operator $\triangledown =1-E^{-1}$, the backwards
difference operator. $E^{a}$ denotes the \emph{translation operator} $%
E^{a}f(x)=f(x+a)$. The \emph{basic sequence} associated with the delta
operator $B$ is the Sheffer sequence $\left\{ b_{n}\right\} $ with initial
values $b_{n}(0)=\delta _{0,n}$.

\subsection{Symmetry\label{SSsymmetry}}

A Sheffer sequence $\left\{ p_{n}(x)\right\} $ is symmetric if 
\[
p_{n}(m)=p_{m}(n) 
\]
for all nonnegative integers $m$ and $n$. Obviously, $\binom{n+m}{n}$ is
symmetric, which is the reason for so many elegant results in ordinary
lattice path counting.

The difference of two different Sheffer sequences for the same delta
operator is again a Sheffer sequence (for the same operator). If $\left\{
p_{n}\right\} $ is symmetric then 
\begin{equation}
t_{n}(x):=p_{n}(x)-p_{n-K}(x+K)  \label{InitialValue}
\end{equation}
is a Sheffer sequence which has initial values $t_{n}(n-K)=0$ for all $n\ge K
$. The well-known solution for the ordinary ballot problem can be obtained
this way. But are there any other symmetric Sheffer sequences besides $%
\left\{ \binom{n+x}{n}\right\} $? In \cite{SymSheff} we have shown that
except for a scaling factor there is only one parameter that describes the
whole class of symmetric Sheffer sequences:

\begin{theorem}
All symmetric Sheffer sequences are of the form $\left\{ \alpha
s_{n}(x)\right\} _{n\ge 0}$ where $\alpha $ is a nonzero scaling factor, and 
\[
s_{n}(x)=\sum_{l=0}^{n}\binom{n}{l}\binom{x}{l}\mu ^{l}
\]
($\mu \neq 0$). The corresponding delta operator $\Omega $ has the expansion 
\begin{equation}
\Omega =\frac{\Delta }{\mu +\Delta }  \label{OmegaFromDelta}
\end{equation}
in terms of the forward difference operator $\Delta =E^{1}-1$.
\end{theorem}

In other words, ``the symmetric Sheffer sequence $\left\{ s_{n}\right\} $ is
as symmetric as $\left\{ \binom{n+x}{n}\right\} $'', which is the reason for
many elegant results on the enumeration of lattice paths with weighted left
turns.

All Sheffer sequences for $\Omega $ satisfy the recurrence relation 
\begin{equation}
s_{n}(x)=s_{n}(x-1)+s_{n-1}(x)+(\mu -1)s_{n-1}(x-1)
\label{SymmetricRecurrence}
\end{equation}
and the identity 
\begin{equation}
s_{n}(x)-s_{n}(x-1)=\mu \sum_{i=0}^{n-1}s_{i}(x-1)
\label{SymShefferIdentity}
\end{equation}
because (\ref{OmegaFromDelta}) has the solution 
\begin{equation}
\Delta =\mu \Omega /(1-\Omega )  \label{DeltaFromOmega}
\end{equation}
Weighted lattice paths are counted by the recurrence (\ref
{SymmetricRecurrence}), with initial values $s_{n}(0)=1$ for all $%
n=0,1,\dots $ if no other restrictions are present. Hence the total weight (%
\ref{unrestricted}) is obtained.

\begin{corollary}
\label{CorBelow}The $\Omega $-Sheffer sequence 
\[
t_{n}(x):=s_{n}(x)-s_{n-K}(x+K)
\]
has the initial values $t_{n}(0)=1$ for all $n=0,\dots ,K-1$, and $%
t_{n}(n-K)=0$ for all $n\le K$.
\end{corollary}

%TCIMACRO{\TeXButton{Proof}{\proof}}
%BeginExpansion
\proof%
%EndExpansion
Follows from (\ref{InitialValue}).%
%TCIMACRO{\TeXButton{End Proof}{\endproof}}
%BeginExpansion
\endproof%
%EndExpansion

\subsection{Skew-Symmetric Sheffer Polynomials}

The generating functions 
\[
(1-t)^{-k}\left( 1+\frac{\mu t}{1-t}\right) ^{x},\quad k\in \Bbb{Z} 
\]
\cite{SymSheff} belong to an important class of $\Omega $-Sheffer sequences
which will be called \emph{skew-symmetric} in the following. They can be
expanded as 
\begin{equation}
s_{n}^{(k)}(x)=\sum_{l=0}^{n}\binom{x}{l}\binom{n+k-1}{n-l}\mu ^{l}
\label{SkewSymmetricSheffer}
\end{equation}
The case $k=1$ has been discussed in the previous section; $k=0$ gives the
basic sequence for $\Omega $. It is easy to check that skew-symmetric
Sheffer sequences have the property 
\begin{equation}
s_{n}^{(k)}(m-k+1)=\mu ^{1-k}s_{m}^{(2-k)}(n+k-1)  \label{SkewSymmetry}
\end{equation}
for all integers $k$, and for all non-negative integers $n$ and $m$.

From the expansion (\ref{SkewSymmetricSheffer}) we can derive another
important property of skew-symmetric Sheffer sequences, 
\begin{equation}
\Delta s_{n}^{(k)}(x)=\mu s_{n-1}^{(k+1)}(x)  \label{DifferenceSkewSheffer}
\end{equation}

\section{Recursive Initial Conditions}

Suppose $\left\{ t_{n}(x)\right\} $ and $\left\{ r_{n}(x)\right\} $ are
Sheffer sequences for the same Delta operator. Assume that $\left\{
t_{n}(x)\right\} $ and the basic sequence $\left\{ b_{n}(x)\right\} $ are
known, and that $r_{n}(x)=t_{n}(x)$ for all $n$ below some given positive
integer $K$. For $n\ge K$ we recursively define the initial values 
\begin{equation}
r_{n}(n-K+\alpha )=r_{n-1}(n-K+\alpha )  \label{Tie}
\end{equation}
where $\alpha $ is some given shift.

If we write 
\[
r_{n}(x)=t_{n}(x)+q_{n-K}(x-\alpha ) 
\]
then $\left\{ q_{n}(x)\right\} $ is a Sheffer sequence for the same delta
operator $B$, satisfying the condition 
\begin{equation}
q_{n}(n)-q_{n-1}(n)=t_{n+K-1}(n+\alpha )-t_{n+K}(n+\alpha )
\label{Difference}
\end{equation}
for all $n\ge 0$.

\subsubsection{Skew-Symmetry}

Let $\left\{ s_{n}^{(k)}(x)\right\} _{n=0,1,\dots }$ be a skew-symmetric
Sheffer sequence as defined in (\ref{SkewSymmetricSheffer}).

\begin{theorem}
\label{ThSkewed}If $r_{n}^{(k)}(x):=s_{n}^{(k)}(x)$ for all $n=0,\dots ,K-1$%
, and $r_{n}^{(k)}(n-K+k-2)=r_{n-1}^{(k)}(n-K+k-2)$ for all $n\ge K$, then 
\[
r_{n}^{(k)}(x)=\sum_{l\ge 0}\left( \binom{x}{l}\binom{n+k-1}{l+k-1}-\binom{%
x+K+2k-4}{l+k-2}\binom{n-K-k+3}{l+1}\right) \mu ^{l}
\]
\end{theorem}

%TCIMACRO{\TeXButton{Proof}{\proof}}
%BeginExpansion
\proof%
%EndExpansion
Let $t_{n}(x)=s_{n}^{(k)}(x)$ and $\alpha =2-k$ in equation (\ref{Difference}%
), 
\begin{eqnarray*}
q_{n}(n)-q_{n-1}(n) &=&s_{n+K-1}^{(k)}(n-k+2)-s_{n+K}^{(k)}(n-k+2) \\
&=&\mu ^{1-k}\left( s_{n+1}^{(2-k)}(n+K+k-2)-s_{n+1}^{(2-k)}(n+K+k-1)\right)
\end{eqnarray*}
because of (\ref{SkewSymmetry}).

Hence, the $n$-th degree $\Omega $-Sheffer polynomials $q_{n}(x)-q_{n-1}(x)$
and $\mu ^{1-k}\left(
s_{n+1}^{(2-k)}(x+K+k-2)-s_{n+1}^{(2-k)}(x+K+k-1)\right) $ all have one
value in common, and therefore must be identical! In terms of $\Delta $ and $%
\Omega $, 
\[
q_{n}(x)-q_{n-1}(x)=\left( 1-\Omega \right) q_{n}(x)=\Omega \left( 1-\Omega
\right) q_{n+1}(x)=-\mu ^{1-k}\Delta s_{n+1}^{(2-k)}(x+K+k-2) 
\]
Applying (\ref{DeltaFromOmega}) and (\ref{DifferenceSkewSheffer}) shows that 
\begin{eqnarray*}
q_{n}(x) &=&\Omega ^{2}q_{n+2}(x)=-\frac{\mu ^{1-k}\Delta \Omega }{\left(
1-\Omega \right) }s_{n+2}^{(2-k)}(x+K+k-2)=-\mu ^{-k}\Delta
^{2}s_{n+2}^{(2-k)}(x+K+k-2) \\
&=&-\mu ^{2-k}s_{n}^{(4-k)}(x+K+k-2)
\end{eqnarray*}
Now we can expand $r_{n}^{(k)}(x)$.

\begin{eqnarray*}
r_{n}^{(k)}(x) &=&s_{n}^{(k)}(x)+q_{n-K}(+k-2)=s_{n}^{(k)}(x)-\mu
^{2-k}s_{n-K}^{(4-k)}(x+K+2k-4) \\
&=&\sum_{l\ge 0}\left( \binom{x}{l}\binom{n+k-1}{n-l}-\mu ^{2-k}\binom{%
x+K+2k-4}{l}\binom{n-K-k+3}{n-K-l}\right) \mu ^{l} \\
&=&\sum_{l\ge 0}\left( \binom{x}{l}\binom{n+k-1}{l+k-1}-\binom{x+K+2k-4}{%
l+k-2}\binom{n-K-k+3}{l+1}\right) \mu ^{l}
\end{eqnarray*}
%TCIMACRO{\TeXButton{End Proof}{\endproof}}
%BeginExpansion
\endproof%
%EndExpansion

Note that for $\mu =1$%
\begin{eqnarray}
r_{n}^{(k)}(x) &=&\sum_{l}\left( \binom{x}{l}\binom{n+k-1}{l+k-1}-\binom{%
x+K+2k-4}{l+k-2}\binom{n-K-k+3}{l+1}\right)   \label{rnkForMu=1} \\
&=&\binom{x+n+k-1}{n}-\binom{x+n+k-1}{n-K}  \nonumber
\end{eqnarray}
%Christian:
In the next section we provide a combinatorial interpretation of this
term.

From $r_{n}^{(k)}(n-K-k+1)=0$ follows that $r_{n}^{(k)}(m-k+1)$ is the
number of lattice paths from $(0,0)$ to $(n,m)$ that stay (strictly) above
the line $y=x-K$ (if $\mu =1$).

%Christian:
\section{Combinatorics}
In this section we describe a combinatorial approach to the
enumeration of weighted lattice paths. Basically, it can be extracted
from \cite{KratMoh}, or, equivalently, from the restriction to two
paths of the Gessel--Viennot theory of nonintersecting lattice paths
\cite{GeViAA}, \cite{GeViAB}, \cite[Sec.~1]{StemAE}.

\begin{figure}\label{F1}
$$\Koordinatenachsen(8,8)(0,0)
\Gitter(8,8)(0,0)
\Pfad(1,-1),221221112122\endPfad
\DickPunkt(1,-1)
\DickPunkt(6,6)
\Label\ro{P_0}(3,3)
\hskip4cm
$$
\end{figure}
%Christian: Ich weiss im Moment nicht, wie ich die Figur numeriere.

Our approach for the enumeration of simple plane lattice paths
with respect to their number of turns
is by encoding lattice paths in terms of two-rowed
arrays. Let $(p_1,q_1)$, $(p_2,q_2)$, \dots,
$(p_l,q_l)$ be the left turns 
of a path $P$. Then the {\em two-rowed array
representation\/}
of $P$ is defined by the two-rowed array
\begin{equation}\label{C1}\begin{array} {cccc}
p_1&p_2&\dots&p_l\hphantom{,}\\
q_1&q_2&\dots&q_l,
\end{array}
\end{equation}
which consists of two strictly increasing sequences.
If
$P$ runs from $(a,b)$ to $(c,d)$ then $a+1\le p_1<p_2<\dots<
p_l\le c$ and $b\le q_1<q_2<\dots<q_l\le d-1$ are satisfied. 
If we wish to make this fact transparent, we write
\begin{equation} \label{C2} 
\begin{array} {rccccl}
a+1\le&\quad p_1&p_2&\dots&p_l&\quad \le c\\
b\le&\quad q_1&q_2&\dots&q_l&\quad \le d-1.
\end{array}
\end{equation}
For a given starting point and a given final point,
by definition the empty array is the representation for the only path
that has no left turn.
For the path in Figure~\ref{F1}
we obtain the left turn representation
$$\begin{array}{ccc} 2\ & 5\ & 6\\
1\ & 3\ & 4\end{array}\ ,$$
or with bounds included,
$$\begin{array}{rcccl}\\
2\le&\quad 2&\ 5&\ 6&\quad \le6\\
-1\le&\quad 1&\ 3&\ 4&\quad \le5\end{array}\ .$$

Also two-rowed arrays with its
rows being of unequal length will be considered. These arrays will
also have the property that the rows are strictly increasing. So by
convention, whenever we speak of two-rowed arrays we
mean two-rowed arrays with strictly increasing rows. For these
arrays we will use a notation of the kind (\ref{C2}) as well. 


\begin{theorem} \label{T1}
Let $(u,v)$ be located below the line $y=x+K$.
There is an explicit bijection between lattice paths from $(0,0)$ to
$(u,v)$ with $l$ left turns, reaching the line $y=x+K$
somewhere, and two-rowed arrays of the form
\begin{equation} \label{C3} 
\begin{array} {rcccl}
-K+1\le&\quad \bar p_1&\dots&\bar p_l&\quad \le u\\
K\le&\quad \bar q_1&\dots&\bar q_l&\quad \le v-1.
\end{array}
\end{equation}
Hence, their cardinality equals $\binom {u+K}l\binom {v-K}l$.
\end{theorem}
\textsc{Proof}. Consider a path $P$ from $(0,0)$ to
$(u,v)$ with $l$ left turns, reaching the line $y=x+K$
somewhere. In terms of its two-rowed array representation,
\begin{equation}\label{C1a}\begin{array} {rccccl}
1\le&\quad p_1&p_2&\dots&p_l&\quad \le u\\
0\le&\quad q_1&q_2&\dots&q_l&\quad \le v-1,
\end{array}
\end{equation}
it means that there is an index $I$, $0\le I\le l?$ such that
$q_{I+1}\ge p_{I}+K$. Without loss of generality assume that $I$ is
the largest such integer. Then map the two-rowed array of $P$ to
\begin{equation} \label{C4} 
\begin{array} {cccccc}
q_1-K+1&\dots&q_I-K+1&p_{I+1}&\dots&  p_l\\
p_1+K-1& \dots&p_I+K-1&q_{I+1}&\dots&  q_l.
\end{array}
\end{equation}
Note that both rows are strictly increasing because of
$q_I-K+1< q_{I+1}-K+1<q_{I+2}-K+1\le p_{I+1}$ and $p_{I}+K-1<q_{I+1}$.
It is no difficulty to see that (\ref{C4}) is of type (\ref{C3}).

The inverse of this map is defined in the same way. We leave it to
the reader to check the details.\quad \quad \qed

\medskip

\begin{theorem} \label{T2}
Let $(n,m)$ be located above the line $y=x-K$.
There is an explicit bijection between lattice paths from $(0,0)$ to
$(n,m)$ with $l$ left turns, reaching the line $y=x-K$
somewhere, and two-rowed arrays of the form
\begin{equation} \label{C5} 
\begin{array} {rcccccl}
K-1\le&\quad \bar p_0&\bar p_1&\bar p_2&\dots&\bar p_l&\quad \le n\\
-K+2\le&\quad           &        &\bar q_2&\dots&\bar q_l&\quad \le m-1.
\end{array}
\end{equation}
Hence, their cardinality equals $\binom {n-K+2}{l+1}\binom
{v+K-2}{l-1}$.
\end{theorem}

\textsc{Proof}. Consider a path $P$ from $(0,0)$ to
$(n,m)$ with $l$ left turns, reaching the line $y=x-K$
somewhere. In terms of its two-rowed array representation (\ref{C1a}),
it means that there is an index $I$, $1\le I\le l$ such that
$q_{I}\le p_{I}-K$. Without loss of generality assume that $I$ is
the largest such integer. Then map the two-rowed array of $P$ to
\begin{equation} \label{C6} 
\begin{array} {ccccccccc}
q_1+K-1&q_2+K-1&q_3+K-1&\dots&q_I+K-1&p_{I}&p_{I+1}&\dots&  p_l\\
       &       &p_1-K+1& \dots&\dots&p_{I-1}-K+1&q_{I+1}&\dots&  q_l.
\end{array}
\end{equation}
Note that both rows are strictly increasing because of
$q_I+K-1<  p_{I}$ and $p_{I-1}-K+1<p_I-K+1<p_{I+1}-K+1\le q_{I+1}$.
Again, it is no difficulty to see that (\ref{C6}) is of type (\ref{C5}).

The inverse of this map is defined in the same way. We leave it to
the reader to check the details.\quad \quad \qed

\medskip
We remark that in the same way it can be seen that
$$\binom xl\binom {n+k-1}{l+k-1}-\binom {x+K+2k-4}{l+k-2}\binom
{n-K-k+3}{l+1}$$
counts two-rowed arrays of the form
\begin{equation} 
\begin{array} {rcccccl}
1\le&\quad  p_1&\dots&p_k&\dots&p_{l+k-1}&\quad \le n+k-1\\
0\le&\quad     &     &q_k&\dots&q_{l+k-1}&\quad \le x-1
\end{array}
\end{equation}
with the property that $q_i>p_i-K-2k+2$ for all $i$.


\begin{thebibliography}{9}
\bibitem{GeViAA}Gessel, I. M. and Viennot, X. (1985)
Binomial determinants, paths, and hook length formulae,
\emph{Adv\@. in Math\@.} \textbf{58}, 300--321.

\bibitem{GeViAB} Gessel, I. M. and Viennot, X. (1989)
Determinants, paths, and plane partitions, preprint.

\bibitem{KratMoh} Krattenthaler, C. and Mohanty, S. G. (1993)
On lattice path counting by major and descents, \emph{Europ\@. J.
Combin\@.} \textbf{14}, 43--51.

\bibitem{SymSheff}  Niederhausen, H. (1996) Symmetric Sheffer sequences and
their applications to lattice path counting, \emph{J. Statist. Planning and
Inference} \textbf{54}, 87-100.

\bibitem{Rota}  Rota, G.-C., Kahaner, D. and Odlyzko, A. (1973). On the
foundations of combinatorial theory, VIII. Finite operator calculus, \emph{%
J. Math. Anal. Appl.} \textbf{42}, 684-760.

\bibitem{StemAE} Stembridge, J. R. (1990) 
Nonintersecting paths, pfaffians and plane partitions,
\emph{Adv\@. in Math\@.} \textbf{83}, 96--131.

\end{thebibliography}

\end{document}
