Padovan-Folge
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]- ↑ a b Eric W. Weisstein: Padovan Sequence, In: MathWorld
- ↑ Richard Padovan presents the plastic number, Nexus Network Journal