Número de Motzkin

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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 para 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[editar | editar código-fonte]

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

MotzkinChords4.svg

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

MotzkinChords5.svg

Propriedades[editar | editar código-fonte]

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

Os números de Motzkin podem ser expressos em termos dos coeficientes binomiais e números de Catalan:

Um primo de Motzkin é um número de Motzkin que é número primo. A outubro de 2013 eram conhecidos quatro destes primos:

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

Interpretações combinatoriais[editar | editar código-fonte]

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):

Motzkin4.svg

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[editar | editar código-fonte]

Referências[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]