Encontrar el número de árboles homeomórficamente irreducibles de grado $N$

Question

Hay una escena en Goodwill Hunting donde el profesor desafía a los estudiantes con la tarea de encontrar todos los árboles homeomórficamente irreducibles de grado $10$. Esto se discute en muchos lugares, como aquí y en sí mismo es un rompecabezas relativamente fácil de resolver.

La parte más complicada de esa tarea, al menos para mí, es decidir si ya he encontrado todos esos árboles o si falta algo. Entonces viene la pregunta: ¿cómo calcular cuántos árboles homeomórficamente irreducibles de grado $N$ hay?

He intentado encontrar si ese problema ya está resuelto, pero solo encontraba varias variantes de discusiones de Goodwill Hunting. ¿Hay alguna fórmula o algoritmo para ello? ¿Cómo lidiar con esa tarea?

Answer 1

Sí lo hay, pero debo admitir que no lo entiendo completamente (http://oeis.org/A000014), ya que no soy Matemático. Encontré que el número de árboles para n=11 es 14, y descubrí una forma de determinar todos los árboles utilizando un método inventado por mí en menos de 4 minutos específicamente para la tarea, pero estos matemáticos ya encontraron la fórmula. Encontré el sitio con la fórmula en http://mathworld.wolfram.com/Series-ReducedTree.html

El método que utilicé fue divertido en sí mismo. Enumeré los árboles para n=11 de la siguiente manera:
1(10)
2(2,7); 2(3,6); 2(4,5)
3(2,1,5); 3(2,2,4); 3(2,3,3); 3(2,4,2); 3(3,1,4); 3(3,2,3)
4(2,1,1,3); 4(2,2,1,2)
H(0)3(2,2,3)
H(1)3(2,2,2)

Donde H(1)3(2,2,2)=

 >+<
  ^

H(1) significa un cubo de inicio desde el cual solo 1 rama es un final directo un cubo es un nodo desde el cual >2 ramas no son finales directos

Utilizando este método pude deducir fácilmente que había 14 árboles para n=11, e inducir que debía existir una fórmula.

Answer 2

De hecho, hay una manera más fácil de hacer esto; si usamos notación como {2,1,1,2,5} significa: ">-<" con uno de los nodos en el lado derecho vinculado a cinco nodos más, podemos enumerarlos como; {1, 10} {2, 1, 1, 7} {2, 1, 1, 2, 5} {2, 1, 1, 2, 2, 3} {2, 1, 1, 2, 3, 2} {2, 1, 1, 3, 4} {2, 1, 1, 3, 2, 2} {2, 1, 1, 4, 3} {3, 1, 1, 6} {3, 1, 1, 2, 4} {3, 1, 1, 2, 2, 2} {3, 1, 1, 3, 3} {3, 1, 1, 4, 2} {4, 1, 1, 5}

Todos los árboles posibles excepto uno tienen un grupo {1, 1}, lo que significa un árbol [(1, 1), (1, 1)] con otros árboles sustituidos por los dos nodos. Además, estoy seguro de que alguien podría escribir un algoritmo para mi método (si nadie lo ha descubierto aún.)