\magnification 1200
\documentstyle{amsppt}\nologo
\vsize 540pt
\newif\ifwriterefs
%\writerefstrue
%\newif\ifDraft
%\Drafttrue
\TagsOnRight
\newcount \eqnumber \eqnumber=0
\def\eqtag{\the\eqnumber}
\def\assigneqnumber #1{
\expandafter\ifx\csname#1^^B\endcsname\relax\else
\write16{Warning: #1 has already been used as an equation label}\fi
\global\advance\eqnumber by1
\expandafter\xdef\csname#1^^B\endcsname {\eqtag}}
\def\eq#1{\assigneqnumber{#1}\eqtag}
\def\tagg #1$${\tag\eq{#1}$$}
%Note: \tagg generally doesn't work in alignments--use\tag\eq instead
\def\(#1){(\csname#1^^B\endcsname)}
\newcount\referenceno
\referenceno=0
%\def\nextref#1{\advance\referenceno by 1
% \expandafter\xdef\csname#1^^C\endcsname{\the\referenceno}}
\def\[#1]{[\reference{#1}]}
\def\reference#1{\expandafter\ifx\csname#1^^C\endcsname\relax
?\immediate\write16{Undefined reference: #1}\else
\csname#1^^C\endcsname\fi}
\let\nx=\noexpand
\def\name#1 {\global\advance\referenceno by 1
\ifwriterefs\immediate\write1
{\nx\expandafter\nx\def\nx\csname #1^^C\endcsname
\nx{\the\referenceno\nx}}\fi
\no \the \referenceno}
%\def\bye{\ifwriterefs\closeout1\fi\vfill\supereject\end}
%\let\enddocument=\bye
%\input \jobname.names
%\ifwriterefs \immediate\openout1=\jobname.names\fi
%\ifDraft
% \def\eq#1{{\tt #1}} \def\(#1){({\tt#1})} \fi
\def\sumz#1{\sum_{#1=0}^\infty}
\def \C{\bold C}
\def\N{\widetilde N}
\def\M{\widetilde M}
\expandafter \def \csname brini^^C\endcsname {1}
\expandafter \def \csname gessel^^C\endcsname {2}
\expandafter \def \csname jab^^C\endcsname {3}
\expandafter \def \csname mohanty^^C\endcsname {4}
\expandafter \def \csname ree^^C\endcsname {5}
\expandafter \def \csname schiffer^^C\endcsname {6}
\expandafter \def \csname schur^^C\endcsname {7}
\topmatter
\title Lattice paths and Faber polynomials\endtitle
\author Ira M. Gessel$^1$ and Sangwook Ree \endauthor
\affil Department of Mathematics\\
Brandeis University\\
Waltham, MA 02254-9110 \\
gessel\@math.brandeis.edu\\
\\
Department of Mathematics\\
SuWon University\\
Kyung-Ki-Do\\
Korea, 445 743\\
swree\@math.snu.ac.kr\\
\endaffil
\leftheadtext{Ira M. Gessel and Sangwook Ree}
\date Sept. 20, 1996\enddate
\abstract
The $r$th Faber polynomial of the Laurent series $f(t)=t+f_0+f_1/t+f_2/t^2+\cdots$ is the
unique polynomial $F_r(u)$ of degree $r$ in $u$ such that $F_r(f)=t^r+\text{negative powers
of $t$}$. We apply Faber polynomials, which were originally used to study univalent
functions, to lattice path enumeration.
\endabstract
\keywords lattice path enumeration, ballot problem, Faber polynomials
\endkeywords
\thanks $^1\,$Research partially supported by NSF Grant DMS-9622456.
\endthanks
\endtopmatter
\document
\subheading{1. Introduction}
The classical ballot problem (see, e.g., Mohanty \[mohanty]) asks for the number $B(m,n)$ of paths
from
$(1,0)$ to $(m,n)$ (where $m>n$), with unit steps up and to the right, that never touch the line
$x=y$. The number $B(m,n)$ can easily be computed by the recurrence
$$B(m,n)=B(m-1,n)+B(m,n-1)\quad\text{for $m>n\ge0$, $(m,n)\ne (1,0)$,}$$ with the
initial condition
$B(1,0)=1$ and the boundary conditions
$B(m,-1)=0$ and
$B(m,m)=0$ for all $m\ge 0$. Displaying these values on the corresponding lattice points, we
have the following array, showing $B(m,n)$ for $m\ge n\ge 0$:
%$$\vbox{\openup.8\jot\halign{&\hbox to 15pt{\hss$#$}\cr
%&&&&&0\cr
%&&&&0& 14\cr
%&&&0& 5&14\cr
%&&0& 2&5&9\cr
%&0&1&2&3&4\cr
%0&1&1&1&1&1\cr
%}}$$
%
$$\vbox{\offinterlineskip\halign{\strut\hfil$#$\hfil\ &
\vrule#&&\hbox to 15pt{\hss$#$}\cr
5&&&&&&&0\cr
4&&&&&&0& 14\cr
3&&&&&0& 5&14\cr
2&&&&0& 2&5&9\cr
1&&&0&1&2&3&4\cr
0&&0&1&1&1&1&1\cr
\noalign{\hrule}
\vrule width0pt height 10pt n/ m&& 0&1&2&3&4&5\cr}}$$
Let us now extend the values of $B(m,n)$ to the region in which $n>m\ge0$ so that the same
recurrence is satisfied; this can be done in only one way, since we may write the recurrence as
$B(m,n-1)=B(m,n)-B(m-1,n)$. We obtain the following array:
$$\vbox{\openup1\jot\halign{&\hbox to 20pt{\hss$#$}\cr
-1&-4&-9&-14&-14&0\cr
-1&-3&-5&-5&0& 14\cr
-1&-2&-2&0& 5&14\cr
-1&-1&0& 2&5&9\cr
-1&0&1&2&3&4\cr
0&1&1&1&1&1\cr
}}$$
We observe that the recurrence $B(m,n)-B(m-1,n)-B(m,n-1)=0$ is now satisfied for all $m,n\ge0$
except $(m,n)=(1,0)$ and $(m,n)=(0,1)$, as long as we take $B(m,n)$ to be 0 for $m<0$
or
$n<0$. In terms of generating functions, the recurrence and initial
conditions are equivalent to the formula
$$(1-x-y)\sumz{m,n}B(m,n)x^my^n=x-y,$$ which gives
$$\sumz{m,n}B(m,n) x^my^n={x-y\over 1-x-y}.\tagg 1$$
Following MacMahon, we may call \(1) a ``redundant generating function,"
since it contains some terms which are not part of the solution of the
original problem.
From \(1) we may derive the well-known formula for the ballot
numbers,
$$B(m,n)={m+n-1\choose m-1}-{m+n-1\choose m}={m-n\over m+n}{m+n\choose m}.\tagg 2$$
There is a gap in our derivation of \(1). It is clear that the
numbers
$B(m,n)$ defined by \(1) do indeed have the property that for $m>n\ge0$,
$$B(m,n)-B(m-1,n)-B(m,n-1)=\cases 1 & \text{if $(m,n)=(1,0)$}\cr
0&\text{otherwise}\cr
\endcases$$ However, we have not yet proved that the boundary condition
$B(m,m)=0$ is satisfied. This follows easily from the explicit formula
\(2), or from the fact that the generating function \(1) is
anti-symmetric. The proof that the coefficients of \(1) are indeed the
solution to our problem is now complete.
By exactly the same reasoning, we find that for any positive integer $r$ and any nonnegative
integers $m>n\ge0$, the number of paths from $(r,0)$ to $(m,n)$ that never touch the line $x=y$ is
the coefficient of $x^my^n$ in $(x^r-y^r)/(1-x-y)$.
We can try a similar approach to paths that begin at $(1,0)$ and stay below the line $y=x/2$. Here
the recurrence is again $C(m,n)=C(m-1,n)+C(m,n-1)$, but the boundary condition is $C(2n,n)=0$.
Extending the recurrence to the region $m < 2n$, we obtain the following
array:
$$\vbox{\openup1.2\jot\halign{&\hbox to 20pt{\hss$#$}\cr
%-2&-9&-24&-49&-84&-126&-168\cr
%-2&-7&-15&-25&-35&-42&-42\cr
-2&-5&-8&-10&-10&-7&0\cr
-2&-3&-3&-2&0&3&7\cr
-2&-1&0&1&2&3&4\cr
0&1&1&1&1&1&1\cr
}}$$
As before, we find that the extended function $C(m,n)$, with $C(m,n)=0$ for $m<0$
or $n<0$, satisfies the recurrence
$C(m,n)=C(m-1,n)+C(m,n-1)$ everywhere except when $(m,n)$ is $(1,0)$ or $(0,1)$, and thus the
generating for the extended function is apparently
$${x-2y\over 1-x-y},\tagg3$$ from which we may derive the formula
$$C(m,n)={m+n-1\choose m-1}-2{m+n-1\choose m}={m-2n\over m+n}{m+n\choose n}.$$
To complete the proof we must show that
the coefficient of $x^{2n}y^n$ in \(3) is indeed zero. Although this may be seen
from the explicit formula for the coefficients, we use a different method that we
will need later on. Let us substitute
$xt$ for $x$ and $y/t^2$ for
$y$ in \(3). Then it suffices to show that the constant term in $t$ in
$${xt-2y/t^2\over 1-xt - y/t^2},$$ when expanded as a power series in $x$ and
$y$, is zero. But
$$ {xt-2y/t^2\over 1-xt - y/t^2}
= t{d\ \over dt}\log{1\over 1-xt - y/t^2},$$
and since the coefficient of $1/t$ in the derivative with respect to $t$ of a Laurent series in
$t$ is 0, the conclusion follows.
Note that this approach cannot easily be applied to paths that are required to stay
below the line $y=2x$: here we would require the boundary conditions
$C(m,2m)=0$ and $C(m,2m+1)=0$, and this is not so easily achieved. However, there
is no problem with paths starting at $(1,0)$ that stay below the line
$x=py$, where $p$ is a positive integer, and we find
in this case the generating function
$(x-py)/(1-x-y)$.
We now consider one final example before embarking on the general case. Suppose we want to count
paths from $(3,0)$ to $(m,n)$ that stay below the line $y=x/2$, where $m>2n$. The same recurrence
is satisfied, and as before, we may extend its solution into the region where $m<2n$, obtaining
the following array:
$$\vbox{\openup1.4\jot\halign{&\hbox to 22pt{\hss$#$}\cr
%-2&-11&-35&-84&-168&-294&-462\cr
%-2&-9&-24&-49&-84&-126&-168\cr
-2&-7&-15&-25&-35&-42&-42\cr
-2&-5&-8&-10&-10&-7&0\cr
0&-3&-3&-2&0&3&7\cr
0&0&0&1&2&3&4\cr
0&0&0&1&1&1&1\cr
}}$$
The recurrence is satisfied except at the points $(3,0)$, $(1,2)$, and $(0,3)$, so the generating
function is apparently
$${x^3 -3xy^2-2y^3\over 1-x-y}.\tagg 4$$
To prove this we must show that the coefficient of $x^{2n}y^n$ in \(4) is zero, and we can do it
exactly as in the previous example: we replace $x$ with $xt$ and $y$ with $y/t^2$. Then we
have
$${x^3t^3 -3xy^2/t^3-2y^3/t^6\over 1-xt-y/t^2}=t{d\ \over dt}\left(\log {1\over 1-S(t)}
-S(t) -S(t)^2/2\right),\tagg 5$$
where $S(t)=xt+y/t^2$, so the constant term in $t$ in \(5) is zero.
In the remainder of this paper, we shall explain the general theory of which \(5)
is a special case. It will turn out that the numerator polynomials are closely
related to certain polynomials called {\it Faber polynomials\/} which have been
studied in connection with univalent functions \[schiffer]; see also
[\reference{brini}, \reference{jab},
\reference{schur}]. Faber polynomials were first applied to lattice path
enumeration, in the special case we consider in Section 5, in \[ree].
\subheading{2. Faber polynomials}
Let
$$f(t)=t+f_0+{f_1\over t}+{f_2\over t^2}+\cdots.$$
In the literature on Faber polynomials, the $f_i$ are complex numbers, and
the series converges in some neighborhood of infinity. However, for our applications
we take $t$ and the $f_i$ to be indeterminates; i.e., we work in the ring of formal Laurent
series $\C[[t, f_0,f_1/t,f_2/t^2,\ldots]]$.
Let $F(u)$ be a polynomial in $u$ of degree $r$ such that
$$F(f)=t^r +\hbox{negative powers of $t$}.$$
We say that $F(u)$ is a {\it Faber polynomial\/} of $f$. It is easy to prove
by induction that there is exactly one Faber polynomial $F_r(u)$ of degree
$r$, which we call the {\it
$r$th Faber polynomial of $f$\/}
For example, we have
$F_1(u)=u-f_0$ and $F_2(f)=u^2-2f_0u+(f_0^2-2f_1)$.
M. Schiffer \[schiffer] gave the generating function
$$\log {f(v) -u\over v}=-\sum_{r=1}^\infty F_r(u){v^{-r}\over r}.\tagg 6$$
If we set $f(v)=vh(1/v)$, so that $h(w)=1+\sum_{i=0}^\infty f_i w^{i+1}$ is a power
series in $w$, then \(6) may be rewritten in terms of formal power series as
$$\log\bigl(h(w) -uw\bigr)=-\sum_{r=1}^\infty F_r(u) {w^r\over r}.\tagg 7$$
Expanding \(6) or \(7) gives the explicit formula
$$F_r(u)=\sum_{i=0}^r u^i \sum_{i+j_0+2j_1+3j_2\cdots=r}(-1)^{j_0+j_1+\cdots}
r{(i-1+j_0+j_1+\cdots)!\over i!\, j_0!\, j_1!\cdots}f_0^{j_0}f_1^{j_1}\cdots.$$
\subheading{3. Counting paths}
Suppose we are given nonnegative
integers $r$, $k$, and $n$ and a subset $S$ of the set
$\{1,0,-1,-2,\cdots\}$. We call the elements of $S$ {\it steps\/}. We want to
count sequences
$(s_1,s_2,\ldots, s_n)$ of elements of $S$ such that every partial sum
$r+s_1+s_2+\cdots+s_i$ is positive and $r+s_1+s_2+\cdots+s_n=k$. We call such a
sequence of steps a {\it good path of length $n$ from $r$ to $k$\/}. The ballot problem
is equivalent to the case $S=\{1,-1\}$, with $r=1$, and the other problems discussed in
Section 1 are all equivalent to specializations of the case $S=\{1, -p\}$ for various
values of $p$, $r$, and $k$.
It is convenient to consider a somewhat more general problem: We take as our set of
steps the entire set $\{1,0,-1,-2,\cdots\}$, but we assign to each path
$(s_1,s_2,\ldots, s_n)$ the weight $f_{-s_1}f_{-s_2}\cdots f_{-s_n}$, where $f_0$,
$f_1$, $f_2$,\dots are indeterminates and (to make all our formulas simpler) $f_{-1}=1$. First
we note that the weight of a path determines the number of steps, so taking $f_{-1}=1$ does not
lose any information.
\proclaim{Lemma 1} A path from $r$ to $k$ with weight $f_0^{j_0}f_1^{j_1}\cdots$ has
$k-r+j_1+2j_2+\cdots$ steps equal to 1, and length $k-r+j_0+2j_1+\cdots$.
\endproclaim
\demo{Proof} Let $j_{-1}$ be the number of steps equal to 1. Since the path is from $r$ to $k$,
we have $r+j_{-1}-0j_0-1j_1-2j_2-\cdots=k$, and the first assertion follows. Then the length of
the path is $j_{-1}+j_1+j_2+\cdots=k-r+j_0+2j_1+\cdots$.
\enddemo
We now fix $r$ throughout the following discussion. Let $G(n,k)$ be the sum of the
weights of all good paths of length $n$ from $r$ to
$k$. Thus the coefficient of $f_0^{j_0}f_1^{j_1}\cdots$ in $G(n,k)$ is the number of good
paths of length $n$ from $r$ to $k$ with $j_0$ steps equal to 0, $j_1$ steps equal to $-1$,
and so on.
The following is clear:
\proclaim{Lemma 2}
\roster
\item"{(i)}" $G(n,0)=0$ for all $n$.
\item"{(ii)}" $G(0,p)=1$ and $G(0,k)=0$ for $k\ne p$.
\item"{(iii)}" For $n>0$, $G(n,k)=\sum_{i=-1}^\infty f_iG(n-1,k+i)$.
\endroster
Moreover, $G(n,k)$ is uniquely determined by conditions (i)--(iii).
\endproclaim
Now let us define
$$G_k=\sum_{n=0}^\infty G(n,k).$$
By Lemma 1, we can recover $G(n,k)$ from $G_k$ as the sum of all terms in $G_k$ in
$f_0^{j_0}f_1^{j_1}\cdots$, where
$k-r+j_0+2j_1+\cdots=n.$
Now let $f(t)$, as in Section 2, be $$f(t)=t+f_0+{f_1\over t}+{f_2\over t^2}+\cdots.$$
\proclaim{Lemma 3}Let $N(t)$ be a Laurent series in $t$
such that
\roster
\item"(a)" $N(t)=t^r+\hbox{negative powers of $t$}$
\item"(b)" $[t^0]{N(t)/ \bigl(1-f(t)\bigr) }=0.$
\endroster
Then for $k>0$, $G_k=[t^k] N(t)/ \bigl(1-f(t)\bigr)$.
\endproclaim
\demo{Proof}
\def\gg{\tilde g}
Suppose that the hypotheses of the lemma are satisfied. For $k\ge0$, let
$$g_k=[t^k] {N(t)\over 1-f(t)}$$
and for each integer $n$, let $g(n,k)$ be the sum of all terms in $g_k$ in
$f_0^{j_0}f_1^{j_1}\cdots$, where
$$k-r+j_0+2j_1+\cdots=n.\tagg G$$
By Lemma 2, it suffices to show
\roster
\item"{(i)}" $g(n,0)=0$ for all $n$.
\item"{(ii)}" $g(0,r)=1$ and $g(0,k)=0$ for $k\ne r$.
\item"{(iii)}" For $n>0$, $g(n,k)=\sum_{i=-1}^\infty f_i g(n-1,k+i)$.
\endroster
First note that (i) follows immediately from (b). By the definition of $g_k$, we have
$${N(t)\over 1-f(t)}=\sum_{k=1}^\infty g_kt^k +t^{-1}R(t),$$
where $R(t)$ is a power series in $t^{-1}$. Multiplying both sides by $1-f(t)$ we get
$$N(t)=\bigl(1-f(t)\bigr)\sum_{k=1}^\infty g_kt^k +S(t),$$
where $S(t)= \bigl(1-f(t)\bigr)t^{-1}R(t)$ is a power series in $t^{-1}$. Equating coefficients
of $t^k$ for $k>0$ on both sides and using (a), we obtain
$$g_k-\sum_{i=-1}^\infty f_i g_{k+i}=
\cases 1,&\text{if $k=r$}\\ 0,&\text{if $k\ne r$.}\endcases \tagg rec1$$
Extracting the terms in $f_0^{j_0}f_1^{j_1}\cdots$, where
$k-r+j_0+2j_1+\cdots=n$, we obtain
$$g(n,k) -\sum_{i=-1}^\infty f_i g(n-1,k+i) =
\cases 1,&\text{if $k=r$ and $n=0$}\\ 0,&\text{otherwise,}\endcases\tagg rec2$$
since the nonzero case of \(rec1) contributes to \(rec2) only when $k=r$ and
$j_0=j_1=\cdots=0$. This proves (iii). Finally, (ii) will follow from the $n=0$ case of \(rec2)
once we show that $g(-1,k)=0$ for all $k$. We show in fact that
$g(n,k)=0$ for all $n<0$: It is clear from \(G) that $g(n,k)=0$ for $n<-r$. It then follows from
\(rec2) by induction on $n$ that $g(n,k)=0$ for all negative $n$. Thus (ii) holds.
\enddemo
\proclaim{Theorem 1} $G_k$ is the coefficient of $t^k$ in
$${t\over r} {d\ \over dt}F_r(f)\big/( 1-f),$$
where $F_r(u)$ is the $r$th Faber polynomial of $f$.
\endproclaim
\demo{Proof} It follows from the definition of Faber polynomials that
$${t\over r}{d\ \over dt}F_r(f)=t^r+\text {negative powers of t}.$$
In view of the lemma, it is sufficient to show that
$${d\ \over dt}F_r(f)\big/ (1-f),$$
is the derivative of some Laurent series in $t$, since this will imply that it has no term in
$t^{-1}$.
Suppose that $F_r(u)=\sum_{i=0}^r c_i u^i$. Then
$${{d\ \over dt}F_r(f)\big/ (1-f)}=\sum_{i=1}^r ic_i f^{i-1}f'\sum_{j=0}^\infty f^j
=\sum_{i=1}^r\sum_{j=0}^\infty ic_i f^{i+j-1}f'.$$
But $f^{i+j-1}f'={d\ \over dt}f^{i+j}/(i+j),$ so
$${{d\ \over dt}F_r(f)\big/( 1-f)}={d\ \over dt}\sum_{i=1}^r\sum_{j=0}^\infty {ic_i\over
i+j}f^{i+j}.$$
\enddemo
\subheading{4. A positivity result}
Let $N_r={t\over r} {d\ \over dt}F_r(f)$ be the numerator in Theorem 1. We know that
$N_r=t^r-M_r$, where $M_r$ contains only negative powers of $t$.
\proclaim{Theorem 2} The coefficients of $M_r$, as a power series in $t^{-1}, f_0, f_1,\ldots$
are nonnegative integers.
\endproclaim
\demo{Proof} By setting $u=f(t)$ in Schiffer's formula \(6), and then
differentiating with respect to $t$, we obtain
$${tf'(t)\over f(v) -f(t)}=\sum_{r=1}^\infty N_r v^{-r}.\tagg N$$
Thus
$$\align\sum_{r=1}^\infty M_r v^{-r}&=\sum_{r=1}^\infty \left[\left(t\over v\right)^r - N_r
v^{-r}\right]\\
&={t\over v-t}-{tf'(t)\over f(v) -f(t)}\\
&=t{v-t\over f(v)-f(t)}\left[{f(v)-f(t)\over (v-t)^2} -{f'(t)\over v-t}\right].
\tag\eq {diff}\endalign
$$
We shall show that the last two factors in \(diff) have positive coefficients when expanded as
power series in $v^{-1}$ and $t^{-1}$. First, we have
$${f(v) -f(t)\over v-t}=\sum_{i=-1}^\infty f_i\left(v^{-i}-t^{-i}\over v-t\right)
=1-\sum_{i=1}^\infty f_i\left({1\over vt^i}+{1\over v^2t^{i-1}}+\cdots +{1\over
v^it}\right).$$ Thus ${(v-t)/ \bigl(f(v)-f(t)\bigr)}$ has nonnegative coefficients.
Next, we have
$$
{f(v)-f(t)\over (v-t)^2} -{f'(t)\over v-t}=
\sum_{i=-1}^\infty f_i\left( {v^{-i}-t^{-i}\over (v-t)^2} + {it^{-i-1}\over v-t}\right).
\tagg f1$$
The coefficient of $f_i$ in \(f1) is zero for $i=-1$ and $i=0$.
It is easily verified (by multiplying both sides by $(v-t)^2$, for example) that
for $i\ge1$,
$${v^{-i}-t^{-i}\over (v-t)^2} +{it^{-i-1}\over v-t}
= \sum_{j=1}^i {j\over v^{i-j+1}t^{j+1}},$$
and thus it follows that the coefficients of \(f1) are nonnegative. This completes the proof of
Theorem 2.
\enddemo
\subheading{5. Examples}
Let us now return to the problem discussed in the first section: given positive integers $r$ and
$p$, count paths in the plane with steps $(1,0)$ and $(0,1)$, from $(r,0)$ to $(m,n)$, where
$m>pn$, that never touch the line $x=py$. (Note that any starting point
below the line $x=py$ would give an equivalent problem.) We can convert this problem to
an instance of the problem introduced in section 3 by representing a horizontal step by a
step equal to 1 and a vertical step by a step equal to
$-p$. The transformed path will then go from $r$ to $k$, where
$k=m-pn$. The solution to the transformed problem is then obtained by setting all the $f_i$ to 0
except for $f_p$ in the general solution given in Theorem 1, where the weight of the transformed
path is $f_p^n$. Explicitly, the required number is the coefficient of $t^{m-pn}f_p^n$ in
$${t\over r} {d\ \over dt}F_r(t+f_p/t^p)\big/( 1-t-f_p/t^p),\tagg e13$$
where the Faber polynomials $F_r(u)$ are given from \(7) by
$$\align
\sum_{r=1}^\infty F_r(u) {w^r\over r}&=-\log ({1+f_pw^{p+1}-uw})\\
&=\sum_{j=1}^\infty (uw-f_pw^{p+1})^j/j\\
&=\sum_{j=1}^\infty \sum_{i=0}^j {(-1)^i\over j}{j\choose i}(f_p
w^{p+1)^i}(uw)^{j-i}\\
&=\sum_{j=1}^\infty \sum_{i=0}^j {(-1)^i\over j}{j\choose i}f_p^i
w^{pi+j}u^{j-i}.
\endalign
$$
Setting $j=r-pi$ and equating coefficients of $w^r$, we obtain
$${F_r(u)\over r} = \sum_{i\le r/(p+1)}{(-1)^i\over r-pi}{r-pi\choose i}f_p^i
u^{r-(p+1)i},$$
and thus the numerator in \(e13) is
$$\align{t\over r}F_r'(&t+f_p/t^p) (1-pf_p/t^{p+1})\\
&=(t-pf_p/t^p)\sum_{i\le r/(p+1)}(-1)^i {r-(p+1)i\over r-pi}{r-pi\choose i}f_p^i
(t+f_p/t^p)^{r-(p+1)i -1}\\
&=(t-pf_p/t^p)\sum_{i< r/(p+1)}(-1)^i {r-pi-1\choose i}f_p^i
(t+f_p/t^p)^{r-(p+1)i -1}\tag\eq{e14}\endalign
$$
To recover a generating function in $x$ and $y$, as in section 1, we substitute $x$ for $t$ and
$x^py$ for $f_p$. Then \(e13) and \(e14) give as the redundant generating function
for our problem
$${x-py\over 1-x-y}\sum_{i < r/(p+1)}(-1)^i {r-pi-1\choose i}(x^py)^i
(x+y)^{r-(p+1)i -1}.\tagg e15$$
For example, if we take $p=2$ and $r=3$, \(e15) gives
$${x-2y\over 1-x-y}(x+y)^2={x^3-3xy^2-2y^3\over 1-x-y},$$
as we obtained in \(4).
Now let \(e15) equal $\N_r/(1-x-y)$ and let $\N_r=x^r-\M_r$. Then $\N_r$ and
$\M_r$ can be obtained from $N_r$ and $M_r$ as defined in section 4 by the
appropriate substitution. Since it is clear from \(e15) that $\N_r$ and $\M_r$ are
homogeneous of degree $r$ in $x$ and $y$, they can be obtained from the generating
functions $\sum_r \N_r$ and $\sum_r \M_r$.
The formulas in the proof of Theorem 2 give
$$\sum_{r=1}^\infty \N_r = {x-py\over 1-x-y+x^py}\tagg N1$$
and
$$\sum_{r=1}^\infty \M_r = y{p+(p-1)x+(p-2)x^2+\cdots +x^{p-1}
\over 1-y(1+x+x^2+\cdots +x^{p-1})}.\tagg M$$
For $p=1$, \(M) gives $\M_r=y^r$, so that $\N_r=x^r -y^r$, as we observed in
section 1. We can also obtain a simple explicit formula when $p=2$. In this case,
\(M) gives
$$\sum_{r=1}^\infty \M_r=y{2+x\over 1-y(1+x)}=\sum_{i,j=0}^\infty
x^i y^{j+1}\left[ {i\choose j} + {i+1\choose j}\right].$$
Extracting the terms that are homogeneous of degree $r$ and simplifying, we obtain
$$\M_r=\sum_{i=0}^{\lfloor r/2\rfloor}{2r-3i\over r-i}{r-i\choose i}x^i y^{r-i}.$$
The method we have described can be used for counting paths in the plane that stay below
the line $x=py$, with arbitrary starting and ending points, and an arbitrary set of
allowed steps subject only to the condition that every step $(i,j)$ satisfies $i-pj\le 1$.
Another method, also using Laurent series, that is not subject to the restriction on steps,
but does not allow an arbitrary starting point, is described in \[gessel].
\Refs
\ref\name brini
\by A. Brini
\paper Higher dimensional recursive matrices and diagonal delta sets of series
\jour J. Combin. Theory Ser. A\vol 36
\yr 1984
\pages 315--331
\endref
\ref \name gessel
\by I. M. Gessel
\paper A factorization for formal Laurent series and lattice path enumeration
\jour J. Combin. Theory Ser. A
\vol 28 \yr 1980 \pages 321--337\endref
\ref\name jab
\by E. Jabotinsky
\paper Representation of functions by matrices. Application to Faber polynomials
\jour Proc. Amer. Math. Soc.
\vol 4
\yr 1953
\pages 546--553
\endref
\ref\name mohanty
\by S. G. Mohanty
\book Lattice Path Counting and Applications
\publ Academic Press
\publaddr New York
\yr 1979
\endref
\ref\name ree
\by S. Ree
\book Enumeration of Lattice Paths and $P$-Partitions
\bookinfo Ph. D. Thesis, Brandeis University
\yr 1994
\endref
\ref\name schiffer
\by M. Schiffer
\paper Faber polynomials in the theory of univalent functions
\jour Bull. Amer. Math. Soc.
\vol 54 \yr 1948 \pages 503--517
\endref
\ref\name schur
\by I. Schur
\paper On Faber polynomials
\jour Amer. J. Math.
\vol 67\yr 1945
\pages 33--41
\endref
\endRefs
\bye