Padovan-Folge

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Die Padovan-Folge ist die ganzzahlige Folge , die rekursiv definiert ist durch[1]

und für  n > 2

 .

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

[Bearbeiten | Quelltext bearbeiten]

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

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

 .

Die reelle Lösung dieser Gleichung ist die Plastische Zahl . Mit den konjugiert komplexen Lösungen und gilt für n 0:

Rekursions- und Summenformeln

[Bearbeiten | Quelltext bearbeiten]

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

 .

Daraus erhält man weitere Rekursionsformeln durch wiederholtes Ersetzen von durch  . Die Partialsummen der Padovan-Folge lassen sich einfach berechnen:

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

 .

Erzeugende Funktion

[Bearbeiten | Quelltext bearbeiten]

Die erzeugende Funktion der Padovan-Folge ist

  .

Zusammenhang mit der Plastikzahl

[Bearbeiten | Quelltext bearbeiten]

Die Quotienten sukzessiver Folgenglieder konvergieren gegen die Plastische Zahl:[1]

Interpretation in der Kombinatorik

[Bearbeiten | Quelltext bearbeiten]

ist die Anzahl möglicher Zerlegungen von in eine geordnete Summe mit den Summanden oder . Zum Beispiel ist , also gibt es Möglichkeiten, als eine solche Summe zu schreiben:

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. a b Eric W. Weisstein: Padovan Sequence, In: MathWorld
  2. Richard Padovan presents the plastic number, Nexus Network Journal