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)):

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

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

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

${\displaystyle M_{n}=M_{n-1}+\sum _{i=0}^{n-2}M_{i}M_{n-2-i}={\frac {2n+1}{n+2}}M_{n-1}+{\frac {3n-3}{n+2}}M_{n-2}.}$

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

${\displaystyle M_{n}=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}C_{k},}$

e inversamente,^[1]​

${\displaystyle C_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}M_{k}.}$

La función generadora ${\displaystyle m(x)=\sum _{n=0}^{\infty }M_{n}x^{n}}$ de los números de Motzkin satisface

${\displaystyle x^{2}m(x)^{2}+(x-1)m(x)+1=0}$

y se expresa explícitamente como

${\displaystyle m(x)={\frac {1-x-{\sqrt {1-2x-3x^{2}}}}{2x^{2}}}.}$

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

${\displaystyle M_{n}={\frac {2}{\pi }}\int _{0}^{\pi }\sin(x)^{2}(2\cos(x)+1)^{n}dx}$.

Tienen el comportamiento asintótico

${\displaystyle M_{n}\sim {\frac {1}{2{\sqrt {\pi }}}}\left({\frac {3}{n}}\right)^{3/2}3^{n},~n\to \infty }$.

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

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

• Número telefónico, que representan el número de formas de trazar cuerdas si se permiten intersecciones
• Números de Delannoy
• Números de Narayana
• Números de Schröder

Referencias

Bibliografía

• Bernhart, Frank R. (1999), «Catalan, Motzkin, and Riordan numbers», Discrete Mathematics 204 (1-3): 73-112, doi:10.1016/S0012-365X(99)00054-0 .
• Donaghey, R.; Shapiro, L. W. (1977), «Motzkin numbers», Journal of Combinatorial Theory, Series A 23 (3): 291-301, MR 0505544, doi:10.1016/0097-3165(77)90020-6 .
• Guibert, O.; Pergola, E.; Pinzani, R. (2001), «Vexillary involutions are enumerated by Motzkin numbers», Annals of Combinatorics 5 (2): 153-174, ISSN 0218-0006, MR 1904383, doi:10.1007/PL00001297 .
• Motzkin, T. S. (1948), «Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products», Bulletin of the American Mathematical Society 54 (4): 352-360, doi:10.1090/S0002-9904-1948-09002-4 .

Enlaces externos

• Weisstein, Eric W. «Motzkin Number». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.