En matemáticas , el n- ésimo número de Motzkin es el número de formas diferentes de dibujar acordes que no se cruzan entre n puntos en un círculo (no necesariamente tocando cada punto por un acorde). Los números de Motzkin llevan el nombre de Theodore Motzkin y tienen diversas aplicaciones en geometría , combinatoria y teoría de números .
Lleva el nombre de | Theodore Motzkin |
---|---|
Año de publicación | 1948 |
Autor de la publicación | Theodore Motzkin |
No. de términos conocidos | infinito |
Fórmula | ver propiedades |
Primeros términos | 1, 1 , 2 , 4 , 9 , 21 , 51 |
Índice OEIS |
|
Los números de Motzkin por forman la secuencia:
Ejemplos de
La siguiente figura muestra las 9 formas de dibujar cuerdas que no se cruzan entre 4 puntos en un círculo ( M 4 = 9 ):
La siguiente figura muestra las 21 formas de dibujar cuerdas que no se cruzan entre 5 puntos en un círculo ( M 5 = 21 ):
Propiedades
Los números de Motzkin satisfacen las relaciones de recurrencia
Los números de Motzkin se pueden expresar en términos de coeficientes binomiales y números catalanes :
La serie generadora de los números de Motzkin satisface
- .
Un primo de Motzkin es un número de Motzkin que es primo . A octubre de 2013[actualizar], se conocen cuatro de estos primos:
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 inicial y final son 1 o 2, y la diferencia entre dos elementos consecutivos cualesquiera es -1, 0 o 1. De manera equivalente, la El número de Motzkin para n es el número de secuencias enteras positivas de longitud n + 1 en las que los elementos inicial 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 uno puede moverse solo hacia la derecha (arriba, hacia abajo o hacia abajo) en cada paso, pero no se puede sumergir por debajo del eje y = 0.
Por ejemplo, la siguiente figura muestra las 9 rutas Motzkin válidas desde (0, 0) a (4, 0):
Hay al menos catorce manifestaciones diferentes de los números de Motzkin en diferentes ramas de las matemáticas, como lo enumeran Donaghey y Shapiro (1977) en su estudio de los números de Motzkin. Guibert, Pergola y Pinzani (2001) mostraron que las involuciones vexilares se enumeran mediante números de Motzkin.
Ver también
Referencias
- Bernhart, Frank R. (1999), "Números en catalán, Motzkin y Riordan", Matemáticas discretas , 204 (1-3): 73-112, doi : 10.1016 / S0012-365X (99) 00054-0
- Donaghey, R .; Shapiro, LW (1977), "Motzkin numbers", Journal of Combinatorial Theory , Serie A, 23 (3): 291–301, doi : 10.1016 / 0097-3165 (77) 90020-6 , MR 0505544
- Guibert, O .; Pérgola, 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
- Motzkin, TS (1948), "Relaciones entre las proporciones cruzadas de hipersuperficie y una fórmula combinatoria para particiones de un polígono, para preponderancia permanente y para productos no asociativos", Boletín de la American Mathematical Society , 54 (4): 352– 360, doi : 10.1090 / S0002-9904-1948-09002-4
enlaces externos
- Weisstein, Eric W. "Número de Motzkin" . MathWorld .