\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
}{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}