Liczenie drzew binarnych

28

(Jestem studentem z pewnym doświadczeniem matematycznym i chciałbym wiedzieć, jak policzyć liczbę określonego rodzaju drzew binarnych).

Patrząc na stronę Wikipedii dotyczącą drzew binarnych , zauważyłem to twierdzenie, że liczba zakorzenionych drzew binarnych o rozmiarze będzie katalońską : $n$

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

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

Ale nie rozumiem, jak sam mogłem wymyślić taki wynik? Czy istnieje metoda znalezienia tego wyniku?

A co, jeśli kolejność pod-drzew (która jest pozostawiona, która jest właściwa) nie jest brana pod uwagę? Na przykład z mojego punktu widzenia uważam, że te dwa drzewa są takie same:

   /\   /\
  /\     /\

Czy można zastosować podobną metodę, aby policzyć, ile z tych obiektów ma dokładnie $n$ węzłów?

combinatorics binary-trees discrete-mathematics

— Stéphane Gimenez
źródło

Czy ma tu zastosowanie twierdzenie Polyi o zakorzenionych drzewach 2-arynkowych?

— Nicholas Mancuso

35

Do zliczania wielu rodzajów obiektów kombinatorycznych, takich jak drzewa w tym przypadku, istnieją potężne narzędzia matematyczne (metoda symboliczna), które pozwalają mechanicznie wyprowadzać takie liczby z opisu budowy obiektów kombinatorycznych. Obejmuje to generowanie funkcji.

Doskonałym odniesieniem jest Analytic Combinatorics autorstwa zmarłego Philipe Flajoleta i Roberta Sedgewicka. Jest dostępny z linku powyżej.

Funkcjonalność generowania książek zmarłego Herberta Wilfa jest kolejnym darmowym źródłem.

I oczywiście Matematyka konkretna GKP jest skarbnicą.

W przypadku drzew binarnych wygląda to tak: Najpierw potrzebujesz jasnej definicji drzewa.

Drzewo binarne jest drzewem zrootowanym, w którym każdy węzeł inny niż liść ma dokładnie stopień 2.

Następnie musimy uzgodnić, co chcemy nazwać rozmiarem drzewa.

wprowadź opis zdjęcia tutaj

Po lewej wszystkie węzły są równe. W środku rozróżniamy liście i liście niebędące liśćmi. Po prawej stronie mamy przycięte drzewo binarne, z którego usunięto liście. Zauważ, że ma jednoargumentowe gałęzie dwóch typów (lewy i prawy)!

Teraz musimy uzyskać opis budowy tych obiektów kombinatorycznych. W przypadku drzew binarnych możliwy jest rekurencyjny rozkład .

Niech będzie zbiorem wszystkich drzew binarnych pierwszego typu, a następnie symbolicznie mamy: $\mathcal{A}$ wprowadź opis zdjęcia tutaj

Brzmi on następująco: „Obiektem klasy drzew binarnych jest albo węzeł, albo węzeł, po którym następują dwa drzewa binarne.” Można to zapisać jako równanie zbiorów:

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

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

Wprowadzając funkcję generującą która wylicza tę klasę obiektów kombinatorycznych, możemy przełożyć zestaw równań na równanie obejmujące funkcję generującą. $A(z)$

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

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

Nasz wybór równego traktowania wszystkich węzłów i przyjmowania liczby węzłów drzewa jako pojęcia jego wielkości wyraża się przez „oznaczenie” węzłów zmienną . $z$

Możemy teraz rozwiązać równanie kwadratowe dla i otrzymać, jak zwykle, dwa rozwiązania, jawnie zamkniętą postać funkcji generującej: $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}$

Teraz potrzebujemy po prostu (uogólnionego) twierdzenia dwumianowego Newtona:

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

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

przy i aby rozwinąć zamkniętą postać funkcji generującej z powrotem do szeregu mocy. Robimy to, ponieważ współczynnik przy jest tylko liczbą obiektów kombinatorycznych o rozmiarze , zwykle zapisywanych jako . Ale tutaj nasze pojęcie „wielkości” drzewa zmusza nas do szukania współczynnika z . Po odrobinie żonglowania dwumianami i silniami otrzymujemy: $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}.$

Jeśli zaczniemy od drugiego pojęcia wielkości, rekurencyjny rozkład jest następujący:

wprowadź opis zdjęcia tutaj

Otrzymujemy inną klasę obiektów kombinatorycznych . Brzmi on następująco: „Obiektem klasy drzew binarnych jest liść lub węzeł interal, po którym następują dwa drzewa binarne.” $\mathcal{B}$

Możemy zastosować to samo podejście i zmienić w . Tylko tym razem zmienna oznacza tylko wewnętrzne węzły, a nie liście, ponieważ tutaj definicja „rozmiar” jest inna. Otrzymujemy również inną funkcję generowania: $\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}$

Wyodrębnienie współczynników daje

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

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

Klasy i zgadzają się co do liczby, ponieważ drzewo binarne z węzłami wewnętrznymi ma liści, a więc łącznie węzłów. $\mathcal{A}$ $\mathcal{B}$ $n$ $n+1$ $2n+1$

W ostatnim przypadku musimy trochę ciężej pracować:

wprowadź opis zdjęcia tutaj

który jest opisem niepustych przycinanych prób binarnych. Rozszerzamy to do

\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}$

i przepisz go za pomocą funkcji generujących

\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}$

rozwiązać równania kwadratowe

\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}$

i jeszcze raz

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

Zauważ, że funkcja generowania katalońskiego to

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

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

wylicza klasę drzew ogólnych . To są drzewa bez ograniczeń stopnia węzła.

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

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

Brzmi on następująco: „Obiektem klasy ogólnych drzew jest węzeł, po którym następuje możliwa pusta sekwencja ogólnych drzew”.

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

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

Dzięki formule inwersyjnej Lagrange-Bürmann otrzymujemy

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

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

Udowodniliśmy więc, że jest tyle drzew ogólnych, ile drzew podwójnych. Nic dziwnego, że istnieje drzewo biologiczne między drzewami ogólnymi i binarnymi. Bijection jest znany jako korespondencja rotacyjna (wyjaśniona na końcu połączonego artykułu), która pozwala nam przechowywać dwa ogólne drzewa jako drzewa binarnego.

Zauważ, że jeśli nie rozróżnimy lewego i prawego rodzeństwa w klasie , otrzymamy kolejną klasę drzew : $\mathcal{C}$ $\mathcal{T}$

wprowadź opis zdjęcia tutaj

jednorzędowe drzewa binarne. Mają też funkcję generującą jednak ich współczynnik jest inny. Otrzymasz liczby Motzkina

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}.$

Aha, a jeśli nie lubisz generować funkcji, jest też wiele innych dowodów. Zobacz tutaj , jest taki, w którym można użyć kodowania drzew binarnych jako słów Dyck i uzyskać wznowienie z ich rekurencyjnej definicji. Następnie rozwiązanie tego problemu daje odpowiedź. Jednak metoda symboliczna ratuje Cię przed wymyśleniem nawrotu, ponieważ działa ona bezpośrednio z planami obiektów kombinatorycznych.

— uli
źródło

Należy zauważyć, że „Wprowadzenie do analizy algorytmów” Sedgewicka i Flajoleta ( aofa.cs.princeton.edu ) obejmuje wiele takich samych materiałów, jak książka „Analytic Combinatorics”, ale w bardziej przystępnej formie.

— vonbrand

7

Funkcje generujące są bardzo potężną i bardzo przydatną magiczną różdżką. Poniższe rozwiązanie pierwszego pytania (dlaczego są drzewa ) jest nieco mniej magiczne. Stąd słodki. $C_n$

Przykład. Aby utworzyć drzewo węzłów, zaczynamy od sekwencji, w której występuje razy, a występuje razy. Na przykład . Spośród tych prefiksów o najmniejszej (i prawdopodobnie ujemnej) sumie wybierz najdłuższą; w tym przypadku . Weź ten prefiks od początku i umieść go na końcu; w tym przypadku otrzymujemy . Teraz zmień na i na ; w tym przypadku otrzymujemy . Usuń literę od początku, dodaj literę $5$ $+1$ $5+1$ $-1$ $5$ $+-++-+--++-$ $+-++-+--$ $++-+-++-+--$ $+$ $T$ $-$ $E$ TTETETTETEE $T$ $E$ na końcu; w tym przypadku otrzymujemy TETETTETEEE. To jest opis drzewa T(E,T(E,T(T(E,T(E,E)),E))). Poniżej znajduje się wyjaśnienie, dlaczego jest to bijection. Kiedy już będziesz o tym przekonany, liczenie jest łatwe. Istnieją z , następnie podzieliliśmy przez ponieważ wybraliśmy jedną z możliwych cyklicznych permutacji. $\binom{5+6}{5}$ $\pm1$ $5+6$

Pierwsze wstrzyknięcie. Typowa definicja drzew w ML to type tree = T of tree * tree | E; to znaczy, drzewo ma dwa (uporządkowane) poddrzewa lub jest puste. Oto w jaki sposób zbudowane są drzewa: T(T(E,E),T(T(E,E),T(E,E))). Upuszczając puch, możemy po prostu pisać TTEETTEETEE. Wszystkie te opisy zakończy ze związkiem E, więc jest zbędny: TTEETTEETE. (Zauważ, że puste drzewo odpowiada teraz pustemu ciągowi.) Ciągi te mają właściwość polegającą na tym, że każdy prefiks ma co najmniej tyle Ts co Es, aw sumie mają Ts i Es, gdzie jest liczbą węzłów drzewo. $n$ $n$ $n$

Drugi zastrzyk. Teraz zamieniamy T na +1, a E na -1. więc na sekwencje o wartości +1, o wartości -1 i sumach wszystkich prefiksów . $n$ $n$ $\ge0$

Trzeci zastrzyk. Teraz nieznacznie zmieniamy wymóg dotyczący prefiksów: Prosimy, aby suma każdego niepustego prefiksu wynosiła . Aby było to możliwe, pozwalamy wartości +1 i wartości -1. (W przeciwnym razie suma całego łańcucha wynosiłaby 0 i nie spełniałaby warunku dla prefiksów.) Sekwencje te muszą zaczynać się od +1. Tak więc naprawdę są takie same jak poprzednio, z tym wyjątkiem, że na początku utknęły +1. $>0$ $n+1$ $n$

Właściwość Raney. Teraz nasze sekwencje zapomnieć na chwilę i zastanowić się jakiś skończony ciąg liczb całkowitych , , którego suma wynosi 1. Jeżeli wszystkie niepuste prefiksy mieć pozytywne sumy, wtedy nie cykliczny permutacji tej sekwencji ma te same właściwości. Czemu? Załóżmy, że istnieje taki, że mają również wszystkie niepuste prefiksy dodatnie. Następnie (właściwość sekwencji zaczynając od ) i (właściwość sekwencji zaczynając od ); stąd $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$ , co jest sprzeczne z założeniem, że suma dla całej sekwencji wynosi 1.

Ponadto, biorąc pod uwagę pewną sekwencję z sumą 1, zawsze występuje permutacja cykliczna, która powoduje, że wszystkie niepuste prefiksy mają sumę dodatnią. (Dotyczy to nawet liczb rzeczywistych.)

Wniosek. Teraz policzmy sekwencje +1 i -1, które są bijection z drzewami. Z liczb musimy wybrać które są równe +1, pozostałe będą wynosić -1. Istnieją na to . Ale tylko w sekwencje zaliczane do tej pory ma pozytywny prefiksów. Tak więc liczba zakorzenionych, uporządkowanych drzew binarnych wynosi: $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
źródło

Bardzo dobra odpowiedź, ale następujące oświadczenie wymaga wyjaśnienia: „biorąc pod uwagę pewną sekwencję z sumą 1, zawsze istnieje permutacja cykliczna, która powoduje, że wszystkie niepuste prefiksy mają sumę dodatnią” ... przynajmniej wskazówką do dowodu byłoby miły.

— vog

1

@vog: weź prefiks z najmniejszą sumą i przenieś go na koniec.

— rgrig

1

@vog: powinien być także najdłuższym prefiksem, w przypadku gdy jest ich wiele z tą samą najmniejszą sumą. Zredagowałem odpowiedź, aby dodać przykład na początku.

— rgrig