Padovan-Folge

Die Padovan-Folge ist die ganzzahlige Folge $(P_{n})$, die rekursiv definiert ist durch

$P_{0}=P_{1}=P_{2}=1$

und für  n > 2

$P_{n}=P_{n-2}+P_{n-3}$ .

Die Folge beginnt mit den Zahlen

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, …

Die Padovan-Folge trägt (mit weiteren 5 vorgeschalteten Gliedern) die Nummer A000931 in der Folgen-Datenbank OEIS. Die Folge ist nach dem britischen Architekten Richard Padovan benannt, der ihre Entdeckung dem niederländischen Architekten Hans van der Laan zuschreibt. Sie wurde durch Ian Stewart in den Mathematical Recreations der Zeitschrift Scientific American im Juni 1996 beschrieben.

Berechnung der Folgenglieder

Die Padovan-Folge genügt der folgenden Summenformel mit Binomialkoeffizienten:

$P_{n-2}=\sum _{j=\lceil n/3\rceil }^{\lfloor n/2\rfloor }{j \choose n-2j}$

Eine andere Darstellung ist die Linearkombination der n-ten Potenzen der Lösungen von

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

Die reelle Lösung dieser Gleichung ist die Plastische Zahl $\psi$. Mit den konjugiert komplexen Lösungen $q$ und ${\bar {q}}$ gilt für n $\geq$ 0:

$P_{n}={\frac {\psi ^{n+4}}{3\psi ^{2}-1}}+{\frac {q^{n+4}}{3q^{2}-1}}+{\frac {{\bar {q}}^{n+4}}{3{\bar {q}}^{2}-1}}$

Rekursions- und Summenformeln

Die Padovan-Folge lässt sich rekursiv auch beschreiben durch

$P_{n}=P_{n-1}+P_{n-5}$ .

Daraus erhält man weitere Rekursionsformeln durch wiederholtes Ersetzen von $P_{n}$ durch $P_{n-2}+P_{n-3}$ . Die Partialsummen der Padovan-Folge lassen sich einfach berechnen:

$\sum _{n=0}^{m}P_{n}=P_{m+5}-2$

Die Perrin-Folge genügt denselben Rekursionsformeln wie die Padovan-Folge, hat aber andere Startwerte. Die beiden Folgen sind verbunden über die Formel

$\mathrm {Perrin} _{n}=P_{n+1}+P_{n-10}$ .

Erzeugende Funktion

Die erzeugende Funktion der Padovan-Folge ist

$\sum _{n=0}^{\infty }P_{n}x^{n}={\frac {1+x}{1-x^{2}-x^{3}}}$  .

Zusammenhang mit der Plastikzahl

Die Quotienten sukzessiver Folgenglieder konvergieren gegen die Plastische Zahl:

$\psi =\lim _{n\to \infty }{\frac {P_{n}}{P_{n-1}}}\approx 1{,}3247$

Interpretation in der Kombinatorik

$P_{n}$ ist die Anzahl möglicher Zerlegungen von $n+2$ in eine geordnete Summe mit den Summanden $2$ oder $3$. Zum Beispiel ist $P_{6}=4$, also gibt es $4$ Möglichkeiten, $8$ als eine solche Summe zu schreiben:

$2+2+2+2\ \ ;\ \ 2+3+3\ \ ;\ \ 3+2+3\ \ ;\ \ 3+3+2$