Número de Motzkin

En matemáticas , el n- ésimo número de Motzkin es el número de formas diferentes de trazar cuerdas no intersecantes entre n puntos de un círculo (no necesariamente tocando cada punto con una cuerda). Los números de Motzkin reciben su nombre de Theodore Motzkin y tienen diversas aplicaciones en geometría , combinatoria y teoría de números .

Los números de Motzkin forman la secuencia: ${\displaystyle M_{n}}$ ${\displaystyle n=0,1,\dots }$

1, 1 , 2 , 4 , 9 , 21 , 51 , 127 , 323, 835, ... (secuencia A001006 en la OEIS )

Ejemplos

La siguiente figura muestra las 9 formas de dibujar cuerdas no intersecantes entre 4 puntos de un círculo ( M ₄ = 9 ):

La siguiente figura muestra las 21 formas de dibujar cuerdas no intersecantes entre 5 puntos de un círculo ( M ₅ = 21 ):

Propiedades

Los números de Motzkin satisfacen las relaciones 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}.}$

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

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

y a la inversa, ^[1]

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

Esto da

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

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

${\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 . Se conocen cuatro de estos primos:

2, 127, 15511, 953467954114363 (secuencia A092832 en la OEIS )

Interpretaciones combinatorias

El número de Motzkin para n es también el número de secuencias de números enteros positivos de longitud n − 1 en las que los elementos de apertura y final 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 de números enteros positivos de longitud n + 1 en las que los elementos de apertura y final 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) a la coordenada ( n , 0) en n pasos si a uno se le permite moverse solo hacia la derecha (arriba, abajo o recto) en cada paso, pero se le prohíbe sumergirse por debajo del eje y = 0.

Por ejemplo, la siguiente figura muestra las 9 rutas válidas de Motzkin de (0, 0) a (4, 0):

Existen al menos catorce manifestaciones diferentes de los números de Motzkin en distintas ramas de las matemáticas, como lo enumeraron Donaghey y Shapiro (1977) en su estudio de los números de Motzkin. Guibert, Pergola y Pinzani (2001) demostraron que las involuciones vexilares se enumeran mediante números de Motzkin.

Véase también

• Número de teléfono que representa la cantidad de formas de dibujar cuerdas si se permiten intersecciones
• Número de Delannoy
• Número de Narayana
• Número de Schröder

Referencias

1. Yi Wang y Zhi-Hai Zhang (2015). "Combinatoria de números de Motzkin generalizados" (PDF) . Journal of Integer Sequences (18).

• Bernhart, Frank R. (1999), "Números de Catalan, Motzkin y Riordan", Discrete Mathematics , 204 (1–3): 73–112, doi : 10.1016/S0012-365X(99)00054-0
• Donaghey, R.; Shapiro, LW (1977), "Números de Motzkin", Journal of Combinatorial Theory , Serie A, 23 (3): 291–301, doi : 10.1016/0097-3165(77)90020-6 , MR  0505544
• Guibert, O.; Pergola, E.; Pinzani, R. (2001), "Las involuciones vexilares se enumeran mediante números de Motzkin", Annals of Combinatorics , 5 (2): 153–174, doi :10.1007/PL00001297, ISSN  0218-0006, MR  1904383, S2CID  123053532
• Motzkin, TS (1948), "Relaciones entre proporciones cruzadas de hipersuperficies y una fórmula combinatoria para particiones de un polígono, para preponderancia permanente y para productos no asociativos", Boletín de la Sociedad Matemática Americana , 54 (4): 352–360, doi : 10.1090/S0002-9904-1948-09002-4

Enlaces externos

• Weisstein, Eric W. "Número de Motzkin". MathWorld .