?rboles y caminos

?Cu¨¢ntos ¨¢ngulos interiores mayores de 180? puede tener un pol¨ªgono en funci¨®n de su n¨²mero de lados?, nos pregunt¨¢bamos la semana pasada.

Un tri¨¢ngulo no puede tener ninguno; salta a la vista, pero como a veces la vista nos enga?a, digamos que, puesto que los ¨¢ngulos interiores de cualquier tri¨¢ngulo suman 180?, para que hubiera un ¨¢ngulo de m¨¢s de 180? la suma de los otros dos tendr¨ªa que ser negativa, lo cual es imposible (al menos en el marco de la geometr¨ªa eucl¨ªdea).

Un cuadril¨¢tero c¨®ncavo puede tener un solo ¨¢ngulo mayor de 180?, y un pent¨¢gono puede tener dos. ?Cu¨¢ntos ¨¢ngulo c¨®ncavos puede tener, como m¨¢ximo, un hex¨¢gono, un hept¨¢gono, un oct¨®gono¡­?

Hay varios caminos (?cu¨¢ntos?) por los que se puede ir de un v¨¦rtice al opuesto de una cuadr¨ªcula de 3 x 3 recorriendo los lados de las casillas y en el menor n¨²mero de pasos posible (¡°caminos mon¨®tonos¡±, que partiendo del v¨¦rtice inferior izquierdo van hasta el superior derecho dando solo pasos hacia arriba y hacia la derecha). Si ponemos la condici¨®n adicional de que los caminos no crucen la diagonal de la cuadr¨ªcula, el n¨²mero se reduce a 5, que es el n¨²mero de Catalan C?, y lo mismo ocurre con las cuadr¨ªculas de n x n para cualquier valor de n: el n¨²mero de caminos mon¨®tonos distintos y que no cortan la diagonal es siempre Cn.

Cn tambi¨¦n es el n¨²mero de ¨¢rboles binarios de n + 1 nodos sin hijos (denominados hojas o nodos externos) en los que cada nodo tiene 2 hijos o ninguno. En la imagen vemos un ¨¢rbol binario de este tipo con 4 hojas, luego habr¨¢ C? = 5 ¨¢rboles distintos. ?Puedes dibujarlos todos? ?Y en el caso de ¨¢rboles con 5, 6, 7¡­ hojas?

En cuanto a las palabras de Dick, hay 5 de longitud 6:

000111

001011

010011

001101

010101

En general, hay Cn palabras de Dick de longitud 2n; en este caso, como 2n = 6, el n¨²mero de palabras distintas es C? = 5 (?y qu¨¦ pasa con las palabras de longitud impar?).

N¨²meros de Delannoy

Para ir paso a paso de un v¨¦rtice al opuesto de una cuadr¨ªcula podemos seguir un ¡°camino mon¨®tono¡±, como acabamos de ver, que es una de tantas maneras (hay consignadas m¨¢s de sesenta, ?se te ocurre alguna diferente de las que ya hemos visto?) de llegar a los n¨²meros de Catalan. Si adem¨¢s de los pasos hacia arriba y hacia la derecha se admiten tambi¨¦n los pasos en diagonal ascendente (o sea, en direcci¨®n norte, este o noreste), tenemos los caminos de Delannoy, llamados as¨ª en honor del oficial del ej¨¦rcito franc¨¦s y matem¨¢tico aficionado Henri Delannoy (1833-1915). El n¨²mero de caminos de Delannoy distintos que en una cuadr¨ªcula de m x n permiten ir de la esquina suroeste (0, 0) a la esquina noreste (m, n) es el n¨²mero de Delannoy para esa cuadr¨ªcula y se representa como D (m, n).

En la imagen vemos los 13 caminos de Delannoy diferentes para una cuadr¨ªcula de 2 x 2: D(2, 2) = 13. ?Cu¨¢l es el n¨²mero de Delannoy para una cuadr¨ªcula de 2 x 3? ?Y para una de 3 x 3? ?Puedes hallar una f¨®rmula general que d¨¦ el n¨²mero D (m, n) en funci¨®n de m y n?

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