Número de Motzkin

Em matemática, um número de Motzkin para um dado número n é o número de diferentes maneiras de desenhar cordas não-intersectantes entre n pontos sobre uma circunferência. Os números de Motzkin são denominados em memória de Theodore Motzkin, tendo diversas aplicações em geometria, combinatória e teoria dos números.

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

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 na OEIS)

Exemplos

A figura seguinte mostra as 9 maneiras de desenhar cordas não-intersectantes entre 4 pontos sobre uma circunferência.

A figura seguinte mostra as 21 maneiras de desenhar cordas não-intersectantes entre 5 pontos sobre uma circunferência.

Propriedades

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

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 dos coeficientes binomiais e números de Catalan:

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

Um primo de Motzkin é um número de Motzkin que é número primo. Desde outubro de 2013 (2013 -10)^[update] eram conhecidos quatro destes primos:

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

Interpretações combinatoriais

O número de Motzkin para n é também o número de sequências inteiras positivas de comprimento n−1, nas quais os elementos inicial e final são 1 ou 2, e a diferença entre quaisquer dois elementos consecutivos é −1, 0 ou 1.

Também no quadrante direito superior de uma malha, o número de Motzkin para n fornece o número de rotas da coordenada (0, 0) à coordenada (n, 0) sobre n passos se é admitido mover-se somente para a direita (para cima, para baixo ou em linha reta) a cada passo, não sendo possível cruzar o eixo y = 0.

Por exemplo, a figura seguinte ilustra as nove trajetórias Motzkin válidas de (0, 0) a (4, 0):

Existem no mínimo quatorze diferentes manifestações dos números de Motzkin em diferentes ramos da matemática, como enunciado por Donaghey & Shapiro (1977) em suas investigações sobre os números de Motzkin. Guibert, Pergola & Pinzani (2001) mostraram que as permutações vexilárias são enumeradas pelos números de Motzkin.

Ver também

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, L. W. (1977), «Motzkin numbers», Journal of Combinatorial Theory, Series A, 23 (3): 291–301, MR 0505544, doi:10.1016/0097-3165(77)90020-6
Guibert, O.; Pergola, E.; Pinzani, R. (2001), «Vexillary involutions are enumerated by Motzkin numbers», Annals of Combinatorics, ISSN 0218-0006, 5 (2): 153–174, MR 1904383, doi:10.1007/PL00001297
Motzkin, T. S. (1948), «Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products», Bulletin of the American Mathematical Society, 54 (4): 352–360, doi:10.1090/S0002-9904-1948-09002-4

Ligações externas

Weisstein, Eric W. «Motzkin Number». MathWorld (em inglês)