Contando alberi binari

Question

(io sono uno studente con alcune basi matematiche e mi piacerebbe sapere come contare il numero di uno specifico tipo di alberi binari.)

Guardando pagina di Wikipedia per binario Alberi , ho notato questa affermazione che il numero di alberi binari radicati di dimensioni $ n $ sarebbe questo Numero catalana : $$ C_n = \ dfrac {1} {n + 1} {2n \ scegliere n} $$

Ma io non capisco come ho potuto venire con un tale risultato da solo? Esiste un metodo per trovare questo risultato?

Ora, che cosa se l'ordine di sotto-alberi (che è a sinistra, che è a destra) non è considerato? Ad esempio, dal mio punto di vista, ritengo che questi due alberi sono gli stessi:

   /\   /\
  /\     /\

sarebbe possibile applicare un metodo simile a contare quanti di questi oggetti hanno nodi esattamente $ n $?

Answer 1

Per contando molti tipi di oggetti combinatori, come gli alberi, in questo caso, ci sono potenti strumenti matematici (il metodo simbolico) che permettono di ricavare mechnically tali conteggi da una descrizione di come sono costruiti gli oggetti combinatori. Questo comporta la generazione di funzioni.

Un riferimento eccellente è Analitica Combinatorics dal compianto Philipe Flajolet e Robert Sedgewick . E 'disponibile dal link qui sopra.

Il libro di Il compianto Herbert Wilf generatingfunctionology è un'altra fonte gratuita.

E naturalmente Concrete Mathematics di GKP è un tesoro .

---

Per gli alberi binari va in questo modo:. In primo luogo è necessario una chiara definizione della struttura

Un albero binario è un albero radicato in cui ogni nodo non foglia ha esattamente gradi 2.

Ora dobbiamo concordare ciò che vogliamo chiamare la dimensione di un albero.

A sinistra tutti i nodi sono uguali. In mezzo si distinguono le foglie e non foglie. Sulla destra abbiamo un albero binario potato in cui sono state rimosse le foglie. Si noti che ha rami unari di due tipi (sinistra e destra)!

Ora dobbiamo ricavare una descrizione di come questi oggetti combinatori sono costruiti. Nel caso di alberi binari di ricorsiva decomposizione è possibile.

Sia $ \ mathcal {A} $ l'insieme di tutti gli alberi binari del primo tipo poi simbolicamente abbiamo:

Si legge come: “Un oggetto della classe degli alberi binari è un nodo o un nodo seguito da due alberi binari.” Questo può essere scritto come equazione di set:

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

Con l'introduzione della funzione generatrice $ A (z) $ che enumera questa classe di oggetti combinatori possiamo tradurre l'equazione insieme in un'equazione che coinvolge la funzione generatrice.

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

La nostra scelta di trattare tutti i nodi allo stesso modo e prendere il numero di nodi dell'albero come idea delle sue dimensioni è espressa da “marcatura” i nodi con la variabile $ Z $.

Ora possiamo risolvere l'equazione quadratica $ zA ^ 2 (z) -A (z) + z = 0 $ per $ A (z) $ e ricevere, come al solito, due soluzioni, la forma chiusa esplicita della generatrice funzione:

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

Ora abbiamo semplicemente bisogno di Newton (generalizzato) binomiale Teorema:

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

con $ a = 1/2 $ e $ x = -4z ^ 2 $ per espandere la forma chiusa della funzione generatrice di nuovo in una serie di potenze. Facciamo questo perché, il coefficiente a $ z ^ n $ è solo il numero di oggetti combinatori di dimensioni $ n $, di solito scritta da $ [z ^ n] A (z) $. Ma qui il nostro concetto di “dimensioni” delle forze albero di guardare per il coefficiente a $ z ^ {2n + 1} $. Dopo un po 'di giocoleria con binomi e fattoriali otteniamo:

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

Se cominciamo con la seconda nozione di dimensione decomposizione ricorsiva è:

Si arriva una diversa classe di oggetti combinatori $ \ mathcal {B} $. Si legge: “Un oggetto della classe di alberi binari è o una foglia o un nodo interal seguito da due alberi binari”

Si può utilizzare lo stesso approccio e trasformare $ \ mathcal {B} = \ {\ quadrato \} \ cup \ bigl (\ {\ bullet \} \ times \ mathcal {b} \ times \ mathcal {B} \ BIGR) $ in $ \ mathcal {B} = 1 + zB ^ 2 (z) $. Solo che questa volta la variabile $ Z $ solo segni di nodi interni, non le foglie, perché la definizione “la dimensione” è differisceent qui. Otteniamo una funzione generatrice diversa così:

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

Estrazione dei rendimenti dei coefficienti

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

Class $ \ mathcal {A} $ e $ \ mathcal {B} $ concordare i conteggi, perché un albero binario con $ n $ nodi interni ha $ n + 1 $ foglie, quindi $ 2n + 1 $ nodi totale.

In quest'ultimo caso dobbiamo lavorare un po 'più difficile:

che è una descrizione di non vuoti tentativi binari potati. Estendiamo questo per $$ \ begin {align} \ mathcal {C} & = \ {\ bullet \} \ cup \ bigl (\ {\ bullet \} \ times \ mathcal {C} \ BIGR) \ tazza \ 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} $$

e riscrivere con funzioni generatrici

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

risolvere le equazioni di secondo grado

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

e ottenere ancora una volta

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

Si noti che il funzione generatrice Catalano è

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

si enumera la classe di alberi generali . Cioè gli alberi senza alcuna restrizione sul grado nodo.

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

Si legge come: “Un oggetto della classe di alberi generali è un nodo seguita da una possibile sequenza vuota di alberi generali”

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

Con il Lagrange-Bürmann formula di inversione otteniamo

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

Così abbiamo dimostrato che ci sono tanti alberi generali in quanto vi sono alberi binari. Non c'è da stupirsi c'è una corrispondenza biunivoca tra gli alberi generali e binari. La biiezione è noto come il rotazione corrispondenza (spiegato alla fine del articolo collegato), che ci permette due negozio ogni albero generale, come un albero binario.

Si noti che se non distinguiamo il fratello a destra ea sinistra in classe $ \ mathcal {C} $ otteniamo un'altra classe di alberi $ \ mathcal {T} $:

gli alberi binari unari. $$ \ mathcal {T} = \ {\ bullet \} \ times \ mathrm {SEQ} _ {\ LE2} (\ mathcal {T}) $$ Hanno una funzione generatrice troppo $$ T (z) = \ frac {1-Z- \ sqrt {1-2z-3z ^ 2}} {} 2z $$ tuttavia il loro coefficiente è diverso. È possibile ottenere i numeri di Motzkin $$ [z ^ n] T (z) = \ frac {1} {n} \ sum_k \ binom {n} {k} \ binom {n-k} {k-1}. $$

Oh, e se non ti piace funzioni generatrici ci sono un sacco di altre prove anche. Vedere qui , v'è quella in cui è possibile utilizzare la codifica di alberi binari come le parole Dyck e e derivano una ricorrenza da loro definizione ricorsiva. Poi la risoluzione che la ricorrenza dà la risposta troppo. Tuttavia il metodo simbolico consente di risparmiare da venire con la ricorrenza, in primo luogo, in quanto funziona direttamente con i progetti degli oggetti combinatori.

Answer 2

funzioni generatrici sono una molto potente e molto utile bacchetta magica. La seguente soluzione alla prima domanda (il motivo per cui sono lì $ C_n $ alberi) è un po 'meno magico. Quindi, sveglio.

Esempio. Per produrre un albero di $ 5 $ nodi si comincia con una sequenza in cui $ + 1 $ si verifica $ 5 + 1 $ volte, e $ -1 $ avviene $ 5 $ volte. Ad esempio, $ + - ++ - + - ++ - $. Tra i prefissi con il più piccolo (e possibilmente negativo) sum, scegliere la più lunga; in questo caso, $ + - ++ - + - $. Prendete questo prefisso fin dall'inizio e metterlo alla fine; in questo caso, si ottiene $ ++ - + - ++ - + - $. Ora cambiare $ + $ in $ T $ e $ - $ in $ E $; in questo caso si ottiene TTETETTETEE. Rimuovere un $ T $ fin dall'inizio, aggiungere un $ E $ alla fine; in questo caso si ottiene TETETTETEEE. Questa è una descrizione del T(E,T(E,T(T(E,T(E,E)),E))) albero. Qui di seguito c'è qualche spiegazione del perché questo è una biiezione. Una volta che siete convinti di questo, il conteggio è facile. Ci sono $ \ binom {5 + 6} {5} $ sequenze di $ \ PM1 $, poi abbiamo diviso per $ 5 + $ 6 perché abbiamo scelto una delle possibili permutazioni cicliche.

.

Primo biiezione Una definizione tipica per gli alberi in ML è type tree = T of tree * tree | E; cioè, un albero siano disponibili due sottoalberi (ordinate), oppure è vuoto. Ecco come sono costruiti gli alberi: T(T(E,E),T(T(E,E),T(E,E))). Lasciando cadere lanugine, possiamo semplicemente scrivere TTEETTEETEE. Tutte queste descrizioni si conclude con un E, quindi è ridondante: TTEETTEETE. (Si noti che l'albero vuoto ora corrisponde alla stringa vuota.) Queste stringhe hanno la proprietà che ogni prefisso ha almeno altrettanti Ts come Es, e in totale hanno $ n $ Ts e $ n $ Es, dove $ n $ è il numero di nodi dell'albero.

Secondo biiezione. Ora sostituiamo T di +1 ed E -1. Quindi, siamo di fronte a sequenze con $ n $ valori +1, con $ n $ valori -1, e con le somme di tutti i prefissi $ \ GE0 $.

.

Terzo biiezione Ora cambiamo la necessità di un po 'di prefissi: Chiediamo che la somma di ogni prefisso non vuoto per essere $> 0 $. Perché ciò sia possibile, lasciamo $ n + 1 $ valori +1 e $ n $ valori -1. (Altrimenti la somma di tutta la stringa sarebbe 0 e non riuscirebbe a soddisfare la condizione per prefissi.) Queste sequenze devono iniziare con +1. Quindi, in realtà sono le stesse di prima, tranne che hanno un +1 bloccato in principio.

immobili Raney. Ora dimenticare le nostre sequenze per un attimo e prendere in considerazione alcuni sequenza finita di interi $ x_1 $, $ \ ldots \, $, $ x_m $ la cui somma è 1. Se tutti i prefissi non vuoti hanno somme positivi, quindi permutazione non ciclico di questa sequenza ha la stessa struttura. Perché? Bene, supponiamo che ci sia un $ k \ ne1 $ tale che $ x_k, \ ldots, x_m, x_1, \ ldots, x_ {k-1} $ ha anche tutti i prefissi non vuoti positivi. Poi $ x_1 + \ cdots + x_ {k-1} \ GE1 $ (proprietà della sequenza a partire da $ x_1 $) e $ x_k + \ cdots + x_m \ GE1 $ (proprietà della sequenza a partire da $ x_k $); di conseguenza, $ x_1 + \ cdots + x_m \ ge2 $, che contraddice l'ipotesi che la somma per l'intera sequenza è 1.

Inoltre, dato qualche sequenza con somma 1, v'è sempre una permutazione ciclica che rende tutti i prefissi non vuoti hanno somma positiva. (Questo è vero anche per i numeri reali.)

Conclusione. Ora contiamo le sequenze di +1 e -1 che sono in una corrispondenza biunivoca con gli alberi. Fuori di $ 2n + 1 $ numeri dobbiamo raccogliere $ n + 1 $ che la parità di 1, gli altri saranno -1. Ci sono $ {2n + 1 \ scelgono n + 1} $ modi per farlo. Ma, solo $ 1 $ a $ 2n + 1 $ sequenze contati finora ha prefissi positivi. Così, il numero di radici, ordinato alberi binari è:

$$ {1 \ over2n + 1} {2n + 1 \ scegliere n + 1} = {1 \ over2n + 1} {2n + 1 \ over n + 1} {2n \ scegliere n} = {1 \ su n + 1} {2n \ scegliere n} $$