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 :

Davantage d’informations

...

$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

Fermer

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.

Formule de type Binet

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].

Variantes

On trouve parfois des initialisations différentes comme dans les suites A133034, A078027, A182097 (simples décalages de la suite de Padovan), A096231, A164001, A228361, A020720 et A001608 de l'OEIS.

Cette dernière est la suite de Perrin : 3, 0, 2, 3, 2, 5, etc.

Formule de type Binet

Propriétés

Interprétations combinatoires

Variantes

Notes et références

Related Articles