Padovan-Folge

Die Padovan-Folge ist die ganzzahlige Folge <math>(P_n)</math>, die rekursiv definiert ist durch<ref name="MathWorld">Eric W. Weisstein: Padovan Sequence, In: MathWorld</ref>

<math>P_0=P_1=P_2=1</math>

und für  n > 2

<math>P_n=P_{n-2}+P_{n-3}</math> .

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<ref>Richard Padovan presents the plastic number, </ref>. 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:

<math>P_{n-2}=\sum_{j=\lceil n/3\rceil}^{\lfloor n/2\rfloor}{j \choose n-2j}</math>

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

<math>x^3 -x -1 = 0</math> .

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

<math>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}</math>

Rekursions- und Summenformeln

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

<math>P_n=P_{n-1}+P_{n-5}</math> .

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

<math>\sum_{n=0}^m P_n=P_{m+5}-2</math>

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

<math>\mathrm{Perrin}_n=P_{n+1}+P_{n-10}</math> .

Erzeugende Funktion

Die erzeugende Funktion der Padovan-Folge ist

<math>\sum_{n=0}^\infty P_n x^n = \frac{1+x}{1-x^2-x^3}</math>  .

Zusammenhang mit der Plastikzahl

Die Quotienten sukzessiver Folgenglieder konvergieren gegen die Plastische Zahl:<ref name="MathWorld" />

<math>\psi = \lim_{n \to \infty}\frac{P_n}{P_{n-1}} \approx 1{,}3247</math>

Interpretation in der Kombinatorik

<math>P_n</math> ist die Anzahl möglicher Zerlegungen von <math>n+2</math> in eine geordnete Summe mit den Summanden <math>2</math> oder <math>3</math>. Zum Beispiel ist <math>P_6=4</math>, also gibt es <math>4</math> Möglichkeiten, <math>8</math> als eine solche Summe zu schreiben:

<math>2 + 2 + 2 + 2\ \ ; \ \ 2 + 3 + 3\ \ ; \ \ 3 + 2 + 3\ \ ; \ \ 3 + 3 + 2</math>

Einzelnachweise

<references/>