El otro día me puse a dibujar árboles siguiendo las líneas de una hoja cuadriculada, como en la figura. (Básicamente, un árbol es un grafo conexo sin ciclos).¿Cuántos árboles de N nodos se podrán dibujar? (Todas las intersecciones del cuadriculado usadas cuentan como nodos).
2 comentarios:
A simple vista este problema estaría emparentado (una especie de problema dual) con determinar el número de N-ominós, considerando a los nodos como cuadrados.
Para "tetrominós" habría un árbol por cada uno de ellos, (el del cuadrado sería una U).
Para los pentominós también hay un árbol para cada uno de ellos, excepto para la P, que genera 4 árboles diferentes (porque hay cuatro formas de romper el ciclo que tiene).
Interesante.
Entonces habría más árboles que pentominós para cada N.
¿Será un simple múltiplo?
Publicar un comentario