Número de Motzkin

En matemáticas, un número de Motzkin para un cierto número n es la cantidad de maneras distintas de dibujar cuerdas que no se intersecan en un círculo entre n puntos. Los números de Motzkin tienen variadas aplicaciones en geometría, combinatoria y teoría de números. Los primeros números de Motzkin son ((sucesión A001006 en OEIS)):

Número de Motzkin
Nombrado por Theodore Motzkin
Año de publicación 1948
Autor de la publicación Theodore Motzkin
No. de términos conocidos Infinito
Fórmula véase Propiedades
Primeros términos 1, 1, 2, 4, 9, 21, 51
índice OEIS

1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829

Un primo de Motzkin es un número de Motzkin que es primo. Los primeros primos de Motzkin son ((sucesión A092832 en OEIS)):

2, 127, 15511, 953467954114363

El número de Motzkin para n es también el número de secuencias de enteros positivos de longitud n−1 en las cuales los elementos iniciales y finales son 1 o 2, y que la resta entre cualquier par elementos consecutivos es −1, 0 o 1.

Asimismo, en el cuadrante superior derecho de una cuadrícula, el número de Motzkin para n es la cantidad de rutas distintas desde la coordenada (0, 0) a la coordenada (n, 0) si sólo se permiten movimientos hacia la derecha (junto con ir hacia arriba, hacia abajo o seguir derecho) en cada paso, pero evitando pasar hacia abajo del eje y = 0.

Ejemplos

editar

La siguiente figura muestra las 9 formas de dibujar cualquier número de cuerdas (0, 1 o 2 como máximo en este caso) con la condición de que no se corten entre sí, trazándolas entre 4 puntos de una circunferencia (M4= 9):

La siguiente figura muestra las 21 formas de dibujar cuerdas que no se corten entre sí entre 5 puntos en una circunferencia (M5= 21):

 
 

Propiedades

editar

Los números de Motzkin satisfacen la relación de recurrencia

 

También se pueden expresar en términos de coeficientes binomiales y de números de Catalan:

 

e inversamente,[1]

 

La función generadora   de los números de Motzkin satisface

 

y se expresa explícitamente como

 

Una representación integral de los números de Motzkin viene dada por

 .

Tienen el comportamiento asintótico

 .

Un primo de Motzkin es un número de Motzkin que es primo. A 2019, solo se conocen cuatro primos de este tipo:

2, 127, 15511, 953467954114363 (sucesión A092832 en OEIS)

Interpretaciones combinatorias

editar
 
Ejemplo de la interpretación combinatoria de los números de Motzkin

El número de Motzkin para n es también el número de secuencias enteras positivas de longitud n − 1 en las que los elementos de apertura y finalización son 1 o 2, y la diferencia entre dos elementos consecutivos es −1, 0 o 1. De manera equivalente, el número de Motzkin para n es el número de secuencias enteras positivas de longitud n + 1 en las que los elementos de apertura y finalización son 1, y la diferencia entre dos elementos consecutivos es −1, 0 o 1.

Además, el número de Motzkin para n da el número de rutas en el cuadrante superior derecho de una cuadrícula desde la coordenada (0, 0) hasta la coordenada (n, 0) en n pasos si se permite moverse solo hacia la derecha (arriba, hacia abajo o en línea recta) en cada paso y queda prohibido situarse por debajo del eje y = 0.

Por ejemplo, en la imagen de la derecha se muestran los 9 caminos de Motzkin válidos desde (0, 0) hasta (4, 0).

Hay al menos catorce manifestaciones diferentes de los números de Motzkin en diferentes ramas de las matemáticas, como enumera Donaghey y Shapiro (1977) en su estudio de los números de Motzkin.

Así mismo,Guibert, Pergola y Pinzani (2001) demostró que las involuciones vexilares se enumeran mediante números de Motzkin.

Véase también

editar

Referencias

editar
  1. Yi Wang and Zhi-Hai Zhang (2015). «Combinatorics of Generalized Motzkin Numbers». Journal of Integer Sequences (18). 

Bibliografía

editar

Enlaces externos

editar