Enumeración de árboles binarios

Un árbol binario está etiquetado si a cada Node se le asigna una etiqueta y un árbol binario no está etiquetado si a los Nodes no se les asigna ninguna etiqueta. 

Below two are considered same unlabelled trees
    o                 o
  /   \             /   \ 
 o     o           o     o 

Below two are considered different labelled trees
    A                C
  /   \             /  \ 
 B     C           A    B 

¿Cuántos árboles binarios sin etiqueta diferentes puede haber con n Nodes? 
 

For n  = 1, there is only one tree
   o

For n  = 2, there are two trees
   o      o
  /        \  
 o          o

For n  = 3, there are five trees
    o      o           o         o      o
   /        \         /  \      /         \
  o          o       o    o     o          o
 /            \                  \        /
o              o                  o      o

La idea es considerar todos los posibles pares de conteos para los Nodes en los subárboles izquierdo y derecho y multiplicar los conteos para un par en particular. Finalmente, sume los resultados de todos los pares. 

For example, let T(n) be count for n nodes.
T(0) = 1  [There is only 1 empty tree]
T(1) = 1
T(2) = 2

T(3) =  T(0)*T(2) + T(1)*T(1) + T(2)*T(0) = 1*2 + 1*1 + 2*1 = 5

T(4) =  T(0)*T(3) + T(1)*T(2) + T(2)*T(1) + T(3)*T(0)
     =  1*5 + 1*2 + 2*1 + 5*1 
     =  14 

El patrón anterior representa básicamente n’ésimos números catalanes . Los primeros números catalanes son 1 1 2 5 14 42 132 429 1430 4862,… 

Aquí, 
T(i-1) representa el número de Nodes en el subárbol izquierdo 
T(n−i-1) representa el número de Nodes en el subárbol derecho 

El enésimo número catalán también se puede evaluar mediante la fórmula directa. 

   T(n) = (2n)! / (n+1)!n!

El número de árboles de búsqueda binarios (BST) con n Nodes también es el mismo que el número de árboles sin etiquetar. La razón de esto es simple, en BST también podemos convertir cualquier clave en una raíz. Si la raíz es la i-ésima clave en orden, entonces las claves i-1 pueden ir en un lado y las teclas (ni) pueden ir en el otro. lado. 

¿Cuántos árboles binarios etiquetados pueden existir con n Nodes?  
Para contar árboles etiquetados, podemos usar el conteo anterior para árboles no etiquetados. La idea es simple, cada árbol sin etiquetar con n Nodes puede crear n! diferentes árboles etiquetados asignando diferentes permutaciones de etiquetas a todos los Nodes. 

Por lo tanto, 

Number of Labelled Trees = (Number of unlabelled trees) * n!
                       = [(2n)! / (n+1)!n!]  × n!

Por ejemplo, para n = 3, ¡hay 5 * 3! = 5*6 = 30 árboles etiquetados diferentes 

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.