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 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, ... Predefinição: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
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. Predefinição:Desde eram conhecidos quatro destes primos:
- 2, 127, 15511, 953467954114363 Predefinição: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 Predefinição:Harvtxt em suas investigações sobre os números de Motzkin. Predefinição:Harvtxt mostraram que as permutações vexilárias são enumeradas pelos números de Motzkin.