\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{eepic}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}
\newtheorem{result}{Result}
\newtheorem{conjecture}{Conjecture}

%\newenvironment{comment}{\setbox0=\vbox\bgroup}{\egroup}
%\newenvironment{singlespace}{\def\baselinestretch{1.0}\large\normalsize}{\par}
%\setlength{\textheight}{8.9in} \setlength{\textwidth}{6.1in}
%\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%\renewcommand{\baselinestretch}{1.02}
\newcommand{\con}{\rightarrow}
\newcommand{\cd}{\mbox{$\stackrel{d}{\rightarrow}$}}
\newcommand{\ep}{\varepsilon}
\newcommand\be{\begin{equation}}
\newcommand\ee{\end{equation}}
\newcommand\ba{\begin{array}{lcr}}
\newcommand\ea{\end{array}}
\newcommand\bea{\begin{eqnarray*}}
\newcommand\eea{\end{eqnarray*}}
%\newcommand{\note}[1]{\mbox{\scriptsize \{{\it comment} $\rightarrow$\}~ #1}}
%\newcommand{\note}[1]{}
\newcommand\QED{\ifhmode\allowbreak\else\nobreak\fi\quad\nobreak$\Box$\medbreak}
\newcommand{\proofstart}{\par\noindent\bf Proof:\rm\enspace}
\newcommand{\proofend}{\hfill\eod\med}
\newenvironment{proof}{\proofstart}{\proofend}

\def\noi{\noindent}
\def\parsec{\par\noindent}
\def\big{\bigskip\parsec}
\def\med{\medskip\parsec}

%\def\basswidth{3.0in}
%\def\gutter{0.1in}
\def\noi{\noindent}
\def\eod{\vrule height 6pt width 5pt depth 0pt}
\def\parsec{\par\noindent}
\def\big{\bigskip\parsec}
\def\med{\medskip\parsec}
\def\pr{{\rm Pr}}
\def\l{\ell}
\def\A{{\cal A}}
\def\kk{\kappa}
\def\W{{\cal W}}
\def\X{\{X_k\}}
\def\Wk{{\A_{k}}}
\def\eps{\varepsilon}
\def\B{{\cal B}}
\def\TB{\widetilde{\B}}
\def\F{{\cal F}}
\def\S{{\cal S}}
\def\TG{\widetilde{G}}
\def\P{{\cal P}}
\def\HC{{\cal H}}
\def\tx{\hat{x}}
\def\HX{\hat{X}}
\def\tb{\widetilde{B}}
\def\tw{\widetilde{\W}}
\def\TX{\widetilde{X}}
\def\pmin{P_{\min}}
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\lb{L_n^{(b)}}
\def\hb{H_n^{(b)}}
\def\sb{s_n^{(b)}}
\def\O{{\cal O}}
\def\var{{\rm Var~}}
\def\cov{{\rm Cov}}
\def\J{{\cal J}}
\def\ow{\overline{w}}
\def\ta{{\widetilde{a}}}
\def\real{{I \!\! R}}
\def\h{\hat}
\def\D{{\cal D}}
\def\Var{{\rm Var}~}
\def\la{\langle}
\def\ra{\rangle}
\def\Var{{\bf Var~}}
\def\E{{\bf E}}
\def\vpi{\mbox{\boldmath $\pi$}}
\def\wt{\widetilde}
\def\t{\theta}
\def\dd{\delta}
\def\TX{\wt{X}}
\def\TV{\wt{V}}
\def\C{{\cal C}}
\def\d{\delta}
\def\bb{\beta}
\def\OG{O_n^{{\rm gr}}}
\def\OP{O_n^{{\rm opt}}}
\def\G{{\cal G}}
\def\r{\bar{r}}
\def\M{{\cal M}}
\def\T{{\cal T}}
\def\U{{\cal U}}
\def\L{{\cal L}}

\def\R{{\cal R}}

\def\om{\omega}
\def\tb{\tilde{b}}

\def\F{{\cal F}}
\def\Q{{\bf Q}}
\def\V{{\bf V}}
\def\N{{\cal N}}
\def\K{{\cal K}}
\def\A{{\cal A}}
\def\M{{\cal M}}
\def\Z{{\cal Z}}
\def\k{{\bf k}}
\def\kk{{\bf k'}}
\def\skk{{\k,\kk}}
\def\skn{{\k,[0]}}
\def\skm{{\k-\kk}}
\def\det{\hbox{\rm det}}
\def\TG{\tilde{G}}
\def\j{{\bf i}}
\def\ss{\sigma}
\def\eps{\epsilon}
\def\z{{\bf z}}
\def\x{{\bf x}}
\def\v{{\bf v}}
\def\kb{{\bf k}}
\def\y{{\bf y}}
\def\t{{\bf t}}


\title{\bf On a Recurrence Arising in Graph Compression\thanks{This work was
supported in part by the NSF Science and Technology Center for
Science of Information Grant CCF-0939370, NSF Grant CCF-0830140,
AFOSR Grant FA8655-11-1-3076, NSA Grants H98230-11-1-0141 and
H98230-11-1-0184, and the MNSW grant N206 369739.}}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Yongwook Choi\\
\small J.~Craig Venter Institute\\[-0.8ex]
\small Rockville, MD, USA 20850\\[-0.8ex]
\small\tt ychoi@jcvi.org
\and
Charles Knessl\\
\small Dept. Math. Stat. \& Comp. Sci.\\[-0.8ex]
\small University of Illinois at Chicago\\[-0.8ex]
\small Chicago, IL, USA 60607\\[-0.8ex]
\small\tt knessl@uic.edu \and Wojciech Szpankowski\thanks{Also,
Visiting Professor at ETI,  Gdansk University of
Technology, Poland.}\\
\small Dept. Computer Science\\[-0.8ex]
\small Purdue University\\[-0.8ex]
\small West Lafayette, IN, USA 47907\\[-0.8ex]
\small\tt spa@cs.purdue.edu }

\date{\dateline{November 16, 2011}{July 11, 2012}\\
\small Mathematics Subject Classification: 05C05, 68W40}
\begin{document}

\maketitle

\begin{abstract}
In a recently proposed graphical compression algorithm by Choi and
Szpankowski (2012), the following tree arose in the course of the
analysis. The root contains $n$ balls that are consequently
distributed between two subtrees according to a simple rule: In each
step, all balls independently move down to the left subtree (say
with probability $p$) or the right subtree (with probability $1-p$).
A new node is created as long as there is at least one ball in that
node. Furthermore, a nonnegative integer $d$ is given, and at level
$d$ or greater one ball is removed from the leftmost node before the
balls move down to the next level. These steps are repeated until
all balls are removed (i.e., after $n+d$ steps). Observe that when
$d=\infty$ the above tree can be modeled as a {\it trie} that stores
$n$ independent sequences generated by a binary memoryless source
with parameter $p$. Therefore, we coin the name $(n,d)$-tries for
the tree just described, and to which we often refer simply as
$d$-tries. We study here in detail the path length, and show how
much the path length of such a $d$-trie differs from that of regular
tries. We use methods of analytic algorithmics, from Mellin
transforms to analytic poissonization.

\end{abstract}


\section{Introduction}

In \cite{isit09-graph} an algorithm was described to compress the {\it
structure} of a graph. The main idea behind the algorithm is quite
simple: First, a vertex of a graph, say $v_1$, is selected and the number of
neighbors of $v_1$ is stored in a binary string. Then the remaining
$n-1$ vertices are partitioned into two sets: the neighbors of $v_1$
and the non-neighbors of $v_1$. This process continues by selecting
randomly a vertex, say $v_2$, from the neighbors of $v_1$ and
storing two numbers: the number of neighbors of $v_2$ among each of
the above two sets. Then the remaining $n-2$ vertices are
partitioned into four sets: the neighbors of both $v_1$ and $v_2$,
the neighbors of $v_1$ that are non-neighbors of $v_2$, the
non-neighbors of $v_1$ that are neighbors of $v_2$, and the
non-neighbors of both $v_1$ and $v_2$. This procedure continues
until all vertices are processed.

In the Erd\H{o}s-R\'enyi model, a random graph has any pair of vertices connected
by an edge with probability $p$. It is proved in \cite{isit09-graph}
that for large $n$ our algorithm optimally compresses any graph
generated by the Erd\H{o}s-R\'enyi model (and, in fact, it works well
in practice even for graphs not generated by the Erd\H{o}s-R\'enyi
model). To establish this asymptotic optimality result, an
interesting tree was used in the construction, that we describe next.

The root of such a tree contains $n$ balls (vertices of the
underlying graph) that are consequently distributed between two
subtrees according to a simple rule: In each step, all balls
independently move down to the left subtree (say with probability
$p$) or the right subtree (with probability $q=1-p$), and  a new
node is created as long as there is at least one ball in that node.
Finally, a non-negative integer $d$ is given so that at level $d$ or
greater one ball is removed from the leftmost node before the balls
move down to the next level. These steps are repeated until all
balls are removed (i.e., after $n$+$d$ steps). Of interest are such
tree parameters as the depth, path length (sum of all depths), size, and
so forth. This is illustrated in Figure~\ref{fig:trie} in which the
deleted ball is shown next to the node from where it was removed.

\begin{figure}[tbp]
\setlength{\unitlength}{1.5mm} \center
\begin{picture}(55,50)(10,20)
%\multiput(0,0)(0,7){10}{\dashbox{1.5}(80,5){}}%
\begin{scriptsize}
\put(50,51){\circle{6}}% 3
\put(49,51){\circle*{1}}%
\put(51,51){\circle*{1}}%
\put(27.5,51){\circle{6}}% 3
\put(27.5,51){\circle*{1}}%
\put(31,44){\circle{6}}% 4
\put(31,44){\circle*{1}}%
\put(22.5,44){\circle{6}}% 4
\put(18,44){\circle*{1}}%
\put(34,37){\circle{6}}% 5
\put(29.5,37){\circle*{1}}%
\put(18.5,51){\circle{6}}% 3
\put(18.5,51){\circle*{1}}%
\put(14,51){\circle*{1}}%
\put(42,58){\circle{6}}% 2
\put(41,58){\circle*{1}}%
\put(43,58){\circle*{1}}%
\put(23,58){\circle{6}}% 2
\put(22,57){\circle*{1}}%
\put(24,57){\circle*{1}}%
\put(18.5,58){\circle*{1}}%
\put(23,59){\circle*{1}}%
\put(32,65){\circle{6}}% 1
\put(30.5,66){\circle*{1}}%
\put(32,66){\circle*{1}}%
\put(33.5,66){\circle*{1}}%
\put(30.5,64){\circle*{1}}%
\put(32,64){\circle*{1}}%
\put(33.5,64){\circle*{1}}%
\put(55,44){\circle{6}}% 4
\put(55,44){\circle*{1}}%
\put(45,44){\circle{6}}% 4
\put(45,44){\circle*{1}}%
\put(42,37){\circle{6}}% 5
\put(42,37){\circle*{1}}%
\put(45,30){\circle{6}}% 6
\put(40.5,30){\circle*{1}}%
\put(60,37){\circle{6}}% 5
\put(60,37){\circle*{1}}%
\put(55,30){\circle{6}}% 6
\put(55,30){\circle*{1}}%
\put(59,23){\circle{6}}% 7
\put(54.5,23){\circle*{1}}%
\end{scriptsize}
% between circles
\put(24.1,60.7){\line(10,7){5}}% 1-2
\put(34.9,64){\line(12,-7){5.8}}% 1-2
\put(25.2,56){\line(8,-7){2.4}}% 2-3
\put(20.7,56){\line(-8,-7){2.4}}% 2-3
\put(45,57){\line(9,-7){4}}% 2-3
\put(48,48.7){\line(-6,-7){1.7}}% 3-4
\put(52,48.6){\line(6,-7){1.7}}% 3-4
\put(29.2,48.6){\line(6,-7){1.5}}% 3-4
\put(20.3,48.6){\line(6,-7){1.5}}% 3-4
\put(57.2,41.8){\line(5,-7){1.5}}% 4-5
\put(42.9,41.9){\line(-4,-7){1.1}}% 4-5
\put(32.5,41.4){\line(5,-7){1}}% 4-5
\put(43.5,34.4){\line(4,-7){0.9}}% 5-6
\put(57.6,35.2){\line(-4,-7){1.4}}% 5-6
\put(56.6,27.5){\line(4,-7){1.1}}% 6-7
\end{picture}
\caption{\small A $(6,1)$-trie with six balls and $d=1$, in which
the deleted ball is shown next to the node where it was removed.}
\label{fig:trie}
\end{figure}

The tree just described falls between two digital trees, namely {\it
tries} and {\it digital search trees}. In fact, when $d=\infty$ the
tree can be modeled as a {\it trie} that stores $n$ independent
sequences generated by a binary memoryless source with parameter $p$.
Hence, we coin the term $(n,d)$-trie (or simply $d$-trie) for the
tree just described. In \cite{isit09-graph} lower and upper bounds
were proved for parameters of interest, by using known results for
tries and digital search trees \cite{drmota09,spa-book}. In this
paper, we establish precise asymptotic results. In particular, we
show by how much the path length of a $d$-trie differs from the path
length of the corresponding regular trie.

Many parameters of a $d$-trie can be described by the following two
dimensional recurrence
\begin{equation}
\label{spa1} a(n,d) = f(n) +\sum_{k=0}^n {n\choose k} p^kq^{n-k}
[a(k,d-1)+a(n-k,k+d-1)],\;\; d\geq 1,
\end{equation}
with $q=1-p$, and the boundary equation
\begin{equation}
\label{spa2} a(n+1,0) = f(n) +\sum_{k=0}^n {n\choose k} p^kq^{n-k}
[a(k,0)+a(n-k,k)],
\end{equation}
for a known additive term $f(n)$. For example, when $f(n)=n$, then
$a(n,d)$ represents the path length. Recurrence (\ref{spa2}) is
equivalent to the following boundary condition
$$
a(n,1) = a(n+1,0).
$$
For $d=\infty$ recurrence (\ref{spa1}) becomes a
traditional recurrence arising in the analysis of tries
\cite{spa-book} whose solutions (exact and asymptotic) are well
known. Thus, it is natural to study the difference
$\tilde{a}(n,d) := a(n,\infty)-a(n,d)$, and that is our objective.
In passing, we should point out that recurrence (\ref{spa2})
resembles the one used to analyze another digital search tree, known
as a {\it digital search tree}. In this paper we prove, however, that
a $(n,d)$-trie more closely resembles a trie, rather than a digital search tree.

Our main interest lies in solving recurrence (\ref{spa1}) for
$d=O(1)$. In fact, for graph compression we only need $d=0$, and we
focus on this case. We shall show that the term in
(\ref{spa1}) involving the sum over $a(n-k,k+d-1)$ becomes exponentially small for $n$ large and $d$ fixed. Then we shall approximate the recurrence
for the excess quantity $\tilde{a}(n,d)$ by
$$
\tilde{a}(n,d) = \sum_{k=0}^n {n\choose k} p^kq^{n-k} \tilde{a}(k,d-1)
$$
with an appropriate initial condition. The above we can solve asymptotically using Mellin transform technique
and depoissonization. In particular, for $f(n)=n$ (that is, for the path
length in a $d$-trie) we prove that the excess quantity $\tilde{a}(n,d)$
 becomes asymptotically, as $n\to \infty$ and $d=O(1)$,
$$
\frac{1}{2h\log (1/p)} \log^2 n - \frac{d}{h}\log n +
\left[\frac{1}{2h} - \frac{1}{h\log p}
\left(\gamma+1+\frac{h_2}{2h} + \Psi(\log_p n) \right)\right]\log n
$$
where $\Psi(\cdot)$ is the periodic function when $\log p/\log
(1-p)$ is rational, and $h$ is the entropy rate.

Digital trees such as tries and digital search trees have been
intensively studied for the last thirty years
\cite{devroye92,drmota09,fgd,fs-book,ks00,KnuthV1,louchard87,pittel85,pittel86,spa91,spa-book}.
However, our two-dimensional recurrence seems to be new and harder to analyze. It somewhat resembles the profile
recurrences for digital trees, which were studied for tries in \cite{park08} and digital search
trees in \cite{ds11}, and which are known to also be challenging.

The paper is organized as follows. In the Section~\ref{sec:Problem Statement} we precisely
formulate our problem and analyze it for $f(n)=n$. Proofs are
presented in Section~\ref{sec:analysis}, where we also discuss some
asymptotics for $d\to \infty$.
%Some numerical studies are carried out in Section~\ref{sec:Numerical Data}.


\section{Problem Statement}
\label{sec:Problem Statement}

In this section, we first formulate some recurrences describing
$(n,d)$-tries, then summarize our main results, discuss some
extensions, and present numerical results.

\subsection{Main Results}

Let us consider a $(n,d)$-trie with $n$ balls and parameter $d\geq
0$. First, we analyze the average path length $b(n,d)$.
It satisfies the following recurrence equations
\begin{equation}\label{b0}
b(n+1,0) = n + \sum_{k=0}^{n} {n \choose k} p^k q^{n-k}
\left[b(k,0)+b(n-k,k)\right], \ \ \mbox{for $n\ge 2$},
\end{equation}
and
\begin{equation}\label{bd}
b(n,d) = n + \sum_{k=0}^{n} {n \choose k} p^k q^{n-k}
\left[b(k,d-1)+b(n-k,k+d-1)\right], \ \ \mbox{for $n\ge 2$, $d\ge
1$}.
\end{equation}
Recurrence (\ref{b0}) follows from the fact that starting with $n+1$
balls in the root node, and removing one ball, we are left with $n$
balls passing through the root node. The root contributes $n$ since
each time a ball moves down it adds $1$ to the path length. Those
$n$ balls move down to the left or the right subtrees. Let us assume
$k$ balls move down to the left subtree (the other $n-k$ balls must
move down to the right subtree); this occurs with probability ${n
\choose k} p^k q^{n-k}$. At level one, one ball is removed from
those $k$ balls in the root of the left subtree. This contributes
$b(k,0)$. There will be no removal from $n-k$ balls in the right
subtree until all $k$ balls in the left subtree are removed. This
contributes $b(n-k,k)$. Similarly, for $d>0$ we arrive at recurrence
(\ref{bd}).

Here $0<p<1$ and $q=1-p$, and we also use the boundary conditions
\begin{equation}\label{bd-boundary}
b(0,d) = b(1,d)=0, \ \ \ \ \ d\ge 0; \ \ \ \  b(2,0)=0.
\end{equation}
By setting $d=1$ in (\ref{bd}) and comparing the result to
(\ref{b0}) we can replace (\ref{b0}) by the simpler boundary
condition
\begin{equation}\label{b-boundary}
b(n,1) = b(n+1,0), \ \ \mbox{for $n\ge 0$}.
\end{equation}
We are primarily interested in estimating $b(n,0)$ for large $n$.

If we let $d\to\infty$ in (\ref{bd}) and assume that $b(n,d)$ tends
to a limit $b(n,\infty)$, then (\ref{bd}) becomes
\begin{equation}\label{binf}
b(n,\infty) = n + \sum_{k=0}^{n} {n \choose k} p^k q^{n-k}
\left[b(k,\infty)+b(n-k,\infty)\right],
\end{equation}
with $b(0,\infty)=b(1,\infty)=0$. This is the same as the recurrence
for the mean path length in a trie, which was analyzed, for example,
in \cite{KnuthV1,spa-book}. One form of the solution is given by the
alternating sum
\begin{equation}\label{bninf2}
b(n,\infty) = \sum_{\l=2}^{n} (-1)^\l {n \choose \l}
\frac{\l}{1-p^\l-q^\l},
\end{equation}
and an alternative form is given by the generating function
\begin{equation}\label{bninf3}
\sum_{n=0}^{\infty} b(n,\infty) \frac{z^n}{n!} e^{-z} = \frac{1}{2\pi i}
\int_{Br}z^{-s}\frac{\Gamma(s+1)}{1-p^{-s}-q^{-s}}
ds,
\end{equation}
where $\Gamma(\cdot)$ is the Gamma function and $Br$ is a vertical
Bromwich contour on which $-2<\Re(s)<-1$. The integral certainly converges for $z$ real and positive.

The asymptotic expansion of $b(n,\infty)$ in (\ref{bninf2}) or (\ref{bninf3}) as $n\to\infty$ may be
obtained by a combination of singularity analysis and
depoissonization arguments (see \cite{fs-book,js98,spa-book}) and we
obtain
\begin{equation}\label{bninf4}
b(n,\infty) = \frac{1}{h}n\log n +
\frac{1}{h}\left[\gamma+\frac{h_2}{2h}+\Phi(\log_p n)\right]n+o(n),
\end{equation}
where $h=-p\log p-q\log q$, $h_2=p\log^2 p +q\log^2q$, $\gamma$ is
the Euler constant, and $\Phi(x)$ is the periodic function
$$
\Phi(x) = \sum_{k=-\infty, k\neq 0}^\infty \Gamma\left(-\frac{2k\pi
ir}{\log p}\right)e^{2k\pi rix},
$$
provided that $\log p/\log q = r/s$ is rational, with $r$ and $s$
being integers with $\gcd(r,s)=1$. If $\log p/\log q$ is irrational,
then the term with $\Phi$ is absent from the $O(n)$ term of
(\ref{bninf4}).


%%INSERT A
Our analysis requires a two-term asymptotic estimate of the {\it
difference} $b(n+1,\infty) - b(n,\infty)$, whose generating function
may be represented, similarly to (\ref{bninf4}), as the inverse
Mellin transform
\begin{equation}
\label{ck1}
\sum_{n\geq 0} [b(n+1,\infty) - b(n,\infty)]\frac{z^n}{n!} e^{-z} =
\frac{1}{2\pi i} \int_{Br} \frac{-s \Gamma(s+1)}{1-p^{-s}-q^{-s}}z^{-s-1} ds.
\end{equation}
This integral has a double pole at $s=-1$, and we can obtain a
two-term approximation for $z\to \infty$, which by depoissonization
becomes
\begin{equation}
\label{ck2}
b(n+1,\infty) - b(n,\infty)= \frac 1h \log n +\frac 1h \left(\gamma+1+
\frac{h_2}{2h}\right) +\frac 1h \Psi(\log_p n) +o(1)
\end{equation}
where $\Psi(\cdot)$ is the periodic function in Theorem~\ref{th:main},
which again appears only for rational $\log p/\log q$.

The $o(1)$ term in (\ref{ck2}), just as the term $o(n)$ in
(\ref{bninf4}), is difficult to characterize explicitly, but our
analysis requires only the first two terms of the asymptotic
estimate in (\ref{ck2}). Note that to obtain the leading term
$O(\log^2 n)$ in Theorem~\ref{th:main}, we only need the leading
term in (\ref{ck2}).

Next we set
\begin{equation}\label{bd2}
b(n,d) = b(n,\infty) - \tb(n,d)
\end{equation}
so that $\tb(n,d) = b(n,\infty) - b(n,d)$ measures how the path
lengths in the $d$-trie differ from those in a trie. From
(\ref{bd}) and (\ref{binf}), we then obtain
\begin{equation}\label{btd}
\tb(n,d) = \sum_{k=0}^{n} {n \choose k} p^k q^{n-k} \left[\tb(k,d-1)
+ \tb(n-k,k+d-1)\right], \ \ \mbox{for $n\ge 2$, $d\ge 1$},
\end{equation}
which unlike (\ref{bd}) is a homogeneous recurrence. Then from
(\ref{b-boundary}) and (\ref{bd2}) we have the boundary condition
\begin{equation}\label{bt-boundary}
\tb(n+1,0)-\tb(n,1) = b(n+1,\infty) - b(n,\infty).
\end{equation}
 From (\ref{bd-boundary}) and (\ref{binf}) we also have
$\tb(0,d)=\tb(1,d)=0$ for $d\ge 0$.

We further define $b_*(n,d)$ to be the solution of
\begin{equation}\label{b*d}
b_*(n,d) =\sum_{k=0}^{n} {n \choose k} p^k q^{n-k} b_*(k,d-1), \ \
\mbox{for $n\ge 2$, $d\ge 1$},
\end{equation}
and
\begin{equation}\label{b*0}
b_*(n+1,0)- b_*(n,1) = b(n+1,\infty) - b(n,\infty).
\end{equation}
Note that (\ref{b*d}) differs from (\ref{btd}) in that the former
neglects the term involving $\tb(n-k,k+d-1)$. We will show that this
term in (\ref{btd}) is asymptotically negligible for $n\to\infty$
with $d=O(1)$, so that $\tb(n,d) \sim b_*(n,d)$. The recurrence
(\ref{b*d}) is much easier to solve by transform methods
\cite{fs-book,spa-book} than is (\ref{btd}).

We summarize our main result below. In Section~\ref{sec:analysis} we
establish Theorem~\ref{th:main} along with some other exact and
asymptotic results for (\ref{b0})--(\ref{b-boundary}) and
(\ref{btd})--(\ref{b*0}).

\begin{theorem}\label{th:main}
For $n\to\infty$ and $d=O(1)$ the difference $b(n,\infty)-b(n,d)=\tb(n,d)$, which is the difference in path length between the present tree and a standard trie, is of order $O(\log^2 n)$ for $n\to\infty$. More
precisely
$$
\tb(n,d) = \frac{1}{2h\log (1/p)} \log^2 n - \frac{d}{h}\log n +
\left[\frac{1}{2h} - \frac{1}{h\log p}
\left(\gamma+1+\frac{h_2}{2h} + \Psi(\log_p n) \right)\right]\log n
+O(1),
$$
where $\Psi(\cdot)$ is the periodic function
$$
\Psi(x) = \sum_{k=-\infty, k \neq 0}^{\infty} \left[1+\frac{2k\pi
ir}{\log p}\right]\Gamma\left(-\frac{2k\pi ir}{\log p}\right)
e^{2k\pi irx}
$$
and $\log p/\log q = r/t$ is rational. If $\log
p/\log q$ is irrational, the term involving $\Psi$ is absent.
\end{theorem}

We see that $b(n,\infty)-b(n,d) = O(\log^2 n)$, which shows that the
$(n,d)$-tries studied in \cite{isit09-graph} are in some sense more
similar to tries than to digital search trees (DST). In
\cite{isit09-graph}, it was shown that $b(n,0)$ was bounded above by
average path lengths in tries and below by average path lengths in
DST's. It was also conjectured that $b(n,\infty)-b(n,d)$ is $O(n)$,
but our result shows that this difference is in fact much smaller.

\subsection{Related Recurrence Equations}

The method presented in the next section, allow us to analyze a
class of recurrences of the type (\ref{b0}) with inhomogeneous terms
other than $n$. For example, suppose we define $a(n,d)$ by
\begin{equation}\label{and}
a(n,d) = f(n) +\sum_{k=0}^n {n\choose k} p^kq^{n-k}
[a(k,d-1)+a(n-k,k+d-1)]
\end{equation}
where $f(n)$ is a given sequence. The boundary condition is again of
the type (\ref{b0}), or equivalently,
$$
a(n,1) = a(n+1,0),
$$
and we have $a(0,d)=a(1,d)=0$. Also, let $a(n,\infty)$ satisfy
(\ref{and}) with the second argument of $a(\cdot,\cdot)$ replaced by
infinity. This recurrence can be solved by generating functions and
Mellin transforms, and we can then establish that
$a(n,\infty)-a(n,d)=\tilde{a}(n,d)$, will satisfy
\begin{equation}\label{atnd}
\tilde{a}(n,d) = \sum_{k=0}^n {n\choose k} p^kq^{n-k}
[\tilde{a}(k,d-1)+\tilde{a}(n-k,k+d-1)]
\end{equation}
and
\begin{equation}\label{atnd-boundary}
\tilde{a}(n+1,0) -\tilde{a}(n,1) = a(n+1,\infty)-a(n,\infty).
\end{equation}
The asymptotic behavior of $\tilde{a}(n,d)$ for $d=O(1)$ and
$n\to\infty$ can be obtained in a manner completely analogous to the
case $f(n)=n$, discussed in the next section.

For example, the case
$$
f(n)= \lceil \log(n+1)\rceil
$$
arose in analyzing the compression algorithm in~\cite{isit09-graph}.
In~\cite{isit09-graph} it was shown that $a(n,\infty)$ has the
asymptotic form
\begin{equation}\label{aninf}
a(n,\infty) = \frac{n}{h} A_*(-1)+o(n), \ \ n\to\infty
\end{equation}
where
$$
A_*(-1) = \sum_{\l=2}^\infty \frac{\lceil
\log(\l+1)\rceil}{\l(\l-1)}
$$
if $\log p/\log q$ is irrational. If $\log p/\log q = r/s$ is
rational, the constant $A_*(-1)$ in (\ref{aninf}) must be replaced
by the oscillatory function
\begin{equation}\label{A}
A_*(-1) + \sum_{k=-\infty, k\neq 0}^\infty A_*\left(-1+\frac{2k\pi
ir}{\log p}\right) e^{2k\pi ir\log_pn}
\end{equation}
where
$$
A_*(s)=\sum_{n\ge 2} \frac{\lceil \log{(n+1)} \rceil}{n!}
\Gamma(n+s).
$$
By analyzing (\ref{atnd}) and (\ref{atnd-boundary}) for $n\to\infty$
we can show that the difference $a(n,\infty)-a(n,d)$ is $O(\log n)$,
and more precisely
$$
\tilde{a}(n,0) = a(n,\infty)-a(n,0) \sim -\frac{A_*(-1)}{h\log p}
\log n.
$$
Again if $\log p/\log q$ is rational we must replace $A_*(-1)$ by
the Fourier series in (\ref{A}).


\subsection{Numerical Data}
\label{sec:Numerical Data}

\begin{figure}[tb]
\center \scriptsize
% GNUPLOT: LaTeX picture
\setlength{\unitlength}{0.240900pt}
\ifx\plotpoint\undefined\newsavebox{\plotpoint}\fi
\begin{picture}(1500,750)(0,0)
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\put(110.0,131.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(90,131){\makebox(0,0)[r]{ 0}}
\put(1419.0,131.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(110.0,186.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(90,186){\makebox(0,0)[r]{ 10}}
\put(1419.0,186.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(110.0,241.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(90,241){\makebox(0,0)[r]{ 20}}
\put(1419.0,241.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(110.0,296.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(90,296){\makebox(0,0)[r]{ 30}}
\put(1419.0,296.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(110.0,351.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(90,351){\makebox(0,0)[r]{ 40}}
\put(1419.0,351.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(110.0,406.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(90,406){\makebox(0,0)[r]{ 50}}
\put(1419.0,406.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(110.0,461.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(90,461){\makebox(0,0)[r]{ 60}}
\put(1419.0,461.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(110.0,516.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(90,516){\makebox(0,0)[r]{ 70}}
\put(1419.0,516.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(110.0,571.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(90,571){\makebox(0,0)[r]{ 80}}
\put(1419.0,571.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(110.0,626.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(90,626){\makebox(0,0)[r]{ 90}}
\put(1419.0,626.0){\rule[-0.200pt]{4.818pt}{0.400pt}}
\put(110.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(110,90){\makebox(0,0){ 0}}
\put(110.0,606.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(376.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(376,90){\makebox(0,0){ 200}}
\put(376.0,606.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(642.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(642,90){\makebox(0,0){ 400}}
\put(642.0,606.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(907.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(907,90){\makebox(0,0){ 600}}
\put(907.0,606.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1173.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1173,90){\makebox(0,0){ 800}}
\put(1173.0,606.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1439.0,131.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(1439,90){\makebox(0,0){ 1000}}
\put(1439.0,606.0){\rule[-0.200pt]{0.400pt}{4.818pt}}
\put(110.0,131.0){\rule[-0.200pt]{0.400pt}{119.245pt}}
\put(110.0,131.0){\rule[-0.200pt]{320.156pt}{0.400pt}}
\put(1439.0,131.0){\rule[-0.200pt]{0.400pt}{119.245pt}}
\put(110.0,626.0){\rule[-0.200pt]{320.156pt}{0.400pt}}
\put(774,29){\makebox(0,0){$n$}}
\put(1279,254){\makebox(0,0)[r]{$\tilde{b}(n,0)$}}
\put(1299.0,254.0){\rule[-0.200pt]{24.090pt}{0.400pt}}
\put(110,131){\usebox{\plotpoint}}
\put(111.17,131){\rule{0.400pt}{4.500pt}}
\multiput(110.17,131.00)(2.000,12.660){2}{\rule{0.400pt}{2.250pt}}
\put(112.67,153){\rule{0.400pt}{2.650pt}}
\multiput(112.17,153.00)(1.000,5.500){2}{\rule{0.400pt}{1.325pt}}
\put(113.67,164){\rule{0.400pt}{3.132pt}}
\multiput(113.17,164.00)(1.000,6.500){2}{\rule{0.400pt}{1.566pt}}
\put(115.17,177){\rule{0.400pt}{2.300pt}}
\multiput(114.17,177.00)(2.000,6.226){2}{\rule{0.400pt}{1.150pt}}
\put(116.67,188){\rule{0.400pt}{2.168pt}}
\multiput(116.17,188.00)(1.000,4.500){2}{\rule{0.400pt}{1.084pt}}
\put(117.67,197){\rule{0.400pt}{1.686pt}}
\multiput(117.17,197.00)(1.000,3.500){2}{\rule{0.400pt}{0.843pt}}
\put(119.17,204){\rule{0.400pt}{1.500pt}}
\multiput(118.17,204.00)(2.000,3.887){2}{\rule{0.400pt}{0.750pt}}
\put(120.67,211){\rule{0.400pt}{1.204pt}}
\multiput(120.17,211.00)(1.000,2.500){2}{\rule{0.400pt}{0.602pt}}
\put(121.67,216){\rule{0.400pt}{1.445pt}}
\multiput(121.17,216.00)(1.000,3.000){2}{\rule{0.400pt}{0.723pt}}
\put(123.17,222){\rule{0.400pt}{0.900pt}}
\multiput(122.17,222.00)(2.000,2.132){2}{\rule{0.400pt}{0.450pt}}
\put(124.67,226){\rule{0.400pt}{1.204pt}}
\multiput(124.17,226.00)(1.000,2.500){2}{\rule{0.400pt}{0.602pt}}
\put(125.67,231){\rule{0.400pt}{0.964pt}}
\multiput(125.17,231.00)(1.000,2.000){2}{\rule{0.400pt}{0.482pt}}
\put(127.17,235){\rule{0.400pt}{0.700pt}}
\multiput(126.17,235.00)(2.000,1.547){2}{\rule{0.400pt}{0.350pt}}
\put(128.67,238){\rule{0.400pt}{0.964pt}}
\multiput(128.17,238.00)(1.000,2.000){2}{\rule{0.400pt}{0.482pt}}
\put(129.67,242){\rule{0.400pt}{0.723pt}}
\multiput(129.17,242.00)(1.000,1.500){2}{\rule{0.400pt}{0.361pt}}
\put(131.17,245){\rule{0.400pt}{0.900pt}}
\multiput(130.17,245.00)(2.000,2.132){2}{\rule{0.400pt}{0.450pt}}
\put(132.67,249){\rule{0.400pt}{0.723pt}}
\multiput(132.17,249.00)(1.000,1.500){2}{\rule{0.400pt}{0.361pt}}
\put(133.67,252){\rule{0.400pt}{0.723pt}}
\multiput(133.17,252.00)(1.000,1.500){2}{\rule{0.400pt}{0.361pt}}
\put(135.17,255){\rule{0.400pt}{0.700pt}}
\multiput(134.17,255.00)(2.000,1.547){2}{\rule{0.400pt}{0.350pt}}
\put(136.67,258){\rule{0.400pt}{0.482pt}}
\multiput(136.17,258.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(137.67,260){\rule{0.400pt}{0.723pt}}
\multiput(137.17,260.00)(1.000,1.500){2}{\rule{0.400pt}{0.361pt}}
\put(139.17,263){\rule{0.400pt}{0.700pt}}
\multiput(138.17,263.00)(2.000,1.547){2}{\rule{0.400pt}{0.350pt}}
\put(140.67,266){\rule{0.400pt}{0.482pt}}
\multiput(140.17,266.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(141.67,268){\rule{0.400pt}{0.723pt}}
\multiput(141.17,268.00)(1.000,1.500){2}{\rule{0.400pt}{0.361pt}}
\put(143,271.17){\rule{0.482pt}{0.400pt}}
\multiput(143.00,270.17)(1.000,2.000){2}{\rule{0.241pt}{0.400pt}}
\put(144.67,273){\rule{0.400pt}{0.482pt}}
\multiput(144.17,273.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(145.67,275){\rule{0.400pt}{0.482pt}}
\multiput(145.17,275.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(147.17,277){\rule{0.400pt}{0.700pt}}
\multiput(146.17,277.00)(2.000,1.547){2}{\rule{0.400pt}{0.350pt}}
\put(148.67,280){\rule{0.400pt}{0.482pt}}
\multiput(148.17,280.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(149.67,282){\rule{0.400pt}{0.482pt}}
\multiput(149.17,282.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(151,284.17){\rule{0.482pt}{0.400pt}}
\multiput(151.00,283.17)(1.000,2.000){2}{\rule{0.241pt}{0.400pt}}
\put(152.67,286){\rule{0.400pt}{0.482pt}}
\multiput(152.17,286.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(153.67,288){\rule{0.400pt}{0.482pt}}
\multiput(153.17,288.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(155,289.67){\rule{0.482pt}{0.400pt}}
\multiput(155.00,289.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(156.67,291){\rule{0.400pt}{0.482pt}}
\multiput(156.17,291.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(157.67,293){\rule{0.400pt}{0.482pt}}
\multiput(157.17,293.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(159,295.17){\rule{0.482pt}{0.400pt}}
\multiput(159.00,294.17)(1.000,2.000){2}{\rule{0.241pt}{0.400pt}}
\put(161,296.67){\rule{0.241pt}{0.400pt}}
\multiput(161.00,296.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(161.67,298){\rule{0.400pt}{0.482pt}}
\multiput(161.17,298.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(162.67,300){\rule{0.400pt}{0.482pt}}
\multiput(162.17,300.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(164,301.67){\rule{0.482pt}{0.400pt}}
\multiput(164.00,301.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(165.67,303){\rule{0.400pt}{0.482pt}}
\multiput(165.17,303.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(167,304.67){\rule{0.241pt}{0.400pt}}
\multiput(167.00,304.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(168,306.17){\rule{0.482pt}{0.400pt}}
\multiput(168.00,305.17)(1.000,2.000){2}{\rule{0.241pt}{0.400pt}}
\put(170,307.67){\rule{0.241pt}{0.400pt}}
\multiput(170.00,307.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(170.67,309){\rule{0.400pt}{0.482pt}}
\multiput(170.17,309.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(172,310.67){\rule{0.482pt}{0.400pt}}
\multiput(172.00,310.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(173.67,312){\rule{0.400pt}{0.482pt}}
\multiput(173.17,312.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(175,313.67){\rule{0.241pt}{0.400pt}}
\multiput(175.00,313.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(176,315.17){\rule{0.482pt}{0.400pt}}
\multiput(176.00,314.17)(1.000,2.000){2}{\rule{0.241pt}{0.400pt}}
\put(178,316.67){\rule{0.241pt}{0.400pt}}
\multiput(178.00,316.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(179,317.67){\rule{0.241pt}{0.400pt}}
\multiput(179.00,317.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(180,319.17){\rule{0.482pt}{0.400pt}}
\multiput(180.00,318.17)(1.000,2.000){2}{\rule{0.241pt}{0.400pt}}
\put(182,320.67){\rule{0.241pt}{0.400pt}}
\multiput(182.00,320.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(183,321.67){\rule{0.241pt}{0.400pt}}
\multiput(183.00,321.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(184,322.67){\rule{0.482pt}{0.400pt}}
\multiput(184.00,322.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(185.67,324){\rule{0.400pt}{0.482pt}}
\multiput(185.17,324.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(187,325.67){\rule{0.241pt}{0.400pt}}
\multiput(187.00,325.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(188,326.67){\rule{0.482pt}{0.400pt}}
\multiput(188.00,326.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(190,327.67){\rule{0.241pt}{0.400pt}}
\multiput(190.00,327.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(191,328.67){\rule{0.241pt}{0.400pt}}
\multiput(191.00,328.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(192,329.67){\rule{0.482pt}{0.400pt}}
\multiput(192.00,329.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(193.67,331){\rule{0.400pt}{0.482pt}}
\multiput(193.17,331.00)(1.000,1.000){2}{\rule{0.400pt}{0.241pt}}
\put(195,332.67){\rule{0.241pt}{0.400pt}}
\multiput(195.00,332.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(196,333.67){\rule{0.482pt}{0.400pt}}
\multiput(196.00,333.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(198,334.67){\rule{0.241pt}{0.400pt}}
\multiput(198.00,334.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(199,335.67){\rule{0.241pt}{0.400pt}}
\multiput(199.00,335.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(200,336.67){\rule{0.482pt}{0.400pt}}
\multiput(200.00,336.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(202,337.67){\rule{0.241pt}{0.400pt}}
\multiput(202.00,337.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(203,338.67){\rule{0.241pt}{0.400pt}}
\multiput(203.00,338.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(204,339.67){\rule{0.482pt}{0.400pt}}
\multiput(204.00,339.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(206,340.67){\rule{0.241pt}{0.400pt}}
\multiput(206.00,340.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(207,341.67){\rule{0.241pt}{0.400pt}}
\multiput(207.00,341.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(208,342.67){\rule{0.482pt}{0.400pt}}
\multiput(208.00,342.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(210,343.67){\rule{0.241pt}{0.400pt}}
\multiput(210.00,343.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(211,344.67){\rule{0.241pt}{0.400pt}}
\multiput(211.00,344.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(212,345.67){\rule{0.482pt}{0.400pt}}
\multiput(212.00,345.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(214,346.67){\rule{0.241pt}{0.400pt}}
\multiput(214.00,346.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(215,347.67){\rule{0.241pt}{0.400pt}}
\multiput(215.00,347.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(216,348.67){\rule{0.482pt}{0.400pt}}
\multiput(216.00,348.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(218,349.67){\rule{0.241pt}{0.400pt}}
\multiput(218.00,349.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(219,350.67){\rule{0.241pt}{0.400pt}}
\multiput(219.00,350.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(220,351.67){\rule{0.482pt}{0.400pt}}
\multiput(220.00,351.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(222,352.67){\rule{0.241pt}{0.400pt}}
\multiput(222.00,352.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(110.0,131.0){\usebox{\plotpoint}}
\put(224,353.67){\rule{0.482pt}{0.400pt}}
\multiput(224.00,353.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(226,354.67){\rule{0.241pt}{0.400pt}}
\multiput(226.00,354.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(227,355.67){\rule{0.241pt}{0.400pt}}
\multiput(227.00,355.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(228,356.67){\rule{0.482pt}{0.400pt}}
\multiput(228.00,356.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(230,357.67){\rule{0.241pt}{0.400pt}}
\multiput(230.00,357.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(231,358.67){\rule{0.241pt}{0.400pt}}
\multiput(231.00,358.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(223.0,354.0){\usebox{\plotpoint}}
\put(234,359.67){\rule{0.241pt}{0.400pt}}
\multiput(234.00,359.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(235,360.67){\rule{0.241pt}{0.400pt}}
\multiput(235.00,360.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(236,361.67){\rule{0.482pt}{0.400pt}}
\multiput(236.00,361.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(238,362.67){\rule{0.241pt}{0.400pt}}
\multiput(238.00,362.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(232.0,360.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(240,363.67){\rule{0.482pt}{0.400pt}}
\multiput(240.00,363.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(242,364.67){\rule{0.241pt}{0.400pt}}
\multiput(242.00,364.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(243,365.67){\rule{0.241pt}{0.400pt}}
\multiput(243.00,365.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(244,366.67){\rule{0.482pt}{0.400pt}}
\multiput(244.00,366.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(239.0,364.0){\usebox{\plotpoint}}
\put(247,367.67){\rule{0.241pt}{0.400pt}}
\multiput(247.00,367.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(248,368.67){\rule{0.482pt}{0.400pt}}
\multiput(248.00,368.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(250,369.67){\rule{0.241pt}{0.400pt}}
\multiput(250.00,369.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(246.0,368.0){\usebox{\plotpoint}}
\put(252,370.67){\rule{0.482pt}{0.400pt}}
\multiput(252.00,370.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(254,371.67){\rule{0.241pt}{0.400pt}}
\multiput(254.00,371.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(251.0,371.0){\usebox{\plotpoint}}
\put(256,372.67){\rule{0.482pt}{0.400pt}}
\multiput(256.00,372.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(258,373.67){\rule{0.241pt}{0.400pt}}
\multiput(258.00,373.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(259,374.67){\rule{0.241pt}{0.400pt}}
\multiput(259.00,374.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(255.0,373.0){\usebox{\plotpoint}}
\put(262,375.67){\rule{0.241pt}{0.400pt}}
\multiput(262.00,375.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(263,376.67){\rule{0.241pt}{0.400pt}}
\multiput(263.00,376.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(260.0,376.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(265,377.67){\rule{0.482pt}{0.400pt}}
\multiput(265.00,377.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(267,378.67){\rule{0.241pt}{0.400pt}}
\multiput(267.00,378.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(264.0,378.0){\usebox{\plotpoint}}
\put(269,379.67){\rule{0.482pt}{0.400pt}}
\multiput(269.00,379.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(271,380.67){\rule{0.241pt}{0.400pt}}
\multiput(271.00,380.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(268.0,380.0){\usebox{\plotpoint}}
\put(273,381.67){\rule{0.482pt}{0.400pt}}
\multiput(273.00,381.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(275,382.67){\rule{0.241pt}{0.400pt}}
\multiput(275.00,382.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(272.0,382.0){\usebox{\plotpoint}}
\put(277,383.67){\rule{0.482pt}{0.400pt}}
\multiput(277.00,383.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(279,384.67){\rule{0.241pt}{0.400pt}}
\multiput(279.00,384.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(276.0,384.0){\usebox{\plotpoint}}
\put(281,385.67){\rule{0.482pt}{0.400pt}}
\multiput(281.00,385.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(280.0,386.0){\usebox{\plotpoint}}
\put(284,386.67){\rule{0.241pt}{0.400pt}}
\multiput(284.00,386.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(285,387.67){\rule{0.482pt}{0.400pt}}
\multiput(285.00,387.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(283.0,387.0){\usebox{\plotpoint}}
\put(288,388.67){\rule{0.241pt}{0.400pt}}
\multiput(288.00,388.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(287.0,389.0){\usebox{\plotpoint}}
\put(291,389.67){\rule{0.241pt}{0.400pt}}
\multiput(291.00,389.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(292,390.67){\rule{0.241pt}{0.400pt}}
\multiput(292.00,390.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(289.0,390.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(295,391.67){\rule{0.241pt}{0.400pt}}
\multiput(295.00,391.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(293.0,392.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(297,392.67){\rule{0.482pt}{0.400pt}}
\multiput(297.00,392.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(299,393.67){\rule{0.241pt}{0.400pt}}
\multiput(299.00,393.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(296.0,393.0){\usebox{\plotpoint}}
\put(301,394.67){\rule{0.482pt}{0.400pt}}
\multiput(301.00,394.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(300.0,395.0){\usebox{\plotpoint}}
\put(304,395.67){\rule{0.241pt}{0.400pt}}
\multiput(304.00,395.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(303.0,396.0){\usebox{\plotpoint}}
\put(307,396.67){\rule{0.241pt}{0.400pt}}
\multiput(307.00,396.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(305.0,397.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(309,397.67){\rule{0.482pt}{0.400pt}}
\multiput(309.00,397.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(311,398.67){\rule{0.241pt}{0.400pt}}
\multiput(311.00,398.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(308.0,398.0){\usebox{\plotpoint}}
\put(313,399.67){\rule{0.482pt}{0.400pt}}
\multiput(313.00,399.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(312.0,400.0){\usebox{\plotpoint}}
\put(316,400.67){\rule{0.241pt}{0.400pt}}
\multiput(316.00,400.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(315.0,401.0){\usebox{\plotpoint}}
\put(319,401.67){\rule{0.241pt}{0.400pt}}
\multiput(319.00,401.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(317.0,402.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(321,402.67){\rule{0.482pt}{0.400pt}}
\multiput(321.00,402.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(320.0,403.0){\usebox{\plotpoint}}
\put(324,403.67){\rule{0.241pt}{0.400pt}}
\multiput(324.00,403.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(323.0,404.0){\usebox{\plotpoint}}
\put(327,404.67){\rule{0.241pt}{0.400pt}}
\multiput(327.00,404.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(325.0,405.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(329,405.67){\rule{0.482pt}{0.400pt}}
\multiput(329.00,405.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(328.0,406.0){\usebox{\plotpoint}}
\put(332,406.67){\rule{0.241pt}{0.400pt}}
\multiput(332.00,406.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(331.0,407.0){\usebox{\plotpoint}}
\put(335,407.67){\rule{0.241pt}{0.400pt}}
\multiput(335.00,407.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(333.0,408.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(337,408.67){\rule{0.482pt}{0.400pt}}
\multiput(337.00,408.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(336.0,409.0){\usebox{\plotpoint}}
\put(340,409.67){\rule{0.241pt}{0.400pt}}
\multiput(340.00,409.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(339.0,410.0){\usebox{\plotpoint}}
\put(343,410.67){\rule{0.241pt}{0.400pt}}
\multiput(343.00,410.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(341.0,411.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(345,411.67){\rule{0.482pt}{0.400pt}}
\multiput(345.00,411.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(344.0,412.0){\usebox{\plotpoint}}
\put(348,412.67){\rule{0.241pt}{0.400pt}}
\multiput(348.00,412.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(347.0,413.0){\usebox{\plotpoint}}
\put(351,413.67){\rule{0.241pt}{0.400pt}}
\multiput(351.00,413.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(349.0,414.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(353,414.67){\rule{0.482pt}{0.400pt}}
\multiput(353.00,414.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(352.0,415.0){\usebox{\plotpoint}}
\put(356,415.67){\rule{0.241pt}{0.400pt}}
\multiput(356.00,415.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(355.0,416.0){\usebox{\plotpoint}}
\put(360,416.67){\rule{0.241pt}{0.400pt}}
\multiput(360.00,416.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(357.0,417.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(363,417.67){\rule{0.241pt}{0.400pt}}
\multiput(363.00,417.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(361.0,418.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(365,418.67){\rule{0.241pt}{0.400pt}}
\multiput(365.00,418.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(364.0,419.0){\usebox{\plotpoint}}
\put(368,419.67){\rule{0.241pt}{0.400pt}}
\multiput(368.00,419.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(366.0,420.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(372,420.67){\rule{0.241pt}{0.400pt}}
\multiput(372.00,420.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(369.0,421.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(374,421.67){\rule{0.482pt}{0.400pt}}
\multiput(374.00,421.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(373.0,422.0){\usebox{\plotpoint}}
\put(377,422.67){\rule{0.241pt}{0.400pt}}
\multiput(377.00,422.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(376.0,423.0){\usebox{\plotpoint}}
\put(381,423.67){\rule{0.241pt}{0.400pt}}
\multiput(381.00,423.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(378.0,424.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(384,424.67){\rule{0.241pt}{0.400pt}}
\multiput(384.00,424.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(382.0,425.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(386,425.67){\rule{0.482pt}{0.400pt}}
\multiput(386.00,425.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(385.0,426.0){\usebox{\plotpoint}}
\put(390,426.67){\rule{0.482pt}{0.400pt}}
\multiput(390.00,426.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(388.0,427.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(393,427.67){\rule{0.241pt}{0.400pt}}
\multiput(393.00,427.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(392.0,428.0){\usebox{\plotpoint}}
\put(397,428.67){\rule{0.241pt}{0.400pt}}
\multiput(397.00,428.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(394.0,429.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(400,429.67){\rule{0.241pt}{0.400pt}}
\multiput(400.00,429.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(398.0,430.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(404,430.67){\rule{0.241pt}{0.400pt}}
\multiput(404.00,430.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(401.0,431.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(406,431.67){\rule{0.482pt}{0.400pt}}
\multiput(406.00,431.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(405.0,432.0){\usebox{\plotpoint}}
\put(410,432.67){\rule{0.482pt}{0.400pt}}
\multiput(410.00,432.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(408.0,433.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(414,433.67){\rule{0.482pt}{0.400pt}}
\multiput(414.00,433.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(412.0,434.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(417,434.67){\rule{0.241pt}{0.400pt}}
\multiput(417.00,434.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(416.0,435.0){\usebox{\plotpoint}}
\put(421,435.67){\rule{0.241pt}{0.400pt}}
\multiput(421.00,435.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(418.0,436.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(425,436.67){\rule{0.241pt}{0.400pt}}
\multiput(425.00,436.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(422.0,437.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(428,437.67){\rule{0.241pt}{0.400pt}}
\multiput(428.00,437.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(426.0,438.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(432,438.67){\rule{0.241pt}{0.400pt}}
\multiput(432.00,438.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(429.0,439.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(436,439.67){\rule{0.241pt}{0.400pt}}
\multiput(436.00,439.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(433.0,440.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(440,440.67){\rule{0.241pt}{0.400pt}}
\multiput(440.00,440.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(437.0,441.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(442,441.67){\rule{0.482pt}{0.400pt}}
\multiput(442.00,441.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(441.0,442.0){\usebox{\plotpoint}}
\put(446,442.67){\rule{0.482pt}{0.400pt}}
\multiput(446.00,442.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(444.0,443.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(450,443.67){\rule{0.482pt}{0.400pt}}
\multiput(450.00,443.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(448.0,444.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(454,444.67){\rule{0.482pt}{0.400pt}}
\multiput(454.00,444.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(452.0,445.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(458,445.67){\rule{0.482pt}{0.400pt}}
\multiput(458.00,445.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(456.0,446.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(462,446.67){\rule{0.482pt}{0.400pt}}
\multiput(462.00,446.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(460.0,447.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(466,447.67){\rule{0.482pt}{0.400pt}}
\multiput(466.00,447.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(464.0,448.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(470,448.67){\rule{0.241pt}{0.400pt}}
\multiput(470.00,448.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(468.0,449.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(474,449.67){\rule{0.241pt}{0.400pt}}
\multiput(474.00,449.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(471.0,450.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(478,450.67){\rule{0.241pt}{0.400pt}}
\multiput(478.00,450.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(475.0,451.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(482,451.67){\rule{0.241pt}{0.400pt}}
\multiput(482.00,451.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(479.0,452.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(486,452.67){\rule{0.241pt}{0.400pt}}
\multiput(486.00,452.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(483.0,453.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(490,453.67){\rule{0.241pt}{0.400pt}}
\multiput(490.00,453.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(487.0,454.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(494,454.67){\rule{0.241pt}{0.400pt}}
\multiput(494.00,454.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(491.0,455.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(499,455.67){\rule{0.482pt}{0.400pt}}
\multiput(499.00,455.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(495.0,456.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(503,456.67){\rule{0.482pt}{0.400pt}}
\multiput(503.00,456.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(501.0,457.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(507,457.67){\rule{0.482pt}{0.400pt}}
\multiput(507.00,457.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(505.0,458.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(513,458.67){\rule{0.241pt}{0.400pt}}
\multiput(513.00,458.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(509.0,459.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(517,459.67){\rule{0.241pt}{0.400pt}}
\multiput(517.00,459.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(514.0,460.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(521,460.67){\rule{0.241pt}{0.400pt}}
\multiput(521.00,460.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(518.0,461.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(526,461.67){\rule{0.241pt}{0.400pt}}
\multiput(526.00,461.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(522.0,462.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(530,462.67){\rule{0.241pt}{0.400pt}}
\multiput(530.00,462.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(527.0,463.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(535,463.67){\rule{0.482pt}{0.400pt}}
\multiput(535.00,463.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(531.0,464.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(539,464.67){\rule{0.482pt}{0.400pt}}
\multiput(539.00,464.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(537.0,465.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(545,465.67){\rule{0.241pt}{0.400pt}}
\multiput(545.00,465.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(541.0,466.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(549,466.67){\rule{0.241pt}{0.400pt}}
\multiput(549.00,466.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(546.0,467.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(554,467.67){\rule{0.241pt}{0.400pt}}
\multiput(554.00,467.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(550.0,468.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(559,468.67){\rule{0.482pt}{0.400pt}}
\multiput(559.00,468.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(555.0,469.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(563,469.67){\rule{0.482pt}{0.400pt}}
\multiput(563.00,469.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(561.0,470.0){\rule[-0.200pt]{0.482pt}{0.400pt}}
\put(569,470.67){\rule{0.241pt}{0.400pt}}
\multiput(569.00,470.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(565.0,471.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(574,471.67){\rule{0.241pt}{0.400pt}}
\multiput(574.00,471.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(570.0,472.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(578,472.67){\rule{0.241pt}{0.400pt}}
\multiput(578.00,472.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(575.0,473.0){\rule[-0.200pt]{0.723pt}{0.400pt}}
\put(583,473.67){\rule{0.241pt}{0.400pt}}
\multiput(583.00,473.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(579.0,474.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(588,474.67){\rule{0.482pt}{0.400pt}}
\multiput(588.00,474.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(584.0,475.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(594,475.67){\rule{0.241pt}{0.400pt}}
\multiput(594.00,475.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(590.0,476.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(599,476.67){\rule{0.241pt}{0.400pt}}
\multiput(599.00,476.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(595.0,477.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(604,477.67){\rule{0.482pt}{0.400pt}}
\multiput(604.00,477.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(600.0,478.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(610,478.67){\rule{0.241pt}{0.400pt}}
\multiput(610.00,478.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(606.0,479.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(615,479.67){\rule{0.241pt}{0.400pt}}
\multiput(615.00,479.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(611.0,480.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(620,480.67){\rule{0.482pt}{0.400pt}}
\multiput(620.00,480.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(616.0,481.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(626,481.67){\rule{0.241pt}{0.400pt}}
\multiput(626.00,481.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(622.0,482.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(631,482.67){\rule{0.241pt}{0.400pt}}
\multiput(631.00,482.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(627.0,483.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(638,483.67){\rule{0.241pt}{0.400pt}}
\multiput(638.00,483.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(632.0,484.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(643,484.67){\rule{0.241pt}{0.400pt}}
\multiput(643.00,484.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(639.0,485.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(648,485.67){\rule{0.482pt}{0.400pt}}
\multiput(648.00,485.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(644.0,486.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(654,486.67){\rule{0.241pt}{0.400pt}}
\multiput(654.00,486.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(650.0,487.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(660,487.67){\rule{0.482pt}{0.400pt}}
\multiput(660.00,487.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(655.0,488.0){\rule[-0.200pt]{1.204pt}{0.400pt}}
\put(666,488.67){\rule{0.241pt}{0.400pt}}
\multiput(666.00,488.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(662.0,489.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(672,489.67){\rule{0.241pt}{0.400pt}}
\multiput(672.00,489.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(667.0,490.0){\rule[-0.200pt]{1.204pt}{0.400pt}}
\put(677,490.67){\rule{0.482pt}{0.400pt}}
\multiput(677.00,490.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(673.0,491.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(684,491.67){\rule{0.241pt}{0.400pt}}
\multiput(684.00,491.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(679.0,492.0){\rule[-0.200pt]{1.204pt}{0.400pt}}
\put(689,492.67){\rule{0.482pt}{0.400pt}}
\multiput(689.00,492.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(685.0,493.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(696,493.67){\rule{0.241pt}{0.400pt}}
\multiput(696.00,493.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(691.0,494.0){\rule[-0.200pt]{1.204pt}{0.400pt}}
\put(701,494.67){\rule{0.482pt}{0.400pt}}
\multiput(701.00,494.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(697.0,495.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(708,495.67){\rule{0.241pt}{0.400pt}}
\multiput(708.00,495.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(703.0,496.0){\rule[-0.200pt]{1.204pt}{0.400pt}}
\put(715,496.67){\rule{0.241pt}{0.400pt}}
\multiput(715.00,496.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(709.0,497.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(721,497.67){\rule{0.482pt}{0.400pt}}
\multiput(721.00,497.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(716.0,498.0){\rule[-0.200pt]{1.204pt}{0.400pt}}
\put(727,498.67){\rule{0.241pt}{0.400pt}}
\multiput(727.00,498.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(723.0,499.0){\rule[-0.200pt]{0.964pt}{0.400pt}}
\put(733,499.67){\rule{0.482pt}{0.400pt}}
\multiput(733.00,499.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(728.0,500.0){\rule[-0.200pt]{1.204pt}{0.400pt}}
\put(740,500.67){\rule{0.241pt}{0.400pt}}
\multiput(740.00,500.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(735.0,501.0){\rule[-0.200pt]{1.204pt}{0.400pt}}
\put(747,501.67){\rule{0.241pt}{0.400pt}}
\multiput(747.00,501.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(741.0,502.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(753,502.67){\rule{0.482pt}{0.400pt}}
\multiput(753.00,502.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(748.0,503.0){\rule[-0.200pt]{1.204pt}{0.400pt}}
\put(760,503.67){\rule{0.241pt}{0.400pt}}
\multiput(760.00,503.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(755.0,504.0){\rule[-0.200pt]{1.204pt}{0.400pt}}
\put(767,504.67){\rule{0.241pt}{0.400pt}}
\multiput(767.00,504.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(761.0,505.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(773,505.67){\rule{0.482pt}{0.400pt}}
\multiput(773.00,505.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(768.0,506.0){\rule[-0.200pt]{1.204pt}{0.400pt}}
\put(781,506.67){\rule{0.241pt}{0.400pt}}
\multiput(781.00,506.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(775.0,507.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(788,507.67){\rule{0.241pt}{0.400pt}}
\multiput(788.00,507.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(782.0,508.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(794,508.67){\rule{0.482pt}{0.400pt}}
\multiput(794.00,508.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(789.0,509.0){\rule[-0.200pt]{1.204pt}{0.400pt}}
\put(801,509.67){\rule{0.241pt}{0.400pt}}
\multiput(801.00,509.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(796.0,510.0){\rule[-0.200pt]{1.204pt}{0.400pt}}
\put(809,510.67){\rule{0.241pt}{0.400pt}}
\multiput(809.00,510.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(802.0,511.0){\rule[-0.200pt]{1.686pt}{0.400pt}}
\put(816,511.67){\rule{0.241pt}{0.400pt}}
\multiput(816.00,511.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(810.0,512.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(824,512.67){\rule{0.241pt}{0.400pt}}
\multiput(824.00,512.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(817.0,513.0){\rule[-0.200pt]{1.686pt}{0.400pt}}
\put(830,513.67){\rule{0.482pt}{0.400pt}}
\multiput(830.00,513.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(825.0,514.0){\rule[-0.200pt]{1.204pt}{0.400pt}}
\put(838,514.67){\rule{0.482pt}{0.400pt}}
\multiput(838.00,514.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(832.0,515.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(845,515.67){\rule{0.241pt}{0.400pt}}
\multiput(845.00,515.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(840.0,516.0){\rule[-0.200pt]{1.204pt}{0.400pt}}
\put(853,516.67){\rule{0.241pt}{0.400pt}}
\multiput(853.00,516.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(846.0,517.0){\rule[-0.200pt]{1.686pt}{0.400pt}}
\put(861,517.67){\rule{0.241pt}{0.400pt}}
\multiput(861.00,517.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(854.0,518.0){\rule[-0.200pt]{1.686pt}{0.400pt}}
\put(869,518.67){\rule{0.241pt}{0.400pt}}
\multiput(869.00,518.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(862.0,519.0){\rule[-0.200pt]{1.686pt}{0.400pt}}
\put(876,519.67){\rule{0.241pt}{0.400pt}}
\multiput(876.00,519.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(870.0,520.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(883,520.67){\rule{0.482pt}{0.400pt}}
\multiput(883.00,520.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(877.0,521.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(891,521.67){\rule{0.482pt}{0.400pt}}
\multiput(891.00,521.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(885.0,522.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(899,522.67){\rule{0.482pt}{0.400pt}}
\multiput(899.00,522.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(893.0,523.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(907,523.67){\rule{0.482pt}{0.400pt}}
\multiput(907.00,523.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(901.0,524.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(915,524.67){\rule{0.482pt}{0.400pt}}
\multiput(915.00,524.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(909.0,525.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(923,525.67){\rule{0.482pt}{0.400pt}}
\multiput(923.00,525.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(917.0,526.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(933,526.67){\rule{0.241pt}{0.400pt}}
\multiput(933.00,526.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(925.0,527.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(941,527.67){\rule{0.241pt}{0.400pt}}
\multiput(941.00,527.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(934.0,528.0){\rule[-0.200pt]{1.686pt}{0.400pt}}
\put(949,528.67){\rule{0.241pt}{0.400pt}}
\multiput(949.00,528.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(942.0,529.0){\rule[-0.200pt]{1.686pt}{0.400pt}}
\put(958,529.67){\rule{0.241pt}{0.400pt}}
\multiput(958.00,529.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(950.0,530.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(966,530.67){\rule{0.241pt}{0.400pt}}
\multiput(966.00,530.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(959.0,531.0){\rule[-0.200pt]{1.686pt}{0.400pt}}
\put(975,531.67){\rule{0.482pt}{0.400pt}}
\multiput(975.00,531.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(967.0,532.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(983,532.67){\rule{0.241pt}{0.400pt}}
\multiput(983.00,532.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(977.0,533.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(992,533.67){\rule{0.482pt}{0.400pt}}
\multiput(992.00,533.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(984.0,534.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(1000,534.67){\rule{0.482pt}{0.400pt}}
\multiput(1000.00,534.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(994.0,535.0){\rule[-0.200pt]{1.445pt}{0.400pt}}
\put(1010,535.67){\rule{0.241pt}{0.400pt}}
\multiput(1010.00,535.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1002.0,536.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(1019,536.67){\rule{0.241pt}{0.400pt}}
\multiput(1019.00,536.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1011.0,537.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(1028,537.67){\rule{0.482pt}{0.400pt}}
\multiput(1028.00,537.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(1020.0,538.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(1038,538.67){\rule{0.241pt}{0.400pt}}
\multiput(1038.00,538.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1030.0,539.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(1047,539.67){\rule{0.241pt}{0.400pt}}
\multiput(1047.00,539.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1039.0,540.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(1056,540.67){\rule{0.482pt}{0.400pt}}
\multiput(1056.00,540.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(1048.0,541.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(1066,541.67){\rule{0.241pt}{0.400pt}}
\multiput(1066.00,541.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1058.0,542.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(1075,542.67){\rule{0.241pt}{0.400pt}}
\multiput(1075.00,542.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1067.0,543.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(1084,543.67){\rule{0.241pt}{0.400pt}}
\multiput(1084.00,543.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1076.0,544.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(1093,544.67){\rule{0.482pt}{0.400pt}}
\multiput(1093.00,544.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(1085.0,545.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(1104,545.67){\rule{0.241pt}{0.400pt}}
\multiput(1104.00,545.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1095.0,546.0){\rule[-0.200pt]{2.168pt}{0.400pt}}
\put(1113,546.67){\rule{0.482pt}{0.400pt}}
\multiput(1113.00,546.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(1105.0,547.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(1124,547.67){\rule{0.241pt}{0.400pt}}
\multiput(1124.00,547.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1115.0,548.0){\rule[-0.200pt]{2.168pt}{0.400pt}}
\put(1133,548.67){\rule{0.482pt}{0.400pt}}
\multiput(1133.00,548.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(1125.0,549.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(1144,549.67){\rule{0.241pt}{0.400pt}}
\multiput(1144.00,549.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1135.0,550.0){\rule[-0.200pt]{2.168pt}{0.400pt}}
\put(1153,550.67){\rule{0.482pt}{0.400pt}}
\multiput(1153.00,550.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(1145.0,551.0){\rule[-0.200pt]{1.927pt}{0.400pt}}
\put(1164,551.67){\rule{0.241pt}{0.400pt}}
\multiput(1164.00,551.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1155.0,552.0){\rule[-0.200pt]{2.168pt}{0.400pt}}
\put(1175,552.67){\rule{0.241pt}{0.400pt}}
\multiput(1175.00,552.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1165.0,553.0){\rule[-0.200pt]{2.409pt}{0.400pt}}
\put(1185,553.67){\rule{0.241pt}{0.400pt}}
\multiput(1185.00,553.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1176.0,554.0){\rule[-0.200pt]{2.168pt}{0.400pt}}
\put(1196,554.67){\rule{0.241pt}{0.400pt}}
\multiput(1196.00,554.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1186.0,555.0){\rule[-0.200pt]{2.409pt}{0.400pt}}
\put(1206,555.67){\rule{0.482pt}{0.400pt}}
\multiput(1206.00,555.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(1197.0,556.0){\rule[-0.200pt]{2.168pt}{0.400pt}}
\put(1217,556.67){\rule{0.241pt}{0.400pt}}
\multiput(1217.00,556.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1208.0,557.0){\rule[-0.200pt]{2.168pt}{0.400pt}}
\put(1228,557.67){\rule{0.241pt}{0.400pt}}
\multiput(1228.00,557.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1218.0,558.0){\rule[-0.200pt]{2.409pt}{0.400pt}}
\put(1238,558.67){\rule{0.482pt}{0.400pt}}
\multiput(1238.00,558.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(1229.0,559.0){\rule[-0.200pt]{2.168pt}{0.400pt}}
\put(1249,559.67){\rule{0.241pt}{0.400pt}}
\multiput(1249.00,559.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1240.0,560.0){\rule[-0.200pt]{2.168pt}{0.400pt}}
\put(1261,560.67){\rule{0.241pt}{0.400pt}}
\multiput(1261.00,560.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1250.0,561.0){\rule[-0.200pt]{2.650pt}{0.400pt}}
\put(1272,561.67){\rule{0.241pt}{0.400pt}}
\multiput(1272.00,561.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1262.0,562.0){\rule[-0.200pt]{2.409pt}{0.400pt}}
\put(1284,562.67){\rule{0.241pt}{0.400pt}}
\multiput(1284.00,562.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1273.0,563.0){\rule[-0.200pt]{2.650pt}{0.400pt}}
\put(1294,563.67){\rule{0.241pt}{0.400pt}}
\multiput(1294.00,563.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1285.0,564.0){\rule[-0.200pt]{2.168pt}{0.400pt}}
\put(1306,564.67){\rule{0.241pt}{0.400pt}}
\multiput(1306.00,564.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1295.0,565.0){\rule[-0.200pt]{2.650pt}{0.400pt}}
\put(1318,565.67){\rule{0.241pt}{0.400pt}}
\multiput(1318.00,565.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1307.0,566.0){\rule[-0.200pt]{2.650pt}{0.400pt}}
\put(1329,566.67){\rule{0.241pt}{0.400pt}}
\multiput(1329.00,566.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1319.0,567.0){\rule[-0.200pt]{2.409pt}{0.400pt}}
\put(1341,567.67){\rule{0.241pt}{0.400pt}}
\multiput(1341.00,567.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1330.0,568.0){\rule[-0.200pt]{2.650pt}{0.400pt}}
\put(1353,568.67){\rule{0.241pt}{0.400pt}}
\multiput(1353.00,568.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1342.0,569.0){\rule[-0.200pt]{2.650pt}{0.400pt}}
\put(1365,569.67){\rule{0.241pt}{0.400pt}}
\multiput(1365.00,569.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1354.0,570.0){\rule[-0.200pt]{2.650pt}{0.400pt}}
\put(1377,570.67){\rule{0.241pt}{0.400pt}}
\multiput(1377.00,570.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1366.0,571.0){\rule[-0.200pt]{2.650pt}{0.400pt}}
\put(1388,571.67){\rule{0.482pt}{0.400pt}}
\multiput(1388.00,571.17)(1.000,1.000){2}{\rule{0.241pt}{0.400pt}}
\put(1378.0,572.0){\rule[-0.200pt]{2.409pt}{0.400pt}}
\put(1402,572.67){\rule{0.241pt}{0.400pt}}
\multiput(1402.00,572.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1390.0,573.0){\rule[-0.200pt]{2.891pt}{0.400pt}}
\put(1414,573.67){\rule{0.241pt}{0.400pt}}
\multiput(1414.00,573.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1403.0,574.0){\rule[-0.200pt]{2.650pt}{0.400pt}}
\put(1426,574.67){\rule{0.241pt}{0.400pt}}
\multiput(1426.00,574.17)(0.500,1.000){2}{\rule{0.120pt}{0.400pt}}
\put(1415.0,575.0){\rule[-0.200pt]{2.650pt}{0.400pt}}
\put(1427.0,576.0){\rule[-0.200pt]{2.891pt}{0.400pt}}
\put(1279,213){\makebox(0,0)[r]{$b_*(n,0)$}}
\multiput(1299,213)(20.756,0.000){5}{\usebox{\plotpoint}}
\put(1399,213){\usebox{\plotpoint}}
\put(110,131){\usebox{\plotpoint}}
\put(110.00,131.00){\usebox{\plotpoint}}
\put(112.79,150.67){\usebox{\plotpoint}}
\put(115.80,171.18){\usebox{\plotpoint}}
\put(119.98,191.45){\usebox{\plotpoint}}
\put(125.65,211.27){\usebox{\plotpoint}}
\put(132.78,230.56){\usebox{\plotpoint}}
\put(141.59,249.19){\usebox{\plotpoint}}
\put(151.93,266.93){\usebox{\plotpoint}}
\put(163.71,283.41){\usebox{\plotpoint}}
\put(177.30,298.30){\usebox{\plotpoint}}
\put(192.09,312.05){\usebox{\plotpoint}}
\put(207.85,324.85){\usebox{\plotpoint}}
\put(224.62,336.31){\usebox{\plotpoint}}
\put(241.65,346.82){\usebox{\plotpoint}}
\put(258.83,356.83){\usebox{\plotpoint}}
\put(276.31,366.00){\usebox{\plotpoint}}
\put(294.29,374.00){\usebox{\plotpoint}}
\put(312.27,382.00){\usebox{\plotpoint}}
\put(330.69,388.85){\usebox{\plotpoint}}
\put(348.91,395.91){\usebox{\plotpoint}}
\put(367.50,402.00){\usebox{\plotpoint}}
\put(385.95,408.00){\usebox{\plotpoint}}
\put(404.57,413.57){\usebox{\plotpoint}}
\put(423.43,419.00){\usebox{\plotpoint}}
\put(442.11,424.05){\usebox{\plotpoint}}
\put(461.69,429.00){\usebox{\plotpoint}}
\put(480.73,434.00){\usebox{\plotpoint}}
\put(499.90,438.45){\usebox{\plotpoint}}
\put(519.23,443.00){\usebox{\plotpoint}}
\put(538.51,447.00){\usebox{\plotpoint}}
\put(557.78,451.00){\usebox{\plotpoint}}
\put(577.24,455.00){\usebox{\plotpoint}}
\put(596.52,459.00){\usebox{\plotpoint}}
\put(615.85,462.85){\usebox{\plotpoint}}
\put(635.66,466.00){\usebox{\plotpoint}}
\put(655.25,469.25){\usebox{\plotpoint}}
\put(674.63,473.00){\usebox{\plotpoint}}
\put(694.50,476.00){\usebox{\plotpoint}}
\put(714.01,479.00){\usebox{\plotpoint}}
\put(733.63,482.31){\usebox{\plotpoint}}
\put(753.35,485.18){\usebox{\plotpoint}}
\put(773.08,488.00){\usebox{\plotpoint}}
\put(792.60,491.00){\usebox{\plotpoint}}
\put(812.47,494.00){\usebox{\plotpoint}}
\put(832.16,497.00){\usebox{\plotpoint}}
\put(852.44,499.00){\usebox{\plotpoint}}
\put(871.95,502.00){\usebox{\plotpoint}}
\put(891.88,504.00){\usebox{\plotpoint}}
\put(911.39,507.00){\usebox{\plotpoint}}
\put(931.32,509.00){\usebox{\plotpoint}}
\put(950.88,511.88){\usebox{\plotpoint}}
\put(970.76,514.00){\usebox{\plotpoint}}
\put(990.87,516.00){\usebox{\plotpoint}}
\put(1010.69,518.69){\usebox{\plotpoint}}
\put(1030.66,521.00){\usebox{\plotpoint}}
\put(1050.59,523.00){\usebox{\plotpoint}}
\put(1070.69,525.00){\usebox{\plotpoint}}
\put(1090.62,527.00){\usebox{\plotpoint}}
\put(1110.55,529.00){\usebox{\plotpoint}}
\put(1130.65,531.00){\usebox{\plotpoint}}
\put(1150.76,533.00){\usebox{\plotpoint}}
\put(1170.69,535.00){\usebox{\plotpoint}}
\put(1190.61,537.00){\usebox{\plotpoint}}
\put(1210.72,539.00){\usebox{\plotpoint}}
\put(1230.65,541.00){\usebox{\plotpoint}}
\put(1251.04,542.52){\usebox{\plotpoint}}
\put(1271.27,544.00){\usebox{\plotpoint}}
\put(1291.20,546.00){\usebox{\plotpoint}}
\put(1311.30,548.00){\usebox{\plotpoint}}
\put(1331.23,550.00){\usebox{\plotpoint}}
\put(1351.57,551.00){\usebox{\plotpoint}}
\put(1371.50,553.00){\usebox{\plotpoint}}
\put(1391.43,555.00){\usebox{\plotpoint}}
\put(1411.77,556.00){\usebox{\plotpoint}}
\put(1431.69,558.00){\usebox{\plotpoint}}
\put(1439,558){\usebox{\plotpoint}}
\sbox{\plotpoint}{\rule[-0.500pt]{1.000pt}{1.000pt}}%
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\put(1279,172){\makebox(0,0)[r]{Asymptotic estimate of
$\tilde{b}(n,0)$}}
\sbox{\plotpoint}{\rule[-0.500pt]{1.000pt}{1.000pt}}%
\multiput(1299,172)(20.756,0.000){5}{\usebox{\plotpoint}}
\put(1399,172){\usebox{\plotpoint}}
\put(111,131){\usebox{\plotpoint}}
\put(111.00,131.00){\usebox{\plotpoint}}
\put(113.30,151.63){\usebox{\plotpoint}}
\put(115.50,172.25){\usebox{\plotpoint}}
\put(119.22,192.65){\usebox{\plotpoint}}
\put(124.82,212.56){\usebox{\plotpoint}}
\put(131.15,232.23){\usebox{\plotpoint}}
\put(140.48,250.48){\usebox{\plotpoint}}
\put(150.60,268.19){\usebox{\plotpoint}}
\put(163.19,284.37){\usebox{\plotpoint}}
\put(176.61,299.31){\usebox{\plotpoint}}
\put(191.84,312.84){\usebox{\plotpoint}}
\put(208.24,325.12){\usebox{\plotpoint}}
\put(225.00,336.00){\usebox{\plotpoint}}
\put(242.11,346.11){\usebox{\plotpoint}}
\put(259.38,355.38){\usebox{\plotpoint}}
\put(277.09,364.00){\usebox{\plotpoint}}
\put(295.22,371.22){\usebox{\plotpoint}}
\put(313.28,379.00){\usebox{\plotpoint}}
\put(331.64,385.64){\usebox{\plotpoint}}
\put(350.30,392.00){\usebox{\plotpoint}}
\put(369.10,398.00){\usebox{\plotpoint}}
\put(387.76,403.88){\usebox{\plotpoint}}
\put(406.59,409.00){\usebox{\plotpoint}}
\put(425.63,414.00){\usebox{\plotpoint}}
\put(445.21,419.00){\usebox{\plotpoint}}
\put(464.78,424.00){\usebox{\plotpoint}}
\put(484.27,428.63){\usebox{\plotpoint}}
\put(503.28,433.00){\usebox{\plotpoint}}
\put(522.74,437.00){\usebox{\plotpoint}}
\put(542.01,441.00){\usebox{\plotpoint}}
\put(561.50,444.50){\usebox{\plotpoint}}
\put(580.98,448.00){\usebox{\plotpoint}}
\put(600.26,452.00){\usebox{\plotpoint}}
\put(619.95,455.00){\usebox{\plotpoint}}
\put(639.40,459.00){\usebox{\plotpoint}}
\put(659.27,462.00){\usebox{\plotpoint}}
\put(678.96,465.00){\usebox{\plotpoint}}
\put(698.83,468.00){\usebox{\plotpoint}}
\put(718.52,471.00){\usebox{\plotpoint}}
\put(738.21,474.00){\usebox{\plotpoint}}
\put(757.90,477.00){\usebox{\plotpoint}}
\put(777.60,480.00){\usebox{\plotpoint}}
\put(797.70,482.00){\usebox{\plotpoint}}
\put(817.57,485.00){\usebox{\plotpoint}}
\put(837.35,487.35){\usebox{\plotpoint}}
\put(857.01,490.00){\usebox{\plotpoint}}
\put(876.94,492.00){\usebox{\plotpoint}}
\put(896.45,495.00){\usebox{\plotpoint}}
\put(916.38,497.00){\usebox{\plotpoint}}
\put(936.66,499.00){\usebox{\plotpoint}}
\put(956.17,502.00){\usebox{\plotpoint}}
\put(976.28,504.00){\usebox{\plotpoint}}
\put(996.21,506.00){\usebox{\plotpoint}}
\put(1016.31,508.00){\usebox{\plotpoint}}
\put(1036.42,510.00){\usebox{\plotpoint}}
\put(1056.52,512.00){\usebox{\plotpoint}}
\put(1076.63,514.00){\usebox{\plotpoint}}
\put(1096.55,516.00){\usebox{\plotpoint}}
\put(1116.66,518.00){\usebox{\plotpoint}}
\put(1136.76,520.00){\usebox{\plotpoint}}
\put(1156.69,522.00){\usebox{\plotpoint}}
\put(1176.80,524.00){\usebox{\plotpoint}}
\put(1196.90,526.00){\usebox{\plotpoint}}
\put(1217.30,527.30){\usebox{\plotpoint}}
\put(1237.35,529.00){\usebox{\plotpoint}}
\put(1257.28,531.00){\usebox{\plotpoint}}
\put(1277.20,533.00){\usebox{\plotpoint}}
\put(1297.72,534.00){\usebox{\plotpoint}}
\put(1318.01,536.00){\usebox{\plotpoint}}
\put(1337.95,537.95){\usebox{\plotpoint}}
\put(1358.27,539.00){\usebox{\plotpoint}}
\put(1378.20,541.00){\usebox{\plotpoint}}
\put(1398.54,542.00){\usebox{\plotpoint}}
\put(1418.65,544.00){\usebox{\plotpoint}}
\put(1438.99,545.00){\usebox{\plotpoint}}
\put(1439,545){\usebox{\plotpoint}}
\sbox{\plotpoint}{\rule[-0.200pt]{0.400pt}{0.400pt}}%
\put(110.0,131.0){\rule[-0.200pt]{0.400pt}{119.245pt}}
\put(110.0,131.0){\rule[-0.200pt]{320.156pt}{0.400pt}}
\put(1439.0,131.0){\rule[-0.200pt]{0.400pt}{119.245pt}}
\put(110.0,626.0){\rule[-0.200pt]{320.156pt}{0.400pt}}
\end{picture}
\caption{\small Numerical values of $\tilde{b}(n,0)$, $b_*(n,0)$,
and asymptotic estimate of $\tilde{b}(n,0)$ with $p=0.5$.}
\label{fig:num}
\end{figure}

\begin{table}[htb]
\begin{center}
\caption{Numerical values of $\tilde{b}(n,0)$ and $b_*(n,0)$
\label{table:num}} \small
\renewcommand{\arraystretch}{1.2}
\begin{tabular}{|c||c|c|c||c|c|c|}
 \hline
 & \multicolumn{3}{|c||}{$p=1/2$} & \multicolumn{3}{c|}{$p=1/3$}\\
\hline
 $n$ & $\tilde{b}(n,0)$ & $b_*(n,0)$ & $\tilde{b}(n,0)-b_*(n,0)$ & $\tilde{b}(n,0)$ & $b_*(n,0)$ & $\tilde{b}(n,0)-b_*(n,0)$\\
 \hline
 1 & 0 & 0 & 0  & 0 & 0 & 0\\
 2 & 4 & 4 & 0  & 4.5 & 4.5 & 0 \\
 3 & 6 & 5 & 1  & 7 & 5 & 2 \\
 4 & 8.321 & 6.696 & 1.625 & 9.507  &  6.248 &   3.259\\
 5 & 10.305 & 8.121 & 2.184 & 11.652 &  7.369  &  4.283\\
 10 & 16.472 & 13.267 & 3.205 &  17.659 &  11.466 &  6.193\\
 20 & 23.034 & 19.752 & 3.282 &  22.521 &  16.260  & 6.261 \\
 30 & 27.406 & 24.124 & 3.282 &  25.802 &  19.494 &  6.308 \\
 50 & 33.489 & 30.207 & 3.282 &  30.150 &  23.891  & 6.259 \\
 100 & 42.724 & 39.442 & 3.282 &  36.849 &  30.550 &  6.298 \\
 \hline
\end{tabular}
\end{center}
\end{table}

To confirm our results, we numerically computed some of the
quantities discussed above. In Figure~\ref{fig:num}, we plot the
values of $\tilde{b}(n,0)$ (defined in (\ref{bd2})), $b_*(n,0)$
(defined by (\ref{b*d}) and (\ref{b*0})), and our asymptotic
estimate of $\tilde{b}(n,0)$ shown in Theorem~\ref{th:main}, with
$p=1/2$. We computed this asymptotic estimate up to the $\log n$
term without the periodic function $\Psi(\cdot)$, that is,
$$
\frac{1}{2h\log (1/p)} \log^2 n - \frac{d}{h}\log n +
\left[\frac{1}{2h} - \frac{1}{h\log p}
\left(\gamma+1+\frac{h_2}{2h} \right)\right]\log n.
$$
We also present the numerical values of $\tilde{b}(n,0)$,
$b_*(n,0)$, and their difference for $p=1/2$ and $p=1/3$ (then $\log(p)/\log(q)$ is irrational) in
Table~\ref{table:num}, which confirms that $\tilde{b}(n,0) \sim
b_*(n,0)$, and suggests that the difference is $O(1)$ for
$n\to\infty$ (which we shall establish analytically).

\section{Analysis}
\label{sec:analysis}

We first discuss some exact solutions of recurrence (\ref{bd}) for
small values of $n$ and arbitrary $d$, then we prove our
Theorem~\ref{th:main}, and finally provide solutions of (\ref{bd})
for other ranges of $(n,d)$, where $d \to \infty$.


\subsection{Some Exact Solutions}

We first consider (\ref{bd}) for small values of $n$ and arbitrary
$d$. Using (\ref{bd-boundary}) we rewrite (\ref{bd}) as
\begin{equation}\label{bnd}
b(n,d) = n + \sum_{k=2}^n {n \choose k}p^k q^{n-k} b(k,d-1) +
\sum_{k=0}^{n-2} {n \choose k}p^k q^{n-k} b(n-k, k+d-1).
\end{equation}
When $n=2$, (\ref{bnd}) yields $b(2,d)=2+(p^2+q^2)b(2,d-1)$ and
since $b(2,0)=0$ we have
$$
b(2,d) = \frac{1}{pq} + \left(2- \frac{1}{pq}\right)(p^2+q^2)^{d-1}
\ \ \mbox{for $d\ge 1$}.
$$
Note that $b(2,\infty)=(pq)^{-1}$ by (\ref{bninf2}). Setting $n=3$
in (\ref{bnd}) and solving the resulting equation leads to, after
some calculation,
$$
b(3,d) = \frac{2}{pq}  +\frac{3}{pq}(2pq^2-1)(p^2+q^2)^d +
\left(2+\frac{1}{pq}-6q\right)(p^3+q^3)^d \ \ \mbox{for $d\ge 0$}.
$$

We can then continue solving $b(n,d)$ for increasing $n$, and it is
clear that $b(n,d)$ will have the form
\begin{equation}\label{bnd-closed}
b(n,d) = b(n,\infty) - \sum_{J=2}^n (p^J+q^J)^d B(n,J),
\end{equation}
where $b(n,\infty)$ is the trie path length in (\ref{bninf2}) and
(\ref{bninf3}). It follows that $b(n,d) -
b(n,\infty)=O\left[(p^2+q^2)^d\right]$ for $n$ fixed and
$d\to\infty$. We can characterize the double sequence $B(n,J)$ by
using (\ref{bnd-closed}) in (\ref{bnd}) and equating coefficients of
$(p^J+q^J)^d$. For $J\ge 2$ this leads to
\begin{equation}\label{BnJ}
B(n,J) = \frac{1}{p^J+q^J} \sum_{k=J}^n {n\choose
k}\left(p^kq^{n-k} + q^k[p(p^J+q^J)]^{n-k}\right)B(k,J).
\end{equation}

 From (\ref{b-boundary}) and (\ref{bnd-closed}) we find that
\begin{equation}\label{bninf5}
b(n,\infty)+\sum_{J=2}^{n+1} B(n+1,J) = b(n+1,\infty) +\sum_{J=2}^n
B(n,J)(p^J+q^J).
\end{equation}
We can transform (\ref{BnJ}) into another equation by introducing
the generating function
\begin{equation}\label{FJz}
\F_J(z) = \sum_{n=0}^\infty B(n,J)\frac{z^n}{n!} = \sum_{n=J}^\infty
B(n,J)\frac{z^n}{n!}.
\end{equation}
Using (\ref{FJz}) in (\ref{BnJ}) leads to the functional equation
$$
\F_J(z) = \frac{1}{p^J+q^J}\left(\F_J(pz)e^{qz} +
\F_J(qz)e^{p(p^J+q^J)z}\right) \ \ \mbox{for $J\ge 2$}.
$$
Then if $\F_J(z)=e^z \G_J(z)$ we obtain
\begin{equation}\label{GJz}
(p^J+q^J)\G_J(z) = \G_J(pz) + \G_J(qz)e^{p(p^J+q^J-1)z}.
\end{equation}
Again this appears difficult to solve explicitly (however, see
\cite{jan-spa97}).

We can take the analysis somewhat further in the {\it symmetric
case} where $p=q=1/2$, as then (\ref{GJz}) simplifies to
\begin{equation}\label{GJz-sym}
\G_J(z)2^{1-J} =
\G_J\left(\frac{z}{2}\right)\left(1+\exp\left[(2^{1-J}-1)\frac{z}{2}\right]\right).
\end{equation}
Solving (\ref{GJz}) and inverting the transform over $z$ leads ultimately to
\begin{equation}\label{BnJ2}
B(n,J) = \frac{B(J,J)}{J!}
 \frac{n!}{2\pi i} \oint \frac{e^z}{z^{n+1-J}}\prod_{L=0}^\infty\left(\frac{1+e^{(2^{1-J}-1)2^{-L-1}z}}{2}\right)dz.
\end{equation}
Thus the double sequence $B(n,J)$ is known up to the single sequence
$B(J,J)$. To determine $B(J,J)$ we must still use
(\ref{bninf5}). Thus putting (\ref{BnJ2}) in (\ref{bninf5}) will
lead to a single variable recurrence for $B(J,J)$.

Next we return to {\it general} $p$, $q$ and estimate $B(n,2)$ in
(\ref{BnJ}) for $n\to\infty$. Let us set $C(n)=B(n,2)$ and we recall
that, by (\ref{bnd-closed}),
\begin{equation}\label{btnd}
\tb(n,d) \sim C(n)(p^2+q^2)^d; \ \ \ \  d\to\infty, \ \ \  n=O(1).
\end{equation}
While we mainly want to estimate $\tb(n,d)$ for $n\to\infty$ and
$d=O(1)$, it is useful to try to understand the full asymptotic
structure of $\tb(n,d)$, for $n$ and/or $d$ large.

We thus examine how (\ref{btnd}) behaves when $n$ also becomes
large. Setting $J=2$ in (\ref{BnJ}) leads to
\begin{equation}\label{Cn}
(p^2+q^2)C(n) = \sum_{k=2}^n {n\choose k}p^kq^{n-k}C(k) +
\sum_{k=0}^{n-2} {n\choose k}p^kq^{n-k} (p^2+q^2)^kC(n-k)
\end{equation}
for $n\ge 3$ with $C(2)=(p^{-1}q^{-1}-2)/(p^2+q^2) = (pq)^{-1}$.

We argue intuitively that $C(n)$ will behave algebraically for
$n\to\infty$ (we shall prove this fact shortly). Then we use the
fact that the ``kernel'' in (\ref{Cn}) behaves
$$
{n\choose k}p^kq^{n-k} \to \delta(k-np), \ \ n\to\infty
$$
where $\delta(\cdot)$ is the delta function. Then for algebraically
or logarithmically varying smooth $f(k)$ (for $k\to\infty$) we have (see
\cite{flajolet99,js99} for rigorous proofs)
$$
\sum_{k=0}^n {n\choose k}p^kq^{n-k} f(k) = f(np) + O(nf''(np)), \
n\to\infty.
$$
Then the term involving $(p^2+q^2)^k C(n-k)$ will lead to terms that
are exponentially smaller than those arising from $C(k)$, and
(\ref{Cn}) may be replaced by the asymptotic relation
\begin{equation}\label{Cn-sim}
C(n)(p^2+q^2) \sim C(np), \ n\to\infty.
\end{equation}
A general solution to (\ref{Cn-sim}) has the form
\begin{equation}\label{Cn-gen}
C(n) = n^\nu \bar{C}(n)
\end{equation}
where $\bar{C}(np)=\bar{C}(n)$ and $p^\nu =p^2+q^2$ so that
\begin{equation}\label{nu}
\nu = \frac{\log (p^2+q^2)}{\log p} > 0.
\end{equation}
Thus $\bar{C}(\cdot)$ is a periodic function of $\log_p n$ of period
1, which we can write as the Fourier series
\begin{equation}\label{Cn-Fs}
\bar{C}(n) = c^{(0)}(p) + \sum_{\l=-\infty,\l\neq 0}^\infty
c^{(\l)}(p)e^{2\pi i \l \log_p n}.
\end{equation}
It again appears difficult to identify explicitly the Fourier
coefficients $c^{(\l)}(p)$, but we can do this in the symmetric case
$p=q=1/2$. Then we set $\sum_{n=0}^\infty C(n)z^n/n! = \F_2(z)$ as
in (\ref{FJz}) and from (\ref{BnJ2}) obtain
\begin{equation}\label{Cn2}
C(n) = \frac{2n!}{2\pi i} \oint
\frac{e^z}{z^{n-1}}\prod_{\l=1}^\infty\left(\frac{1+e^{-z2^{-\l-1}}}{2}\right)dz.
\end{equation}
To obtain the large $n$ behavior of the integral in (\ref{Cn2}) we
first expand the integral for $z\to\infty$ and apply a
depoissonization argument. Setting $\l=\log_2 z +J$ we have
$2^\l=2^Jz$ and
\begin{eqnarray*}
\prod_{\l=1}^\infty\left(\frac{1+e^{-z2^{-\l-1}}}{2}\right) &=& \exp\left[\sum_{\l=1}^\infty\log \left(\frac{1+e^{-z2^{-\l-1}}}{2}\right)\right]\\
&=&\exp\left[\sum_{J=1-\log_2 z}^\infty\log \left(\frac{1+e^{-2^{-J-1}}}{2}\right)\right]\\
&=&\exp\left[\sum_{J=0}^\infty\log \left(\frac{1+e^{-2^{-J-1}}}{2}\right) + \sum_{J=1}^{\log_2z -1}\log \left(\frac{1+e^{-2^{J-1}}}{2}\right)\right]\\
&\sim&\exp\left[\log(\frac{1}{2})(\log_2z-1) + \sum_{J=0}^\infty\log
\left(\frac{1+e^{-2^{-J-1}}}{2}\right) + \sum_{J=1}^{\infty}\left(1+e^{-2^{J-1}}\right)\right]\\
&=&\frac{2}{z}K_*
\end{eqnarray*}
where
$$
K_* =\prod_{J=0}^\infty \left(\frac{1+e^{-2^{-J-1}}}{2}\right)
\prod_{J=1}^{\infty}\exp\left(1+e^{-2^{J-1}}\right) = 1.
$$
Thus $C(n) \sim 4n!/(n-1)! = 4n$ as $n\to\infty$. This shows that
$c^{(0)}(1/2) = 4$ and a more careful calculation can be used to
identify the other Fourier coefficients $c^{(\l)}(1/2)$ in
(\ref{Cn-Fs}) (then we would set $\l=\lfloor\log_2 z\rfloor+J =
\log_2 z +J -\{\log_2 z\}$ so that $2^\l=2^Jz2^{-\{\log_2 z\}}$. We
omit the details.

In Table~\ref{table:cn} we consider various values of $p$ and
estimate $\bar{C}(n) \approx c^{(0)}(p)$ numerically, by computing
$C(n)n^{-\nu}$ from (\ref{Cn}), for large $n$. This shows that as a
function of $p$, $|c^{(0)}(p)|$ is minimal when $p$ is between 0.6
and 0.7, and becomes large as either $p\to 0$ or $p\to 1$. For $p\to
0$ the oscillatory terms in (\ref{Cn-Fs}) become more numerically
significant. Table~\ref{table:cn} indicates this when $p=0.1$, by
giving a range of values of $C(n)n^{-\nu}$.

\begin{table}[htb]

\begin{center}
\caption{Values of the zeroth Fourier coefficient.\label{table:cn}}
\par
\medskip
\begin{tabular}{|c|c|}
 \hline
 % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
 $p$ & $C(n)n^{-\nu}|_{n\to\infty}\approx c^{(0)}(p) $ \\
 \hline
 0.5 & 4 \\
 0.4 & 5.664 \\
 0.3 & 9.728\\
 0.25 & 14.03\\
 0.2 & 22.5\\
 0.1 & 98 to 105\\
     &   \\
 0.6 & 3.331\\
 0.7 & 3.276\\
 0.75 & 3.479\\
 0.8 & 3.903\\
 0.9 & 6.423\\
 \hline
\end{tabular}
\end{center}
\end{table}
\par
\medskip

To justify the approximation in (\ref{Cn-sim}) we first inductively
show that for all $n$
\begin{equation}\label{Cn-le}
C(n) \le An^{\nu+\eps}
\end{equation}
for all $\eps>0$ and $A>0$. By isolating the terms in the sums in
(\ref{Cn}) with $k=n$ and $k=0$ we obtain, for $n>2$,
\begin{equation}\label{Cn2a}
C(n) = \frac{1}{p^2+q^2-p^n-q^n}\left[\sum_{k=2}^{n-1} {n\choose
k}p^kq^{n-k}C(k) + \sum_{k=1}^{n-2} {n\choose k}p^kq^{n-k}
(p^2+q^2)^kC(n-k)\right].
\end{equation}
Assuming inductively that (\ref{Cn-le}) holds for $C(k)$ for
$k=1,2,\cdots,n-1$ we then have
\begin{eqnarray*}
\sum_{k=2}^{n-1} {n\choose k}p^kq^{n-k}C(k) &\le & \sum_{k=2}^{n-1}
{n\choose k}p^kq^{n-k}Ak^{\nu+\eps} \\
&\le& A(np)^{\nu+\eps}.
\end{eqnarray*}
Using a similar estimate for the second sum in (\ref{Cn2a}) we are
led to
\begin{eqnarray}\label{Cn3}
C(n) &\le & \frac{A}{p^2+q^2-p^n-q^n}\left[(np)^{\nu+\eps} +
n^{\nu+\eps}(p(p^2+q^2)+q)^n\right] \nonumber \\
&=&An^{\nu+\eps}\left[\frac{p^2+q^2}{p^2+q^2-p^n-q^n}p^{\eps}
+\frac{(p(p^2+q^2)+q)^n}{p^2+q^2-p^n-q^n} \right],
\end{eqnarray}
as $C(n-k)\le A(n-k)^{\nu+\eps} \le An^{\nu+\eps}$ and $p^\nu =
p^2+q^2$. Since $p(p^2+q^2)+q < p+q = 1$, the second term in
(\ref{Cn3}) is asymptotically negligible for $n$ large and
(\ref{Cn-le}) follows by induction.

We have thus obtained some exact expressions for $b(n,d)$ for small
values of $n$, a general asymptotic result for $d\to\infty$ with
$n=O(1)$, and then examined how this result behaves when $n$ also
becomes large. However, this cannot be used to infer the behavior of
$b(n,d)$ for $n\to\infty$ with $d=O(1)$, which we examine next.

\subsection{Main Asymptotic Result for $b(n,d)$}

We first give an intuitive derivation of the asymptotics of $b(n,d)$
for fixed $d\ge 0$ and $n\to\infty$, and in particular of $b(n,0)$.
Starting from (\ref{btd}) we again argue that the second sum is
negligible for $n\to\infty$ and that the first is asymptotic to
$\tb(np,d-1)$ so that (\ref{btd}) becomes
\begin{equation}\label{btnd2}
\tb(n,d) \sim \tb(np,d-1), \ n\to\infty
\end{equation}
and, in particular,
\begin{equation}\label{btn1}
\tb(n,1) \sim \tb(np,0), \ n\to\infty
\end{equation}
which when added to (\ref{bt-boundary}) leads to
\begin{equation}\label{btn0}
\tb(n+1,0)-\tb(np,0) \sim b(n+1,\infty) - b(n,\infty).
\end{equation}
The right side of (\ref{btn0}) may be estimated from (\ref{bninf4})
or by (\ref{bninf3}). Using (\ref{bninf3}) we can show that term by
term differentiating of the asymptotic series in (\ref{bninf4}) is
permissible, and thus (\ref{btn0}) becomes, for $n\to\infty$,
\begin{equation}\label{btn02}
\tb(n+1,0)-\tb(np,0) = \frac{1}{h}\log n +
\frac{1}{h}\left(\gamma+1+\frac{h_2}{2h}\right) +
\frac{1}{h}\psi(\log_p n)+o(1),
\end{equation}
where $\psi(\cdot)$ is the periodic function
\begin{equation}\label{psi}
\psi(x) = \sum_{k=-\infty, k\neq 0}^\infty \left[1+\frac{2k\pi
ir}{\log p}\right]\Gamma\left(-\frac{2k\pi ir}{\log
p}\right)e^{2k\pi irx},
\end{equation}
where we note that $\psi$ and $\Phi$ are related by $\psi(x)=\Phi(x)+(\log
p)^{-1}\Phi'(x)$.

Now (\ref{btn02}) suggests that $\tb(n,0)$ admits an asymptotic
expansion of the form
\begin{equation}\label{btn03}
\tb(n,0) = A\log^2 n +B\log n+C+o(1), \ n\to\infty
\end{equation}
and then
\begin{equation}\label{btn04}
\tb(n+1,0)-\tb(np,0) =-2A(\log p)\log n -A\log^2p-B\log p +o(1).
\end{equation}
Comparing (\ref{btn02}) to (\ref{btn04}) we conclude that $A=-(2h\log
p)^{-1}$ and then
\begin{equation}\label{B}
B= \frac{1}{2h} -\frac{1}{h\log
p}\left[\gamma+1+\frac{h_2}{2h}+\psi(\log_p n)\right].
\end{equation}
We have thus formally derived the result in Theorem~\ref{th:main}
for $\tb(n,0)$. For any fixed $d>0$ we can extend this argument by
asymptotically solving (\ref{btnd2}) by an expansion of the form
\begin{equation}\label{btnd3}
\tb(n,d) = A(d)\log^2 n +B(d)\log n+C(d)+o(1)
\end{equation}
to find from (\ref{btnd2}) that $A(d)=A(d-1)$ and $B(d)=B(d-1)+2\log
 pA(d-1)$. Then using (\ref{btnd3}) in (\ref{btn0}) or (\ref{btn02})
 we find that $A(d)=A(0)=-(2h\log p)^{-1}$ and $B(d)-B(d-1) =2\log pA(d-1)=-h^{-1}$
 so that $B(d)=B(0)-h^{-1}d$, where $B(0)=B$ is as in
 (\ref{B}).

We proceed to provide a rigorous derivation of the theorem. Using
arguments completely analogous to (\ref{Cn-le})--(\ref{Cn3}), we can
inductively establish the bound
\begin{equation}\label{btnd4}
\tb(n,d) \le A_0 n^{\nu+\eps}(p^2+q^2)^d;\ n\ge 2, d\ge 0
\end{equation}
where again $\nu$ is given by (\ref{nu}). When $n=2$ we have (exactly)
$$\tb(2,d)=\left(\frac{1}{pq}-2\right)(p^2+q^2)^{d-1},$$
so (\ref{btnd4}) clearly holds. Assuming that (\ref{btnd4}) holds for all $(N,D)$ with $N+D<n+d$ we can estimate the first sum in the right side of (13) by
\begin{eqnarray*}
\sum_{k=0}^{n-2} {n\choose k}p^kq^{n-k} \tb(k,d-1) &\le &
A_0 \sum_{k=0}^{n} k^{\nu+\eps}(p^2+q^2)^{d-1} p^kq^{n-k}{n\choose k}\\
&\le &
A_0 (np)^{\nu+\eps}(p^2+q^2)^{d-1}\\
&= & A_0 n^{\nu+\eps}(p^2+q^2)^{d},
\end{eqnarray*}
and the second sum (\ref{btd}) by
\begin{eqnarray*}
\sum_{k=0}^{n-2} {n\choose k}p^kq^{n-k} \tb(n-k,k+d-1) &\le &
A_0 \sum_{k=0}^{n} (n-k)^{\nu+\eps}(p^2+q^2)^{k+d-1} p^kq^{n-k}{n\choose k}\\
&\le &
A_0 n^{\nu+\eps}(p^2+q^2)^{d-1}\sum_{k=0}^{n} {n\choose k}\left[p(p^2+q^2)\right]^{k} q^{n-k}\\
&= & A_0 n^{\nu+\eps}(p^2+q^2)^{d-1} \left[q+p(p^2+q^2)\right]^n
\end{eqnarray*}
which is $o(\tb(n,d))$ (by an exponentially small factor).

Now let $b_{\it diff}(n,d)=\tb(n,d)-b_*(n,d).$ Then from (\ref{btd})--(\ref{b*0})
we see that
\begin{equation}\label{star}
b_{\it diff}(n,d)=\sum_{k=0}^{n} {n \choose k} p^k q^{n-k}
b_{\it diff}(k,d-1)+\sum_{k=0}^{n} {n \choose k} p^k q^{n-k}
\tb(n-k,k+d-1)
\end{equation}
with $b_{\it diff}(n+1,0)=b_{\it diff}(n,1)$. Using an inductive argument analogous
to that used to obtain (\ref{btnd4}) we can show that $b_{\it diff}(n,d)$ is
$O(1)$, since the second sum in (\ref{star}) may be estimated to be exponentially
small for $n\to\infty$. We shall show below that $b_*(n,d)=O(\log^2 n)$
for a fixed $d$ and $n\to\infty$, and hence $\tb(n,d)\sim b_*(n,d)$.

We proceed to analyze (\ref{b*d}),
with (\ref{b*0}), and thus re-establish Theorem~\ref{th:main}.
Introducing the exponential generating function
\begin{equation}\label{Bdz}
B_d^*(z) = \sum_{n=2}^\infty b_*(n,d)\frac{z^n}{n!} = e^z A_d(z),
\end{equation}
where $b_*(n,d)$ is defined from (\ref{b*d}), we find that
$$
B_d^*(z) = B_{d-1}^*(pz)e^{qz}
$$
or, since $A_d(z)=B_d^*(z)e^{-z}$,
\begin{equation}\label{Adz}
A_d(z) = A_{d-1}(pz).
\end{equation}
This can be solved by iteration to yield
$$
A_d(z) = A_{0}(p^dz).
$$
Then setting
$$
\G_*(z) = \sum_{n=2}^\infty b(n,\infty)\frac{z^n}{n!}
$$
and noting that
$$
\sum_{n=1}^\infty b_*(n+1,0)\frac{z^n}{n!} = \frac{d}{dz}B_0^*(z),
$$
(\ref{b*0}) leads to
\begin{equation}\label{Bz}
\frac{d}{dz}B_0^*(z) - B_1^*(z) = -\G_*(z)+\G_*'(z).
\end{equation}
If $\G_*(z)=e^z \tilde{\G}(z)$, from the integral representation in
(\ref{bninf3}) we conclude that the Mellin transform of
$\tilde{\G}(z)$ is
\begin{equation}\label{Gtz}
\int_0^\infty \tilde{\G}(z)z^{s-1}dz =
\frac{\Gamma(s+1)}{1-p^{-s}-q^{-s}},
\end{equation}
Using the definitions of
$A_d(\cdot)$ and $\tilde{\G}(\cdot)$, (\ref{Bz}) becomes
\begin{equation}\label{A0}
A_0'(z)+A_0(z) -A_0(pz) = \tilde{\G}'(z).
\end{equation}
We introduce the negative Mellin transform of $A_0(z)$
\begin{equation}\label{Ms}
\M(s)=-\int_0^\infty A_0(z)z^{s-1}dz
\end{equation}
and use (\ref{Ms}) in (\ref{A0}) to obtain the functional equation
\begin{equation}\label{Ms2}
-(s-1)\M(s-1) +
(1-p^{-s})\M(s)=\frac{(s-1)\Gamma(s)}{1-p^{1-s}-q^{1-s}}.
\end{equation}
Next we set
\begin{equation}\label{Ms3}
\M(s) =\Gamma(s)\N(s)
\end{equation}
with which (\ref{Ms2}) becomes
\begin{equation}\label{Ns}
-\N(s-1) +(1-p^{-s})\N(s) = \frac{s-1}{1-p^{1-s}-q^{1-s}}.
\end{equation}
To solve (\ref{Ns}) we let
\begin{equation}\label{Ns2}
\N(s) = \prod_{k=0}^\infty
\left[\frac{1-p^{k+2}}{1-p^{k-s}}\right]\N_1(s)
\end{equation}
and then (\ref{Ns}) becomes
\begin{equation}\label{Ns3}
\N_1(s)-\N_1(s-1) = \prod_{k=1}^\infty
\left[\frac{1-p^{k-s}}{1-p^{k+1}}\right]\frac{s-1}{1-p^{1-s}-q^{1-s}}.
\end{equation}
Now, for $s\to-\infty$ the right side of (\ref{Ns3}) behaves as
$(s-1)\prod_{k=1}^\infty (1-p^{k+1})^{-1}$, with an exponentially
small error. Letting
\begin{equation}\label{N1s}
\N_1(s) = \frac{s(s-1)}{2} \prod_{k=1}^\infty
\left(\frac{1}{1-p^{k+1}}\right) + \N_2(s)
\end{equation}
the equation for $\N_2(\cdot)$ becomes
\begin{equation}\label{N2s}
\N_2(s)-\N_2(s-1) = \frac{s-1}{\prod_{k=1}^\infty
\left(1-p^{k+1}\right)} \left[
\frac{1}{1-p^{1-s}-q^{1-s}}\prod_{k=1}^\infty (1-p^{k-s})-1\right]
\end{equation}
whose right hand side is, unlike that of (\ref{Ns3}), exponentially
small for $s\to-\infty$. The solution to (\ref{N2s}) is
\begin{equation}\label{N2s2}
\N_2(s) = \N_2(-\infty) + \sum_{i=0}^\infty
 \left[
\frac{\prod_{k=1}^\infty
(1-p^{k-s+i})}{1-p^{1+i-s}-q^{1+i-s}}-1\right]
\frac{s-1-i}{\prod_{k=1}^\infty (1-p^{k+1})}.
\end{equation}

 From (\ref{Bdz}) we see that $A_d(z)=O(z^2)$ as $z\to 0$ so that
$\M(s)$ in (\ref{Ms}) must be analytic at $s=-1$. From (\ref{Ms3}) we
then conclude that $\N(-1)=0$. From (\ref{Ns2}) we have $\N_1(-1)=0$
and from (\ref{N1s}) and (\ref{N2s2}) we thus obtain an expression
for $\N_2(-\infty)$:
\begin{equation}\label{N2inf}
\N_2(-\infty)\prod_{k=1}^\infty (1-p^{k+1})+1 -\sum_{i=0}^\infty
 (i+2)\left[
\frac{\prod_{k=1}^\infty (1-p^{k+i+1})}{1-p^{2+i}-q^{2+i}}-1\right]
= 0.
\end{equation}
We have thus obtained the final expression for $\M(s)$ in
(\ref{Ms3}) as
\begin{equation}\label{Ms4}
\M(s) = \frac{\Gamma(s)}{\prod_{L=0}^\infty (1-p^{L-s})} \left(
\frac{s(s-1)}{2} +\beta + \sum_{i=0}^\infty
 (s-i-1)\left[
\frac{\prod_{k=1}^\infty
(1-p^{k-s+i})}{1-p^{1+i-s}-q^{1+i-s}}-1\right]
 \right),
\end{equation}
where
$$
\beta= \N_2(-\infty)\prod_{k=1}^\infty (1-p^{k+1})
$$
can be computed from (\ref{N2inf}). Inverting the transform in (\ref{Ms}) we obtain the generating function of $b_*$ as
\begin{equation}\label{b*nd}
\sum_{n=0}^{\infty} \frac{z^n}{n!}b_*(n,d)= \frac{-1}{2\pi
i}\int_{Br}(p^dz)^{-s}\M(s)ds.
\end{equation}

The final step is to expand $b_*(n,d)$ ($\sim \tb(n,d)$) for
$n\to\infty$ with $d$ fixed. Inverting the generating function over $z$ can be done
asymptotically by a standard depoissonization argument, which amounts to simply replacing $z$ by $n$ for large $n$. Thus we need only evaluate the integral in (\ref{b*nd}) for $z$ large and positive.
The function $\M(s)$ in (\ref{Ms4}) has a {\it triple pole} at $s=0$, and
there are other double poles on the imaginary $s$-axis if
$1-p^{1-s}-q^{1-s}$ has zeros there, which occurs only if $\log
p/\log q$ is rational, say $r/t$ where $r$ and $t$ are integers.
First we compute the contribution from $s=0$. Using the expansion
$\Gamma(s)=[1-\gamma s+O(s^2)]/s$ as $s\to 0$, with $\gamma$ being
the Euler constant, (\ref{Ms4}) becomes
\begin{eqnarray}\label{Ms5}
\M(s) &= &\frac{1}{s}[1-\gamma
s+O(s^2)](1-p^{-s})^{-1}\prod_{L=1}^\infty (1-p^{L-s})^{-1}
\nonumber
\\
&&\times \left(\frac{s-1}{1-p^{1-s}-q^{1-s}}\prod_{k=1}^\infty
(1-p^{k-s}) -(s-1)
+\frac{s(s-1)}{2} +\beta \right. \nonumber \\
&& \left.+ \sum_{i=1}^\infty
 (s-i-1)\left[
\frac{\prod_{k=1}^\infty
(1-p^{k-s+i})}{1-p^{1+i-s}-q^{1+i-s}}-1\right]
 \right).
\end{eqnarray}
Now
$$
1-p^{-s} = s\log p -\frac{1}{2}s^2(\log p)^2 +O(s^3)
$$
and
$$
1-p^{1-s}-q^{1-s} = -hs -\frac{h_2}{2}s^2 +O(s^3).
$$
Also, using the expression in (\ref{N2inf}) to compute $\beta+1$ the
expansion of (\ref{Ms5}) for $s\to 0$ becomes
\begin{eqnarray}\label{Ms6}
\M(s)& =& \frac{1}{s^3}\frac{1-\gamma s}{\log
p}\left[1+\frac{s}{2}\log p
+O(s^2)\right]\left\{\frac{1-s}{h}\left[1-\frac{h_2}{2h}s+O(s^2)\right]
+O(s^2)\right\} \nonumber \\
&=& \frac{1}{s^3}\frac{1}{h\log p} +
\frac{1}{s^2}\left[-\frac{\gamma}{h\log p}-\frac{1}{h\log
p}\left(1+\frac{h_2}{2h}\right)+\frac{1}{2h}\right]
+O\left(\frac{1}{s}\right).
\end{eqnarray}
It follows that the integrand $p^{-ds}z^{-s}\M(s)$ in (\ref{b*nd})
has the residue
\begin{equation}\label{res}
{\rm Res}_{s=0} \left\{p^{-ds}z^{-s}\M(s)\right\} =
\frac{1}{2}\frac{\log^2 z}{h\log p} + \frac{d}{h}\log z + \log z
\left[\frac{1}{\log
p}\left(\frac{\gamma+1}{h}+\frac{h_2}{2h^2}\right)
-\frac{1}{2h}\right] +O(1)
\end{equation}
where the $O(1)$ refers to terms that are $O(1)$ for $z\to\infty$,
and these can be evaluated by explicitly computing the $O(s^{-1})$
term(s) in (\ref{Ms6}). Then the expansion of $\tb(n,d)\sim
b_*(n,d)$ follows by setting $z=n$ in (\ref{res}), and we have thus
regained the formula in Theorem~\ref{th:main}. If $\log p/\log q$ is
rational we must also compute the contribution from the double poles
along the imaginary axis at such points $p^{-s}=q^{-s}=1$ and
$p^{1-s}+q^{1-s}=1$. These poles lead to the oscillatory terms in
Theorem~\ref{th:main}, as can be seen by computing their residues from
(\ref{Ms4}).

We have thus established Theorem~\ref{th:main} rigorously, though the
intuitive derivation in (\ref{btnd2})--(\ref{btnd3}) is much
simpler, and more revealing of the basic asymptotic structure of the
equations (\ref{btd}) and (\ref{bt-boundary}).


\subsection{Other Asymptotic Ranges}

Here we briefly discuss $\tb(n,d)$ when $n$ and $d$ are
simultaneously large, and try to identify what ranges of $n$ and $d$
lead to different asymptotic expansions. We recall that (\ref{btnd})
applies for $n$ fixed and $d\to\infty$, while Theorem~\ref{th:main}
applies for $d$ fixed and $n\to\infty$. We confine ourselves here to
an intuitive discussion.

The form of the expansion in (\ref{btnd}) (with $C(n)$ given by
(\ref{Cn-gen}) and (\ref{Cn-Fs})) suggests that an important scale
is $n,d\to\infty$ with $d-\log_{1/p}(n)=O(1)$. Note that then the
algebraic growth of $n^\nu$ as $n\to\infty$ is balanced by the
geometric decay of $(p^2+q^2)^d$ in (\ref{btnd}). We introduce the
new variable $\xi$ with
\begin{equation}\label{d}
d = \frac{\log n}{\log(1/p)}+\xi, \ \ \xi=O(1)
\end{equation}
with
\begin{equation}\label{btnd5}
\tb(n,d) = \B(n,\xi) = \B(n,d-\log_{1/p}(n)),
\end{equation}
and we note that
\begin{equation}\label{btnd6}
\tb(np,d-1) = \B(np,\xi).
\end{equation}
We again argue that for $n\to\infty$ the second sum in (\ref{btd})
is negligible and approximate (\ref{btd}) by
\begin{equation}\label{btnd7}
\tb(n,d) = \tb(np,d-1) + O[n\tb''(np,d-1)].
\end{equation}
In view of (\ref{btnd5}) and (\ref{btnd6}) a
general asymptotic solution of (\ref{btnd7}) is any function that
satisfies $\B(n,\xi)=\B(np,\xi)$ which we can write as a Fourier
series, with
\begin{equation}\label{Bn}
\B(n,\xi) = \B_0(\xi) + \sum_{\l=-\infty,\l\neq 0}^\infty e^{2\pi
i\l\log_p(n)} \B_\l(\xi).
\end{equation}
Thus (\ref{Bn}) gives an approximation to $\tb(n,d)$ for
$n,d\to\infty$ with $\xi=O(1)$, but we cannot explicitly determine
the Fourier coefficients $\B_\l(\xi)$, which are now functions of
$\xi$. If we require $\B(n,\xi)$ to asymptotically match to
(\ref{btnd}), we would equate the large $n$ behavior (\ref{btnd}) to
the expansion of $\B(n,\xi)$ for $\xi\to+\infty$, and this yields
\begin{equation}\label{Bx}
\B_0(\xi) \sim c^{(0)}e^{\xi\log(p^2+q^2)}, \ \ \xi\to+\infty,
\end{equation}
and a similar matching condition can be obtained for $\B_\l(\xi)$
for $\l\neq 0$, by comparing (\ref{Bn}) and (\ref{Cn-gen}) with
(\ref{Cn-Fs}). Thus (\ref{Bx}) shows that $\B_0(\xi)$ will decay
exponentially for $\xi\to+\infty$.

Next we examine $\tb(n,d)$ for $d=O(\log n)$ by defining $\om$ from
\begin{equation}\label{d2}
d = \om\log n, \ \ 0<\om<\frac{1}{\log(1/p)}
\end{equation}
and then set
\begin{equation}\label{btnd8}
\tb(n,d) = \log^2(n)\F(\om).
\end{equation}
Then we approximate (\ref{btd}) again by $\tb(n,d) \sim \tb(np,d-1)$
which in view of (\ref{btnd8}) becomes
\begin{equation}\label{F}
\log^2(n)\F(\om)\sim \log^2(np)\F\left(\frac{d-1}{\log(np)}\right)
\sim (\log n+\log p)^2\F\left(\om - \frac{1}{\log n} -\frac{\om \log
p}{\log n} + O(\log^{-2}n)\right).
\end{equation}
 From (\ref{F}) we obtain the following limiting ODE:
\begin{equation}\label{ODE}
0 = -\F'(\om)(1+\om\log p) +2\log p\F(\om).
\end{equation}
The solution to (\ref{ODE}) is
\begin{equation}\label{F2}
\F(\om) = (1+\om\log p)^2 \F_*
\end{equation}
where $\F_*$ is a constant. For $\om\to 0$, the expansion in
(\ref{btnd8}) behaves as $\F_*\log^2(n)$ and if we match the
$\om$-scale result to the $d=O(1)$ result in Theorem~\ref{th:main},
we conclude that
$$
\F_* =\frac{1}{2h}\frac{1}{\log (1/p)}.
$$
Finally, by asymptotically matching (\ref{btnd8}) as $\om \to [\log
(1/p)]^{-1}$ to the approximation in (\ref{btnd5}) and (\ref{Bn}),
for $\xi\to-\infty$, we conclude that
$$
\B_0(\xi) \sim \frac{1}{2h} \log^2(p) \xi^2, \ \ \xi\to-\infty.
$$
Note that $\xi$ and $\om$ are related by
$$
1+\om\log p = \frac{\log p}{\log n}\xi
$$
so that when $0<\om<[\log (1/p)]^{-1}$ we have $\xi<0$.

To summarize the formal results in this subsection, our analysis
suggests that the asymptotics of $\tb(n,d)$ are different for the
three cases:\\
\parsec
(i) $n=O(1), d\to\infty$ (where (\ref{btnd}) holds),\\
\parsec
(ii) $\xi=d-\log_{1/p}(n)=O(1)$ where (\ref{Bn}) holds, and\\
\parsec
(iii) $d=O(\log n)$ where $\tb(n,d) \sim (2h)^{-1}(1+\om\log
p)^2\log^2 n/(-\log p)$ with $d=\om\log n$ and $0<\om<[\log (1/p)]^{-1}$.\\

The result in Theorem~\ref{th:main} appears to be a limiting case of
the $d=O(\log n)$ expansion, when it is expanded for $\om\to 0$.
However, Theorem~\ref{th:main} also gives the second term ($O(\log
n)$) in the asymptotic series for $d=O(1)$.

We have only given the asymptotic behaviors of $\B_0(\xi)$ as
$\xi\to\pm\infty$. To get a more
explicit expression for $\tb(n,d)\sim \B(n,\xi)$ in (\ref{Bn}) we
again argue that $\tb(n,d)\sim b_*(n,d)$ holds for $\xi=O(1)$ (in
fact this relation fails only for $n=O(1)$ and $d\to\infty$). If
instead of defining $\xi$ from (\ref{d}) we let
\begin{equation}\label{d3}
d = \lfloor \log_{1/p}(n)\rfloor +\xi' = \log_{1/p}(n) +\xi' -
\{\log_{1/p}(n)\},
\end{equation}
where $\{\cdot\}$ denotes the fractional part, then
$$
p^dn = p^{\xi'}\exp[-d\log(1/p)\{\log_{1/p}(n)\}]
$$
and for $n\to\infty$ with $\xi,\xi'=O(1)$ the limiting form of
(\ref{b*nd}) is
\begin{equation}\label{limit}
\frac{-1}{2\pi i}\int_{Br}p^{-s\xi'}\M(s)p^{sd\{\log_{1/p}(n)\}}ds
\end{equation}
with $\M(\cdot)$ as in (\ref{Ms4}). We therefore conjecture that the
right side of (\ref{Bn}) is given explicitly by (\ref{limit}), with
$\xi$ in (\ref{Bn}) replaced by $\xi'$ in (\ref{d3}).



%\newpage

\begin{thebibliography}{99}


\bibitem{isit09-graph}
Y. Choi and W. Szpankowski,
\newblock Compression of Graphical Structures: Fundamental Limits, Algorithms,
and Experiments,
\newblock {\em IEEE Transaction on Information Theory}, 58, 620--638, 2012.

\bibitem{devroye92}
L. Devroye, A Study of Trie-Like Structures Under the Density Model,
{\it Annals of Applied Probability}, 2, 402--434, 1992.


\bibitem{drmota09}
M. Drmota, {\it Random Trees}, Springer, New York, 2009.

\bibitem{ds11}
M. Drmota and W. Szpankowski, The Expected Profile of Digital Search
Trees, {\it J. Combin. Theory, Ser. A}, 118, 1939--1965, 2011.



\bibitem{fgd}
P. Flajolet, X. Gourdon, and P. Dumas, Mellin Transforms and
Asymptotics: Harmonic Sums, {\it Theoretical Computer Science}, 144,
3--58, 1995.

\bibitem{flajolet99}
P. Flajolet, Singularity Analysis and Asymptotics of Bernoulli
Sums, {\it Theoretical Computer Science}, 215, 371--381, 1999.

\bibitem{fs-book}
P. Flajolet and R. Sedgewick, {\it Analytic Combinatorics},
Cambridge University Press, Cambridge, 2009.

\bibitem{js98}
P. Jacquet, and W. Szpankowski, Analytical Depoissonization and its
Applications, {\it Theoretical Computer Science}, 201, 1--62, 1998.

\bibitem{js99}
P. Jacquet and W. Szpankowski, Entropy Computations via Analytic
Depoissonization, {\it IEEE Trans. Information Theory}, 45, 1072--1081, 1999.

\bibitem{jan-spa97}
S. Janson and W. Szpankowski, Analysis of an Asymmetric leader
Election Algorithm, {\it Electronic J. of Combinatorics}, 4, R17,
1997.

\bibitem{ks00}
C. Knessl, and W. Szpankowski, Asymptotic Behavior of the Height in
a Digital Search Tree and the Longest Phrase of the Lempel-Ziv
Scheme, {\it SIAM J. Computing}, 30, 923--964, 2000.

\bibitem{KnuthV1}
D. Knuth, {\it The Art of Computer Programming. Sorting and
Searching}, Vol. 3, Second Edition,  Addison-Wesley, Reading, MA,
1998.
%{\em The Art of Computer Programming. Fundamental Algorithms.
%Vol.~1\/} (Addison-Wesley, Reading MA, 1968).

\bibitem{louchard87}
G. Louchard, Exact and Asymptotic Distributions in Digital and
Binary Search Trees, {\it RAIRO Theoretical Inform. Applications},
21, 479--495, 1987.

\bibitem{Mahmoudrandomsearchtrees}
{H.\ Mahmoud,} {\it Evolution of Random Search Trees}, John Wiley \&
Sons Inc., New York, 1992.

\bibitem{park08}
G. Park, H.K. Hwang, P. Nicod\`eme, and W. Szpankowski, Profile of
Tries, {\it SIAM J. Computing}, 8, 1821--1880, 2009.


\bibitem{pittel85}
B. Pittel, Asymptotic Growth of a Class of Random Trees, {\it Annals
of Probability}, 18, 414--427, 1985.

\bibitem{pittel86}
 B.~Pittel,
Path in a Random Digital Tree: Limiting Distributions, {\it Advances
in Applied Probability}, 18, 139--155, 1986.


\bibitem{spa91}
W. Szpankowski, A Characterization of Digital Search Trees from the
Successful Search Viewpoint, {\it Theoretical Computer Science}, 85,
117--134,  1991.

\bibitem{spa-book}
W. Szpankowski,
 {\it Average Case Analysis of Algorithms on Sequences},
Wiley, New York, 2001.





\end{thebibliography}

\end{document}
