N¨²meros de Motzkin

La primera ilustraci¨®n de la semana pasada, con sus l¨ªneas quebradas de distintos colores, no es un cuadro abstracto minimalista, sino la representaci¨®n gr¨¢fica de los 63 caminos de Delannoy distintos en una cuadr¨ªcula de 3 x 3, o sea, D(3, 3). Y como se?ala Salva Fuster: ¡°Para contar el n¨²mero de recorridos mon¨®tonos en los que tambi¨¦n podemos ir en diagonal, una de las im¨¢genes del art¨ªculo puede ser de utilidad, pues la coloraci¨®n depende del n¨²mero de segmentos diagonales. Para...

La primera ilustraci¨®n de la semana pasada, con sus l¨ªneas quebradas de distintos colores, no es un cuadro abstracto minimalista, sino la representaci¨®n gr¨¢fica de los 63 caminos de Delannoy distintos en una cuadr¨ªcula de 3 x 3, o sea, D(3, 3). Y como se?ala Salva Fuster: ¡°Para contar el n¨²mero de recorridos mon¨®tonos en los que tambi¨¦n podemos ir en diagonal, una de las im¨¢genes del art¨ªculo puede ser de utilidad, pues la coloraci¨®n depende del n¨²mero de segmentos diagonales. Para cada caso (en funci¨®n del n¨²mero de segmentos diagonales), convendr¨ªa utilizar permutaciones con repetici¨®n con los segmentos Norte y Este restantes¡±.

Y a?ade Luca Tanganelli: ¡°En efecto, distinguiendo los casos seg¨²n el n¨²mero de segmentos diagonales da que D(m, n) = (m, n)(m ¨C n, 0) + (m + 1, n ¨C 1)(m ¨C n + 2, 1) + (m + 2, n ¨C 2)(m ¨C n + 4, 2) +...+ (m + n, 0)(m + n, n)¡±.

Y se?ala Francisco Montesinos: ¡°Como no hay marchas atr¨¢s, D(m, n) = D(m - 1, n) + D(m - 1, n - 1) + D(m, n - 1)¡±.

No hay una f¨®rmula sencilla que d¨¦ el valor de D(m, n) en funci¨®n de m y n; hay que recurrir a sumatorios, matrices o series infinitas. Y como cada n¨²mero de Delannoy depende de dos enteros, no se puede listarlos linealmente, se requiere una tabla de doble entrada, denominada matriz de Delannoy.

Obs¨¦rvese que D(0, 0) = 1, D(0, n) = 1, D(n, 0) = 1 para cualquier valor de n. ?C¨®mo se justifica esto, dado que no hay cuadr¨ªculas de 0 filas o 0 columnas?

De las cuadr¨ªculas a los c¨ªrculos

Si marcamos 4 puntos en una circunferencia, ?de cu¨¢ntas maneras diferentes podemos trazar cuerdas no secantes entre esos puntos? Si contamos tambi¨¦n la opci¨®n de no trazar ninguna cuerda, hay 9 posibilidades: 1 con 0 cuerdas, 6 con 1 cuerda y 2 con 2 cuerdas.

Obs¨¦rvese que no es posible trazar 3 cuerdas sin que ninguna se corte, por lo que 0, 1 y 2 cuerdas son, con 4 puntos, las ¨²nicas posibilidades.

Con esta construcci¨®n hemos hallado el cuarto de los n¨²meros de Motzkin (llamados as¨ª en honor del matem¨¢tico estadounidense Theodore Motzkin), correspondiente a 4 puntos. Si solo marcamos un punto en la circunferencia, solo tenemos la opci¨®n 0 cuerdas, por lo que el primer n¨²mero de Motzkin es 1. Con 2 puntos, podemos trazar una cuerda o ninguna, por lo que el segundo n¨²mero de Motzkin es 2. Con 3 puntos podemos no trazar ninguna cuerda o las 3 que unen los puntos dos a dos, por lo que el tercer n¨²mero de Motzkin es 4. Y ya hemos visto que el quinto es 9. Tenemos, pues, la secuencia:

1, 2, 4, 9¡­

?C¨®mo sigue? Me conformo con el quinto, pues el sexto es 51 y es bastante trabajoso dar con ¨¦l. Y la secuencia crece r¨¢pidamente:

¡­51, 127, 323, 835, 2188, 5798¡­

Y la metapregunta de rigor: ?por qu¨¦ menciono los n¨²meros de Motzkin despu¨¦s de hablar de los de Delannoy? ?Qu¨¦ relaci¨®n hay entre ambos tipos de n¨²meros?

Como curiosidad, los primos de Motzkin, o sea, los n¨²meros de Motzkin que adem¨¢s son primos, han despertado el inter¨¦s de los matem¨¢ticos a pesar de su escasez (o precisamente por ella). Hasta el momento solo se conocen cuatro:

2, 127, 15511 y 953467954114363.

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