¿Cuántas hojas tiene el árbol 2017?

¿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.

 

Advertisements

Dos de cada tres estudiantes de la UIB, matriculados en carreras con muchos estudiantes. ¿Notición?

Estos días estoy meditando sobre aplicaciones de la paradoja de la amistad en el análisis de redes de interacciones de proteínas. Como Clara Grima ya explicó coj…mente esta paradoja en esta entrada de Cienciaxplora, voy a ahorraros los detalles. En todo caso, y en resumen, se trata del hecho que, para la mayoría de nosotros, nuestros amigos tienen, de media, más amigos que nosotros (y son más felices y más guapos que nosotros, y han ligado a lo largo de su vida más que nosotros y …). Por suerte, esto (normalmente) no tiene nada que ver con nuestra personalidad, sino que es un teorema de teoría de grafos atribuido a Scott Feld, que lo enunció, demostró y analizó en su artículo del 1991 titulado Why your friends have more friends than You do.

En realidad, esta paradoja viene de más lejos, de la llamada “paradoja del tamaño de la clase” que introdujeron el mismo Scott Feld y Bernard Grofman en un artículo de 1977 titulado Variation in class size, the class size paradox, and some consequences for students:

si escogemos al azar un estudiante de un centro, el tamaño esperado del curso en el que está matriculado es casi siempre estrictamente mayor que el tamaño medio de los cursos de su centro, y en todo caso nunca menor.

Además, en muchas distribuciones razonables de números de matriculados por curso, una gran mayoría de los estudiantes están matriculados en cursos más numerosos que la media (lo que les lleva, por comparación, al desánimo y al abandono de los estudios, según los autores; igual se lo podemos explicar a las comisiones de acreditación de los grados: “no es culpa nuestra que abandonen los estudios, es que no saben teoría de grafos y creen que son unos desgraciados por estar en cursos numerosos”).

Aquí viene la demostración. Sean x_1,\ldots, x_n los números de alumnos de los n cursos que ofrece un determinado centro. Entonces:

  • El valor medio de alumnos por curso es \overline{x}=(\sum_{i=1}^n x_i)/n
  • Pero si consultamos todos los estudiantes uno a uno y les pedimos cuántos estudiantes hay en su curso, y calculamos la media de los valores obtenidos, será otro cantar: para cada curso de x_i alumnos, habrá  x_i alumnos que contestarán “x_i”, por lo que cada respuesta  x_i aparecerá x_i veces. La suma total de respuestas será, por lo tanto, \overbrace{x_1+\cdots+x_1}^{x_1} +\cdots+ \overbrace{x_n+\cdots+x_n}^{x_n}=\sum_{i=1}^n x_i^2. La respuesta media por alumno (es decir, el número medio de matriculados en el curso en el que está matriculado un alumno escogido al azar), llamémosle \overline{x}_{al}, se obtendrá dividiendo esta suma por el número de respuestas:  \overline{x}_{al}=(\sum_{i=1}^n x_i^2)/(\sum_{i=1}^n x_i)

Si ahora restamos \overline{x}_{al}-\overline{x}=(\sum_{i=1}^n x_i^2)/(\sum_{i=1}^n x_i)-(\sum_{i=1}^n x_i)/n, un pequeño cálculo algebraico muestra que es igual a la varianza \mathrm{var}(x) de x_1,\ldots, x_n partido por su media \overline{x}. Y ahora es el momento de recordar que la varianza siempre es positiva, y es 0 sólo cuando x_1=\cdots=x_n. Por lo tanto, salvo en este caso, el número medio de matriculados en el curso de un estudiante escogido al azar será siempre mayor que el número medio de matriculados por curso. Y cuánto mayor sea la varianza, es decir, cuánto más variados sean los números x_1,\ldots, x_n, mayor será el cociente entre estas dos medias.

Vale, un experimento. He sacado de aquí los números de matriculados en los 30 grados de la UIB en el curso 2013-14 (los matriculados en dobles titulaciones los he contado en cada una de los grados involucrados). Estos números van de los 1228 matriculados en Administración de Empresas a los 93 matriculados en Matemáticas. He calculado el número medio de estudiantes por grado, \overline{x}, y el número medio de estudiantes matriculados en el grado de un estudiante aleatorio, \overline{x}_{al}. Los resultados (redondeados) han sido \overline{x}=366\overline{x}_{al}=593: un estudiante está matriculado de media en un grado de 593 estudiantes, pero el número medio de estudiantes por grado es de 366. Además, un 66.5% de los estudiantes de la UIB están matriculados en grados con un número de estudiantes mayor que la media. Es raro que algunos periódicos tradicionalmente críticos por defecto con la UIB no lo hayan publicado nunca.

El código R, por si queréis confirmar los números, es muy sencillo.

 ests.UIB=c(1228,1042,1028,623,612,560,497,467,432,412,400,351,339,
252,243,231,228,226,215,180,174,154,169,156,146,140,134,131,116,93)
#Media de alumnos por grado
mean(ests.UIB)
#Media de alumnos por grado desde el punto de vista del alumno
sum(ests.UIB^2)/sum(ests.UIB)
#Porcentaje de alumnos en grados más numerosos que la media
sum(ests.UIB[ests.UIB>mean(ests.UIB)])/sum(ests.UIB)

En cambio no sé cómo usar la paradoja de la amistad para explicar la percepción de los estudiantes de que sus amigos siempre tienen menos tareas que ellos para hacer en casa.

 

La simetría también es buena… en el cáncer

Las caras simétricas nos parecen más bonitas. Las simetrías en las decoraciones de la Alhambra y otros edificios árabes nos resultan fascinantes. 196.000 resultados en Google de “symmetry is good”. Bueno, pues resulta que un tipo concreto de simetría también es buena señal en el cáncer.

Para algunos tipos de cáncer, se han publicado sus redes de interacciones de proteínas (PPI) en la base de datos KEGG PATHWAY. Estas redes representan el conocimiento actual sobre las interacciones entre proteínas en células cancerosas. Desde el punto de vista matemático, son grafos no dirigidos relativamente grandes, sin bucles ni aristas múltiples. Una línea de investigación muy popular en biología computacional de sistemas es la reconstrucción automática de este tipo de redes a partir de datos experimentales, y el estudio y comparación de los grafos resultantes.

Una propiedad que se puede estudiar en un grafo es su simetría. Se dice que un grafo es simétrico cuando tiene algún automorfismo diferente de la identidad, y más simétrico es cuantos más automorfismos tiene, ea decir, cuanto más fácil sea intercambiar algunos de sus nodos sin que se modifique la estructura abstracta de conexiones que representa.Es bien sabido que si escogemos al azar (de manera equiprobable) un grafo de n nodos, la probabilidad de que sea simétrico tiende a 0 a medida que n tiende a \infty. En cambio, las grandes redes complejas de la vida real (desde Internet a las redes biomoleculars) tienen grupos de automorfismos muy grandes, como se puede comprobar en la tabla 1 de Symmetry in Complex Networks de B. MacArthur, R. Sánchez-García y J. Anderson. Esto se puede tomar como un síntoma más de que las redes complejas de la vida real son poco aleatorias.

Una manera de medir la simetría de un grafo G de n nodos es mediante el siguiente índice, que cuantifica la fracción  de automorfismos en el conjunto total de permutaciones de sus vértices:

\displaystyle\beta(G)=\left(\frac{|Aut(G)|}{n!}\right)^{\frac{1}{n}}

En un artículo colgado en el arXiv el pasado mes de mayo, P. Hinow, A. Rietman, J. Tuszynski han calculado este índice \beta para las redes PPI de algunos tipos de cáncer, y los han comparado con su probabilidad estimada p de supervivencia a los 5 años (que se puede obtener del Surveillance, Epidemiology, and End Results Program). Su conclusión se resume en el gráfico siguiente:

regrsim

Este gráfico muestra una clara correlación positiva entre la probabilidad de supervivencia y el índice de simetría \beta: a más simétrico, más benigno. El coeficiente de determinación R^2 que obtienen es de 0.52. No es para echar las campanas al vuelo, pero dados por un lado la gran imprecisión en la estimación de la mortalidad para los diferentes tipos de cáncer que se obtiene del SEER, y por otro nuestro desconocimiento del detalle completo de las redes PPI, la correlación que obtienen se puede considerar significativa.

So what? Bueno, es curioso. Cuánto más simétrica es una red PPI, más reemplazables son sus elementos por otras proteínas en la misma red, lo que la vuelve más robusta a fallos cuando alguna proteína se elimina del sistema por ejemplo mediante algún medicamento. Que esta propiedad esté correlacionada positivamente con la probabilidad de supervivencia a 5 años va completamente en contra de nuestra intuición, y muestra que aún nos falta mucho por aprender sobre el comportamiento del cáncer.