Padovan-Folge

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

${\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. 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:

${\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. 1 2 Eric W. Weisstein: Padovan Sequence, In: MathWorld
2. ↑ Richard Padovan presents the plastic number, Nexus Network Journal