Suite de Padovan

La suite de Padovan est la suite d'entiers $(P n)$ définie par récurrence par^[1] :

P_{0}=P_{1}=P_{2}=1{\text{ et }}\forall n\in \mathbb {N} \quad P_{n+3}=P_{n+1}+P_{n}.

C'est une suite récurrente linéaire qui ressemble dans sa forme à la suite de Fibonacci, à une nuance près : la somme des termes de rang $n$ et $n + 1$ ne donne pas le terme de rang $n + 2$ mais celui de rang $n + 3$ .

Cette suite d'entiers est strictement croissante à partir du rang 4 ;étendue aux termes d'indice négatifs de sorte que la relation de récurrence ci-dessus soit valable $\forall n\in \mathbb {Z}$ , elle prend les valeurs :

$n$	-5	-4	-3	-2	-1	0	1	2	3	4	5	6	7	8	9	10
$P_{n}$	1	0	0	1	0	1	1	1	2	2	3	4	5	7	9	12

Elle correspond, décalée d'un cran, à la suite A134816 de l'OEIS ( $P_{n}=A134816(n+1)$ ) et, décalée de cinq crans, à la suite A000931 de l'OEIS ( $P_{n}=A000931(n+5)$ ).

Elle porte le nom de l'architecte Richard Padovan (en) qui l'a étudiée, et est associée au nombre plastique étudié par l'architecte puis moine Hans van der Laan^[2]. Le mathématicien Ian Stewart, dans l'Univers des nombres, évoque et étudie cette suite et lui attribue le nom de suite de Padovan^[3] ; il remarque que par une coïncidence heureuse, "Padovan" a la même origine que "Padoue", ville peu éloignée de Pise, dont Fibonacci était originaire.

Le terme général de la suite de Padovan est lié aux trois racines du polynôme $X 3 - X - 1$ .

Le quotient de deux termes consécutifs tend vers le nombre plastique.

En fonction des trois racines $r 1$ , $r 2$ et $r 3$ de $X 3 - X - 1$ (une réelle et deux complexes conjuguées) on a la formule de type Binet :

P_{n}={\frac {(1-r_{2})(1-r_{3})}{(r_{1}-r_{2})(r_{1}-r_{3})}}r_{1}^{n}+{\frac {(1-r_{3})(1-r_{1})}{(r_{2}-r_{3})(r_{2}-r_{1})}}r_{2}^{n}+{\frac {(1-r_{1})(1-r_{2})}{(r_{3}-r_{1})(r_{3}-r_{2})}}r_{3}^{n}.

Les formules de Cardan donnent pour la racine réelle le nombre plastique :

r_{1}=\psi ={\sqrt[{3}]{{\frac {1}{2}}+{\frac {\sqrt {69}}{18}}}}+{\sqrt[{3}]{{\frac {1}{2}}-{\frac {\sqrt {69}}{18}}}}\approx 1,32472.

D'après les relations entre coefficients et racines, on a $r_{2}+r_{3}=-\psi ,r_{2}r_{3}=1/\psi$ , donc $r_{2},r_{3}$ , qui sont conjuguées, sont de module ${\frac {1}{\sqrt {\psi }}}<1$ . On obtient :

P_{n}={\frac {\psi ^{5}}{2\psi +3}}\psi ^{n}+\varepsilon _{n}

où

\varepsilon _{n}\rightarrow 0

ainsi que $P_{n}=\left\lfloor {\frac {\psi ^{n+5}}{2\psi +3}}\right\rceil$ où $\left\lfloor x\right\rceil$ est l'entier le plus proche de $x$ .

Propriétés

Comme pour la suite de Fibonacci, la suite de Padovan s'obtient par puissance $n$ -ième de la matrice compagnon du polynôme caractéristique :

{\begin{pmatrix}0&1&0\\0&0&1\\1&1&0\end{pmatrix}}^{n}{\begin{pmatrix}1\\1\\1\end{pmatrix}}={\begin{pmatrix}P_{n}\\P_{n+1}\\P_{n+2}\end{pmatrix}}

La fonction génératrice est donnée par :
$\sum _{n=0}^{\infty }P_{n}\,x^{n}={\frac {1+x}{1-x^{2}-x^{3}}}$

$\sum _{k=0}^{n}P_{k}=P_{n+5}$
Les nombres de Padovan premiers sont 2, 3, 5, 7, 37, 151, etc. (suite A100891 de l'OEIS).

Interprétations combinatoires

$P_{n-2}$ est le nombre de décompositions ordonnées (compositions) de $n$ comme somme de 2 et de 3 ; par exemple, pour $n=8$ on a 2 + 3 + 3 , 3 + 2 + 3 , 3 + 3 + 2 , 2 + 2 + 2 + 2.
On en déduit l'expression à l'aide de coefficients binomiaux ^[4] :
pour $n\geqslant 2$ , $P_{n-2}=\sum _{2i+3j=n}{\binom {i}{i+j}}=\sum _{k=\lfloor n/3\rfloor }^{\lfloor n/2\rfloor }{\binom {k}{n-2k}}$
$P_{n-5}$ est le nombre de décompositions ordonnées de $n$ comme somme de nombres impairs au moins égaux à 3. Par exemple, pour $n$ = 11, on a 11, 5+3+3, 3+5+3 et 3+3+5 ^[4].
$P_{n-4}$ est le nombre de décompositions ordonnées de $n$ comme somme d’entiers naturels congrus à 2 modulo 3. Par exemple, pour $n$ = 10, on a 2 + 8, 8 + 2, 5 + 5 et 2+2+2+2+2^[4].
$P_{n+1}$ est le nombre de dispositions maximales de $n$ personnes assises en ligne de sorte que deux personnes ne soient jamais côte à côte. 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 (pour le cas où les personnes sont placées en rond, il s'agit de la suite de Perrin)^[4].
$P_{n+3}$ est le nombre de mots de $n$ lettres A ou B tels qu’il n’y a jamais deux A voisins et jamais plus de deux B voisins. Par exemple, pour $n$ = 3, ABA, ABB, BAB et BBA^[4].

Propriétés

Interprétations combinatoires

Variantes

Notes et références

Related Articles