Suite de Perrin

En mathématiques, la suite de Perrin est une variante de la suite de Padovan, de même relation de récurrence. Cette suite d'entiers est définie par récurrence linéaire par :

$P_{0}=3,P_{1}=0,P_{2}=2$ et pour tout $n\geqslant 3,P_{n}=P_{n-2}+P_{n-3}$.

Les 20 premiers termes en sont :

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
$P_{n}$	3	0	2	3	2	5	5	7	10	12	17	22	29	39	51	68	90	119	158	209

Elle forme la suite A001608 de l'OEIS.

Construction de la suite de Perrin à l'aide de triangles équilatéraux, utilisant la relation $P_{n}=P_{n-1}+P_{n-5}$. Le nombre dans chaque triangle désigne la longueur de ses côtés.

Construction géométrique

La suite de Perrin vérifie aussi la relation de récurrence d'ordre 5 : $P_{n}=P_{n-1}+P_{n-5}$, pour $n\geqslant 5$. Cette propriété est à la base de la construction en spirale ci-contre, débutant avec un triangle équilatéral de côté $P_{2}=2$, un triangle équilatéral de côté $P_{3}=3$ tronqué d'un triangle de côté 1, puis un triangle équilatéral de côté $P_{4}=2$ (comparer avec la construction en triangles de la suite de Padovan).

Formule de type Binet

L'équation caractéristique de la récurrence s'écrit $x^{3}-x-1=0$ ; les solutions en sont le nombre plastique $\psi ={\sqrt[{3}]{{\frac {1}{2}}+{\frac {\sqrt {69}}{18}}}}+{\sqrt[{3}]{{\frac {1}{2}}-{\frac {\sqrt {69}}{18}}}}\approx 1,325$ et deux nombres complexes conjugués $r,{\overline {r}}$.

L'expression de $P_{n}$ en fonction des trois suites de base $(\psi ^{n}),(r^{n}),({\overline {r}}^{n})$ s'écrit simplement sous la forme

$P_{n}=\psi ^{n}+r^{n}+{\overline {r}}^{n}$.

Des relations $r+{\overline {r}}=-\psi ,r{\overline {r}}=1/\psi$, on tire $r={\frac {\mathrm {e} ^{\mathrm {i} \theta }}{\sqrt {\psi }}}$ où $\theta =\arccos(-{\sqrt {\psi ^{3}}}/2)$, d'où la formule

$P_{n}=\psi ^{n}+{\frac {2\cos n\theta }{\sqrt {\psi ^{n}}}}$

Comme $\psi >1$, on en déduit que $P_{n}\sim \psi ^{n}$ et $\lim {\frac {P_{n+1}}{P_{n}}}=\psi$,

ainsi que $P_{n}=\left\lfloor \psi ^{n}\right\rceil$ où $\left\lfloor x\right\rceil$ est l'entier le plus proche de $x$, à partir de $n=10$.

Propriétés

• Relation avec la suite de Padovan, notée ici $(P'_{n})$ : $P_{n}=3P'_{n-5}+2P'_{n-4}$.
• Comme pour la suite de Fibonacci, la suite de Perrin s'obtient par puissance $n$-ième de la matrice compagnon du polynôme caractéristique :

${\begin{bmatrix}0&1&0\\0&0&1\\1&1&0\end{bmatrix}}^{n}{\begin{bmatrix}3\\0\\2\end{bmatrix}}={\begin{bmatrix}P_{n}\\P_{n+1}\\P_{n+2}\end{bmatrix}}$

et

$P_{n}=\psi ^{n}+r^{n}+{\overline {r}}^{n}=\operatorname {Trace} \left({\begin{bmatrix}0&1&0\\0&0&1\\1&1&0\end{bmatrix}}^{n}\right)$.

• Fonction génératrice :
  $\sum _{n=0}^{\infty }P_{n}\,x^{n}={\frac {3-x^{2}}{1-x^{2}-x^{3}}}$

• Expression à l'aide de coefficients binomiaux pour $n\geqslant 1$ :
  $P_{n}=n\times \sum _{k=\lfloor (n+2)/3\rfloor }^{\lfloor n/2\rfloor }{\frac {\binom {k}{n-2k}}{k}}$

Texte de Perrin dans l'intermédiaire des mathématiciens.

Utilisation comme test de primalité

Dans une question posée en 1899 dans l'intermédiaire des mathématiciens, François Olivier Raoul Perrin fait référence à une question antérieure demandant si le fait que $2^{n}-2$ soit divisible par $n$ soit un "criterium" pour que $n$ soit premier (hypothèse chinoise populaire au XIX^e siècle). On sait aujourd'hui que le nombre $341=11\times 31$ ne passe pas ce test connu aujourd'hui comme "test de primalité de Fermat".

La suite $u_{n}=2^{n}-2$ étant définie par récurrence par $u_{0}=-1,u_{1}=0,u_{n}=3u_{n-1}-2u_{n-2}$, Perrin dit avoir trouvé une autre suite récurrente jouissant de la même propriété, suite portant maintenant son nom. Et en effet :

Si n est un nombre premier alors $P_{n}$ est divisible par n.

Perrin dit avoir vérifié la réciproque de cette propriété pour de grandes valeurs de n. De fait, le premier contre-exemple n'a été trouvé qu'en 1982 par Adams et Shanks : il s'agit de $n$ = 271 441 : ce nombre divise $P_{271\,441}$ mais 271 441 = 521². Le nombre $P_{271441}$ a 33 150 chiffres.

Le nombre 271 441 est le plus petit des nombres pseudo-premiers de Perrin, formant la suite  A013998 de l'OEIS. Il a été prouvé en 2010 qu'il y en a une infinité.

Les nombres de la suite de Perrin qui sont premiers forment la suite A074788 de l'OEIS, et leurs indices la suite  A112881.

Démonstration du théorème de divisibilité

Les congruences s'entendant modulo un nombre premier $p$, la propriété $P_{p}\equiv 0$ est une conséquence de la propriété :$\operatorname {Trace} (A^{p})\equiv \operatorname {Trace} (A)=0$ valable pour toute matrice à coefficients entiers, utilisée ici avec la matrice $A={\begin{bmatrix}0&1&0\\0&0&1\\1&1&0\end{bmatrix}}$.

Une autre démonstration, similaire à celle du petit théorème de Fermat consistant à écrire  : $a^{p}=(1+1+\cdots +1)^{p}\equiv 1+1+\cdots +1=a$, car, d'après le théorème de Lucas, ${\binom {p}{k}}\equiv 0$ pour $1\leqslant k\leqslant p-1$, est la suivante.

On va démontrer que $P_{p}=\psi ^{p}+r^{p}+{\overline {r}}^{p}\equiv (\psi +r+{\overline {r}})^{p}$, ce qui prouvera $P_{p}\equiv 0$, car $\psi +r+{\overline {r}}=0$.

D'après la formule du trinôme, $(\psi +r+{\overline {r}})^{p}=\sum _{i+j+k=p}{\binom {p}{i,j,k}}\psi ^{i}r^{j}{\overline {r}}^{k}$, et l'on a ${\binom {p}{i,j,k}}={\frac {p!}{i!j!k!}}\equiv 0$ pour $i,j,k\leqslant p-1$.

Les nombres $\psi ,r,{\overline {r}}$ n'étant pas entiers, on va utiliser les relations coefficients racines :

${\begin{alignedat}{3}\sigma _{1}&=\psi +r+\gamma &&=0\\\sigma _{2}&=\psi r+r{\overline {r}}+{\overline {r}}\psi &&=-1\\\sigma _{3}&=\psi r{\overline {r}}&&=1.\end{alignedat}}$

On peut alors écrire :

$(\psi +r+{\overline {r}})^{n}-(\psi ^{n}+r^{n}+{\overline {r}}^{n})=\sum _{i\leqslant j\leqslant k\leqslant p-1 \atop i+j+k=p}{\binom {p}{i,j,k}}\sum _{\pi (i,j,k)}\psi ^{i}r^{j}{\overline {r}}^{k}.$

La dernière somme s'entendant pour toutes les permutations de $(i,j,k)$, elle est symétrique et s'exprime comme fonction polynomiale avec des coefficients entiers de $\sigma _{1},\sigma _{2},\sigma _{3}$ et est donc égale à un nombre entier. Le résultat attendu s'en déduit.

Interprétation combinatoire : disposition de convives avec distanciation physique

Description

Inspiré par la distanciation physique imposée par l'épidémie de covid, Vincent Vatter s'est posé la question du nombre de façons de placer des convives autour d'une table comportant n chaises de sorte que deux convives aient au moins une chaise libre entre eux et qu'on ne puisse plus ajouter de convive sans violer cette condition (donc pas plus de deux chaises libres entre deux convives). Par exemple, pour $n=6$, il y a cinq solutions, trois avec deux convives séparés par deux chaises et deux avec trois convives séparés par une chaise.

Il a montré que le nombre de solutions pour $n\geqslant 2$ est égal au nombre de Perrin $P_{n}$.

Démonstration

Considérons un convive d'une disposition à $n$ chaises. Soit ce convive a une seule chaise libre à sa droite et le nombre de dispositions valables est le nombre de dispositions à $n-2$ chaises (enlever mentalement la chaise du convive et la chaise libre), soit il a 2 chaises libres à sa droite et le nombre de dispositions valables est le nombre de dispositions à $n-3$ chaises. Les initialisations étant identiques, on obtient le résultat.

Application

Cette interprétation combinatoire permet de retrouver la propriété de divisibilité ci-dessus (démonstration similaire à celle du petit théorème de Fermat par double dénombrement).

Démonstration

Supposons en effet qu'une rotation d'angle $2k\pi /p$ donne la même disposition qu'une disposition donnée à $p$ chaises (avec $0<k<p$ et $p$ premier). Alors, d'après le théorème de Bézout, il existe deux entiers >0 $u,v$ tels que $ku-pv=1$, donc $u\times 2k\pi /p=2\pi /p+2v\pi$. La rotation d'angle $2\pi /p$ donne donc la même disposition que celle de départ, ce qui fait que deux convives sont côte à côte, ce qui est absurde.

Dès qu'une disposition conforme à $p$ chaises existe, les $p$ rotations d'angle $2\pi /p$ successives de cette disposition sont bien distinctes, donc $P_{p}$ est multiple de $p$.

Autres dispositions "covidiennes"

Le nombre de dispositions maximales de convives vérifiant la propriété de distanciation à rotation de la table (supposée circulaire) près, forme la suite $(P''_{n})_{n\geqslant 1}$ définie par $nP''_{n}=\sum _{d|n}\varphi (n/d)P_{d}$, où $\varphi$ est l'indicatrice d'Euler. Par exemple, pour six convives les cinq dispositions vues ci-dessus, ne sont plus que deux à rotation près. Les dix premiers termes de la suite sont : 0, 1, 1, 1, 1, 2, 1, 2, 2, 3 ; suite A127687 de l'OEIS.

Le nombre de dispositions maximales vérifiant la propriété de distanciation où les personnes sont cette fois disposées en ligne est égal à $P'_{n+1}$ où $(P'_{n})$ est la suite de Padovan. Par exemple, pour $n=5$, il y a 01010, 10010, 01001 et 10101 en notant 0 pour une place vide et 1 pour une place occupée.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Perrin number » (voir la liste des auteurs).

Voir aussi

• Suite de Padovan
• Suite de Lucas, qui est à la suite de Fibonacci, ce qu'est la suite de Perrin à la suite de Padovan.
• Suite de Narayana, associée à une suite vérifiant la même propriété de divisibilité que la suite de Perrin.

Bibliographie

• (en) Zoltán Füredi (de), « The number of maximal independent sets in connected graphs », Journal of Graph Theory, vol. 11, n^o 4,‎ 1987, p. 463-470 (DOI 10.1002/jgt.3190110403)
• (en) Donald E. Knuth, The Art of Computer Programming, vol. 4A : Combinatorial Algorithms, Part 1, Addison-Wesley, 2011 (ISBN 978-0-201-03804-0 et 0-201-03804-8)
• Édouard Lucas, « Théorie des fonctions numériques simplement périodiques », Amer. J. Math., vol. 1, n^o 3,‎ 1878, p. 197-240 (DOI 10.2307/2369311, JSTOR 2369311, lire en ligne)

Liens externes

• Lionel Fourquaux, « Construction de nombres pseudo-premiers de Perrin », sur normalesup.org, août 2015
• (en) Eric W. Weisstein, « Perrin Sequence », sur MathWorld
• (en) Eric W. Weisstein, « Perrin Pseudoprime », sur MathWorld
• (es) Suite et fichiers avec suite (en espagnol)