¿Cuántas hojas tiene el árbol 2017?

Cesc

¿Conocéis el chiste aquel de los dos presos que hace mucho tiempo que comparten celda,  y va uno y le pide al otro “Va, cuéntame un chiste”, el otro contesta “El 56” y el primero se parte de risa? Pues últimamente yo estoy en la tesitura de “Va, dame un árbol”, y ya me va bien que me den el 56, pero claro, luego he de saber cuál es. En última instancia, numerar objetos es una manera de ponerles nombre y por lo tanto de poseerlos. Pero entonces es necesario un diccionario que nos permita recuperar los objetos a partir de los números, y si ese diccionario se puede reducir a un algoritmo sencillo, mejor.

En el caso de los árboles (en lo que sigue, por un “árbol” entiendo  un árbol en el sentido de la teoría de grafos y con raíz, que en los dibujos corresponde al nodo superior), hay una numeración muy útil: los números de Matula, que se definen recursivamente de la manera siguiente. Si T es un árbol de un solo nodo, M(T)=1. Si T tiene más de un nodo y T_1,\ldots,T_k son los subárboles que cuelgan de los hijos de su raíz y m_1=M(T_1),\ldots, m_k=M(T_k) son los números de Matula de estos subárboles y p_{m_1},\ldots,p_{m_k} son los primos m_1-ésimo, m_2-ésimo, …, m_k-ésimo, entonces M(T)=p_{m_1}\cdots p_{m_k}.

Veamos un ejemplo. Considerad el árbol de la figura, lo llamaremos T (y como hoy es el día del orgullo friki, uso Comic Sans).

Para calcular su número de Matula, hemos de calcular los de sus subárboles T1 y T2. El de T2 és fácil: 1, porque es un solo nodo (una hoja). El número de Matula de T1 será el producto de los primos correspondientes a los de T3 y T4, así que necesitamos calcular primero los números de Matula de T3 y T4. Veamos: la raíz de T3 tiene 3 hijos y los tres son hojas, por lo que cada uno define un subárbol de un solo nodo; por lo tanto, cada uno de estos subárboles tiene número de Matula 1, y como el primer primo es p_1=2, tenemos que M(T3)=p_1\cdot p_1\cdot p_1=2\cdot 2 \cdot 2=8. Por otro lado,  la raíz de T4 tiene 2 hijos, los dos hojas, por lo que cada uno define un subárbol de un solo nodo, de número de Matula 1. Obtenemos entonces que M(T4)=p_1\cdot p_1=2\cdot 2=4.

Como T3 y T4 son los árboles número 8 y 4, respectivamente, por la recurrencia, M(T1) será el producto del octavo primo, p_{8}=19, y del cuarto primo, p_4=7: M(T_2)=19\cdot 7=133. Y como M(T2)=1, tenemos finalmente que M(T) será el producto del primo en la posición 133, p_{133}=751 y del primer primo, p_1=2. Es decir, M(T)=751\cdot 2=1502.

Este proceso se puede invertir. Dado un número N, lo descomponemos en producto de números primos N=q_1\cdots q_m y buscamos cuál es el número de orden de cada q_i en la lista de todos los primos: digamos que cada q_i es el primo m_i-ésimo. Entonces, la raíz de el árbol T M(T)=N tendrá m hijos, y de ellos colgarán los árboles T_i número M(T_i)=m_i. Naturalmente, si N=1 entonces T es el árbol de un solo nodo, por definición.

Por ejemplo, ¿cuál el es árbol 2017? 2017 es primo, en concreto p_{306}. Por lo tanto el árbol 2017 estará formado por una raíz de la que cuelga un solo hijo, que es la raíz del árbol número 306. Ahora 306=2\cdot 3\cdot 3 \cdot 17. Como p_1=2, p_2=3 y p_7=17, el árbol 306 está formado por una raíz de la que cuelgan 4 hijos, que son raíces de un árbol número 1 (un solo nodo), dos árboles número 2, y un árbol número 7. Os dejo terminar: el árbol número 2 está formado por una raíz con un único hijo que además es una hoja, y el árbol número 7 (=p_4) está formado por una raíz con un único hijo del que cuelgan dos hijos que son hojas. El resultado es el de la figura que sigue.

 

Por lo tanto, cada árbol tiene su número y cada número (natural y a partir de 1) representa un único árbol. Ya los tenemos numerado. Pero además,  muchas propiedades de un árbol se pueden obtener a partir de su número, sin tener que reconstruir el árbol. Por ejemplo, su número de hojas. Es fácil comprobar, siguiendo la reconstrucción de un árbol a partir de su número, que si llamamos N(T) al número de hojas de T e indicamos por T_n el árbol número n, entonces

  • N(T_1)=1,
  • N(T_n)=N(T_m)  si n=p_m
  • N(T_n)=N(T_{q_1})+\cdots+N(T_{q_k}) si n=q_1\cdots q_k y k\geq 2

Por ejemplo, el número de hojas de nuestro árbol T número 2017 es N(T_{2017}) =N(T_{306}) =N(T_{2\cdot 3\cdot 3 \cdot 17}) =N(T_2)+2N(T_3)+N(T_{17})=N(T_2)+2N(T_2)+N(T_{7})=3N(T_2) +N(T_4)=3N(T_2) +2N(T_2)=5N(T_2)=5N(T_1)=5

¡Bien!

Otros muchos índices de un árbol se pueden calcular de manera recursiva a partir de su número de Matula. De hecho, ya os podéis imaginar que todo lo que se pueda calcular recurrentemente de hijos a padres se podrá determinar a partir del número de Matula.  Si os interesa, este artículo de E. Deutsch explica la manera de calcular una trentena de índices.

Esta entrada participa en la edición 8.4 del Carnaval de Matemáticas, cuyo blog anfitrión es matematicascercanas.

 

2 thoughts on “¿Cuántas hojas tiene el árbol 2017?”

  1. Pingback: Resumen de la Edición 8.4 del Carnaval de Matemáticas
  2. Pingback: Ganador de la Edición 8.4 del Carnaval de Matemáticas

Leave a comment