Binäre Bäume zählen

28

(Ich bin ein Student mit mathematischem Hintergrund und möchte wissen, wie man die Anzahl einer bestimmten Art von Binärbäumen zählt.)

Mit Blick auf Wikipedia - Seite für Binary Trees , habe ich diese Behauptung aufgefallen , dass die Zahl der Wurzeln Binärbäumen der Größe wäre diese katalanische Nummer : $n$

C_{n} = \frac{1}{n + 1} (\binom{2 n}{n})

$C_n = \dfrac{1}{n+1}{2n \choose n}$

Aber ich verstehe nicht, wie ich selbst zu einem solchen Ergebnis kommen könnte? Gibt es eine Methode, um dieses Ergebnis zu finden?

Was ist nun, wenn die Reihenfolge der Unterbäume (welche ist links, welche ist rechts) nicht berücksichtigt wird? Aus meiner Sicht denke ich beispielsweise, dass diese beiden Bäume gleich sind:

   /\   /\
  /\     /\

Wäre es möglich, eine ähnliche Methode anzuwenden, um zu zählen, wie viele dieser Objekte genau Knoten haben? $n$

combinatorics binary-trees discrete-mathematics Stéphane Gimenez
quelle

Ist der Zählsatz von Polya auf zweiwurzelige Bäume hier anwendbar?

Nicholas Mancuso

35

Zum Zählen vieler Arten von kombinatorischen Objekten, wie in diesem Fall Bäume, gibt es leistungsstarke mathematische Werkzeuge (die symbolische Methode), mit denen Sie solche Zählungen maschinell aus einer Beschreibung ableiten können, wie die kombinatorischen Objekte aufgebaut sind. Dabei werden Funktionen generiert.

Eine ausgezeichnete Referenz ist Analytic Combinatorics von Philipe Flajolet und Robert Sedgewick. Es ist über den obigen Link verfügbar.

Der verstorbene Herbert Wilf Buch generatingfunctionology ist eine andere freie Hand.

Und natürlich ist die Konkrete Mathematik von GKP eine Fundgrube.

Für binäre Bäume gilt: Zuerst müssen Sie den Baum klar definieren.

Ein binärer Baum ist ein verwurzelter Baum, in dem jeder Nicht-Blattknoten genau den Grad 2 hat.

Als nächstes müssen wir uns einigen, was wir die Größe eines Baumes nennen wollen .

Bildbeschreibung hier eingeben

Links sind alle Knoten gleich. In der Mitte unterscheiden wir die Blätter und Nichtblätter. Rechts haben wir einen beschnittenen Binärbaum, in dem die Blätter entfernt wurden. Beachten Sie, dass es unäre Zweige von zwei Typen gibt (links und rechts)!

Nun müssen wir eine Beschreibung ableiten, wie diese kombinatorischen Objekte aufgebaut sind. Bei binären Bäumen ist eine rekursive Zerlegung möglich.

Sei die Menge aller binären Bäume des ersten Typs, dann haben wir symbolisch: $\mathcal{A}$ Bildbeschreibung hier eingeben

Es lautet wie folgt: „Ein Objekt der Klasse der Binärbäume ist entweder ein Knoten oder ein Knoten, auf den zwei Binärbäume folgen.“ Dies kann als Mengengleichung geschrieben werden:

A = {∙} \cup ({∙} \times A \times A)

$\mathcal{A}=\{\bullet\}\cup\bigl(\{\bullet\}\times\mathcal{A}\times\mathcal{A}\bigr)$

Durch die Einführung der Erzeugungsfunktion , die diese Klasse von kombinatorischen Objekten auflistet, können wir die Mengengleichung in eine Gleichung mit der Erzeugungsfunktion übersetzen. $A(z)$

A (z) = z + z A^{2} (z)

$A(z)=z+zA^2(z)$

Unsere Wahl, alle Knoten gleich zu behandeln und die Anzahl der Knoten im Baum als Begriff ihrer Größe zu nehmen, drückt sich durch "Markieren" der Knoten mit der Variablen . $z$

Wir können nun die quadratische Gleichung für lösen und erhalten wie üblich zwei Lösungen, die explizit geschlossene Form der Erzeugungsfunktion: $zA^2(z)-A(z)+z=0$ $A(z)$

A (z) = \frac{1 \pm \sqrt{1 - 4 z^{2}}}{2 z}

$A(z)=\frac{1\pm\sqrt{1-4z^2}}{2z}$

Jetzt brauchen wir einfach Newtons (verallgemeinerten) Binomialsatz:

(1 + x)^{a} = \sum_{k = 0}^{\infty} (\binom{a}{k}) x^{k}

$(1+x)^a=\sum_{k=0}^\infty\binom{a}{k}x^k$

mit und erweitern Sie die geschlossene Form der Erzeugungsfunktion zurück in eine Potenzreihe. Wir tun dies, weil der Koeffizient bei nur die Anzahl der kombinatorischen Objekte der Größe , die typischerweise als . Aber hier zwingt uns unser Begriff der „Größe“ des Baumes, nach dem Koeffizienten bei zu suchen . Nach einigem Jonglieren mit Binomialzahlen und Fakultätszahlen erhalten wir: $a=1/2$ $x=-4z^2$ $z^n$ $n$ $[z^n]A(z)$ $z^{2n+1}$

[z^{2 n + 1}] A (z) = \frac{1}{n + 1} (\binom{2 n}{n}) .

$[z^{2n+1}]A(z)=\frac{1}{n+1}\binom{2n}{n}.$

Wenn wir mit dem zweiten Begriff der Größe beginnen, ist die rekursive Zerlegung:

Bildbeschreibung hier eingeben

Wir erhalten eine andere Klasse von kombinatorischen Objekten . Es lautet: "Ein Objekt der Klasse der Binärbäume ist entweder ein Blatt oder ein Zwischenknoten, gefolgt von zwei Binärbäumen." $\mathcal{B}$

Wir können den gleichen Ansatz anwenden und zu . Nur diesmal markiert die Variable nur die internen Knoten, nicht die Blätter, da hier die Definition „die Größe“ unterschiedlich ist. Wir bekommen auch eine andere Erzeugungsfunktion: $\mathcal{B}=\{\square\}\cup\bigl(\{\bullet\}\times\mathcal{B}\times\mathcal{B}\bigr)$ $\mathcal{B}=1+zB^2(z)$ $z$

B (z) = \frac{1 - \sqrt{1 - 4 z}}{2 z}

$B(z)=\frac{1-\sqrt{1-4z}}{2z}$

Das Extrahieren des Koeffizienten ergibt

[z^{n}] B (z) = \frac{1}{n + 1} (\binom{2 n}{n}) .

$[z^n]B(z)=\frac{1}{n+1}\binom{2n}{n}.$

Die Klassen und stimmen in der Anzahl überein, da ein Binärbaum mit internen Knoten Blätter hat, also insgesamt Knoten. $\mathcal{A}$ $\mathcal{B}$ $n$ $n+1$ $2n+1$

Im letzten Fall müssen wir etwas härter arbeiten:

Bildbeschreibung hier eingeben

Dies ist eine Beschreibung nicht leerer beschnittener Binärversuche. Wir erweitern dies auf

\begin{aligned} C & = {∙} \cup ({∙} \times C) \cup ({∙} \times C) \cup ({∙} \times C \times C) \\ D & = {ϵ} \cup ({∙} \times C \times C) \end{aligned}

$\begin{align}\mathcal{C}&=\{\bullet\}\cup\bigl(\{\bullet\}\times\mathcal{C}\bigr)\cup\bigl(\{\bullet\}\times\mathcal{C}\bigr)\cup\bigl(\{\bullet\}\times\mathcal{C}\times\mathcal{C}\bigr)\\\mathcal{D}&=\{\epsilon\}\cup\bigl(\{\bullet\}\times\mathcal{C}\times\mathcal{C}\bigr)\end{align}$

und mit generierenden Funktionen neu schreiben

\begin{aligned} C (z) & = z + 2 z C (z) + z C^{2} (z) \\ D (z) & = 1 + z C^{2} (z) \end{aligned}

$\begin{align}C(z)&=z+2zC(z)+zC^2(z)\\D(z)&=1+zC^2(z)\end{align}$

Löse die quadratischen Gleichungen

\begin{aligned} C (z) & = \frac{1 - 2 z - \sqrt{1 - 4 z}}{2 z} \\ D (z) & = \frac{1 - \sqrt{1 - 4 z}}{2 z} \end{aligned}

$\begin{align}C(z)&=\frac{1-2z-\sqrt{1-4z}}{2z}\\D(z)&=\frac{1-\sqrt{1-4z}}{2z}\end{align}$

und nochmal holen

[z^{n}] C (z) = \frac{1}{n + 1} (\binom{2 n}{n}) n \geq 1 [z^{n}] D (z) = \frac{1}{n + 1} (\binom{2 n}{n}) n \geq 0

$[z^n]C(z)=\frac{1}{n+1}\binom{2n}{n}\quad n\ge1 \qquad [z^n]D(z)=\frac{1}{n+1}\binom{2n}{n} \quad n\ge0$

Beachten Sie, dass die katalanische Erzeugungsfunktion ist

E (z) = \frac{1 - \sqrt{1 - 4 z}}{2}

$E(z)=\frac{1-\sqrt{1-4z}}{2}$

es zählt die Klasse der allgemeinen Bäume auf . Das sind die Bäume ohne Einschränkung des Knotengrades.

E = {∙} \times S E Q (E)

$\mathcal{E}=\{\bullet\}\times\mathrm{SEQ}(\mathcal{E})$

Es lautet wie folgt: "Ein Objekt der Klasse der allgemeinen Bäume ist ein Knoten, dem eine mögliche leere Folge von allgemeinen Bäumen folgt."

E (z) = \frac{z}{1 - E (z)}

$E(z)=\frac{z}{1-E(z)}$

Mit der Lagrange-Bürmann Inversion Formula erhalten wir

[z^{n}] E (z) = \frac{1}{n + 1} (\binom{2 n}{n})

$[z^n]E(z)=\frac{1}{n+1}\binom{2n}{n}$

Wir haben also bewiesen, dass es so viele allgemeine Bäume gibt wie es binäre Bäume gibt. Kein Wunder, dass zwischen dem allgemeinen und dem binären Baum ein Unterschied besteht. Die Bijektion ist als Rotationskorrespondenz bekannt (erklärt am Ende des verlinkten Artikels), die es uns ermöglicht, jeden allgemeinen Baum als binären Baum zu speichern.

Beachten Sie, dass wir, wenn wir das linke und das rechte Geschwister in class nicht unterscheiden, eine weitere Klasse von Bäumen : $\mathcal{C}$ $\mathcal{T}$

Bildbeschreibung hier eingeben

die unären binären Bäume. Sie haben auch eine Erzeugungsfunktion jedoch ist ihr Koeffizient unterschiedlich. Sie erhalten die Motzkin-Zahlen

T = {∙} \times {S E Q}_{\leq 2} (T)

$\mathcal{T}=\{\bullet\}\times\mathrm{SEQ}_{\le2}(\mathcal{T})$

T (z) = \frac{1 - z - \sqrt{1 - 2 z - 3 z^{2}}}{2 z}

$T(z)=\frac{1-z-\sqrt{1-2z-3z^2}}{2z}$

[z^{n}] T (z) = \frac{1}{n} \sum_{k} (\binom{n}{k}) (\binom{n - k}{k - 1}) .

$[z^n]T(z)=\frac{1}{n}\sum_k\binom{n}{k}\binom{n-k}{k-1}.$

Oh, und wenn Sie keine Funktionen generieren möchten, gibt es auch viele andere Beweise. Sehen Sie hier , es gibt einen Punkt, an dem Sie die Kodierung von Binärbäumen als Dyck-Wörter verwenden und eine Wiederholung aus ihrer rekursiven Definition ableiten können. Wenn Sie dann diese Wiederholung lösen, erhalten Sie auch die Antwort. Die symbolische Methode erspart Ihnen jedoch in erster Linie die Wiederholung, da sie direkt mit den Blaupausen der kombinatorischen Objekte zusammenarbeitet.

uli
quelle

Zu beachten ist, dass Sedgewick und Flajolet in "Introduction to the Analysis of Algorithms" ( aofa.cs.princeton.edu ) eine Menge des gleichen Materials wie das Buch "Analytic Combinatorics" behandeln, jedoch in einer zugänglicheren Form.

Vonbrand

7

Das Generieren von Funktionen ist ein sehr mächtiger und sehr nützlicher Zauberstab. Die folgende Lösung zur ersten Frage (warum gibt es Bäume) ist etwas weniger magisch. Daher süß. $C_n$

Beispiel. Um einen Baum zu produzieren Knoten wir mit einer Sequenz zu starten , in der auftreten - mal, und auftritt mal. Zum Beispiel . Wählen Sie unter den Präfixen mit der kleinsten (und möglicherweise negativen) Summe die längste aus. in diesem Fall . Nehmen Sie dieses Präfix von Anfang an und setzen Sie es am Ende. In diesem Fall erhalten wir . Ändern Sie nun in und in ; in diesem Fall bekommen wir . Entfernen Sie ein vom Anfang und fügen Sie ein $5$ $+1$ $5+1$ $-1$ $5$ $+-++-+--++-$ $+-++-+--$ $++-+-++-+--$ $+$ $T$ $-$ $E$ TTETETTETEE $T$ $E$ Am Ende; in diesem Fall bekommen wir TETETTETEEE. Dies ist eine Beschreibung des Baumes T(E,T(E,T(T(E,T(E,E)),E))). Nachfolgend finden Sie eine Erklärung, warum dies eine Bijektion ist. Sobald Sie davon überzeugt sind, ist das Zählen einfach. Es gibt Sequenzen von , dann haben wir durch weil wir eine der möglichen zyklischen Permutationen gewählt haben. $\binom{5+6}{5}$ $\pm1$ $5+6$

Erste Biktion. Eine typische Definition für Bäume in ML ist type tree = T of tree * tree | E; Das heißt, ein Baum hat entweder zwei (geordnete) Teilbäume oder er ist leer. Hier ist , wie Bäume sind so aufgebaut: T(T(E,E),T(T(E,E),T(E,E))). Flusen fallen lassen, wir können einfach schreiben TTEETTEETEE. Alle diese Beschreibungen werden mit einem Ende E, so dass es überflüssig ist: TTEETTEETE. (Beachten Sie, dass der leere Baum jetzt der leeren Zeichenfolge entspricht.) Diese Zeichenfolgen haben die Eigenschaft, dass jedes Präfix mindestens so viele Ts wie Es hat, und insgesamt haben sie Ts und Es, wobei die Anzahl der Knoten von ist der Baum. $n$ $n$ $n$

Zweite Bijektion. Wir ersetzen nun T durch +1 und E durch -1. Wir betrachten also Sequenzen mit Werten +1, mit Werten -1 und mit den Summen aller Präfixe . $n$ $n$ $\ge0$

Dritte Bijektion. Wir ändern nun die Vorgabe für Präfixe ein wenig: Wir fordern, dass die Summe aller nicht leeren Präfixe . Damit dies möglich ist, lassen wir Werte +1 und Werte -1. (Andernfalls wäre die Summe der gesamten Zeichenfolge 0 und würde die Bedingung für Präfixe nicht erfüllen.) Diese Sequenzen müssen mit +1 beginnen. Sie sind also wirklich die gleichen wie zuvor, außer dass sie am Anfang eine +1 haben. $>0$ $n+1$ $n$

Raney Eigentum. Vergessen Jetzt ist unsere Sequenzen für einen Moment und betrachten eine endliche Folge von ganzen Zahlen , , , deren Summe 1. Wenn alle nicht-leeren Präfixe positive Summen haben, dann keine zyklische Permutation dieser Sequenz hat die gleiche Eigenschaft. Warum? Angenommen, es gibt ein , bei dem auch alle nicht leeren Präfixe positiv sind. Dann (Eigenschaft der Sequenz ab ) und (Eigenschaft der Sequenz ab ); daher $x_1$ $\ldots\,$ $x_m$ $k\ne1$ $x_k,\ldots,x_m,x_1,\ldots,x_{k-1}$ $x_1+\cdots+x_{k-1}\ge1$ $x_1$ $x_k+\cdots+x_m\ge1$ $x_k$ $x_1+\cdots+x_m\ge2$ Dies widerspricht der Annahme, dass die Summe für die gesamte Sequenz 1 ist.

Darüber hinaus gibt es bei einer Sequenz mit der Summe 1 immer eine zyklische Permutation, die bewirkt, dass alle nicht leeren Präfixe eine positive Summe haben. (Dies gilt auch für reelle Zahlen.)

Fazit. Zählen wir nun die Folgen von +1 und -1, die sich in einer Bijektion mit Bäumen befinden. Aus Zahlen müssen wir auswählen , die gleich +1 sind, die anderen werden -1 sein. Es gibt Möglichkeiten, dies zu tun. Aber nur in - Sequenzen bisher gezählt hat positive Präfixe. Die Anzahl der verwurzelten, geordneten Binärbäume ist also: $2n+1$ $n+1$ ${2n+1\choose n+1}$ $1$ $2n+1$

\frac{1}{2 n + 1} (\binom{2 n + 1}{n + 1}) = \frac{1}{2 n + 1} \frac{2 n + 1}{n + 1} (\binom{2 n}{n}) = \frac{1}{n + 1} (\binom{2 n}{n})

${1\over2n+1}{2n+1\choose n+1}={1\over2n+1}{2n+1\over n+1}{2n\choose n}={1\over n+1}{2n\choose n}$

rgrig
quelle

Sehr gute Antwort, aber die folgende Aussage bedarf einer Erklärung: "Bei einer bestimmten Folge mit der Summe 1 gibt es immer eine zyklische Permutation, die bewirkt, dass alle nicht leeren Präfixe eine positive Summe haben" .... zumindest ein Hinweis auf den Beweis wäre nett.

Vog

1

@vog: Nimm das Präfix mit der kleinsten Summe und verschiebe es ans Ende.

rgrig

1

@vog: Es sollte auch das längste Präfix sein, falls es mehrere mit der gleichen kleinsten Summe gibt. Ich habe die Antwort bearbeitet, um am Anfang ein Beispiel hinzuzufügen.

rgrig

Binäre Bäume zählen

Antworten: