% AMSTEX-file 
\input amstex
\documentstyle{amsppt}

\NoBlackBoxes
\TagsOnRight
\vsize = 21 cm
\hsize = 14 cm
%\nologo
\define \lli {\left(}
\define \rre {\right)}
\define \mq {\overline \mu_i}
\define \mqj {\overline \mu_j}

\topmatter
\title
DIE KOMPONENTENVERTEILUNG VON GES\"ATTIGTEN  \\
TEILGRAPHEN IN BAUMFAMILIEN
\endtitle
\author
Gerd Baron und Michael Drmota
\endauthor
\affil
Technische Universit\"at Wien
\endaffil
\address{
Abteilung f\"ur Diskrete Mathematik,
Technische Universit\"at Wien,
Wiedner Hauptstra{\ss}e 8--10/118,
A-1040 Wien, \"Osterreich.
}
\endaddress
\endtopmatter

\document
Ein Teilgraph $H$ eines Graphen $G$ (mit Knotenmenge $V(G)$ und
Kantenmenge $E(G)$) hei{\ss}t ges\"attigt, wenn eine Kante $(v,w)\in E(G)$ in
$E(H)$ enthalten ist, sobald die Knoten $v,w$ in $V(H)$ liegen.
Es bezeichne $g_{klm}(G)$ $(m = (m_1,m_2,\ldots))$ die Anzahl der
ges\"attigten Teilgraphen $H$ von $G$ mit $|V(H)| = k$, $|E(H)|=l$ und
$m_j$ (Zusammenhangs-) Komponenten mit $j$ Knoten $(j\ge 1)$.

Es sei $\Cal F$ eine einfach erzeugte Baumfamilie von ebenen Wurzelb\"aumen,
die durch eine Potenzreihe $\varphi(t) = \sum\limits_{i\ge 0} \varphi_it^i$
$(\varphi_0 =1)$
charakterisiert wird, mit Hilfe derer jedem ebenen Wurzelbaum $T$ ein
Gewicht $\omega(T)$ zugeordnet wird, soda{\ss} $\omega(T)>0$ nur f\"ur B\"aume
$T$ aus $\Cal F$ gilt. (Siehe \cite{MM}.)
Ist nun $C(x,y,z,v) = \sum\limits_{n,k,l,m}
c_{nklm}x^ny^kz^lv^m$ ($v=(v_1,v_2,\ldots)$,
$v^m=v_1^{m_1}v_2^{m_2}\cdots)$) die (formale) erzeugende Funktion
der Gr\"o{\ss}en $c_{nklm} = \sum\limits_{|V(T)| = n} \omega(T)g_{klm}(T)$,
so erf\"ullt diese, wie in \cite{BD} gezeigt wurde, die Funktionalgleichung
$$
\aligned
C &= x\varphi(C)
+ xy\varphi \lli zC+(1-z)x\varphi(C)
+ \sum_{j\ge 1} (1-v_j)(xyz)^j
\frac 1j [t^{j-1}] \varphi\lli x\varphi(C)+t \rre^j \rre\\
&- \sum_{j\ge 1} (1-v_j)(xy)^jz^{j-1}
\frac 1j [t^{j-1}] \varphi\lli x\varphi(C)+t \rre^j .
\endaligned
\tag 1
$$
Sei weiters $J$ eine endliche Menge positiver ganzer Zahlen und
$c_{nklm_J} = \sum\limits_{m_j,j\not\in J} c_{nklm}$
($m_J = (m_j)_{j\in J}$), dann ist $C(x,y,z,v_J)$ die erzeugende
Funktion dieser Zahlen, wobei in $v$ f\"ur $j\not\in J$ $v_j = 1$
gesetzt wird. (Entsprechend ist $C(x,y,1,v_J)$ die erzeugende
Funktion von Gr\"o{\ss}en $c_{nk\cdot m_J}$, usw.)

Ist nun $(X_n^J)$ eine Folge von Zufallsvektoren der Dimension $|J|+2$
mit $\text{P}[X_n^J = (k,l,m_J)] = c_{nklm_J}/c_n$
($c_n = \sum\limits_{k,l,m_J} c_{nklm_J}$), so wurde in \cite{BD}
gezeigt, da{\ss} $(X_n^J)$ unter sehr schwachen Voraussetzungen f\"ur
$\varphi(t)$ asymptotisch normalverteilt ist mit
Mittel $\mu_n^J = \mu^J n+ O(1)$ und Kovarianzmatrix
$\Sigma_n^J = \sigma^J n + O(1)$. Es wurden allerdings nur
$$
\mu^J = \lli \frac 12,\frac 14, (\mu_j)_{j\in J} \rre \qquad\text{mit}
\quad\mu_j = \frac{\frac 1j [t^{j-1}]\varphi\lli \frac {u_0}2 + t\rre^j }
{2^{j+1} \varphi'(u_0)^{j-1} \varphi(u_0) } 
\tag 2
$$
(wobei $u_0$ die positive L\"osung von $t\varphi'(t)=\varphi(t)$ bedeutet)
und $\Sigma^J$ f\"ur $J = \emptyset$ angegeben. F\"ur $J = \{i,j\}$
ergibt sich
$$
\Sigma^J =  \pmatrix  \frac 14 & \frac 14 & \sigma_{yi} & \sigma_{yj}\\
\frac 14 & \frac {5+\alpha}{16} & \sigma_{zi} & \sigma_{zj} \\
\sigma_{yi} & \sigma_{zi} & \sigma_{ii} & \sigma_{ij}\\
\sigma_{yj} & \sigma_{zj} & \sigma_{ij} & \sigma_{jj}
\endpmatrix\qquad\text{mit}\quad
\alpha= \frac {\varphi(u_0)\varphi''(u_0)}{\varphi'(u_0)^2},
$$
$$
\aligned
\sigma_{yi} &= \frac {(i-1)\mu_i-i\mq}2 \qquad\text{mit}\quad
\mq = \frac{\frac 1i [t^{i}]\varphi\lli \frac {u_0}2 + t\rre^i }
{2^{i+2} \varphi'(u_0)^{i} }, \\
\sigma_{zi} &= \frac {(3i-5-\alpha)\mu_i}4 - \frac{i\mq}2,  \\
\sigma_{ii} &= \mu_i + (1+\alpha-2i)\mu_i^2 - \frac 1\alpha \lli
\mu_i-i\mq \rre^2, \\
\sigma_{ij} &= (1+\alpha-i-j)\mu_i\mu_j - \frac 1\alpha \lli
\mu_i-i\mq \rre\lli\mu_j-j\overline \mu_j \rre.
\endaligned
\tag 3
$$
F\"ur gr\"o{\ss}eres $J$ l\"a{\ss}t sich das Resultat daraus unmittelbar ablesen.
Au{\ss}erdem erh\"alt man jetzt wie in \cite{BD} beschrieben multivariate
asymptotische Entwicklungen f\"ur $c_{nklm_J}$, $c_{nk\cdot m_J}$, usw.

Da im allgemeinen die Eintragungen f\"ur $\Sigma^J$ umst\"andlich zu
berechnen sind, kann man wie f\"ur $\mu_j$ in \cite{BD} asymptotische
Entwicklungen angeben. Sie berechnen sich aus den asymptotischen 
Entwicklungen von $\mu_j$ und $\overline\mu_j$:
$$
\aligned
\mu_j &= \frac 1{2u_0} \left[ \frac {\varphi\lli \frac {u_0}2 + v_0 \rre }
{2\pi \varphi''\lli \frac {u_0}2 + v_0 \rre } \right]^{\frac 12}
\left[ \frac {\varphi'\lli \frac {u_0}2 + v_0 \rre }{2\varphi'(u_0)}
\right]^j j^{-3/2} \lli 1 + O \lli \frac 1j \rre \rre, \\
\overline \mu_j &=\frac 1{4v_0} \left[ 
\frac {\varphi\lli \frac {u_0}2 + v_0 \rre }
{2\pi \varphi''\lli \frac {u_0}2 + v_0 \rre } \right]^{\frac 12} 
\left[ \frac {\varphi'\lli \frac {u_0}2 + v_0 \rre }{2\varphi'(u_0)}
\right]^j j^{-3/2} \lli 1 + O \lli \frac 1j \rre \rre ,
\endaligned
\tag 4
$$
wobei $v_0$ die kleinste positive L\"osung von $t\varphi'(u_0/2+t) =
\varphi(u_0/2+t)$ bezeichnet.

F\"ur $\varphi(t) = 1/(1-t)$ (ebene Wurzelb\"aume), f\"ur $\varphi(t) = (1+t)^N$
($N$-\"are Wurzelb\"aume mit $n$ inneren Knoten) und f\"ur $\varphi(t) = e^t$
(markierte Wurzelb\"aume)
k\"onnen diese Eintragungen auch exakt angegeben werden. Man ben\"otigt
zun\"achst $\alpha$, $\mu_j$ und $\overline\mu_j$. (Man beachte, da{\ss}
der erste und der dritte Fall als ``Spezialf\"alle'' des zweiten angesehen
werden k\"onnen, wenn man in den Formeln von $\varphi(t) = (1+t)^N$
die F\"alle $N = -1$ und $N \to \infty$ betrachtet.)
$$
\alignedat4
\varphi(t) &= \frac 1{1-t} &\quad \alpha &= 2 &\quad
\mu_j &= \frac 1j \binom{2j-2}{j-1} \frac {2^{j-2}}{3^{2j-1}}&\quad
\mqj &= \mu_j \frac {2j-1}{3j} \\
\varphi(t) &=(1+t)^N&\quad\alpha&=1-\frac 1N &\quad
\mu_j &= \frac 1j \binom {Nj}{j-1} \frac {(2N-1)^{(N-1)j+1}}{4(2N)^{Nj}}&
\quad \mqj &= \mu_j\frac {(N-1)j+1}{(2N-1)j} \\
\varphi(t) &= e^t&\quad\alpha&=1 &\quad
\mu_j &= \frac {j^{j-1}}{j!2^{j+1}e^{j/2}}&\quad \mqj &= \frac {\mu_j}2
\endalignedat
\tag 5
$$
F\"ur $\varphi(t) = (1+t)^N$ ergibt sich unmittelbar
$$
\aligned
\sigma_{yi} &= \mu_i\frac{N(i-2)}{2(2N-1)},\\
\sigma_{zi} &= \mu_i\frac {iN(4N-1)-(12N^2-6N+1)}{4N(2N-1)},\\
\sigma_{ii} &= \mu_i-\mu_i^2 \frac {i^2 N^2(N-1)+2iN(2N^2-2N+1)
-(4N^3-8N^2+6N-1)}{N(2N-1)^2},\\
\sigma_{ij} &= -\mu_i\mu_j \frac {ij N^2(N-1)+(i+j)N(2N^2-2N+1)
-(4N^3-8N^2+6N-1)}{N(2N-1)^2}.
\endaligned
\tag 6
$$
Daraus gewinnt man f\"ur $\varphi(t) = 1/(1-t)$ (1. Spalte) und
$\varphi(t) = e^t$ (2. Spalte):
$$
\alignedat2
\sigma_{yi} &= \mu_i \frac {i-2}6, &\quad
\sigma_{yi} &= \mu_i \frac {i-2}4, \\
\sigma_{zi} &= \mu_i \frac {5i-19}{12}, &\quad
\sigma_{zi} &= \mu_i \frac {i-3}2, \\
\sigma_{ii} &= \mu_i - \mu_i^2 \frac{2i^2+10i-19}9, &\quad
\sigma_{ii} &= \mu_i - \mu_i^2 \frac{i^2+4i-4}4 \\
\sigma_{ij} &= -\mu_i\mu_j \frac{2ij+5i+5j-19}9, &\quad
\sigma_{ij} &= -\mu_i\mu_j \frac{ij+2i+2j-4}4.
\endalignedat
\tag 7
$$

In diesen drei F\"allen ist es \"ubrigens auch m\"oglich, explizite Formeln
zu gewinnen. In \cite{BD} wurden bereits die Gesamtanzahlen
$c_{nklm}$ angegeben. F\"ur $\varphi(t) = 1/(1-t)$ erh\"alt man
$$
c_{nklm} = \frac 1{k-l} \binom {2n-2}{n-k-1} \binom {n-l-2}{k-l-1}
\binom {k-l}{m} P^m,
\tag 8
$$
wobei $\binom {k-l}{m}$ den Multinomialkoeffizienten
$(k-l)!/\prod\limits_{j\ge 1} m_j!$, $P^m = \prod\limits_{j\ge 1} 
P_j^{m_j}$ und $P_j = \frac 1j \binom {2j-2}{j-1}$
die Catalanzahlen bezeichen. F\"ur $\varphi(t) = (1+t)^N$ ist
$$
c_{nklm} = \frac 1{k-l} \binom {Nn-k}{n-k-1} \binom {N(n-k)}{k-l-1}
\binom {k-l}{m} P^m \qquad\text{mit}\quad P_j = \frac 1j \binom {Nj}{j-1}
\tag 9
$$
und f\"ur $\varphi(t) = e^t$ 
$$
c_{nklm}  = \frac 1{k-l}
\frac {n^{n-k}(n-k)^{k-l-1}}{(n-k)!(k-l-1)!} \binom {k-l}{m} P^m
\qquad\text{mit}\quad P_j = \frac {j^{j-1}}{j!}.
\tag 10
$$
Etwas aufwendiger ist es aber, f\"ur vorgegebenes $J$, $c_{nklm_J}$ 
explizit anzugeben. Es m\"ussen daf\"ur die Methoden von \cite{BD}
verfeinert werden. Die auftretenden Ausdr\"ucke enthalten in den
meisten F\"allen alternierende Summen, die nicht mehr zu einer
geschlossenen Form zusammengefa{\ss}t werden k\"onnen. Zur
Illustration sollen die Resultate f\"ur $J = \{1\}$ angegeben werden.
In der Reihenfolge $\varphi(t) = 1/(1-t)$, $\varphi(t) = (1+t)^N$,
$\varphi(t) = e^t$ erh\"alt man
$$
\aligned
c_{nklm_1} &= \frac 2n \binom {2n-2}{n-k-1} \frac 
{(n-l-2)!(2l-1)!(k(3n-2)-n(2l+1-n))}
{(n-k)!m_1!(k-l-m_1-1)!(k-m_1)!(2l-k+m_1)!}, \\
c_{nklm_1} &= \frac N{k-l} \binom {Nn-k}{n-k-1} 
\binom {N(n-k)-1}{k-l-1}\cdot\\
&\quad\cdot \sum_{j=m_1}^{k-l} (-1)^{j-m_1} 
\frac {k-j-l}{k-l} \binom {k-l}j
\binom j{m_1} \binom {N(k-j)}l,  \\
c_{nklm_1} &= \frac {n^{n-k-1}(n-k)^{k-l-1}}{(n-k)!l!m_1!}
\sum_{j=m_1}^{k-l-1} (-1)^{j-m_1} \frac {(k-j)^{(l-1)}(n-j)}
{(j-m_1)!(k-l-j-1)!}   .
\endaligned
\tag 11
$$
Auch bei diesen expliziten Resultaten k\"onnen der erste und der
dritte Fall f\"ur $N = -1$ und $N\to\infty$ aus dem zweiten 
gewonnen werden.

\Refs\nofrills{Literatur}
\widestnumber\key{XX}

\ref \key  BD
\by Baron, G., and M. Drmota
\paper Distribution Properties of Induced Subgraphs of Trees
\jour Ars Combinatoria 35 (1993), 193--213. 
\endref

\ref \key  MM
\by Meir, A., and J.W. Moon
\paper On Maximal Independent Sets of Nodes in Trees
\jour J. Graph Th.
\vol 12   \yr 1988   \pages 265--283
\endref

\endRefs
\enddocument

