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 (Plantilla: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 (Plantilla: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 (Plantilla:Math):	La siguiente figura muestra las 21 formas de dibujar cuerdas que no se corten entre sí entre 5 puntos en una circunferencia (Plantilla:Math):

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 }(\genfrac{}{}{0ex}{}{n}{2k})C_k,$

e inversamente,

$C_{n+1}=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})M_k.$

La función generadora $m(x)=\sum _{n=0}^{\mathrm{\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 }\underset{0}{\overset{\pi }{\int }}\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 \mathrm{\infty }$.

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

2, 127, 15511, 953467954114363 Plantilla:OEIS

Interpretaciones combinatorias

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

El número de Motzkin para Plantilla:Mvar es también el número de secuencias enteras positivas de longitud Plantilla:Math 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 Plantilla:Mvar es el número de secuencias enteras positivas de longitud Plantilla:Math 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 Plantilla:Mvar da el número de rutas en el cuadrante superior derecho de una cuadrícula desde la coordenada (0, 0) hasta la coordenada (Plantilla:Mvar, 0) en Plantilla:Mvar 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 Plantilla:Mvar = 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 Plantilla:Harvtxt en su estudio de los números de Motzkin.

Así mismo,Plantilla:Harvtxt 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

• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation

Enlaces externos

• Plantilla:MathWorld