Número de Motzkin
# 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 $(M_4=$ 9): | La siguiente figura muestra las 21 formas de dibujar cuerdas que no se corten entre sí entre 5 puntos en una circunferencia $(M_5=$ 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

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.

