Número de Motzkin

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	A001006 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

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

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

e inversamente,​

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

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

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

y se expresa explícitamente como

$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

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

Tienen el comportamiento asintótico

$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

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

• 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

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. 

• Datos: Q2915234
• Multimedia: Motzkin numbers / Q2915234