Número de Perrin

Em matemática os números de Perrin são definidos pela relação de recorrência

P(n) = P(n − 2) + P(n − 3) para n > 2,

com valores iniciais

P(0) = 3, P(1) = 0, P(2) = 2.

A sequência dos números de Perrin começa com

3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, ... (sequência A001608 na OEIS)

O número de diferentes conjuntos independentes máximos em um n-vértice grafo ciclo é contado pelo n-ésimo número de Perrin para n > 1.^[1]

História

Esta sequência foi mencionada implicitamente por Édouard Lucas (1876). Em 1899 e mesma sequência foi mencionada explicitamente por Raoul Perrin.^[2] O mais extensivo tratamento desta sequência foi dado por Adams e Shanks (1982).

Propriedades

Função geratriz

A função geratriz da sequência de Perrin é

${\displaystyle G(P(n);x)={\frac {3-x^{2}}{1-x^{2}-x^{3}}}.}$

Fórmula matricial

${\displaystyle {\begin{pmatrix}0&1&0\\0&0&1\\1&1&0\end{pmatrix}}^{n}{\begin{pmatrix}3\\0\\2\end{pmatrix}}={\begin{pmatrix}P\left(n\right)\\P\left(n+1\right)\\P\left(n+2\right)\end{pmatrix}}}$

Fórmula tipo Binet

Os números da sequência de Perrin podem ser escritos em termos das potências das raízes da equação

${\displaystyle x^{3}-x-1=0.}$

esta equação tem 3 rraízes; uma raiz real p (conhecida como número plástico) e duas raízes complexas conjugadas q e r. dadas estas três raízes, a sequência de Perrin análoga à fórmula de Binet da sequência de Lucas é

${\displaystyle P\left(n\right)={p^{n}}+{q^{n}}+{r^{n}}.}$

Como as magnitudes das raízes complexas q e r são ambas menores que 1, as potências destas raízes convergem para 0 para n grande, e a fórmula se reduz a

${\displaystyle P\left(n\right)\approx {p^{n}}.}$

esta fórmula pode ser usada para calcular rapidamente valores da sequência de Perrin para n grande. A razão de termos sucessivos na sequência de Perrin se aproxima de p, também conhecido como número plástico, que tem um valor de aproximadamente 1,324718. esta constante tem a mesma relação com a sequência de Perrin como acontece com a proporção áurea em relação à sequência de Lucas. Conexões similares também exestem entre p e a sequência de Padovan, entre a proporção áurea e os números de Fibonacci, e entre a proporção prateada e os números de Pell.

Referências

Bibliografia

• Füredi, Z. (1987). «The number of maximal independent sets in connected graphs». Journal of Graph Theory. 11 (4): 463–470. doi:10.1002/jgt.3190110403 

• Knuth, Donald E. (2011). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. [S.l.]: Addison-Wesley. ISBN 0201038048 

Leitura adicional

• Adams, William; Shanks, Daniel (1982). «Strong primality tests that are not sufficient». American Mathematical Society. Mathematics of Computation. 39 (159): 255–300. JSTOR 2007637. MR 0658231. doi:10.2307/2007637 

• Perrin, R. (1899). «Query 1484». L'Intermédiaire des Mathématiciens. 6. 76 páginas 

• Lucas, E. (1878). «Théorie des fonctions numériques simplement périodiques». The Johns Hopkins University Press. American Journal of Mathematics. 1 (3): 197–240. JSTOR 2369311. doi:10.2307/2369311 

Ligações externas

• Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence
• Perrin Primality Tests