.fp 4 SC
.S 12
.nr W 5.9375i
.ll 5.9375i
.am DS
.ll 5.9375i
.W 5.9375i
..
.nr Pt 1
.nr Hu 4
.EQ
delim $$
define as % roman "as" %
define scrO % font 4 size +2 O ~ %
define trn % t sub {r,^n} %
define h1n % h sub {1,^n} %
define h2n % h sub {2,^n} %
define hkn % h sub {k,^n} %
define ykn % y sub {k,^n} %
define y1n % y sub {1,^n} %
define y2n % y sub {2,^n} %
define y1z % y sub 1 (z) %
define y2z % y sub 2 (z) %
define y1s % y sub {1,^s} %
define nInf % n ~->~ inf %
gsize 12
.EN
.de XX
.nf
.ta 5.8125i
	\(sq
.fi
..
.am DE
.ls 2
.sp
..
.ds HP 12 12 12 12 12 12 12
.ds HF 3 3 2 2 2 2 2
.ND ""
.TL
On Heights of Monotonically Labelled Binary Trees
.AF "Bell Laboratories"
.AU "A. M. Odlyzko" AMO MH 11218 5617 2C-364
.TM ""
.AS 1
.ls 2
.P
Monotonically $k "-"$labelled binary trees are
binary trees in which the internal nodes are labelled
with integers from $"{" 1,2,"...", k "}"$ for some
$k ~>=~ 2$, and the labels along any path starting at
the root are non-decreasing.
A simple proof is given of a result of Kirschenhofer and
Prodinger, namely that the average height of
monotonically \%2-labelled binary trees of size
(number of internal nodes) $n$ is
.sp
.ce
$wig ~ sqrt { {8 pi n} over 3 } ~~~ as ~~~ nInf ~.$
.sp
It is also shown how to extend this result
to the case of $k ~>=~ 3$ labels.
.ls 1
.AE
.OK ""
.MT 4
.ls 2
.H 1 "Introduction"
.P
A monotonically labelled binary tree is a binary
tree with integer labels attached to the internal
nodes in such a way that the labels along any
path from the root are nondecreasing.
If there is only one label, we are dealing with ordinary
binary trees.
Prodinger and Urbanek [6]
introduced a variety of families of
monotonically labelled trees and obtained enumerative
results about many of them.
This note is concerned largely with monotonically labelled
binary trees that have at most two labels,
call them 1 and 2.
Several examples of such trees are shown in Fig.\ 1.
Prodinger and Urbanek showed that the number $y2n$
of monotonically \%2-labelled binary trees of size $n$
(i.e., with $n$ internal nodes and with $k ~=~ 2$ labels) satisfies
.DS 3
.EQ (1.1)
y2n ~wig~ 4( 6 pi ) sup -1/2 ( 16/3) sup n n sup -3/2 ~~~ as ~~~
nInf ~.
.EN
.DE
This result followed rather easily from the formula
.DS 3
.EQ (1.2)
y2z ~=~ {1 ~-~ ( -1 ~+~ 2 (1-4z) sup 1/2 ) sup 1/2 } over
2z ~,
.EN
.DE
proved in [6],
where $y2z$ is the generating function of the $y2n$:
.DS 3
.EQ (1.3)
y2z ~=~ sum from n=0 to inf ~ y2n ~ z sup n ~.
.EN
.DE
In the case of ordinary binary trees $(k ~=~ 1)$, it is well-known
that the corresponding generating function
$y1z$ satisfies
.DS 3
.EQ (1.4)
y1z ~=~
{1 ~-~ (1-4z) sup 1/2} over 2z ~,
.EN
.DE
and
.DS 3
.EQ (1.5)
y1n ~=~ 1 over n+1 ~ left ( pile {2n above n} right ) ~wig~
pi sup -1/2 4 sup n n sup -3/2 ~~~ as ~~~
nInf ~.
.EN
.DE
.P
Kirschenhofer and Prodinger [5] later
studied the average heights of monotonically \%2-labelled
binary trees.
(For some other results about average shapes of such trees,
see [4].)
As is true of ordinary binary trees (\f2cf.\f1 [2]),
there do not appear to be any closed-form formulas like
(1.2) for any generating functions of heights.
However, in [2] it was shown that if $hkn$ denotes
the average height of monotonically labelled binary
trees of sizes $n$ with $k$ labels,
.DS 3
.EQ (1.6)
hkn ~=~ ykn sup -1 ~ sum from T ~ ht(T) ~,
.EN
.DE
where the sum is over all the different monotonic
$k "-"$labellings of all the binary trees of size $n$,
then
.DS 3
.EQ (1.7)
h1n ~wig~ 2 ( pi n ) sup 1/2 ~~~ as ~~~ nInf ~.
.EN
.DE
The proof relied on a very detailed study
of singularities of generating functions.
(A different proof of (1.7), which also
used deep analytic methods, has been given in [1].)
Kirschenhofer and Prodinger [5] extended the
method of [2] and showed that
.DS 3
.EQ (1.8)
h2n ~wig~ (8 pi n / 3 ) sup 1/2 ~~~ as ~~~ nInf ~.
.EN
.DE
This note shows that it is possible to obtain the result (1.8)
from (1.7) by quite elementary methods, without having to
resort to the analytic machinery of Kirschenhofer and Prodinger.
Furthermore, the new method leads to a simple
proof that for any fixed $k ~>=~ 1$, there is an easily computable
constant $c sub k$ such that
.DS 3
.EQ
hkn ~wig~ c sub k n sup 1/2 ~~~ as ~~~ nInf ~.
.EN
.DE
The proof is not completely elementary in that it relies on the analytic
results of [2], but it is short and easy to motivate.
.H 1 "Proof of the $bold {k~=~2}$ \f3result\f1"
.P
The basic idea behind our proof is very simple.
A typical monotonically \%2-labelled binary tree
($k ~=~ 2$ labels will be assumed throughout this
section) looks like the tree in Fig.\ 2.
If $m$ nodes have the label\ 2, then the $n-m$ nodes with label\ 1 form
(after the addition of the necessary leaves) a binary tree of size $n-m$.
The $m$ nodes with label\ 2 then can be regarded as
forming an ordered $(n-m+1) "-"$rooted forest of binary trees of total
size $m$, with some of the trees in that forest possibly being
empty.
Figure\ 3 illustrates such a decomposition.
For each pair of a binary tree of size $n-m$ and an ordered
$(n-m+1) "-"$rooted binary forest, there is exactly one monotonically
\%2-labelled binary tree that decomposes into this pair.
Since it is easy to enumerate both binary trees and ordered
binary forests, this decomposition leads to a quick
enumeration of monotonically \%2-labelled binary trees
by $m$, the number of nodes labelled with 2.
This can then be used to give another
proof of (1.2).
Furthermore, this enumeration shows that the only significant
contribution to the total number of monotonically \%2-labelled
binary trees comes from the trees for which $m$
satisfies $m ~wig~ n/3$.
Now the height of an ordered $N "-"$rooted binary forest of
size $M$, where $M ~wig~ N/2$, is very small
(Lemma\ 2), so the average height of a monotonically
\%2-labelled binary tree of size $n$ is approximately
that of an ordinary binary tree of size $wig ~2n/3$, which
satisfies (1.8) by (1.7).
The rest of this section fills in the details of the above argument.
.HU "Lemma\ 1."
.I
The number $trn$ of ordered $r "-"$rooted binary forests of
size $n$ satisfies
.DS 3
.EQ (2.1)
trn ~=~ r over 2n+r ~ left ( pile {2n+r above n} right ) ~.
.EN
.DE
.R
.HU "Proof."
This result is old and well-known, although perhaps
not in this particular form.
Note that $trn$ is the coefficient of $z sup n$
in $y sub 1 (z) sup r$, and so satisfies (2.1) by [7; p.\ 153],
or by Lagrange inversion, or by using Cauchy's formula
and shifting the contour of integration.
In addition, this lemma can be deduced from
[3; p.\ 125, Problem\ 2.7.3(a)].
.XX
.P
Lemma\ 1, Eq.\ (1.5), and the decomposition described at the
beginning of this section show that the number of monotonically
\%2-labelled binary trees of size $n$ with $m$ nodes labelled 2
is exactly
.DS 3
.EQ (2.2)
u sub m ~=~ u sub m (n) ~=~ 1 over n+m+1 ~
left ( pile {2n-2m above n-m} right ) left ( pile {n+m+1 above m} right ) ~.
.EN
.DE
Hence for $m ~<=~ n-2$,
.DS 3
.EQ (2.3)
{u sub m} over {u sub m+1} ~=~
4 ~ {(n-m) (m+1)} over {(n+m+1) (n-m-1)} ~,
.EN
.DE
so
.DS 3
.EQ
left ( {u sub m} over {u sub m+1} ~-~ 1 right )
(n+m+1) (n-m-1) ~=~
1 + 6n - 4m - ( n-3m ) ( n-m ) ~,
.EN
.DE
and therefore
$u sub m ~<~ u sub m+1$ for
$0 ~<=~ m ~<=~ [n/3] ~-~ 20$,
and $u sub m ~>~ u sub m+1$ for $[n/3] ~+~ 20 ~<=~ m ~<=~ n-20$.
Let $m sup star ~=~ [n/3]$.
Then Eq.\ (2.3) shows that uniformly for $0 ~<=~ h ~<=~ n sup 2/3$,
.DS 3
.EQ
{u sub {m sup star - h}} over {u sub {m sup star}} ~ mark =~
prod from j=0 to h-1 ~
{4( m sup star - j ) ( n - m sup star + 1 + j )} over
{(n+m sup star - j ) ( n - m sup star + j )}
.EN
.sp
.EQ (2.4)
lineup =~
prod from j=0 to h-1 ~
left ( 1 ~-~ {n-3m sup star + 3j} over {n+m sup star -j} right )
left ( 1 ~+~ 1 over {n-m sup star + j} right )
.EN
.sp
.EQ
lineup =~
exp ( - 9h sup 2 ( 8n ) sup -1 ~+~ o (1) ) ~~~ as ~~~ nInf ~.
.EN
.DE
An analogous argument shows that (2.4) also holds for
$- n sup 2/3 ~<=~ h ~<=~ 0$.
Therefore we conclude that the probability of a random
monotonically \%2-labelled binary tree having $m$ labels equal to 2, with
$0 ~<=~ m ~<=~ n-20$ and
$| ^ m-m sup star ^ | ~>=~ n sup 2/3$,
is $scrO ( exp ( -n sup 1/3 ) )$.
The same bound also applies to the probability of
$m ~>=~ n-20$, by a simple estimate of the expression
(2.2) for $u sub m$.
Since the height of a tree of size $n$ is
$<=~ n+1$, we conclude that trees with
$|^ m-m sup star ^| ~>=~ n sup 2/3$ contribute
$scrO ( n ~ exp ( -n sup 1/3 ))$ to the average height.
.P
We now observe that the height of a monotonically
\%2-labelled binary tree which decomposes into a
binary tree $T$ and an ordered binary forest $F$ is
bounded below by
the height of $T$ and above by
the sum of
the height of
$T$ and the height of $F$.
Since the average height of $T$ is by the preceding discussion
asymptotic to the average height of an ordinary binary tree
of size $wig 2n/3$, it only remains to show
that the average height of an $(n-m+1) "-"$rooted ordered binary forest
of size $m$ is $o(n sup 1/2 )$ for $m ~wig~ n/3$.
That result, however, follows easily from the following
lemma.
.HU "Lemma\ 2."
.I
The average height of an ordered $r "-"$rooted binary forest
of size $n$, where $1/10 ~<=~ n/r ~<=~ 10$, is
$scrO ( log ~ n )$.
.R
.HU "Proof."
We will actually obtain an estimate for the probability that
any one of the $r$ trees is large.
Let
.DS 3
.EQ
N(r,^n,^s) ~=~ | ^ "{" r "-" roman "rooted forests of size" ~
n ~ roman "with some tree of size" ~ s "}" ^ | ~.
.EN
.DE
Then $N(r,^n,^s) ~<=~ U(r,^n,^s)$, where
.DS 3
.EQ
U(r,^n,^s) ~=~ r y sub {1,^s} t sub {r-1,^n-s} ~=~
r over s+1 ~
left ( pile {2s above s} right ) ~
r-1 over 2n-2s+r-1 ~
left ( pile {2n-2s+r-1 above n-s} right ) ~.
.EN
.DE
But for $n$ sufficiently large,
.DS 3
.EQ
{U(r,^n,^s+1)} over {U(r,^n,^s)} ~ mark =~
{2(n-s)(n-s+r-1)(2s+1)} over
{(s+2)(2n-2s+r-3)(2n-2s+r-2)}
.EN
.sp
.EQ
lineup <~ {4(n-s)(n-s+r-1)} over
{(2n-2s+r-3)(2n-2s+r-2)} ~<~ 1 ~,
.EN
.DE
so that $U(r,^n,^s)$ is monotone decreasing in $s$.
We now consider $s ~<=~ c ~ log ~ n$ for some $c ~>~ 0$.
We have
.DS 3
.EQ
{U(r,^n,^s)} over trn ~ mark =~
scrO left ( n left ( pile {2s above s} right )
left ( pile {2n-2s+r-1 above n-s} right )
left ( pile {2n+r above n} right ) sup -1 right )
.EN
.sp
.EQ
lineup =~ scrO left ( n4 sup s ~
{n(n-1)"..."(n-s+1)} over
{(n+r+1)"..."(n+r+s)} ~
prod from j=0 to n-s-1 ~
{2n+r-2s-1-j} over {2n+r-j} right )
.EN
.sp
.EQ
lineup =~ scrO left ( n 4 sup s 
~exp ( - 2ns / ( 2n+r )) right )
.EN
.sp
.EQ
lineup =~ scrO left ( n ~exp ( - s/10 ) right ) ~.
.EN
.DE
If $s ~>=~ 100 ~ log ~ n$, we find that the
probability that any tree in the forest has size $>=~ s$
is $scrO ( n sup -8 )$.
Since the height of the forest is bounded above by the
size of the largest tree in it,
this proves the lemma.
.XX
.H 1 "Extensions to $bold {k ~>=~ 3}$ \f3labels\f1"
.P
The result obtained above can be easily extended to
estimate the average height of monotonically $k "-"$labelled
binary trees for any fixed $k$.
Any monotonically $k "-"$labelled binary tree of size $n$ and with $m$
labels equal to $k$ can be decomposed uniquely into a monotonically
$(k-1) "-"$labelled binary tree of size $n-m$ (with internal
nodes being precisely the nodes of the original tree with
labels $< ~ k$) and an ordered $(n-m+1) "-"$rooted binary forest of
size $m$.
Hence
.DS 3
.EQ (3.1)
y sub k,n ~=~
sum from m=0 to n ~
y sub k-1,n-m ~ t sub n-m+1,n ~.
.EN
.DE
Since Prodinger and Urbanek [6] have shown
that
.DS 3
.EQ
y sub g,n ~wig~ p sub g ~ q sub g sup -n r sup -3/2 ~~~ as ~~~
n ~->~ inf
.EN
.DE
for some positive real numbers $p sub g$ and $q sub g$,
it is readily seen that the only significant
contribution to the sum in (3.1) comes from the
terms with
.DS 3
.EQ (3.2)
m ~wig~ {q sub k-1} over {1-q sub k-1} ~ n ~~~ as ~~~ n ~->~ inf ~.
.EN
.DE
Therefore the average height of monotonically $k "-"$labelled
binary trees of size $n$ is asymptotic to the average
height of monotonically $(k-1) "-"$labelled binary trees of
size $[nq sub k-1 / ( 1 - q sub k-1 )]$.
Induction on $k$ and (1.7) show that this average height is
asymptotic to
.DS 3
.EQ
c sub k ~ n sup 1/2 ~~~ as ~~~ n ~->~ inf ~,
.EN
.DE
where
.DS 3
.EQ (3.3)
c sub k sup 2 ~=~ 4 pi ~ prod from i=1 to k-1 ~
{q sub i} over {1-q sub i} ~.
.EN
.DE
Since $q sub 1 ~=~ 1/4$ and $q sub k+1 ~=~ q sub k (1-q sub k )$,
as is shown in [6], the $c sub k$ can be evaluated fast.
It can also be shown that
.DS 3
.EQ
log ~ c sub k ~wig~ -~ 1 over 2 ~ k ~ log ~ k
~~~ as ~~~ k ~->~ inf ~.
.EN
.DE
.bp
.ce
.I
REFERENCES
.R
.AL
.LI
G.\ B. Brown and B.\ O. Schubert,
On random binary trees,
preprint.
.LI
P.\ Flajolet and A.\ M. Odlyzko,
The average height of binary trees and other sample trees,
.ul
J.\ Computer Systems Sci.,
.B 25
(1982), 171-213.
.LI
I.\ P. Goulden and D.\ M. Jackson,
.ul
Combinatorial Enumeration,
Wiley, 1983.
.LI
P.\ Kirschenhofer,
On the average shape of monotonically labelled tree
structures,
.ul
Discrete Appl. Math.
.B 7
(1984), 161-181.
.LI
P.\ Kirschenhofer and H.\ Prodinger,
On the average height of monotonically labelled binary trees,
Colloq. Math. Soc. Janos Bolyai,
Proc. 1981 Eger Combinatorics Conference,
to appear.
.LI
H.\ Prodinger and F.\ J. Urbanek,
On monotone functions of tree structures,
.ul
Discrete Appl. Math.
.B 5
(1983),
223-239.
.LI
J.\ Riordan,
.ul
Combinatorial Identities,
Wiley, 1968.
.LE
.bp
.ce
.I
FIGURE CAPTIONS
.R
.VL 8
.LI "Fig.\ 1."
Half of the six monotonically labelled binary trees
of size three.
(The other three are mirror images of the ones shown.)
.LI "Fig.\ 2."
General schematic of a monotonically \%2-labelled
binary tree.
.LI "Fig.\ 3."
Decomposition of a monotonically labelled binary tree with labels
1 and 2 into a binary tree and an ordered binary forest.
(\(sq denotes the empty binary tree.)
.LE
.ls 1
.CS \0 \0 \0 \0 \0 \0