Angel "Java" Lopez en Blog

Publicado el 2 de Abril, 2011, 12:00

Venga hoy, igual que ayer, un problema de matemáticas.

Sea un grafo con nodos, en forma de árbol (no tiene ciclos), con una jerarquía: hay nodos "padres" de otros:

Marcamos cada nodo con una letra (el color no importa, lo puse para animar el blog ;-). Podemos enumerar sus nodos, como en:

A B C D E .....

El problema es ¿Cuántas formas de enumerar un árbol hay, siempre y cuando cada nodo aparezca DESPUES de sus padres y ascendientes? Es decir, en el ejemplo de arriba, H debe enumerarse (aparecer en la lista) pero NO ANTES de A o de C, que son sus ascendientes.

Ejemplos válidos (parciales):

A B E F G ....
A B G F E ....  (no importa el orden de los hermanos)
A B C H I ...  (se pueden enumerar los hijos de C antes de los de B)
A B G C I ... (se pueden mezclar las enumeraciones de descendientes: no hace falta enumerar todos los descendientes de B antes de los de C, no importa)
A D J C I H M B F K .... (creo que ya quedaron las principales variantes)

Vean que no planteo la pregunta para un árbol en particular. ¿Pueden encontrar el resultado para un árbol de n nodos? ¿Importará "la forma" del árbol?

En un futuro post, escribiré mis primeros intentos de solución, y finalmente, la solución que encontré.

(Nota para informáticos: el problema fue planteado por A.V. en una lista de programación Smalltalk. ¿Cuántas formas hay de escribir en un archivo el código de las clases de una jerarquía, siempre que cada clase NO aparezca ANTES de sus superclases?) Simpático problema ;-)

Nos leemos!

Angel "Java" Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez