\documentclass[12pt,reqno]{amsart}%{article}
%\usepackage{a4ams}
\usepackage{amsfonts,amsmath,amssymb}
\usepackage{graphicx}
\usepackage{psfrag}
\usepackage{pstricks}
\usepackage{pst-tree}

\allowdisplaybreaks
\topmargin 0 pt                        
\textheight 46\baselineskip     
\advance\textheight by \topskip

\setlength{\textwidth}{155mm}         
\setlength{\oddsidemargin}{5.6mm}     
\setlength{\evensidemargin}{5.6mm}   

\def\al{\alpha}
\def\a{\alpha}
\def\b{\beta}

\newtheorem{theorem}{Theorem}

\newtheorem{lemma}{Lemma}

\newtheorem{prop}{Proposition}
\numberwithin{equation}{section}

\def\P{{\Bbb {P}}}
\let\ttt\tt
\def\t{\vartheta}\def\tt{\bar{\vartheta}}
\let\vvv\v
\def\v{\textsf{value}}
\def\mm{\widehat m}
\def\ma{\widehat a}
\def\Card{\mathit{Card}}
\def\ZZ{\mathbb{Z}}



% other useful commands
\newcommand{\Leaf}{\qedsymbol}

\title
{The kernel method:\\
A collection of examples}


\author{Helmut Prodinger}
\address{Helmut Prodinger\\
The John Knopfmacher Centre for Applicable Analysis and Number Theory\\
 School of Mathematics\\
University of the Witwatersrand, Private Bag~3,
Wits, 2050 Johannesburg, South Africa}
\email{helmut@maths.wits.ac.za}


\date{}
%\subjclass{Primary: ; Secondary:}
\keywords{Kernel method, generating function, random walk, bin packing, 
toilet paper problem, card guessing, binary tree, functional equation,
Banach's match box problem.}

\begin{document}
\begin{abstract}
The kernel method has recently  become quite popular. Roughy speaking, 
in certain cases one obtains for a multivariate generating function
a functional equation. For certain couplings of the variables, the denominator
vanishes, but since one knows a priori that a power series expansion exists, 
one concludes that the numerator must also vanish. This is sufficient to 
compute the generating function, at least at special values, and subsequently
in general.

We present a collection of examples where this technique works. All of them
have a certain random walk flavour.
\end{abstract}


\maketitle

%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 50 \rms (2004), Article~B50f\hfill}
\def\thepage{}

\begin{center}
\parbox{12cm}{
\begin{small}
\textsl{I am very glad of having been an invited speaker at SLC50. I presented
many examples, related to my own work. I had prepared some examples about
the kernel method, but no time to talk about them. Since this subject is
\textit{dear to my heart,} I extended that section and present these examples here.}
\end{small}
}
\end{center}

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering


\section{Introduction}


In my view, the \emph{kernel method} originated in Knuth's book
\cite{Knuth97}, where it was presented as an innocent exercise~2.2.1.-4.
Later, it was turned into a method in \cite{Petkovsek98, BuPe00, BaBoDeFlGaGo02}. 
It was probably rediscovered independently by many people; I recommend 
to follow the references in \cite{BaBoDeFlGaGo02}.

I feel that I cannot do anything better as an introduction than to
reproduce Knuth's original exercise. 
One starts at the origin, and can advance from $(n,i)$ to both
$(n+1,i\pm 1)$, except in the case when $i=0$, when one can only go to
$(n+1,1)$. In this way, one models nonnegative lattice paths (or random walks).
One wants to know how many paths lead from the origin to $(n,0)$, and,
more generally, to $(n,i)$. Clearly, this is a very classical subject, 
but the derivation that Knuth presented is the subject of this note.
One uses generating functions $f_i(z)$, describing walks leading to
 $(n,i)$; the coefficient of $z^n$, denoted by $[z^n]f_i(z)$,
is the number of walks from the origin to 
 $(n,i)$. The following recursions are immediate:
\begin{align*}
f_i(z)&=zf_{i-1}(z)+zf_{i+1}(z), \qquad i\geq1,\\
f_0(z)&=1+zf_1(z).
\end{align*}
Now one introduces $F(z,x)=\sum_{n\ge0}f_n(z)x^n$, multiplies the
recursion by $x^i$ and sums:
\begin{align*}
F(z,x)-f_0(z)=zxF(z,x)+\frac zx\big[F(z,x)-f_0(z)-xf_1(z)\big],
\end{align*}
or		
\begin{align*}
F(z,x)=zxF(z,x)+\frac zx\big[F(z,x)-F(z,0)\big]+1,
\end{align*}
whence
\begin{equation*}
F(z,x)=\frac{ zF(z,0)-x}{zx^2-x+z}.
\end{equation*}
Plugging in $x=0$ leads to nothing, but the denominator factors as
$z(x-r_1(z))(x-r_2(z))$, with
\begin{equation*}
r_{1,2}(z)=\frac{1\mp\sqrt{1-4z^2}}{2z}.
\end{equation*}
Note that $x-r_1(z)\sim x-z$ as $x,z\to0$. Therefore
the factor $1/(x-r_1(z))$ has no power series expansion around $(0,0)$, 
but $F(z,x)$ \emph{has,} so this ``bad'' factor must actually disappear, i.e.,
$(x-r_1(z))$ must be a factor of the \emph{numerator} as well, which leads
to the equation $zF(z,0)=r_1(z)$, from which $F(z,0)$ can be computed.
Consequently, $F(z,x)$ is then also explicitly computed, and the factor
$(x-r_1(z))$ can be cancelled from both, numerator and denominator.

 From this, one finds for instance that $[z^{2n}]F(z,0)=\frac1{n+1}\binom{2n}n$,
a well-known \emph{Catalan number,} and similar expressions for 
$[z^nx^i]F(z,x)$, for $n\equiv i\bmod2$. A technique to read off coefficients
like this will be described in subsequent sections for numerous examples.
\medskip


%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL HELMUT PRODINGER}{\SMALL THE KERNEL METHOD: A COLLECTION
OF EXAMPLES}
%
%


Now since I find this method fascinating, simple, and extremely useful, 
I tried during the last few years to collect several examples where it works. 
In the present paper, which can thus be seen partially as a tutorial, I
present them. It is my ambitious wish
that it might be useful for seminars and other courses.
I rederive some known results with the kernel method but also try to 
work out a few new ones.

\medskip

The first one (Section~\ref{knoedel_section}) considers random
walks originating from a bin packing problem. It was originally
considered by Kn\"odel\footnote{The austrian mathematician
Walter Kn\"odel received his Ph.~D. under E.~Hlawka in Vienna. He
eventually became a professor in Stuttgart, Germany.}.
There are bins of size~1 and randomly arriving objects of size
$\frac id$, for $i=1,\dots,d-1$, and an online strategy to fill the bins
as well as possible. The problem can be described by \emph{states},
coding the partially filled bins at a specific moment. We treat the instances
$d=3,4$. Higher values of $d$ lead to very complicated situations and
I am not aware of any results in these cases.

The next one (Section~\ref{toilet_section}) looks again at the
\emph{toilet paper problem}, a popular subject introduced
 by Knuth \cite{Knuth84}.
He considers two rolls of tissues, with $m$ resp. $n$ units, and
random users, who are with probability $p$ \emph{big-choosers} (taking
one unit from the larger roll) resp. with probability $q=1-p$
 \emph{little-choosers} (taking one unit from the smaller roll).
The parameter of interest is the (average) number of units remaining
on the larger roll, when the smaller one became empty.

The following Section~\ref{dani_section} considers walk on the comb, 
a theme studied by D.~Bertacchi\footnote{
Daniela Bertacchi got her Ph.~D. under Wolfgang Woess in Milano;
like me, she is a frequent visitor of the Technical University Graz.}
 in several papers \cite{Bertacchi1, Bertacchi2}. The walk
is on $\ZZ\times \ZZ$, and from $(i,j)$, $j\neq0$, one can reach
$(i,j\pm1)$, both with probability $\frac12$. If $j=0$, however, one can
reach $(i\pm1,0)$, $(i,\pm1)$ all with probability $\frac14$.
One wants generating functions $f_{i,j}(z)$, describing all walks from 
the origin to $(i,j)$. We employ the kernel method to derive the simpler
generating functions $\phi_j(z)$ describing walks from the origin
to $(\ast,j)$, i.~e., ignoring the first coordinate. This means now
a random walk on $\ZZ$, as usual, but with different rules for $0$:
if one is in $0$, one can stay there with probability $\frac12$.

The next two sections deal with subjects that I published already
in \cite{KnPr01b, Prodinger01e}.
To extend this collection of examples, I repeat (parts of) them here.


Section~\ref{cards_section} reviews a card guessing game with a certain
random walk flavour.

Section~\ref{carlitz_section} deals with a functional equation from
a queuing system.

In the short final sections, I first
deal with \emph{Banach's match box problem}, see
\cite{GrKnPa94}. The
relevant recursions
somehow resemble the ones in the card guessing game. Knuth's toilet paper
problem may be seen as an extension of Banach's match box problem, although
only expectations were considered in the toilet paper problem.
Then I show how the generating function of the central binomial coefficients
can be derived with the kernel method.

In my practice \cite{PaPr98}, a
recursion that occurs when one analyzes a certain procedure to generate binary trees 
could readily be   solved with the kernel.  Since there isn't anything 
significantly different from the previous examples, this example won't be included here.
To wet the reader's appetite, here is the recursion:
\begin{equation*}   
g_{n,k}=g_{n-1,k-1}+2g_{n-1,k}+g_{n-1,k+1}+1\qquad\text{for }0\le k\le n 
\end{equation*}
with the assumption that all values $g_{n,k}$
 outside the range $0\le k\le n $  are zero.


The generating functions that will be obtained in this survey
are all rational. This is not a necessity.
For instance, a Kn\"odel problem with $3$ resp. $4$. replaced by $5$ (or even a higher
number) would lead to nonalgebraic functions. 
Then one would probably be in the framework of \emph{multidimensional linear recurrence
relations} as investigated in \cite{BuPe00}. To my knowledge, nobody has considered these
more difficult Kn\"odel problems in detail. 







\section{Kn\"odel walks}\label{knoedel_section}

Kn\"odel \cite{Knoedel83} formulated a simple bin packing model as a random 
walk on a special graph:
\begin{figure}[!h]
$$\hspace*{-3cm}
\cnode[linewidth=1.5pt](-0.5,0){0.3cm}{A}
\nput[labelsep=0]{-90}{A}{%
\uput{0.2cm}[90](-0.05,0.4){\beta}}
\cnode[linewidth=1.5pt](-2,-2){0.3cm}{B}
\nput[labelsep=0]{90}{A}{%
\uput{0.2cm}[-90](-1.5,-2.5){0}}
\cnode[linewidth=1.5pt](1,-2){0.3cm}{C}
\nput[labelsep=0]{90}{A}{%
\uput{0.2cm}[-90](1.5,-2.5){1}}
\cnode[linewidth=1.5pt](4,-2){0.3cm}{D}
\nput[labelsep=0]{90}{A}{%
\uput{0.2cm}[-90](4.5,-2.5){2}}
\pnode(-3.5,-2){E}
\pnode(7,-2){F}
\psset{nodesep=2pt,offset=3pt,arrows=->,arrowsize=3pt 2,arrowlength=2,linewidth=1.5pt}
\ncline{A}{B}
\ncline{B}{A}
\ncline{B}{C}
\ncline{C}{B}
\ncline{A}{C}
\ncline{C}{D}
\ncline{D}{C}
\ncline{E}{B}
\ncline{D}{F}
\ncline{F}{D}
$$
\end{figure}
\vspace*{3cm}

Some aspects of the analysis were treated by Prodinger in a series
of papers \cite{Prodinger85, Prodinger90, Prodinger92}. 
Recently, Drmota \cite{Drmota03} has picked up the subject again.

In the simplest version, there are bins of size 1, and items of
size $\frac13$ resp. $\frac23$ arriving at random. One tries to complete
as many bins as possible with an online strategy, leaving us basically with
a number of bins filled $\frac23$, which we reduce by 1 or augment by 1. 
There is also a special ``state'' $\beta$, representing a bin
filled $\frac13$ (and no bins filled $\frac23$). 


Here, we want to find the bivariate generating function
related to the number of steps taken and the state where the random
walk currently is. From this, one can get the wasted space:
State 0 contributes 0, state $\beta$ contributes $2/3$, and state
$i$ for $i\ge1$ contributes $i/3$.

Random walks in this graph, starting at state 0 will be called
``Kn\"odel walks,'' in honour of their   creator.



Let $f_i(z)$ be the generating function, where $[z^n]f_i(z)$ counts all
Kn\"odel walks starting at $0$ and ending at state $i$ in $n$ steps, for
$i\in\{\beta,0,1,\ldots\}$. We have the following recursions:
\begin{align}
\begin{split}\label{system}
f_i(z)&=zf_{i-1}(z)+zf_{i+1}(z),\qquad\text{for $i\ge2$},\\
f_1(z)&=zf_0(z)+zf_\beta(z)+zf_2(z),\\
f_0(z)&=1+zf_1(z)+zf_\beta(z),\\
f_\beta(z)&=zf_0(z).\\
\end{split}
\end{align}
We introduce the bivariate generating function $F(z,x)=\sum_{i\ge0}f_i(z)x^i$
and get from summing up (\ref{system})
\begin{align*}
F(z,x)&=\sum_{i\ge2}x^izf_{i-1}(z)+\sum_{i\ge2}x^izf_{i+1}(z)\\
&\qquad\qquad +xzf_0(z)+xzf_\beta(z)+xzf_2(z)+1+zf_1(z)+zf_\beta(z)\\
&=xzF(z,x)+\frac zxF(z,x)+1-\frac zxf_0(z)+(1+x)zf_\beta(z)\\
&=xzF(z,x)+\frac zxF(z,x)+1-\Big(\frac zx-(1+x)z^2\Big)F(z,0),\\
\end{align*}
or
\begin{align*}
F(z,x)
&=\frac{z\big(1-x(1+x)z\big)F(z,0)-x}
{x^2z-x+z}=\frac{z\big(1-x(1+x)z\big)F(z,0)-x}
{z(x-r_1(z))(x-r_2(z))},\\
\end{align*}
with 
\begin{equation*}
r_1(z)=\frac{1-\sqrt{1-4z^2}}{2z},\qquad
r_2(z)=\frac{1+\sqrt{1-4z^2}}{2z}.
\end{equation*}
Note that $r_1(z)r_2(z)=1$, which is used frequently.

Now $x-r_1(z)$ must be a factor of the numerator, so we find
\begin{equation*}
z\Big(1-zr_1(z)\big(1+r_1(z)\big)\Big)F(z,0)-r_1(z)=0
\end{equation*}
or
\begin{equation}\label{pet2}
f_0(z)=F(z,0)=\frac{r_1(z)}{z(1+z)\big(1-r_1(z)\big)}.
\end{equation}
Therefore
\begin{equation*}
F(z,x)=\frac{r_1(z)}{z(1+z)\big(1-r_1(z)\big)}\frac{1+xzr_1(z)}{1-xr_1(z)}.
\end{equation*}
From this we get for $i\ge1$
\begin{equation}\label{pet1}
f_i(z)=\frac{r_1^{i+1}(z)}{z\big(1-r_1(z)\big)}.
\end{equation}
We also have
\begin{equation}\label{pet3}
f_\beta(z)=zf_0(z)=\frac{r_1(z)}{(1+z)\big(1-r_1(z)\big)}
\end{equation}
and find as a check that
\begin{equation}\label{pet3a}
f_\beta(z)+\sum_{i\ge0}f_i(z)=\frac1{1-2z},
\end{equation}
as it should.

To extract coefficients%
\footnote{I saw this method for the first time in \cite{BrKnRi72}. It is equivalent
to  Lagrange inversion. For me, it is easier to remember.}, we use Cauchy's integral formula:
\begin{equation*}
[z^n]F(z)=\frac1{2\pi i}\oint\frac{dz}{z^{n+1}}H(z)
\end{equation*}
and the substitution
$z=\dfrac{v}{1+v^2}$, $dz=dv\dfrac{1-v^2}{(1+v^2)^2}$.

For an arbitrary generating function $H(z)$ we have
\begin{equation*}
[z^n]H(z)=[v^n](1-v^2){(1+v^2)}^{n-1}H\big(z(v)\big).
\end{equation*}
And so, applying this to \eqref{pet1},
\begin{align*}
[z^n]f_i(z)&=[v^n](1-v^2){(1+v^2)}^{n-1}\frac{v^{i}(1+v^2)}{1-v}\\
&=[v^{n-i}](1+v){(1+v^2)}^{n}=\binom{n}{\lfloor\frac{n-i}{2}\rfloor}
\end{align*}
and further
\begin{gather*}
[z^{2n}]\sum_{i\ge1}f_i(z)=2\sum_{i\ge1}\binom{2n}{n-i}=2^{2n}-\binom{2n}n,\\
[z^{2n+1}]\sum_{i\ge1}f_i(z)=2\sum_{i\ge0}\binom{2n+1}{n-i}
-\binom{2n+1}{n}=2^{2n+1}-\binom{2n+1}{n}.
\end{gather*}
Hence, using the expressions found in \eqref{pet3} and \eqref{pet3a},
\begin{equation*}
[z^n]\Big(f_0(z)+f_\beta(z)\Big)=[z^{n}](1+z)f_0(z)
=\binom{n}{\lfloor\frac n2\rfloor}.
\end{equation*}
So
\begin{equation*}
[z^n]f_0(z)
=\sum_{k=0}^n\binom{k}{\lfloor\frac k2\rfloor}(-1)^{n-k},
\end{equation*}
or
\begin{gather*}
[z^{2n}]f_0(z)=\sum_{k=0}^{n}\binom{2k}{k}-\sum_{k=0}^{n-1}\binom{2k+1}{k},\\
[z^{2n+1}]f_0(z)=\sum_{k=0}^{n}\binom{2k+1}{k}-\sum_{k=0}^{n}\binom{2k}{k}
.\\
\end{gather*}




These formul\ae{} evaluate $[z^n]f_k(z)$ for any $n$ and any state $k$.
In other words, they enumerate the number of walks of length $n$ starting at
the origin and ending in state $k$. Since the formul{\ae} are reasonably simple,
one can possibly derive them in a more combinatorial fashion; I leave this as
an interesting challenge for those who want to do it \emph{without the kernel method}.


\subsection*{Kn\"odel walks related to $\mathbf{\frac14}$, $\mathbf{\frac24}$,
 $\mathbf{\frac34}$ }

The next model is related again to bins of size 1 and random items of
size $\frac i4$, for $i=1,2,3$. This time one finds two infinite sequences
of states, representing $i$ bins filled $\frac34$ resp.
representing $i$ bins filled $\frac34$ and one bin filled $\frac12$.

%

Here is the  corresponding graph. The first layer represents $i$ bins, filled $\frac34$
each, the second layer similar, but with one additional bin filled $\frac12$, and the
special state just one bin filled $\frac14$.
\vspace*{2cm}
\begin{figure}[!h]
$$\hspace*{-5cm}
\cnode[linewidth=1.5pt](0,0){0.3cm}{C0}
\nput[labelsep=0]{90}{C0}{%
\uput{0.2cm}[-90](0.4,-0.4){0}}
\cnode[linewidth=1.5pt](2,0){0.3cm}{C2}
\nput[labelsep=0]{90}{C0}{%
\uput{0.2cm}[-90](2.4,-0.4){1}}
\cnode[linewidth=1.5pt](4,0){0.3cm}{C4}
\nput[labelsep=0]{90}{C0}{%
\uput{0.2cm}[-90](4.4,-0.4){2}}
\cnode[linewidth=1.5pt](6,0){0.3cm}{C6}
\nput[labelsep=0]{90}{C0}{%
\uput{0.2cm}[-90](6.4,-0.4){3}}
\cnode[linewidth=1.5pt](0,-2){0.3cm}{D0}
\nput[labelsep=0]{90}{D0}{%
\uput{0.2cm}[-90](0,-0.5){0,\frac12}}
\cnode[linewidth=1.5pt](2,-2){0.3cm}{D2}
\nput[labelsep=0]{90}{D2}{%
\uput{0.2cm}[-90](0,-0.5){1,\frac12}}
\cnode[linewidth=1.5pt](4,-2){0.3cm}{D4}
\nput[labelsep=0]{90}{D4}{%
\uput{0.2cm}[-90](0,-0.5){2,\frac12}}
\cnode[linewidth=1.5pt](6,-2){0.3cm}{D6}
\nput[labelsep=0]{90}{D6}{%
\uput{0.2cm}[-90](0,-0.5){3,\frac12}}
\cnode[linewidth=1.5pt](-3,2){0.3cm}{beta}
\nput[labelsep=0]{90}{C0}{%
\uput{0.2cm}[-90](-3.4,1.6){\beta}}
\pnode(-2.1,2){betaa}
\pnode(-0.1,-2){D00}
\pnode(8,0){C8}
\pnode(8,-2){D8}
\pnode(-1.3,-0.3){fake}
\psset{nodesep=2pt,offset=3pt,arrows=->,arrowsize=3pt 2,arrowlength=2,linewidth=1.5pt}
\ncline{C0}{C2}
\psset{nodesep=2pt,offset=-2pt,arrows=->,arrowsize=3pt 2,arrowlength=2,linewidth=1.5pt}
\ncline{fake}{C0}
\psset{nodesep=2pt,offset=3pt,arrows=->,arrowsize=3pt 2,arrowlength=2,linewidth=1.5pt}
\ncline{C2}{C0}
\ncline{C2}{C4}
\ncline{C4}{C2}
\ncline{C4}{C6}
\ncline{C6}{C4}
\ncline{C6}{C8}
\ncline{C8}{C6}
\ncline{D0}{D2}
\ncline{D2}{D0}
\ncline{D2}{D4}
\ncline{D4}{D2}
\ncline{D4}{D6}
\ncline{D6}{D4}
\ncline{D6}{D8}
\ncline{D8}{D6}
\ncline{C0}{D0}
\ncline{D0}{C0}
\ncline{C2}{D2}
\ncline{D2}{C2}
\ncline{C4}{D4}
\ncline{D4}{C4}
\ncline{C6}{D6}
\ncline{D6}{C6}
\psset{nodesep=2pt,offset=-1pt,arrows=->,arrowsize=3pt 2,arrowlength=2,linewidth=1.5pt}
\ncline{D0}{C2}
\psset{nodesep=2pt,offset=3pt,arrows=->,arrowsize=3pt 2,arrowlength=2,linewidth=1.5pt}
\ncline{C0}{beta}
\ncline{beta}{C0}
\ncline{beta}{C2}
\psset{nodesep=3pt,offset=-4pt,arrows=->,arrowsize=3pt 2,arrowlength=2,linewidth=1.5pt}
\ncline{beta}{D0}
$$
\end{figure}
\vspace*{3cm}


Now we move to generating functions:
  $f_i(z)$ represents $i$ bins, $\frac34$ full, and
 $g_i(z)$ represents $i$ bins, $\frac34$ full and one bin filled
$\frac12$. The special $h(z)$
 represents one bin, $\frac14$ full.

The equations are
\begin{align*}
f_0(z)&=1+zf_1(z)+zg_0(z)+zh(z),\\
g_0(z)&=zf_0(z)+zg_1(z)+zh(z),\\
f_1(z)&=zf_0(z)+zf_2(z)+zg_0(z)+zg_1(z)+zh(z),\\
f_i(z)&=zf_{i-1}(z)+zf_{i+1}(z)+zg_i(z),\qquad i\ge2,\\
g_i(z)&=zg_{i-1}(z)+zg_{i+1}(z)+zf_i(z),\qquad i\ge1,\\
h(z)&=zf_0(z).
\end{align*}
With $F(z,x)=\sum_{i\ge0}f_i(z)x^i$, $G(z,x)=\sum_{i\ge0}g_i(z)x^i$,
we find
\begin{align*}
F(z,x)&=1+zxF(z,x)+\frac zxF(z,x)-\frac zxf_0(z)+zG(z,x)+zxg_0(z)+z(1+x)h(z),\\
G(z,x)&=zF(z,x)+ zxG(z,x)+\frac zxG(z,x)-\frac zxg_0(z)+zh(z).\\
\end{align*}
Set $A(z,x)=F(z,x)+G(z,x)$:
\begin{align*}
A(z,x)=1&+zxA(z,x)+\frac zxA(z,x)-\frac zx(f_0(z)+g_0(z))+zA(z,x)\\*&
+zxg_0(z)+z^2(2+x)f_0(z),\\
\end{align*}
thus
\begin{align*}
A(z,x)&=\frac{1-\frac zx(f_0(z)+g_0(z))+zxg_0(z)+z^2(2+x)f_0(z)}{1-zx-\frac zx-z}.\\
\end{align*}
%
Define
\begin{equation*}
r_{1,2}(z)=\frac{1-z\mp\sqrt{1-2z-3z^2}}{2z}.
\end{equation*}
The numerator must disappear for $x=r_1(z)$, which leads to
\begin{align*}
1-\frac z{r_1(z)}\big(f_0(z)+g_0(z)\big)+zr_1(z)g_0(z)+z^2\big(2+r_1(z)\big)f_0(z)=0.
\end{align*}
Similarly, set $B(z,x)=F(z,x)-G(z,x)$:
\begin{align*}
B(z,x)=1&+zxB(z,x)+\frac zxB(z,x)-\frac zx(f_0(z)-g_0(z))-zB(z,x)\\
&+zxg_0(z)+z^2xf_0(z),
\end{align*}
thus
\begin{align*}
B(z,x)&=\frac{1-\frac zx(f_0(z)-g_0(z))+zxg_0(z)+z^2xf_0(z)}
{1-zx-\frac zx+z}.
\end{align*}
The numerator must disappear for $x=-r_1(-z)$, thus
\begin{align*}
1+\frac z{r_1(-z)}(f_0(z)-g_0(z))-zr_1(-z)g_0(z)-z^2r_1(-z)f_0(z)
=0.
\end{align*}
Now we have two equations and can compute the functions $f_0(z)$ and
$g_0(z)$:
\begin{align*}
f_0(z)&=\frac{
{ r_1}(z)-{ r_1}(-z)+{ r_1^2}(z){ r_1}(-z)
+{ r_1}(z){ r_1^2}(-z)
}
{z\big (2-2z{ r_1}(z)-(1+z){ r_1^2}(z)+ 
(1-z){ r_1^2}(-z)-2z{r_1}(z){ r_1^2}(-z)
\big )}\\
&=1+3{z}^{2}+3{z}^{3}+15{z}^{4}+28{z}^{5}+101{z}^{6}+230{z}
^{7}+763{z}^{8}+1882{z}^{9}+\cdots,\\
g_0(z)&=\frac{
{r_1}(z)+{r_1}(-z)-2z{r_1}(z){r_1}(-z)-z{r_1^2}(z){r_1}(-z)
-z{r_1}(z){r_1^2}(-z)}
{z\big (2-2z{ r_1}(z)-(1+z){ r_1^2}(z)+ 
(1-z){ r_1^2}(-z)-2z{r_1}(z){ r_1^2}(-z)
\big )}\\
&=z+{z}^{2}+5{z}^{3}+9{z}^{4}+33{z}^{5}+73{z}^{6}+245{z}^{7}+
593{z}^{8}+1921{z}^{9}+\cdots.
\end{align*}

The expressions for $F(z,x)$ and $G(z,x)$, although known
in principle, become quite messy, so we don't give them here.
However, we want to compute the average wasted space after
$n$ steps. For this, we need
\begin{equation*}
\sum_{i\ge0}\frac i4f_i(z)+\sum_{i\ge0}\Big(\frac i4+\frac12\Big)g_i(z)+
\frac34h(z),
\end{equation*}
which we get as
\begin{equation*}
\frac14\frac{\partial F}{\partial x}(z,1)+
\frac14\frac{\partial G}{\partial x}(z,1)+
\frac12G(z,1)+\frac34zf_0(z).
\end{equation*}
Computer algebra can generate an expression equivalent to this
which is not nice, but we give its local expansion around the dominant
singularity, $z=\frac13$:
\begin{align*}
\frac{\sqrt3}{12}{(1-3z)}^{-3/2}+\Big(\frac18+\frac{\sqrt3}{24}\Big){(1-3z)}^{-1}
+\cdots,
\end{align*}
whence we get for the average wasted $W_n$ space using singularity analysis of
generating functions \cite{FlOd90}
\begin{equation*}
W_n=\frac{\sqrt3}{6}\sqrt{\frac n\pi}+\frac18+\frac{\sqrt3}{24}+O(n^{-1/2}),
\end{equation*}
with more terms being available if necessary. (There is also a singularity
at $z=-\frac13$, but it contributes only terms of order $n^{-1/2}$.)



\section{The toilet paper problem}\label{toilet_section}

Following the description in the introduction, let $m$ be the number of
units on the larger, and $n$ on the smaller roll; $M_{m,n}$ is the
expected number of units left on the larger roll, when the smaller one
becomes empty.


The recursions are 
\begin{align*} M_{m,0}&=m,\\ M_{m,m}&=M_{m,m-1},\qquad
m\ge1 ,\\ M_{m,n}&=pM_{m-1,n}+qM_{m,n-1},\qquad m>n>0.
 \end{align*}
Define 
\begin{align*} F_0(z)=\sum_{m\ge0}M_{m,m}z^m,\qquad
F_1(z)=\sum_{m\ge1}M_{m,m-1}z^m.
\end{align*} 
Note that
\begin{equation*}
F_0(z)=\sum_{m\ge0}M_{m,m}z^m= \sum_{m\ge1}M_{m,m-1}z^m=F_1(z).
\end{equation*}
 Define 
\begin{equation*} 
F(z,x)=\sum_{m\ge n\ge0}M_{m,n}z^mx^{m-n}. 
\end{equation*} 
Then, by summing up,
\begin{align*} F(z,x)&=\sum_{m>
n>0}M_{m,n}z^mx^{m-n}+\sum_{m>0}M_{m,0}z^mx^{m}+ \sum_{m\ge 0}M_{m,m}z^m\\
&=\sum_{m> n>0}[pM_{m-1,n}+qM_{m,n-1}]z^mx^{m-n}+\frac{zx}{(1-zx)^2}
+F_0(z)\\ 
&=pzx\sum_{m-1\ge n>0}M_{m-1,n}z^{m-1}x^{(m-1)-n}+ \frac
qx\sum_{m> n>0}M_{m,n-1}z^mx^{m-(n-1)}\\
&\hspace*{5cm}+
\frac{zx}{(1-zx)^2} +F_0(z)\\ 
&=pzx\Big[F(z,x)-\sum_{m\ge0}M_{m,0}z^mx^m\Big]+
\frac qx\kern-2pt
\sum_{m>> n\ge0}\kern-3pt
M_{m,n}z^mx^{m-n}+ \frac{zx}{(1-zx)^2} +F_0(z)\\
&=pzx\Big[F(z,x)-\frac{zx}{(1-zx)^2}\Big]+ \frac qx\Big[F(z,x)- x\sum_{
n\ge0}M_{n+1,n}z^{n+1}- \sum_{
n\ge0}M_{n,n}z^{n}\Big]\\&\hspace*{5cm}+\frac{zx}{(1-zx)^2}+F_0(z)\\
&=pzxF(z,x)+ \frac qx\Big[F(z,x)- xF_1(z)-
F_1(z)\Big]+\frac{zx(1-pzx)}{(1-zx)^2}+F_1(z).
\end{align*} 
(Here, we used the ad hoc notation $a>>b:\Leftrightarrow a-b\ge2$.)
Solving,
\begin{align*}
F(z,x)&=\frac{\frac{zx(1-pzx)}{(1-zx)^2}+F_1(z)[1-q-q/x]}{1-pzx-q/x}=
\frac{F_1(z)[q-px]-\frac{zx^2(1-pzx)}{(1-zx)^2}}{pzx^2-x+q}\\*
&=\frac{F_1(z)[q-px]-\frac{zx^2(1-pzx)}{(1-zx)^2}}{pz(x-r_1(z))(x-r_2(z))},
\end{align*} 
with 
\begin{equation*}
r_{1,2}(z)=\frac{1\mp\sqrt{1-4pqz}}{2pz}. 
\end{equation*} 
Therefore, for
$x=r_1(z)$, the numerator must vanish, yielding 
\begin{equation*}
F_1(z)[q-pr_1(z)]-\frac{zr_1^2(z)(1-pzr_1(z))}{(1-zr_1(z))^2}=0,
\end{equation*} 
or 
\begin{equation*}
F_1(z)=\frac{zr_1^2(z)(1-pzr_1(z))}{(q-pr_1(z))(1-zr_1(z))^2}= \frac
z{q(1-z)^2}\big(q-C(pqz)\big), 
\end{equation*} 
with 
\begin{equation*}
C(z)=\frac{1-\sqrt{1-4z}}{2}. 
\end{equation*}
Note that $r_1(z)=\frac{C(pqz)}{pz}$ and that $1/r_2(z)=r_1(z)pz/q$.

The expression for $F(z,x)$ is ugly, but we can extend Knuth's 
asymptotic analysis to $M_{m,m-n}$ for $m\to\infty$ and fixed $n$;
the instance $n=0$ was given in \cite{Knuth84}.

For $q<p$, Knuth has shown that the local expansion of $C(pqz)$ around $z=1$
starts like 
\begin{equation*}
q+\tfrac{pq}{p-q}(z-1)+\tfrac{(pq)^2}{(p-q)^3	}(z-1)^2+\cdots. \end{equation*} 
Hence the local expansion of $F(z,x)$ around $z=1$
starts like 
\begin{equation*}
\frac1{1-z}\cdot\frac{p}{(2p-1)(1-x)}+\cdots. 
\end{equation*}
 So
$M_{m,m-n}= p/(2p-1)+O(r^m)$, and the $n$ plays no role here. Well, this
is intuitive, the big-choosers dominate, so it does not really make a
difference whether the second roll is slightly smaller. Now let us assume
that $p<q$. Then $F(z,x)$ starts like 
\begin{equation*}
\frac1{(1-z)^2}\cdot \frac{2p-1}{(p-1)(1-x)}+
\frac1{1-z}\bigg[-\frac1{1-x} +{\frac {p}{q (1-x )^{2} }}-{\frac {p(1-p)}{
(2p-1)(q-px)}} \bigg]+\cdots. \end{equation*} 
The coefficient of $z^m$ is
asymptotic to 
\begin{equation*} (m+1)\cdot \frac{1-2p}{(1-p)(1-x)}+
\bigg[-\frac1{1-x} +{\frac {p}{q (1-x )^{2} }}-{\frac {p(1-p)}{
(2p-1)(q-px)}}\bigg]. 
\end{equation*} 
And the coefficient of $x^n$ ($n$ fixed) in this is 
\begin{equation*} (m+1)\cdot \frac{1-2p}{1-p}+ \bigg[-1
+{\frac {p}{q }}(n+1)-{\frac {p}{ 2p-1}}\Big(\frac pq\Big)^n\bigg],
\end{equation*}
 or 
\begin{equation*} m\cdot \frac{1-2p}{q}+ {\frac {pn}{q
}}+{\frac {p}{ 1-2p}}\Big(\frac pq\Big)^n. 
\end{equation*} 
For $n=0$, we
find again Knuth's value $\frac{q-p}{q}m+\frac{p}{q-p}$. Perhaps it is not
very intuitive at the first glance
why this \emph{grows\/} with $n$. However, for larger $n$,
the process tends to be over more quickly, and so more will be left on the
large roll.

Now let us discuss the case $p=q$. Then 
\begin{equation*} 
C(pqz)=\frac12-\frac12\sqrt{1-z},
 \end{equation*} 
and%
\footnote{We use the symbol `$\sim$' in the sense that a full \emph{asymptotic
series} in powers $1-z$ would be available, at least in principle, to which
the method of \emph{singularity analysis of generating functions (transfer theorems)} \cite{FlOd90} is applicable.} 
\begin{equation*}
F(z,x)\sim(1-z)^{-3/2}\cdot\frac1{1-x}-(1-z)^{-1/2}\cdot\frac{1-2x}{(1-x)^3},
\end{equation*} 
and the coefficient of $z^m$ behaves like
\begin{equation*} \bigg[2\sqrt{\frac m\pi}+\frac3{4\sqrt{\pi
m}}\bigg]\cdot\frac1{1-x} -\frac1{\sqrt{\pi m}}\cdot\frac{1-2x}{(1-x)^3}.
\end{equation*}
Furthermore the coefficient of $x^n$ ($n$ fixed) in this is 
\begin{equation*} 2\sqrt{\frac m\pi}+\frac3{4\sqrt{\pi
m}} +\frac1{\sqrt{\pi m}}\cdot \frac{(n+1)(n-2)}{2}. 
\end{equation*} 
For $n=0$ we find again 
\begin{equation*} 2\sqrt{\frac m\pi}-\frac1{4\sqrt{\pi
m}}. 
\end{equation*} 
Again, since everybody takes at random, the process
tends to be over more quickly, leaving more on the larger roll.




\vspace{2.5cm}




\section{Walks on a comb}\label{dani_section}

As explained in the introduction, we walk on the integers as described
in the following graph.

%\newpage
\vspace*{1.0cm}
\begin{figure}[!h]
$$
\cnode[linewidth=1.5pt](0,0){0.4cm}{A}
{\uput{0cm}[-90](0,0.1){0}}
{\uput{0cm}[-90](0,1.8){\tfrac{1}{2}}}  
\nccircle[nodesep=4pt,linewidth=1.5pt]{->}{A}{0.6cm}
\cnode[linewidth=1.5pt](-2,0){0.4cm}{B}
{\uput{0cm}[-90](-2,0.1){-1}}
\cnode[linewidth=1.5pt](-4,0){0.4cm}{C}
{\uput{0cm}[-90](-4,0.1){-2}}
\cnode[linewidth=1.5pt](2,0){0.4cm}{D}
{\uput{0cm}[-90](2,0.1){1}}
\cnode[linewidth=1.5pt](4,0){0.4cm}{E}
{\uput{0cm}[-90](4,0.1){2}}
\pnode(-6,0){F}
\pnode(6,0){G}
\pnode(0,-1.5){H}
\psset{nodesep=2pt,offset=3pt,arrows=->,arrowsize=3pt 2,arrowlength=2,linewidth=1.5pt}
\ncline{A}{B}
\naput{\tfrac{1}{4}}
\ncline{B}{A}
\naput{\tfrac{1}{2}}
\ncline{B}{C}
\naput{\tfrac{1}{2}}
\ncline{C}{B}
\naput{\tfrac{1}{2}}
\ncline{C}{F}
\naput{\tfrac{1}{2}}
\ncline{F}{C}
\naput{\tfrac{1}{2}}
\ncline{A}{D}
\naput{\tfrac{1}{4}}
\ncline{D}{A}
\naput{\tfrac{1}{2}}
\ncline{D}{E}
\naput{\tfrac{1}{2}}
\ncline{E}{D}
\naput{\tfrac{1}{2}}
\ncline{E}{G}
\naput{\tfrac{1}{2}}
\ncline{G}{E}
\naput{\tfrac{1}{2}}
\psset{nodesep=2pt,offset=0pt,arrows=->,arrowsize=3pt 2,arrowlength=2,linewidth=1.5pt}
\ncline{H}{A}
$$
\end{figure}

\newpage

One derives recursions for the probability generating functions immediately:
\begin{align}\label{dani}
\begin{split}
\phi_0(z)&=1+\frac z2\Big(\phi_{-1}(z)+\phi_{1}(z)\Big)+\frac z2\phi_0(z),\\
\phi_1(z)&=\frac z4\phi_{0}(z)+\frac z2\phi_{2}(z),\\
\phi_i(z)&=\frac z2\Big(\phi_{i-1}(z)	+\phi_{i+1}(z)\Big),\qquad i\ge2,\\
\phi_{-i}(z)&=\phi_{i}(z).
\end{split}
\end{align}
Now set
\begin{equation*}
F(z,x)=\sum_{i\ge0}x^i\phi_i(z).
\end{equation*}
As a check, we should have $2F(z,1)-F(z,0)=\frac{1}{1-z}$.

Summing, we get
\begin{align*}
F(z,x)&=1+z\phi_{1}(z)+\frac z2\phi_{0}(z)+
x\frac z4\phi_{0}(z)+x\frac z2\phi_{2}(z)+
			\sum_{i\ge2}x^i\frac z2\Big(\phi_{i-1}(z)+\phi_{i+1}(z)\Big)\\
&=(1-\frac z2)\phi_{0}(z)+\frac z2\phi_{0}(z)+
x\frac z4\phi_{0}(z)+x\frac z2\phi_{2}(z)\\
&\kern6cm+
\frac {zx}2\sum_{i\ge1}x^i\phi_{i}(z)+
\frac {z}{2x}\sum_{i\ge3}x^i\phi_{i}(z)\\
&=\phi_{0}(z)+
\frac {zx}4\phi_{0}(z)+
\frac {zx}2\Big[F(z,x)-\phi_0(z)\Big]+
\frac {z}{2x}\Big[F(z,x)-\phi_0(z)-x\phi_1(z)\Big].
\end{align*}
Note that by the first equation of \eqref{dani} and symmetry,
 $\phi_0(z)=1+z\phi_{1}(z)+\frac z2\phi_0(z)$, and so one can express
$\phi_1(z)$ by $\phi_0(z)$. Therefore,
\begin{align*}
F(z,x)\Big[1-\frac {zx}2-\frac {z}{2x}\Big]
&=\phi_{0}(z)+
\frac {zx}4\phi_{0}(z)-\frac {zx}2\phi_0(z)-
\frac {z}{2x}\phi_0(z)
-\frac {z}{2}\phi_1(z)\\
&=\phi_{0}(z)-\frac {zx}4\phi_{0}(z)-
\frac {z}{2x}\phi_0(z)
-\frac12\Big(1-\frac z2\Big)\phi_0(z)+\frac12\\
\end{align*}
and
\begin{align*}
F(z,x)
&=\frac{\phi_{0}(z)-\frac {zx}4\phi_{0}(z)-
\frac {z}{2x}\phi_0(z)
-\frac12(1-\frac z2)\phi_0(z)+\frac12}{1-\frac {zx}2-\frac {z}{2x}}\\
&=\frac{F(z,0)(-x+\frac {zx^2}2+
{z}-\frac {zx}2)-x}{{zx^2}-2x+z}.
\end{align*}
Now, set as usual
\begin{equation*}
r_1(z)=\frac{1-\sqrt{1-z^2}}{z},\qquad
r_2(z)=\frac{1+\sqrt{1-z^2}}{z}.
\end{equation*}
For $x=r_1(z)$ the numerator vanishes, as always:
\begin{align*}
F(z,0)&=\frac{2r_1(z)}{-2r_1(z)+zr_1^2(z)+
{2z}-zr_1(z)}\\
&=\frac{2r_1(z)}{-2r_1(z)+2r_1(z)-z+
{2z}-zr_1(z)}\\
&=\frac{2r_1(z)}{
z(1-r_1(z))}\\
\end{align*}
and
\begin{align*}
F(z,x)
&=\frac{\frac{2r_1(z)}{z(1-r_1(z))}(-x+\frac {zx^2}2+
{z}-\frac {zx}2)-x}{{zx^2}-2x+z}\\
&=\frac{ -2z+z r_1(z)x} {z^2(x-r_2(x))(1- r_1(z))}\\
&=\frac{ 2zr_1(z)-2x r_1(z)+xz} {z^2(1- r_1(z))(1-xr_1(z))}\\
&=\frac{ r_1(z)(2- r_1(z)x)} {z(1- r_1(z))(1-xr_1(z))}\\
&=\frac{ r_1(z)} {z(1- r_1(z))}\Big(1+\frac1{1-xr_1(z)}\Big).
\end{align*}
 From this explicit form we can now read off coefficients:
\begin{align*}
[x^n]F(z,x)&=\frac{ r_1^{n+1}(z)} {z(1- r_1(z))}.
\end{align*}
This is only correct for $n\ge1$.


And now set $z=2v/(1+v^2)$, which is the trick we used  in Section~2.
Then $r_1=v$;
\begin{align}\label{previous}
\begin{split}
[z^m]\frac{ r_1^{n+1}(z)} {z(1- r_1(z))}
&=\frac1{2\pi i}\oint\frac{dz}{z^{m+1}}\frac{ r_1^{n+1}(z)} {z(1- r_1(z))}\\
&=\frac1{2\pi i}\oint\frac{(1-v^2)(1+v^2)^{m+1}}{2^{m}v^{m+1}(1+v^2)^{2}}
\frac{ v^{n+1}(1+v^2)} {2v(1- v)}dv\\
&=\frac1{2\pi i}\oint\frac{(1+v)(1+v^2)^{m}}{2^{m+1}v^{m-n+1}}dv\\
&=2^{-m-1}[v^{m-n}](1+v)(1+v^2)^{m}\\
&=2^{-m-1}\binom{m}{\left\lfloor\frac{m-n}{2}\right\rfloor}.
\end{split}
\end{align}
This simple formula expresses the probability to end up in state $n$ after
$m$ random steps. We leave a combinatorial proof of it as an exercise
(aka challenge).

For $n=0$ we can do this:
\begin{align*}
[x^0]F(z,x)=F(z,0)=\frac{ 2r_1(z)} {z(1- r_1(z))},
\end{align*}
and one must multiply the instance $n=0$ of  formula \eqref{previous} by $2$:
\begin{equation*}
[z^mx^0]F(z,x)=
2^{-m}\binom{m}{\left\lfloor\frac{m}{2}\right\rfloor}.
\end{equation*}









\section{A card guessing game}\label{cards_section}


One starts with a deck of cards consisting of $m$ red and $n$ black cards. A
guess is made as to the colour of the top card, after which it is revealed and
discarded. To maximise the number of correct guesses one chooses the colour
corresponding to the majority of cards remaining in the deck. 
 We rederive here
the probability distribution for the number of correct guesses for a
pack of $m+n$ cards, found originally by 
Sulanke \cite{Sulanke95}.

The probability model is that all $\binom{m+n}{m}$ possible orderings of cards
are equally likely.

In what follows, $m$ always refers to the number of cards of the
colour that is predominant, $n$ to the other colour. 

Note also that one makes at least $m$ correct guesses, since after $n$ false
guesses, there is only one colour left in the deck, and the remaining guesses
are necessarily correct. 



Let $p(m,n;k)$  denote the probability that, assuming that one has $m$
cards of one colour and  $n$ cards of a second colour, 
with $m\ge n\ge0$,  one guesses $k$ cards correctly.
Introducing probability generating functions
\begin{equation*}
\varphi_{m,n}(u)=\sum_{m\le k\le m+n  }p(m,n;k)u^k,
\end{equation*}
one sees the recursions
\begin{align*}
\varphi_{m,n}(u)&=u\frac{m}{m+n}\varphi_{m-1,n}(u)
+\frac{n}{m+n}\varphi_{m,n-1}(u) \qquad \text{for $m>n\ge0 $},\\
\varphi_{m,m}(u)&=\frac{1+u}{2}\varphi_{m,m-1}(u)
\qquad \text{for $m\ge1 $},\quad  \varphi_{0,0}(u)=1
\end{align*}
almost immediately. If one defines $\Phi_{m,n}(u)=\binom{m+n}{m}
\varphi_{m,n}(u)$ instead, the recursions are nicer, viz.
\begin{align*}
\Phi_{m,n}(u)&=u\Phi_{m-1,n}(u)
+\Phi_{m,n-1}(u) \qquad \text{for $m>n\ge0 $},\\
\Phi_{m,m}(u)&=(1+u)\Phi_{m,m-1}(u)
\qquad \text{for $m\ge1 $},\quad  \Phi_{0,0}(u)=1.
\end{align*}
Now we use the kernel method to get the probabilities $p(m,n;k)$:
We set
\begin{align*}
F(z,x)&=\sum_{m\ge n\ge 0} \Phi_{m,n}(u)z^mx^{m-n},\\
F_0(z)&=\sum_{m\ge 0} \Phi_{m,m}(u)z^m,\\
F_1(z)&=\sum_{m\ge 1} \Phi_{m,m-1}(u)z^m.\\
\end{align*}
The first and second recursions for $\Phi_{m,n}(u)$ give
\begin{equation*}
F(z,x)-F_0(z)=uzx\,F(z,x)+\frac1x\big[F(z,x)-F_0(z)-F_1(z)x\big]
\end{equation*}
and $F_0(z)=1+(1+u)F_1(z)$, respectively. 
Hence
\begin{equation*}
(1-x+uzx^2)F(z,x)=1-x+(1+u-ux)F_1(z).
\end{equation*}
Now the fact that the power series $F(z,x)$ remains finite at
$x=\lambda:=2/(1+\sqrt{1-4uz}\,)$ gives
$F_1(z)=(\lambda-1)/(1+u-\lambda u)$ and finally
\begin{equation*}
F(z,x)=\bigg(
\frac{1+\sqrt{1-4uz}}{2}-
\frac{1-\sqrt{1-4uz}}{2}u
\bigg)^{-1}
\bigg(1-\frac{1-\sqrt{1-4uz}}{2}x\bigg)^{-1}.
\end{equation*}
Hence
\begin{equation*}
[x^n] F(z,x)=\bigg(
\frac{1+\sqrt{1-4uz}}{2}-
\frac{1-\sqrt{1-4uz}}{2}u
\bigg)^{-1}
\bigg(\frac{1-\sqrt{1-4uz}}{2}\,\bigg)^{n}.
\end{equation*}
Following the coefficient extraction method used earlier, we substitute $z=\dfrac{v}{(1+v)^2u}$.
Then
\begin{equation*}
[x^{m-n}] F(z,x)=\frac{1+v}{1-uv}\Big(\frac{v}{1+v}\Big)^{m-n},
\end{equation*}
and
\begin{align*}
[z^mx^{m-n}] F(z,x)&=\frac1{2\pi i}\oint\frac{dz}{z^{m+1}}\frac{1+v}{1-uv}\Big(\frac{v}{1+v}\Big)^{m-n}\\
&=\frac1{2\pi i}\oint\frac{dv(1-v)(1+v)^{2m+2}u^{m+1}}{(1+v)^3uv^{m+1}}\frac{1+v}{1-uv}\Big(\frac{v}{1+v}\Big)^{m-n}\\
&=[v^n](1-v)(1+v)^{m+n}u^{m}\frac{1}{1-uv}.
\end{align*}
Furthermore,
\begin{align*}
\binom{m+n}{m}p(m,n;k)&=[z^mx^{m-n}u^k] F(z,x)\\*
&=[v^nu^k](1-v)(1+v)^{m+n}u^{m}\frac{1}{1-uv}\\
&=[v^nu^{k-m}](1-v)(1+v)^{m+n}\frac{1}{1-uv}\\
&=[v^n](1-v)(1+v)^{m+n}v^{k-m}\\
&=[v^{m+n-k}](1-v)(1+v)^{m+n}\\
&=\binom{m+n}{k}-\binom{m+n}{k+1}.
\end{align*}
So we eventually find
\begin{equation*} 
p(m,n;k)=\frac{1}{\binom{m+n}{m}
}\bigg[\binom{m+n}{k}-\binom{m+n}{k+1} \bigg]\qquad \text{for $m\le k\le m+n $},
\end{equation*}
which is the probability to make $k$ correct guesses when $m$ red resp. $n$ black cards with
$m\ge n$ are given.





\section{A functional--difference equation of Runyon, Morrison, 
Carlitz, and Riordan} \label{carlitz_section}

A certain functional--difference equation
that Runyon encountered when analyzing a queuing system
was solved in a combined effort of Morrison, Carlitz,
and Riordan \cite{Morrison64, Carlitz64, Riordan66}
Here we apply the kernel method to it. The treatment is taken from my
own paper \cite{Prodinger01e}.


The functional--difference equation is
\begin{equation*}
(x-\a)(\a-\b)^{n-1}g_n(x)=\a(x-\b)^ng_{n-1}(\a)-x(\a-\b)^ng_{n-1}(x)
,\quad n\ge 1, \ g_0(x)=1,
\end{equation*}
which defines a sequence of polynomials $g_n(x)$.

We introduce the generating function 
\begin{equation*}   
G(x,t):=\sum_{n\ge0}(\a-\b)^{n-1}g_n(x)t^n.
\end{equation*}
Multiplying the recursion by $t^n$ and summing we get
\begin{equation*}
G(x,t)=\frac{\a\sum_{n\ge1}(x-\b)^nt^ng_{n-1}(\a)+
\frac{x-\a}{\a-\b}}{x-\a+xt(\a-\b)^2}=
\frac{\a(x-\b)(\a-\b)tG\Big(\a,\frac{t(x-\b)}{\a-\b}\Big)
+\frac{x-\a}{\a-\b}}{x-\a+xt(\a-\b)^2}.
\end{equation*}
 For 
\begin{equation*}   
x=\bar x=\frac{\a}{1+t(\a-\b)^2}
\end{equation*}
the denominator vanishes. Consequently,
the numerator must also vanish:
\begin{equation*}   
\sum_{n\ge1}(\bar x-\b)^nt^ng_{n-1}(\a)=
\frac{\bar x-\a}{(\b-\a)\a}.
\end{equation*}
Now we set $T=(\bar x-\b)t$, i.~e.,
\begin{equation*}   
t=\frac{1-T(\a-\b)-\sqrt{1-2T(\a+\b)+T^2(\a-\b)^2}}
{2\b(\a-\b)}.
\end{equation*} 
So
\begin{equation*}   
\sum_{n\ge0}T^ng_n(\a)=
(\a-\b)G\big(\a,\tfrac{T}{\a-\b}\big)=
\frac{1+T(\a-\b)-
\sqrt{1-2T(\a+\b)+T^2(\a-\b)^2}}{2T\a}.
\end{equation*}
Since this series is now known, the generating function $G(x,t)$ is known
as well. From this, one can expand this function and describe its coefficients.
We refer for this to the  paper \cite{Prodinger01e} where all this is described in
more detail. 

\section{Banach's match box problem}

This is a very classical exercise. A certain mathematician has 
two   match boxes, one  in each of his two pockets.
Initially, both contain $m$ matches each.
 He makes random drawings from one of his pockets to  get one
match box. How many matches are left in the larger box when one box has become
empty? 
(A small variation is to count the remaining matches when he tries to get
a match and  finds that his chosen box is empty. We are not studying this variant.)

In what follows, $m$ ($n$) is always the number of matches in the
larger (smaller) box. We want the probability generating function
$\varphi_{m,n}(u)$, where the coefficient of $u^k$ is the probability that
this parameter 
(number of matches  left in the larger box when one box has become
empty)
is $k$. The following recursions are self-explanatory:
\begin{align*}
\varphi_{m,n}(u)&=\frac12\varphi_{m-1,n}(u)+\frac12\varphi_{m,n-1}(u)\qquad
\text{for $m>n\ge1$},\\
\varphi_{m,m}(u)&=\varphi_{m,m-1}(u) \qquad
\text{for $m\ge1$},\\
\varphi_{m,0}(u)&=u^m,\qquad \text{for $m\ge0$}.
\end{align*}
Define
\begin{gather*}
F(z,x)=\sum_{m\ge n\ge 0}\varphi_{m,n}(u)z^mx^{m-n},\\
F_0(z)=\sum_{m\ge 0}\varphi_{m,m}(u)z^m,
\qquad
F_1(z)=\sum_{m\ge 1}\varphi_{m,m-1}(u)z^m.
\end{gather*}
Summing the recursion, we get
\begin{multline*}
\sum_{m>n\ge1}\varphi_{m,n}(u)z^mx^{m-n}+\sum_{m\ge1}\varphi_{m,m}(u)z^m
\\=\frac12\sum_{m>n\ge1}\varphi_{m-1,n}(u)z^mx^{m-n}
+\frac12\sum_{m>n\ge1}\varphi_{m,n-1}(u)z^mx^{m-n}+
\sum_{m\ge1}\varphi_{m,m-1}(u)z^m
\end{multline*}
or
\begin{multline*}
F(z,x)-\sum_{m\ge0}\varphi_{m,0}z^mx^m
\\*
=\frac{zx}2\sum_{m\ge n\ge1}\varphi_{m,n}(u)z^mx^{m-n}
+\frac1{2x}\sum_{m-1>n\ge0}\varphi_{m,n}(u)z^mx^{m-n}+
F_1(z)
\end{multline*}
or
\begin{multline*}
F(z,x)-\frac1{1-zxu}\\*
=\frac{zx}2\bigg[F(z,x)-\frac1{1-zxu}\bigg]
+\frac1{2x}\bigg[F(z,x)-xF_1(z)-F_0(z)\bigg]+F_1(z).
\end{multline*}
Note $F_1(z)=F_0(z)-1$. We get
\begin{equation*}
F(z,x)=\frac{\frac1{1-zxu}(1-\frac{zx}{2})+\frac{x-1}{2x}F_0(z)-\frac12}
{1-\frac{zx}{2}-\frac{1}{2x}}
=\frac{\frac{x}{1-zxu}({zx}-2)+(1-x)F_0(z)+x}
{{zx^2}-2x+1}.
\end{equation*}
Now set $r_1(z)=\frac{1-\sqrt{1-z}}{z}$; as before, $(x-r_1(z))$ must be a factor
of the numerator, which gives us the equation
\begin{equation*}
\frac{r_1(z)}{1-uzr_1(z)}(2-{zr_1(z)})+(1-r_1(z))F_0(z)+r_1(z)=0,
\end{equation*}
whence
\begin{equation*}
F_0(z)={\frac {r_1(z) (-zr_1(z)+1+uzr_1(z) )}{ (1-uzr_1(z) ) (1-r_1(z) )}}.
\end{equation*}
We don't want to explore that in much detail; let us just compute
the averages, as this is the classical problem. So, we differentiate this
with respect to $u$ and set $u=1$ and get the generating function $E(z)$
of the averages:
\begin{equation*}
E(z)={\frac {\left (zr_1(z)-2\right )z{r_1^2(z)}}
{\left (1-zr_1(z)\right )^{2}\left (1-r_1(z)\right )}}.
\end{equation*}
With the substitution $z=4v/(1+v)^2$,
\begin{equation*}
E(z)=\frac{4v(1+v)}{(1-v)^3}.
\end{equation*}
Hence, using our traditional method to extract coefficients,
\begin{align*}
[z^m]E(z)&=\frac1{2\pi i}\oint\frac{dz}{z^{m+1}}E(z)
=\frac1{2\pi i}\oint\frac{4dv(1-v)(1+v)^{2m+2}}{(1+v)^3(4v)^{m+1}}
\frac{4v(1+v)}{(1-v)^3}\\
&=4^{1-m}[v^{m-1}]\frac{(1+v)^{2m}}{(1-v)^2}\\&=
4^{1-m}\sum_{k=0}^{m-1}\binom{2m}{k}(m-k)=
4^{1-m}\frac{(2m-1)!}{(m-1)!^2}\sim 2\sqrt{\frac m\pi}.
\end{align*}

Note that this is the special case $p=q$ of the toilet paper problem,
considered in Section~\ref{toilet_section}. However, there, the recursions
were only set up for the averages (expectations), whereas here we have
full access to the probability generating functions.

One could consider them in the toilet paper as well. We leave this to the
interested reader. All one has to do is to replace the boundary
conditions $M_{m,0}=m$ by $M_{m,0}=u^m$.

%\newpage

\section{Central binomial coefficients}


The explicit form of the generating function     
\begin{equation*}
\sum_{n\ge0}\binom {2n}nz^n=\frac1{\sqrt{1-4z}}
\end{equation*}
is usually derived by the Lagrange inversion formula or by residue calculations.




Of course, we will derive it here using the kernel method.

Define
\begin{align}\label{symmy}
\begin{split}
a_{n,k}&=a_{n-1,k-1}+a_{n-1,k+1},\quad n\ge k\ge1,\\*
a_{n,0}&=2a_{n-1,1}, \quad n\ge1, \quad a_{0,0}=1.
\end{split}
\end{align}
There is a combinatorial interpretation of these numbers: They count walks of
length~$n$ leading to level $k$, where one can make steps $+1$ or $-1$. The path has to stay nonnegative, 
and a step leading back to level $0$ is counted with  weight $2$. By a simple
symmetry argument, one can drop the weight $2$ as well as the nonnegativity.
These numbers are modeled in such a way that
\begin{equation*}
a_{2n,2k}=\binom{2n}{n+k},\qquad
a_{2n+1,2k+1}=\binom{2n+1}{n+1+k},
\end{equation*}
and all the other $a_{n,k}$'s being zero. 
(One could just start from these numbers, write down the usual recursions,  notice
the symmetry and end up with \eqref{symmy}. This is completely equivalent.)


Now we introduce $F(z,x)=\sum_{0\le k\le n}a_{n,k}x^kz^n$ and get, summing
the recursion (multiplied by $x^kz^n$):
\begin{equation*}
F(z,x)=\frac{F(z,0)\big[z-\frac x2\big]-\frac x2}{zx^2-x+z}.
\end{equation*}
As usual, for $x=r_1(z)=(1-\sqrt{1-4z^2}\,)/(2z)$, the numerator must vanish, 
which leads to
\begin{equation*}
F(z,0)=\frac{r_1(z)}{2z-r_1(z)}=\frac1{\sqrt{1-4z^2}},
\end{equation*}
as expected.
\medskip

The generating function of the \emph{central trinomial coefficients}
$[t^n]{(1+t+t^2)}^n$ can be treated in the same way.


\bigskip
\textbf{Acknowledgment.} Thanks are due to Margaret Archibald and Michael 
Drmota who read earlier drafts of this paper. Special thanks are due to an
anonymous referee for a very careful reading of a not so careful manuscript.






%\newpage





\bibliographystyle{amsplain} 

%\bibliography{C:/Documents and Settings/Owner/My Documents/texfiles2003/pro_bib}
%\bibliography{pro_bib}

%\bibliography{C:/texfiles2002/pro_bib}

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}

\begin{thebibliography}{10}

\bibitem{BaBoDeFlGaGo02}
C.~Banderier, M.~Bousquet-M\'elou, A.~Denise, P.~Flajolet, D.~Gardy, and
  D.~Gouyou--Beauchamps, \emph{Generating functions of generating trees},
  Discrete Mathematics \textbf{246} (2002),  29--55.


\bibitem{Bertacchi2}
D.~Bertacchi, \emph{Inhomogeneous quantities for the simple random walk on the
  $2$-comb}, preprint (2003).


\bibitem{Bertacchi1}
D.~Bertacchi and F.~Zucca, \emph{Uniform asymptotic estimates of transition
  probabilities on combs}, 
J. Aust. Math. Soc. \textbf{75} (2003),  325--353.

\bibitem{BrKnRi72}
N.~G. De~Bruijn, D.~E. Knuth, and S.~O. Rice, \emph{The average height of
  planted plane trees}, Graph Theory and Computing (R.~C. Read, ed.), Academic
  Press, 1972, pp.~15--22.

\bibitem{BuPe00}
M.~Bousquet-M\'elou  and M.~Petkov\vvv sek, \emph{Linear recurrences with constant
coefficients: the multivariate case},
  Discrete Mathematics \textbf{225} (2000),  51--75.

\bibitem{Carlitz64}
L.~Carlitz, \emph{A functional--difference equation}, Duke Mathematical Journal
  \textbf{31} (1964), 449--453.


\bibitem{Drmota03}
M.~Drmota, \emph{Discrete random walks on one-sided ``periodic'' graphs},
  Discrete Mathematics and Theoretical Computer Science \textbf{AC} 
(Discrete Random Walks 2003), 83--94.

\bibitem{FlOd90}
P.~Flajolet and A.~Odlyzko, \emph{Singularity analysis of generating
  functions}, SIAM Journal on Discrete Mathematics \textbf{3} (1990), 216--240.

\bibitem{GrKnPa94}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik, \emph{Concrete mathematics}, 
second
  edition, Addison Wesley, 1994.

\bibitem{Knoedel83}
W.~Kn{\"o}del, \emph{\"{U}ber das mittlere {V}erhalten von
  on-line-{P}ackungsalgorithmen}, Elektron.\ Informationsverarb.\ Kybernet.\
  \textbf{19} (1983), 427--433.

\bibitem{KnPr01b}
A.~Knopfmacher and H.~Prodinger, \emph{A simple card guessing game revisited},
  Electron. J. Combin. \textbf{8} (2001), Research Paper 13, 9 pp.
  (electronic).

\bibitem{Knuth97}
D.~E. Knuth, \emph{The art of computer programming}, vol. 1: Fundamental
  Algorithms, Addison-Wesley, 1973, Third edition, 1997.

\bibitem{Knuth84}
\bysame, \emph{The toilet paper problem}, Amer. Math. Monthly \textbf{91}
  (1984), 465--470, reprinted in: Selected papers on analysis of algorithms,
CSLI lecture notes, 2000.

\bibitem{Morrison64}
J.~Morrison, \emph{A certain functional--difference equation}, Duke
  Mathematical Journal \textbf{31} (1964), 445--448.


\bibitem{PaPr98}
A.~Panholzer and H.~{P}rodinger, \emph{Towards a more precise analysis of an
  algorithm to generate binary trees : A tutorial}, The Computer Journal
  \textbf{41} (1998), 201--204.

\bibitem{Petkovsek98}
M.~Petkov\vvv sek, \emph{The irrational chess knight}, Proceedings FPSAC '98
  \ (1998), 513--522.



\bibitem{Prodinger85}
H.~Prodinger, \emph{{E}inige {B}emerkungen zu einer {A}rbeit von {W}.
  {K}n{\"o}del {\"u}ber das mittlere {V}erhalten von
  on-line--{P}ackungsalgorithmen}, Elektron.\ Informationsverarb.\ Kybernet.\ \textbf{21} (1985), 3--7.

\bibitem{Prodinger90}
\bysame, \emph{Further results on a problem of {K}n{\"o}del concerning the
  analysis of bin--packing}, Number--theoretic Analysis (E.~Hlawka and R.~F.
  Tichy, eds.), Lecture Notes in Mathematics, vol. 1452, 1990, pp.~193--198.

\bibitem{Prodinger92}
\bysame, \emph{{E}inige {B}emerkungen zu einer {B}in--{P}acking {A}ufgabe von
  {W}. {K}n{\"o}del}, Computing \textbf{47} (1992), 247--254.

\bibitem{Prodinger01e}
\bysame, \emph{On a functional-difference equation of {R}unyon, {M}orrison,
  {C}arlitz, and {R}iordan}, S\'em. Lothar. Combin. \textbf{46} (2001), 
Art.~B46a, 4~pp. (electronic).

\bibitem{Riordan66}
J.~Riordan, \emph{A functional--difference equation}, Duke Mathematical Journal
  \textbf{33} (1966), 23--25.


\bibitem{Sulanke95}
R.~Sulanke, \emph{Guessing, ballot numbers, and refining {P}ascal's 
triangle}, manuscript, 9~pages (1995);
available at
{\ttt http://diamond.idbsu.edu/$\sim$sulanke/recentpapindex.html}.







\end{thebibliography}


\end{document}