Zählen von binären Bäumen

Question

(Ich bin ein student mit einigen mathematischen hintergrund und ich würde gerne wissen, wie man die Anzahl der einer bestimmten Art von binären Bäumen.)

Auf der Suche zur Wikipedia-Seite für Binäre Bäume, Ich habe bemerkt, diese Behauptung, dass die Anzahl der verwurzelt binäre Bäume der Größe $n$ wäre dies Catalan-Zahl:$$C_n = \dfrac{1}{n+1}{2n \choose n}$$

Aber ich verstehe nicht, wie ich kommen konnte mit so einem Ergebnis von mir?Gibt es eine Methode, um dieses Ergebnis?

Nun, was ist, wenn die Reihenfolge der sub-Bäume (was ist Links, was ist rechts) wird nicht berücksichtigt?Für Beispiel, aus meiner Sicht, ich denke, dass diese beiden Bäume sind die selben:

   /\   /\
  /\     /\

Würde es möglich sein, eine ähnliche Methode zu zählen, wie viele dieser Objekte haben genau $n$ - Knoten?

Answer 1

Um viele Arten von kombinatorischen Objekten zu zählen, wie in diesem Fall Bäume, gibt es leistungsstarke mathematische Werkzeuge (die symbolische Methode), mit denen Sie solche Zählungen aus einer Beschreibung maßgeblich ableiten können, wie die kombinatorischen Objekte konstruiert werden. Dies beinhaltet die Erzeugung von Funktionen.

Eine hervorragende Referenz ist Analytische Kombinatorik durch den verstorbenen Philipe Flajolet und Robert Sedgebick. Es ist über den obigen Link erhältlich.

Das Buch des verstorbenen Herbert Wilfs Erzeugungsfunktionologie ist eine weitere freie Quelle.

Und natürlich Betonmathematik von GKP ist eine Schatzkammer.

---

Für binäre Bäume geht es so: Erstens benötigen Sie eine klare Definition des Baumes.

Ein binärer Baum ist ein verwurzeltes Baum, bei dem jeder nicht-Blattknoten genau Grad 2 hat.

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

Links sind alle Knoten gleich. In der Mitte unterscheiden wir die Blätter und Nichtblätter. Auf der rechten Seite haben wir einen Binärbaum, an dem die Blätter entfernt wurden. Beachten Sie, dass es unäre Zweige von zwei Arten (links und rechts) hat!

Jetzt müssen wir eine Beschreibung der Erstellung dieser kombinatorischen Objekte ableiten. Im Fall von Binärbäumen a rekursive Zerlegung ist möglich.

Sei $ mathcal {a} $ der Satz aller binären Bäume des ersten Typs, dann haben wir symbolisch:

Es lautet: "Ein Objekt der Klasse von Binärbäumen ist entweder ein Knoten oder ein Knoten, gefolgt von zwei binären Bäumen." Dies kann als Gleichung von Mengen geschrieben werden:

acht

Durch Einführung der Erzeugungsfunktion $ a (z) $, die diese Klasse von kombinatorischen Objekten aufzählt, können wir die festgelegte Gleichung in eine Gleichung übersetzt, die die Generierungsfunktion umfasst.

$$ a (z) = z+za^2 (z) $$

Unsere Wahl, alle Knoten gleichermaßen zu behandeln und die Anzahl der Knoten im Baum als Begriff seiner Größe zu nehmen, wird ausgedrückt, indem die Knoten mit dem variablen $ z $ „markieren“.

Wir können jetzt die quadratische Gleichung $ za^2 (z) -a (z)+z = 0 $ für $ a (z) $ lösen und wie üblich zwei Lösungen die explizite geschlossene Form der Erzeugungsfunktion erhalten:

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

Jetzt brauchen wir einfach Newtons (verallgemeinertes) Binomialsatz:

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

mit $ a = 1/2 $ und $ x = -4Z^2 $, um die geschlossene Form der Erzeugungsfunktion in eine Power-Serie zurück zu erweitern. Wir tun dies, weil der Koeffizient von $ z^n $ nur die Anzahl der kombinatorischen Objekte von Größe $ n $ ist, die normalerweise als $ [z^n] a (z) $ geschrieben ist. Aber hier zwingt uns unsere Vorstellung von „der Größe“ des Baumes, nach dem Koeffizienten bei $ z^{2n+1} $ zu suchen. Nach ein bisschen Jonglieren mit Binomials und Faktorien bekommen wir:

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

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

Wir erhalten eine andere Klasse kombinatorischer Objekte $ Mathcal {B} $. Es lautet: "Ein Objekt der Klasse von Binärbäumen ist entweder ein Blatt oder ein Interalknoten, gefolgt von zwei binären Bäumen."

Wir können den gleichen Ansatz verwenden und $ mathcal {b} = { square } cup bigl ( { bullet } times mathcal {b} times mathcal {b} bigr) $ drehen in $ mathcal {b} = 1+zb^2 (z) $. Nur dieses Mal markiert die Variable $ z $ nur die internen Knoten, nicht die Blätter, da die Definition „Die Größe“ hier anders ist. Wir erhalten auch eine andere Erzeugungsfunktion:

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

Extrahieren der Koeffizientenausbeuten

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

Klasse $ mathcal {a} $ und $ mathcal {b} $ stimmen auf die Zählungen zu, da ein Binärbaum mit $ n $ internen Knoten $ n+1 $ Blätter hat, also $ 2n+1 $ Knoten insgesamt.

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

Dies ist eine Beschreibung von nicht leeren Binärversuchen. Wir erweitern dies auf $$ begin {align} mathcal {c} & = { bullet } cup bigl ( { bullet } times mathcal {c} bigr) cup bigl (Bigl (Bigl (Bigl ( { bullet } times mathcal {c} bigr) cup bigl ( { bullet } times mathcal {c} times mathcal {c} bigr) mathcal {d {d times mathcal {c} bigr) mathcal {d {d ^ } & = oder

und schreiben Sie es mit Erzeugung von Funktionen um

$$ begin {align} c (z) & = z+2zc (z)+zc^2 (z) d (z) & = 1+zc^2 (z) end {align} $$

Lösen Sie die quadratischen Gleichungen

$$ begin {align} c (z) & = frac {1-2z- sqrt {1-4z}} {2z} d (z) & = frac {1- sqrt {1-4z }} {2z} end {align} $$

Und noch einmal

$$ [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 $$

Notiere dass der Katalanische Erzeugungsfunktion ist

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

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

$$ mathcal {e} = { bullet } times mathhrm {seq} ( mathcal {e}) $$

Es lautet: „Ein Objekt der Klasse der allgemeinen Bäume ist ein Knoten, gefolgt von einer möglichen leeren Abfolge allgemeiner Bäume.“

$$ e (z) = frac {z} {1-e (z)} $$

Mit dem LaGrange-Bürmann-Inversionsformel wir bekommen

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

Wir haben also bewiesen, dass es so viele allgemeine Bäume gibt wie Binärbäume. Kein Wunder, dass zwischen den allgemeinen und den binären Bäumen eine Bijection besteht. Die Bijektion ist als die bekannt Rotationskorrespondenz (Am Ende des verknüpften Artikels), das uns zwei allgemeine Baum als binärer Baum speichern.

Beachten Sie, dass wir in der Klasse $ mathcal {c} $ nicht eine weitere Klasse von Bäumen $ mathcal {t} $ erhalten, wenn wir das linke und rechte Geschwister nicht unterscheiden:

Die unären Bäume. $$ mathcal {t} = { bullet } times mathcrm {seq} _ { le2} ( mathcal {t}) $$ Sie haben eine Erzeugungsfunktion zu $$ T (Z) = Frac {1-z- sqrt {1-2z-3z^2}} {2z} $$, aber ihr Koeffizient ist anders. Sie erhalten die Motzkin-Nummern $$ [z^n] t (z) = frac {1} {n} sum_k binom {n} {k} binom {nk} {k-1}. $$

Oh, und wenn Sie keine Funktionen generieren, gibt es auch viele andere Beweise. Sehen hier, Es gibt einen, in dem Sie die Kodierung von Binärbäumen als Dyck -Wörter verwenden und ein Wiederauftreten ihrer rekursiven Definition abgeben können. Dann gibt es auch die Antwort, diese Wiederholung zu lösen. Die symbolische Methode rettet Sie jedoch vor dem Auftreten des Wiederauftretens, da sie direkt mit den Blaupausen der kombinatorischen Objekte funktioniert.

Answer 2

Erzeugende Funktionen sind ein sehr mächtiges und sehr nützlich magic Wand.Die folgende Lösung der ersten Frage (warum gibt es $C_n$ die Bäume) ist etwas weniger magisch.Daher Niedlich.

Beispiel. Erzeugt einen Baum der $5$ - Knoten beginnen wir mit einer Sequenz, in der $+1$ Eintritt von 5 $+1$ mal, und $-1$ erfolgt $5$ mal.Zum Beispiel, $+-++-+--++-$.Unter denen, die die Präfixe mit den kleinsten (und möglicherweise negativen) Betrag, wählen Sie die längste;in diesem Fall, $+-++-+--$.Nehmen Sie dieses Präfix von Anfang an und setzen Sie es an die Ende;in diesem Fall bekommen wir $++-+-++-+--$.Ändern Sie nun $+$ in $T$ und $-$ in $E$;in diesem Fall erhalten wir TTETETTETEE.Entfernen Sie eine $T$ von Anfang an, fügen Sie einen $E$ am Ende;in diesem Fall erhalten wir TETETTETEEE.Dies ist eine Beschreibung des Baumes T(E,T(E,T(T(E,T(E,E)),E))).Unten gibt es eine Erklärung, warum dies ist eine bijection.Sobald Sie davon überzeugt sind, dass das zählen ist einfach.Es gibt $\binom{5+6}{5}$ - Sequenzen von $\pm1$, dann haben wir geteilt durch $5+6$, da haben wir eine der möglichen zyklischen Permutationen.

Erste bijection. Eine typische definition für Bäume in ML type tree = T of tree * tree | E;das ist ein Baum, der entweder zwei (geordnete) unterstrukturen, oder es ist leer.Hier ist, wie Bäume aufgebaut sind: T(T(E,E),T(T(E,E),T(E,E))).Fallen die Flusen, können wir einfach schreiben TTEETTEETEE.Alle diese Beschreibungen werden am Ende mit einem E, so dass es überflüssig ist: TTEETTEETE.(Beachten Sie, dass die leeren Baum nun entspricht der leeren Zeichenfolge.) Diese strings haben die Eigenschaft, dass jedes Präfix hat mindestens so viele Ts, wie Es und in insgesamt, Sie haben $n$ Ts und $n$ Es, wobei $n$ die Anzahl der Knoten des Baumes.

Zweite bijection. Wir ersetzen jetzt T von +1 und E von -1.So, wir sind auf der Suche Sequenzen mit $n$ - Werte +1, mit $n$ - Werte -1, und mit den Summen aller Präfixe $\ge0$.

Dritte bijection. Wir ändern jetzt die Voraussetzung für das Präfix ein wenig:Wir fordern, dass die Summe jeder nicht-leeren Präfix $>0$.Um dies zu ermöglichen, lassen wir $n+1$ Werte +1 und $n$ - Werte -1.(Andernfalls ist die Summe der gesamten saite würde 0 sein und nicht erfüllen die Bedingung für die Präfixe.) Diese Sequenzen muss beginnen mit +1.Also, Sie sind wirklich das gleiche wie zuvor, außer Sie haben a +1 stuck am Anfang.

Raney-Eigenschaft. Jetzt vergessen unsere Sequenzen für einen moment und betrachten eine endliche Folge von Ganzzahlen $x_1$, $\ldots\,$, $x_m$, deren Summe 1 ist.Wenn alle nicht-leeren Präfixe positive Summen, dann keine zyklische permutation dieser Folge hat die gleiche Eigenschaft.Warum?Gut, angenommen, es ist ein $k e1$, so dass $x_k,\ldots,x_m,x_1,\ldots,x_{k-1}$ hat auch alle nicht-leeren Präfixe positiv.Dann $x_1+\cdot \ prod_+x_{k-1}\ge1$ (Eigentum der Reihenfolge ausgehend von $x_1$) und $x_k+\cdot \ prod_+x_m\ge1$ (Eigentum der Reihenfolge ausgehend von $x_k$);also $x_1+\cdot \ prod_+x_m\ge2$, was ein Widerspruch zu der Annahme, dass die Summe für die gesamte Sequenz ist 1.

Außerdem, da eine Sequenz mit Summe 1, es ist immer eine zyklische permutation, die macht, dass alle nicht-leeren Präfixe positive Summe.(Dies gilt auch für reelle zahlen.)

Fazit. Jetzt lasst uns zählen die Sequenzen von +1 und -1, die in eine bijection mit Bäumen.Von $2n+1$ zahlen, die wir Holen müssen $n+1$, die gleich +1, die andere wird -1 sein.Es gibt ${2n+1\wähle n+1}$ Möglichkeiten, dies zu tun.Aber, nur $1$ in $2n+1$ - Sequenzen gezählt, so weit hat positive Präfixe.Also, die Anzahl der verwurzelt, geordnete binäre Bäume:

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