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 é

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

Fórmula matricial

{\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

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 é

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

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.

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

[1] Füredi (1987)

[2] Knuth (2011)

[1]

[2]

v d e Classes de números primos
Por fórmula	Fermat ( $2 2 n + 1$ ) Mersenne ( $2 p - 1$ ) Duplo de Mersenne $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Fatorial ( $n! \pm 1$ ) Euclides ( $p n # + 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Leyland ( $x y + y x$ ) Mills ( $⌊ A 3 n ⌋$ )
Por propriedade	Wall–Sun–Sun Pillai
Dependentes de base	Palíndromo Omirp Circular Estrobogramático
Padrões	Gêmeos ( $p, p + 2$ ) Chen Equilibrado ( $consecutivos p - n, p, p + n$ )
Por dimensão	Maior conhecido
Números compostos	Pseudoprimo Número de Carmichael Quase-primo Semiprimo Número esfênico Interprimo Pernicioso
Tópicos relacionados	Ilegal Intervalo entre primos
Lista de números primos