Padovan-Folge

Die Padovan-Folge ist die ganzzahlige Folge ${\displaystyle (P_{n})}$, die rekursiv definiert ist durch^[1]

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

und für  n > 2

${\displaystyle 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^[2]. 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:

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

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

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

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

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

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

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

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

Erzeugende Funktion

Die erzeugende Funktion der Padovan-Folge ist

${\displaystyle \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:^[1]

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

Interpretation in der Kombinatorik

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

${\displaystyle 2+2+2+2\ \ ;\ \ 2+3+3\ \ ;\ \ 3+2+3\ \ ;\ \ 3+3+2}$

Einzelnachweise

1. Eric W. Weisstein: Padovan Sequence, In: MathWorld
2. Richard Padovan presents the plastic number, Nexus Network Journal