\documentstyle[oldlfont,righttag,ctagsplt,11pt]{amsart}

\catcode`\@=11
\if@twocolumn \textwidth175mm \marginparsep2.5mm
              \oddsidemargin-7.9mm \evensidemargin-7.9mm
\else  \ifcase \@ptsize\relax
       \textwidth145mm \oddsidemargin7.1mm  \evensidemargin7.1mm \or
       \textwidth154mm \oddsidemargin2.6mm  \evensidemargin2.6mm \or
       \textwidth164mm \oddsidemargin-2.4mm \evensidemargin-2.4mm \fi
   \marginparsep4mm \fi
\ifcase \@ptsize\relax \textheight 52\baselineskip \or
       \textheight 46\baselineskip \or \textheight 43\baselineskip \fi
\addtolength{\textheight}{\topskip} \topmargin-10mm
\catcode`\@=12

% emlines.sty  Mai 1990, Georg Horn / Eberhard Mattes.
%
% Makros zum Zeichnen von Linien mit beliebiger Steigung.
%
% ****************************************************************
% * Nur funktionsf�hig mit den dvi-Treibern von Eberhard Mattes  *
% * ab Version 1.3j.                                             *
% ****************************************************************
%
% Der Makro \emline#1#2#3#4#5#6 verbindet den Punkt mit den
% Koordinaten (#1,#2) und den Punkt mit den Koordinaten (#4,#5).
% Die Parameter #3 und #6 werden ignoriert.
%
% TeXcad erzeugt Aufrufe dieses Makros f�r mit eingeschalteter
% EMLines-Option gezeichnete Linien.
% (z.B. \emline{0.0}{0.0}{1}{17.0}{4.0}{2}).
%
\def\emline#1#2#3#4#5#6{%
       \put(#1,#2){\special{em:moveto}}%
       \put(#4,#5){\special{em:lineto}}}
%
% Der Makro \newpic#1 wird ignoriert, da nicht mehr erforderlich.
%
\def\newpic#1{}

\title{ABZ\"AHLPROBLEME BEI B\"AUMEN}
\author[]{Helmut Prodinger (Wien)}
\date{}


\def \Reg{\text{\rm Reg}}

\begin{document}
\maketitle
\noindent
Es sei ${\cal B}$ die Familie der bin\"aren B\"aume. ${\cal B}$ kann durch eine
{\it formale Gleichung} beschrieben werden:
\begin{figure}[h]
%\input{baum2.pic} 
\special{em:linewidth 0.4pt}
\unitlength .800mm
\linethickness{0.4pt}
\begin{picture}(117.00,24.36)
\put(106.33,21.67){\circle{5.37}}
\emline{104.33}{19.67}{1}{98.67}{11.00}{2}
\emline{108.00}{19.33}{3}{114.33}{11.33}{4}
\put(67.67,13.00){\framebox(6.33,5.67)[cc]{}}
\put(96.67,8.00){\makebox(0,0)[cc]{$\cal B$}}
\put(117.00,8.00){\makebox(0,0)[cc]{$\cal B$}}
\put(86.67,16.33){\makebox(0,0)[cc]{+}}
\put(56.67,16.33){\makebox(0,0)[cc]{$\cal B\ \ = \ \ $}}
\end{picture}
\end{figure}


\noindent
Dies besagt, da{\ss} ein bin\"arer Baum entweder ein Blatt (externer Knoten) ist,
oder eine Wurzel zusammen mit einem linken und einem rechten Teilbaum, welche 
selbst bin\"are B\"aume sind. Diese formale Gleichung kann \"ubersetzt werden in
eine Gleichung f\"ur die erzeugende Funktion $B(z)$:

$$ B(z)=1+zB^{2}(z);$$
$$ B(z)=\frac{1-\sqrt{1-4z}}{2z}=\sum_{n\geq 0}\,\frac{1}{n+1}\,{2n\choose n}z^n.$$

Bin\"are B\"aume k\"onnen verwendet werden, um arithmetische Ausdr\"ucke 
darzustellen:

\begin{figure}[h]
%\input{baum1.pic} 
\special{em:linewidth 0.4pt}
\unitlength 0.70mm
\linethickness{0.4pt}
\begin{picture}(170.00,59.09)
\put(83.00,54.00){\circle{10.18}}
\emline{79.33}{50.33}{1}{65.00}{36.00}{2}
\emline{86.00}{50.00}{3}{100.00}{36.00}{4}
\put(118.33,3.33){\framebox(10.00,9.67)[cc]{}}
\put(55.33,26.33){\framebox(10.00,9.67)[cc]{}}
\put(101.00,31.00){\circle{10.18}}
\emline{97.33}{27.33}{5}{83.00}{13.00}{6}
\emline{104.00}{27.00}{7}{118.00}{13.00}{8}
\put(73.33,3.33){\framebox(10.00,9.67)[cc]{}}
\put(83.00,54.00){\makebox(0,0)[cc]{$\times$}}
\put(101.00,31.00){\makebox(0,0)[cc]{$+$}}
\put(60.33,31.00){\makebox(0,0)[cc]{3}}
\put(78.33,8.00){\makebox(0,0)[cc]{7}}
\put(123.33,8.00){\makebox(0,0)[cc]{4}}
\put(139.67,32.00){\makebox(0,0)[cc]{$\longleftrightarrow$}}
\put(170.00,32.00){\makebox(0,0)[cc]{$3\, \times \, (\, 7\, +\, 4\, )$}}
\end{picture}
\end{figure}


Die Auswertung kann mit Hilfe von Registern erfolgen; diese werden verwendet,
um Zwischen\-ergebnisse zu speichern.

Die {\it Registerfunktion {\rm Reg}(t)} ist definiert als die minimale Anzahl von
Registern zur Auswertung des Baumes {\it t} unter Verwendung der optimalen 
Strategie.
\newpage

Es gilt: 

$$ {\rm Reg}(\square)=0 $$
\begin{figure}[h]
%\input{baum3.pic} 
\special{em:linewidth 0.4pt}
\unitlength 1.00mm
\linethickness{0.4pt}
\begin{picture}(49.00,19.67)
%\vector(27.33,10.00)(32.33,19.33)
\put(32.33,19.33){\circle{2.67}}
\emline{27.33}{10.00}{1}{32.33}{19.33}{2}
%\end
\emline{32.67}{18.67}{3}{37.33}{10.67}{4}
\put(26.67,6.67){\makebox(0,0)[cc]{$t_1$}}
\put(38.00,6.67){\makebox(0,0)[cc]{$t_2$}}
\put(19.00,14.33){\makebox(0,0)[cc]{$\Reg\bigg($}}
\put(42.67,14.67){\makebox(0,0)[lc]{$\bigg)\quad =\quad \Bigg\{\ $}}
\put(65.00,19.67){\makebox(0,0)[lc]{$1+\Reg(t_1)$\quad falls $\Reg(t_1)=\Reg(t_2)$}}
\put(65.00,10.00){\makebox(0,0)[lc]{$\max\{\Reg(t_1),\Reg(t_2)\}$\quad sonst}}
\end{picture}
\end{figure}



Es sei ${\cal R}_{p} \ ({\cal S}_{p})$ die Familie der B\"aume mit Registerfunktion
$=p \: \ (\geq p);$
$R_{p}(z)$ und $S_{p}(z)$ seien die entsprechenden erzeugenden Funktionen. Man sieht 
unmittelbar:
\begin{figure}[h]
%\input{baum5.pic} 
\special{em:linewidth 0.4pt}
\unitlength 1mm
\linethickness{0.4pt}
\begin{picture}(129.00,22.67)
%\vector(50.00,9.00)(57.33,22.00)
\put(57.33,22.00){\circle{2.67}}
\emline{50.00}{9.00}{1}{57.33}{22.00}{2}
%\end
\emline{57.67}{21.33}{3}{62.33}{9.33}{4}
%\vector(83.33,9.33)(90.67,22.33)
\put(90.67,22.33){\circle{2.67}}
\emline{83.33}{9.33}{5}{90.67}{22.33}{6}
%\end
%\vector(116.67,9.67)(124.00,22.67)
\put(124.00,22.67){\circle{2.67}}
\emline{116.67}{9.67}{7}{124.00}{22.67}{8}
%\end
\emline{91.00}{21.67}{9}{95.67}{9.67}{10}
\emline{124.33}{22.00}{11}{129.00}{10.00}{12}
\put(47.33,6.00){\makebox(0,0)[cc]{${\cal R}_{p-1}$}}
\put(62.33,5.67){\makebox(0,0)[cc]{${\cal R}_{p-1}$}}
\put(27.67,15.67){\makebox(0,0)[cc]{${\cal R}_p$}}
\put(41.00,15.67){\makebox(0,0)[cc]{$=$}}
\put(75.00,15.67){\makebox(0,0)[cc]{$+$}}
\put(108.33,15.67){\makebox(0,0)[cc]{$+$}}
\put(81.33,5.33){\makebox(0,0)[cc]{$\sum\limits_{j<p}{\cal R}_j$}}
\put(129.00,5.33){\makebox(0,0)[cc]{$\sum\limits_{j<p}{\cal R}_j$}}
\put(96.67,7.00){\makebox(0,0)[cc]{${\cal R}_p$}}
\put(117.00,7.00){\makebox(0,0)[cc]{${\cal R}_p$}}
\end{picture}
\end{figure}
\begin{figure}[h]
%\input{baum6.pic} 
\special{em:linewidth 0.4pt}
\unitlength 1mm
\linethickness{0.4pt}
\begin{picture}(129.00,22.67)
%\vector(50.00,9.00)(57.33,22.00)
\put(57.33,22.00){\circle{2.67}}
\emline{50.00}{9.00}{1}{57.33}{22.00}{2}
%\end
\emline{57.67}{21.33}{3}{62.33}{9.33}{4}
%\vector(83.33,9.33)(90.67,22.33)
\put(90.67,22.33){\circle{2.67}}
\emline{83.33}{9.33}{5}{90.67}{22.33}{6}
%\end
%\vector(116.67,9.67)(124.00,22.67)
\put(124.00,22.67){\circle{2.67}}
\emline{116.67}{9.67}{7}{124.00}{22.67}{8}
%\end
\emline{91.00}{21.67}{9}{95.67}{9.67}{10}
\emline{124.33}{22.00}{11}{129.00}{10.00}{12}
\put(47.33,6.00){\makebox(0,0)[cc]{${\cal S}_{p-1}$}}
\put(62.33,5.67){\makebox(0,0)[cc]{${\cal S}_{p-1}$}}
\put(27.67,15.67){\makebox(0,0)[cc]{${\cal S}_p$}}
\put(41.00,15.67){\makebox(0,0)[cc]{$=$}}
\put(75.00,15.67){\makebox(0,0)[cc]{$+$}}
\put(108.33,15.67){\makebox(0,0)[cc]{$+$}}
\put(81.33,5.33){\makebox(0,0)[cc]{${\cal B\setminus\cal S}_{p-1}$}}
\put(129.00,5.33){\makebox(0,0)[cc]{${\cal B\setminus\cal S}_{p-1}$}}
\put(96.67,5.33){\makebox(0,0)[cc]{${\cal S}_p$}}
\put(117.00,5.33){\makebox(0,0)[cc]{${\cal S}_p$}}
\end{picture}
\end{figure}



Daher gilt:

$$ R_{p}=zR_{p-1}^{2} + 2zR_{p} \sum_{j<p}R_j ,\quad R_{0}=1~,$$
$$ S_{p}=zS_{p-1}^{2} + 2zS_{p}(B-S_{p-1}) ,\quad S_{0}=B~; $$
$$ S_{p}=\frac{zS_{p-1}^{2}}{1-2zB+2zS_{p-1}} ~.$$ 

Wir setzen $\varepsilon :=\sqrt{1-4z}=1-2zB $ :
$$
\frac{1}{S_{p}}=\frac{\varepsilon}{z}\, \frac{1}{S_{p-1}^{2}}+2\frac{1}{S_{p-1}}\: .
$$

Wir multiplizieren mit $\varepsilon /z$ und substituieren $U_{p}:=\varepsilon /zS_{p}$:

$$  U_{p}=U_{p-1}^{2}+2U_{p-1}\ \Rightarrow\  U_{p}+1=(U_{p-1}+1)^{2}\ \Rightarrow\  $$
$$  U_{p}=-1+(U_{0}+1)^{2^{p}} ;\quad U_{0}=\frac{\varepsilon}{zB}\Rightarrow $$
$$  S_{p}=\frac{\varepsilon}{z}\cdot\frac{1}{-1+\big(\frac{1+\varepsilon}{1-\varepsilon}
    \big)^{2^{p}}} ~ .
$$
Es ist g\"unstig, $z=u/(1+u)^{2}$ zu setzen:
$$
   S_{p}=\frac{1-u^{2}}{u}\cdot \frac{u^{2^{p}}}{1-u^{2^{p}}} 
$$
$$ 
   R_{p}=S_{p}-S_{p+1}=\frac{1-u^{2}}{u}\cdot \frac{u^{2^{p}}}{1-u^{2^{p+1}}}\: .
$$
Sei nun $M_{n}$ die mittlere Registerfunktion eines bin\"aren Baumes mit $n$ Knoten.
Es gilt:
$$
M_n=\frac{\sum_{p\geq0}\, p\cdot[z^n]R_p(z)}{[z^n]B(z)}=\frac{[z^n]\sum_{p\geq1}S_p(z)}
{[z^n]B(z)}\: .
$$

Wir studieren den Z\"ahler:

\begin{align*}\begin{split}
E(z)=\sum_{p\geq 1}S_p(z) & =  \frac{1-u^2}{u}\sum_{p\geq 1}
                                           \frac{u^{2^p}}{1-u^{2^p}}  \\
                          & =  \frac{1-u^2}{u}
                            \sum_{p\geq 1 \atop\lambda \geq 1} u^{2^p\lambda} \\
                          & =  \frac{1-u^2}{u}\sum_{k\geq 1} v_2(k)u^k
\end{split}\end{align*}
mit $v_2(k)=\sum\limits_{k=2^p\lambda ,\atop p,\lambda\geq 1}1$~. (Beachte\: $v_2(2n)=
1+v_2(n),\ v_2(2n+1)=0$.) 

Um den Koeffizienten von $z^n$ in $E(z)$ zu finden, bedienen wir uns einer
analytischen Methode. Das Verhalten der Koeffizienten wird n\"amlich weitgehend
beschrieben durch das Verhalten der erzeugenden Funktion in der N\"ahe der
Singularit\"aten am Konvergenzkreis. Es liegt eine Singularit\"at bei $u=1$ vor. \\

Mit Hilfe der {\it Mellin--Transformation} findet man f\"ur $t\to 0$:

$$
\sum_{k\geq 1}v_2(k)e^{-tk}\sim \sum_s {\rm Res}
       \left( \frac{\Gamma (s)\zeta (s)}{2^s-1}t^{-s}\right)
$$
und insgesamt $(z \to 1/4)$

$$
E(z)\sim 2\varepsilon \log_{2}\varepsilon +2\left(\frac{3}{2}-\log_22\pi 
  +\frac{\gamma}{\log2}\right)+4\sum_{k\not= 0}\varepsilon^{1-\chi_k}\: 
  \text{\ mit\ } 
\chi_k=\frac{2k\pi i}{\log2}
$$

Beachtet man noch, da{\ss}
$$
[z^n]B(z)\sim \frac{4^n}{\sqrt{\pi}}\, n^{-3/2}
$$
ist, folgt nun
$$
M_n\sim \log_4 n-\frac{1}{2}-\frac{\gamma}{2\log 2}-\frac{1}{\log 2}+\log_2 2\pi+
\frac{1}{\log 2}\sum_{k\neq 0}\, \zeta (\chi_k)\Gamma\big(\frac{\chi_k}{2}\big)
(\chi_k -1)^{n^{\chi_k /2}}.
$$
Es gilt $n^{\chi_k /2}=e^{2k\pi i\cdot\log_4 n}$, und somit $M_n\sim\log_4 n+
D(\log_4 n)$. \\
Hier ist $D(x)$ eine periodische Funktion mit Periode $1$. \\

Die Fourierreihenentwicklung $D(x)=\sum_k d_k\,  e^{2k\pi ix}$ ist:
\begin{align*}
d_0 &=-\frac{1}{2}-\frac{\gamma}{2\log 2}-\frac{1}{\log 2}+\log_2 
2\pi ,\\
d_k &=\frac{1}{\log 2}\, \zeta (\chi_k)\Gamma\big(\frac{\chi_k}{2}\big) 
(\chi_k -1), \; k\neq 0,\quad\chi_k =\frac{2k\pi i}{\log 2}.
\end{align*}
\medskip

Man kann auch {\it Motzkinb\"aume} betrachten:
\begin{figure}[h]
%\input{baum4.pic} 
\special{em:linewidth 0.4pt}
\unitlength 1.00mm
\linethickness{0.4pt}
\begin{picture}(102.00,17.05)
\put(77.67,3.67){\makebox(0,0)[cc]{$\cal M$}}
\put(95.00,3.67){\makebox(0,0)[cc]{$\cal M$}}
\put(102.00,3.67){\makebox(0,0)[cc]{$\cal M$}}
\put(87.00,11.00){\makebox(0,0)[cc]{+}}
\put(62.00,11.00){\makebox(0,0)[cc]{$\square\quad +$}}
\put(49.00,11.00){\makebox(0,0)[rc]{$\cal M\quad = \ $}}
\emline{77.67}{6.33}{1}{77.67}{16.00}{2}
\emline{98.00}{15.33}{3}{95.33}{6.33}{4}
\emline{98.33}{15.00}{5}{101.67}{6.67}{6}
\put(98.00,16.00){\circle{2.11}}
\put(77.67,16.00){\circle{2.00}}
\end{picture}
\end{figure}



${\cal M}$ kann aus ${\cal B}$ durch Substitution gewonnen werden:

\begin{figure}[h]
%\input{baum7.pic} 
\special{em:linewidth 0.4pt}
\unitlength 1.00mm
\linethickness{0.4pt}
\begin{picture}(112.00,24.00)
\put(37.67,19.00){\framebox(5.33,5.00)[cc]{}}
%\vector(53.00,21.67)(89.33,21.67)
\put(89.33,21.67){\vector(1,0){0.2}}
\emline{53.00}{21.67}{1}{89.33}{21.67}{2}
%\end
\put(107.67,21.67){\circle{2.67}}
\emline{107.67}{20.33}{3}{107.67}{12.33}{4}
\put(103.67,21.67){\makebox(0,0)[cc]{$\big($}}
\put(112.00,21.67){\makebox(0,0)[lc]{$\big)^\ast$}}
\put(105.00,7.00){\framebox(5.33,5.00)[cc]{}}
\end{picture}
\end{figure}

\begin{figure}[h]
%\input{baum7a.pic} 
\special{em:linewidth 0.4pt}
\unitlength 1.00mm
\linethickness{0.4pt}
\begin{picture}(110.67,21.01)
%\vector(51.67,17.67)(88.00,17.67)
\put(88.00,17.67){\vector(1,0){0.2}}
\emline{51.67}{17.67}{1}{88.00}{17.67}{2}
%\end
\put(106.33,17.67){\circle{2.67}}
\emline{106.33}{16.33}{3}{106.33}{8.33}{4}
\put(102.33,17.67){\makebox(0,0)[cc]{$\big($}}
\put(110.67,17.67){\makebox(0,0)[lc]{$\big)^\ast$}}
\put(106.33,6.33){\circle{2.67}}
\emline{105.67}{5.33}{5}{103.33}{2.33}{6}
\emline{107.33}{5.00}{7}{110.00}{2.33}{8}
\put(39.33,19.67){\circle{2.67}}
\emline{38.67}{18.67}{9}{36.33}{15.67}{10}
\emline{40.33}{18.33}{11}{43.00}{15.67}{12}
\end{picture}
\end{figure}


Daher:
$$
M(z)=\frac{1}{1-z}B\left(\frac{z}{(1-z)^2} \right).
$$
Die Registerfunktion von B\"aumen aus ${\cal M}$ wird durch die folgende Erweiterung
gewonnen:

\begin{figure}[h]
%\input{baum10.pic} 
\special{em:linewidth 0.4pt}
\unitlength 1.00mm
\linethickness{0.4pt}
\begin{picture}(66.00,16.39)
\put(62.00,15.33){\circle{2.11}}
\emline{62.00}{14.67}{1}{62.00}{7.33}{2}
\put(62.00,4.00){\makebox(0,0)[cc]{$t$}}
\put(58.00,10.33){\makebox(0,0)[rc]{$\Reg\Big($}}
\put(66.00,10.33){\makebox(0,0)[lc]{$\Big)\ = \ \Reg(t)$}}
\end{picture}
\end{figure}

Es gilt auch
$$
R_p^{({\cal M})}(z)=\frac{1}{1-z}\,  R_p \left(\frac{z}{(1-z)^2} \right) 
\quad \mbox{usw.}
$$
Deshalb ist die mittlere Registerfunktion jetzt gegeben durch
$$
\frac{[z^n]\frac{1}{1-z}E\big(\frac{z}{(1-z)^2}\big)}
{[z^n]\frac{1}{1-z}B\big(\frac{z}{(1-z)^2}\big)}\; .
$$
\"Ahnlich wie vorher erh\"alt man
$$
\sim\log_4 n+\bar{D}(\log_4 n).
$$

\medskip
Die Situation kann noch verallgemeinert werden durch Gewichte:

\begin{figure}[h]
%\input{baum12.pic} 
\special{em:linewidth 0.4pt}
\unitlength 1.00mm
\linethickness{0.4pt}
\begin{picture}(119.67,17.38)
\put(83.33,16.00){\circle{2.75}}
\put(114.33,16.00){\circle{2.75}}
\emline{83.33}{15.00}{1}{83.33}{5.33}{2}
\emline{110.00}{5.00}{3}{114.00}{14.67}{4}
\emline{114.67}{14.67}{5}{119.33}{5.33}{6}
\put(58.67,9.00){\framebox(5.00,4.67)[cc]{}}
\put(54.33,10.33){\makebox(0,0)[rc]{${\cal F} \ = \ c_0\cdot$}}
\put(80.33,10.33){\makebox(0,0)[rc]{$+\ c_1\cdot$}}
\put(105.67,10.33){\makebox(0,0)[rc]{$+\ c_2\cdot$}}
\put(109.33,2.00){\makebox(0,0)[cc]{$\cal F$}}
\put(119.67,2.00){\makebox(0,0)[cc]{$\cal F$}}
\put(83.33,1.33){\makebox(0,0)[cc]{$\cal F$}}
\end{picture}
\end{figure}
\medskip

In einem bin\"aren Baum bezeichnen wir einen Knoten $t$ als {\it kritisch}, falls
die Registerfunktion des linken und rechten Unterbaumes gleich sind. Nach l\"angerer 
Rechnung erh\"alt man: die mittlere Anzahl der kritischen Knoten eines bin\"aren
Baumes mit $n$ Knoten ist
$$
\frac{[z^n]V(z)}{[z^n]B(z)} \; ,
$$ 
wo
$$
V(z)=\frac{u(1+u)}{1-u}-2\cdot \frac{1-u^2}{u}\sum_{k\geq 1}\omega (k) u^k \; ;
\; \omega (k)=i\; \mbox{falls}\;  k=2^m(1+2i).
$$
Durch \"ahnliche Methoden wie vorher erh\"alt man:

\begin{center}
``ungef\"ahr $\frac{n}{3}$ Knoten sind kritisch"
\end{center}
Man kann auch explizit errechnen, da{\ss}
$$
[z^n]V(z)={2n\choose n-1}-2\sum_{k\geq 1}\omega (k)
\left[
{2n\choose n+1-k}-2{2n\choose n-k}+{2n\choose n-1-k}
\right].
$$
Durch partielle Summation (zweimal durchzuf\"uhren) und Information \"uber
$$
\sum_{n<N}\, \sum_{k\leq n}\omega (k)
$$
kann man das asymptotische Verhalten auch relativ ``elementar" (daf\"ur 
m\"uhsam) errechnen.
\medskip

Auf eine ungel\"oste Frage im Zusammenhang mit der Registerfunktion bin\"arer
B\"aume soll noch eingegangen werden:
Die erzeugende Funktion der bin\"aren B\"aume mit Registerfunktion $<p$ ist
$$
B(z)-S_p(z)=\frac{F_{2^p-1}(z)}{F_{2^p}(z)}\; ,
$$
mit
$$
F_n(z)=\sum_j {n-1-j \choose j}(-z)^j \;\quad\mbox{(Fibonaccipolynom)}.
$$
Die {\it linksseitige H\"ohe} $h$ eines bin\"aren Baumes ist definiert durch
$$
h(\square)=0
$$
\begin{figure}[h]
%\input{baum9.pic} 
\special{em:linewidth 0.4pt}
\unitlength 1.00mm
\linethickness{0.4pt}
\begin{picture}(67.00,14.67)
\put(61.33,13.67){\circle{2.00}}
\emline{60.67}{13.00}{1}{58.00}{4.67}{2}
\emline{61.67}{12.33}{3}{64.00}{5.00}{4}
\put(55.00,9.67){\makebox(0,0)[rc]{$h\Big($}}
\put(67.00,9.67){\makebox(0,0)[lc]{$\Big)\quad =\quad \max\{1+h(t_1),h(t_2)\}$}}
\put(57.67,2.67){\makebox(0,0)[cc]{$t_1$}}
\put(64.00,2.67){\makebox(0,0)[cc]{$t_2$}}
\end{picture}
\end{figure}

Die erzeugende Funktion der B\"aume mit $h(t)<h$ ist
$$
\frac{F_h(z)}{F_{h+1}(z)}
$$
Somit ist die Anzahl der bin\"aren B\"aume mit $n$ Knoten und Registerfunktion
$<p$ gleich der Anzahl der bin\"aren B\"aume mit $n$ Knoten und linksseitiger
H\"ohe $<2^p-1$. Gesucht ist eine geeignete Bijektion dieser Objekte.
\vspace{2cm}
\begin{center}
\textsc{Literatur}
\end{center}

\begin{enumerate}
\item N.G.de Bruijn, D.E.Knuth, S.O.Rice: The average height of planted plane trees,
           in: Graph Theory and Computing (R.C.Read, Ed.), 15-22, Academic Press, 1972.
\item P.Flajolet: Analyse d'algorithmes de manipulation d'arbres et de 
           fichiers, Th\`ese Paris-Sud-Orsay, 1979. 
\item P.Flajolet, A.Odlyzko: The average height of binary trees and other simple
           trees, JCSS 25(1982), 171-213.
\item P.Flajolet, H.Prodinger: The number of registers to evaluate unary-binary
           trees, SIAM J. Computing 15(1986), 629-640.
\item P.Flajolet, J.C.Raoult, J.Vuillemin: The number of registers required for
           evaluating arithmetical expressions, TCS 9(1979), 99-125.
\item R.Kemp: The average number of registers to evaluate a binary tree optimally,
           Acta Inf. 11(1979), 313-372.
\item H.Prodinger: Some recent results on the register function of a binary tree,
           Annals of Discrete Math. 33(1987), 241-260.
\item H.Prodinger, R.F.Tichy: \"Uber ein zahlentheoretisches Problem aus der
           Informatik, Sitzungsberichte der \"Osterreichischen Akademie der 
           Wissenschaften, Abt. II, 192(1983), 385-396.
\end{enumerate}
 
\end{document}

