Palabras y ¨¢rboles

?De cu¨¢ntas maneras distintas se puede dividir un hex¨¢gono convexo en tri¨¢ngulos mediante diagonales que no se corten?, nos pregunt¨¢bamos la semana pasada.

Y la respuesta es 14, o sea, el n¨²mero de Catalan (Cn) correspondiente a n = 4. De hecho, una de las distintas maneras de interpretar los n¨²meros de Catalan es definir Cn como el n¨²mero de maneras distintas de dividir en tri¨¢ngulos un pol¨ªgono convexo de n + 2 lados mediante diagonales que no se corten. Si n = 4, n + 2= 6, ...

?De cu¨¢ntas maneras distintas se puede dividir un hex¨¢gono convexo en tri¨¢ngulos mediante diagonales que no se corten?, nos pregunt¨¢bamos la semana pasada.

Y la respuesta es 14, o sea, el n¨²mero de Catalan (Cn) correspondiente a n = 4. De hecho, una de las distintas maneras de interpretar los n¨²meros de Catalan es definir Cn como el n¨²mero de maneras distintas de dividir en tri¨¢ngulos un pol¨ªgono convexo de n + 2 lados mediante diagonales que no se corten. Si n = 4, n + 2= 6, luego el pol¨ªgono a dividir es un hex¨¢gono.

Si las diagonales pueden cortarse, el n¨²mero de tri¨¢ngulos resultantes es obviamente mayor. He aqu¨ª lo que dice Salva Fuster al respecto:

¡°Si podemos trazar diagonales que se crucen en un pol¨ªgono convexo, me parece que el n¨²mero m¨¢ximo de tri¨¢ngulos que se puede conseguir en un pent¨¢gono es de 2 x 5 = 10. Aunque variemos la forma del pent¨¢gono, siempre tendremos una zona central en forma de pent¨¢gono y 10 tri¨¢ngulos que la rodean. En el caso del hex¨¢gono no ocurre lo mismo, pues para el hex¨¢gono regular tendremos 3 x 6 = 18 tri¨¢ngulos que rodean una zona central formada por 6 cuadril¨¢teros, pero variando la forma del hex¨¢gono podr¨ªamos conseguir un tri¨¢ngulo adicional, como se puede ver en la figura adjunta¡±.

Conviene recalcar que todo lo anterior se refiere a pol¨ªgonos convexos, que son aquellos cuyos ¨¢ngulos interiores miden, todos ellos, menos de 180?. Si un pol¨ªgono tiene alg¨²n ¨¢ngulo interior mayor de 180?, es c¨®ncavo. Pero ?cu¨¢ntos ¨¢ngulos mayores de 180? puede tener un cuadril¨¢tero, un pent¨¢gono, un hex¨¢gono¡­? ?Hay alguna f¨®rmula que nos d¨¦ el n¨²mero m¨¢ximo de ¨¢ngulos c¨®ncavos posibles en funci¨®n del n¨²mero de lados?

En cuanto al problema ¡°fordiano¡± de los tres c¨ªrculos tangentes entre s¨ª y a una recta, Bretos Burs¨® ofrece la siguiente soluci¨®n:

¡°Dados dos n¨²meros naturales coprimos, m menor que n, los tres radios siguientes son una soluci¨®n (ordenados de menor a mayor):

m? n?, (m + n)? m?, (m + n)? n?

Y cualquier otra soluci¨®n es un m¨²ltiplo de alguna de ellas.

En particular, la menor soluci¨®n (m = 1, n = 2) es la de radios 4, 9 y 36¡å.

Palabras de Dyck y ¨¢rboles binarios

Volviendo a los n¨²meros de Catalan, hay otras muchas maneras de interpretarlos, adem¨¢s de la que acabamos de ver relativa a las diagonales de un pol¨ªgono. Los siguientes problemas pueden conducirnos a otras tantas interpretaciones/definiciones de los n¨²meros de Catalan:

1. Dada una cuadr¨ªcula de 3 x 3, ?por cu¨¢ntos caminos distintos podemos ir de un v¨¦rtice al opuesto recorriendo los lados de las casillas?
2. Un palabra de Dyck es una cadena de ceros y unos (o de X e Y) con el mismo n¨²mero de ceros y de unos y en las que ning¨²n subsegmento inicial (es decir, ning¨²n prefijo de la cadena) tiene m¨¢s unos que ceros. Solo hay una palabra de Dyck de longitud 2: 01; hay dos palabras de Dyck de longitud 4: 0011, 0101. ?Cu¨¢ntas palabras de Dyck hay de longitud 6?
3. ?Cu¨¢ntos ¨¢rboles binarios distintos se pueden formar con 7 nodos? Recordemos que en un ¨¢rbol binario cada nodo solo puede ramificarse en dos como m¨¢ximo.

Y la metapregunta de rigor: ?qu¨¦ tienen que ver estos tres problemas con los n¨²meros de Catalan?

Puedes seguir a MATERIA en Facebook, Twitter e Instagram, o apuntarte aqu¨ª para recibir nuestra newsletter semanal.