Número de Motzkin

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)

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.

• 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

• 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.

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