Número Motzkin - Motzkin number

Número Motzkin

Nomeado após	Theodore Motzkin
Ano de publicação	1948
Autor da publicação	Theodore Motzkin
Nº de termos conhecidos	infinidade
Fórmula	veja Propriedades
Primeiros termos	1, 1 , 2 , 4 , 9 , 21 , 51
Índice OEIS

Em matemática , o n th número Motzkin é o número de diferentes formas de desenho que não se cruzam cordas entre os n pontos sobre um círculo (não necessariamente tocando cada ponto por um acorde). Os números de Motzkin são nomeados em homenagem a Theodore Motzkin e têm diversas aplicações em geometria , combinatória e teoria dos números .

Os números Motzkin para formar a sequência: ${\displaystyle M_{n}}$${\displaystyle n=0,1,\dots }$

1, 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, ... (sequência A001006 no OEIS )

Exemplos

A figura a seguir mostra as 9 maneiras de desenhar cordas que não se cruzam entre 4 pontos em um círculo ( M ₄ = 9 ):

A figura a seguir mostra as 21 maneiras de desenhar cordas que não se cruzam entre 5 pontos em um círculo ( M ₅ = 21 ):

Propriedades

Os números de Motzkin satisfazem as relações de recorrência

${\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}.}$

Os números de Motzkin podem ser expressos em termos de coeficientes binomiais e números catalães :

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

A série geradora dos números de Motzkin satisfaz ${\displaystyle m(x)=\sum _{n=0}^{\infty }M_{n}x^{n}}$

${\displaystyle x^{2}m(x)^{2}+(x-1)m(x)+1=0}$.

Um primo de Motzkin é um número primo de Motzkin . Em outubro de 2013, quatro desses primos são conhecidos:

2, 127, 15511, 953467954114363 (sequência A092832 no OEIS )

Interpretações combinatórias

O número de Motzkin para n também é o número de sequências inteiras positivas de comprimento n - 1 em que os elementos de abertura e final são 1 ou 2, e a diferença entre quaisquer dois elementos consecutivos é -1, 0 ou 1. Equivalentemente, o O número de Motzkin para n é o número de sequências inteiras positivas de comprimento n + 1 em que os elementos de abertura e final são 1 e a diferença entre quaisquer dois elementos consecutivos é -1, 0 ou 1.

Além disso, o número de Motzkin para n fornece o número de rotas no quadrante superior direito de uma grade da coordenada (0, 0) para a coordenada ( n , 0) em n etapas se for permitido mover apenas para a direita (para cima, para baixo ou em linha reta) em cada etapa, mas proibido de mergulhar abaixo do eixo y = 0.

Por exemplo, a figura a seguir mostra os 9 caminhos válidos do Motzkin de (0, 0) a (4, 0):

Existem pelo menos quatorze manifestações diferentes dos números de Motzkin em diferentes ramos da matemática, conforme enumerado por Donaghey & Shapiro (1977) em seu levantamento dos números de Motzkin. Guibert, Pergola & Pinzani (2001) mostraram que involuç~oes vexillary são enumeradas por números Motzkin.

Veja também

• Número de telefone que representa o número de maneiras de desenhar acordes se os cruzamentos forem permitidos
• Número Delannoy
• Número de Narayana
• Número Schröder

Referências

• 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, LW (1977), "Motzkin numbers", Journal of Combinatorial Theory , Series A, 23 (3): 291–301, doi : 10.1016 / 0097-3165 (77) 90020-6 , MR  0505544
• Guibert, O .; Pergola, E .; Pinzani, R. (2001), "Vexillary involutions are enumerated by Motzkin numbers", Annals of Combinatorics , 5 (2): 153-174, doi : 10.1007 / PL00001297 , ISSN  0218-0006 , MR  1904383
• Motzkin, TS (1948), "Relações entre razões cruzadas de hipersuperfície e uma fórmula combinatória para partições de um polígono, para preponderância permanente e para produtos não associativos", Bulletin of the American Mathematical Society , 54 (4): 352- 360, doi : 10.1090 / S0002-9904-1948-09002-4

links externos

• Weisstein, Eric W. "Motzkin Number" . MathWorld .