Padovan rækkefølge

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 10. august 2019; verifikation kræver 1 redigering .

Padovan-sekvensen er en heltalssekvens P ( n ) med begyndelsesværdier

P(0)=P(1)=P(2)=1

og den lineære gentagelsesrelation

P(n)=P(n-2)+P(n-3).

De første værdier af P ( n ) er

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, … ( OEIS -sekvens A000931 )

Padovan-sekvensen er opkaldt efter Richard Padovan , som i sit essay Dom. Hans van der Laan: Modern Primitive fra 1994 tilskrev sin opdagelse til den hollandske arkitekt Hans van der Laan [1] . Sekvensen blev almindeligt kendt, efter at Ian Stuart beskrev den i kolonnen Mathematical Recreations i Scientific American i juni 1996 .

Tilbagevendende relationer

Padovan-sekvensen adlyder følgende rekursive relationer:

P(n)=P(n-1)+P(n-5)

P(n)=P(n-2)+P(n-4)+P(n-8)

P(n)=2P(n-2)-P(n-7)

P(n)=P(n-3)+P(n-4)+P(n-5)

P(n)=P(n-3)+P(n-5)+P(n-7)+P(n-8)+P(n-9)

P(n)=P(n-4)+P(n-5)+P(n-6)+P(n-7)+P(n-8)

P(n)=4P(n-5)+P(n-14).

Perrin-sekvensen opfylder de samme relationer, men har forskellige begyndelsesværdier. Padovan- og Perrin-sekvenserne er også relateret til:

\mathrm {Perrin} (n)=P(n+1)+P(n-10).

Udvidelse til området med negative tal

Padovan-sekvensen kan udvides til regionen med negative tal ved hjælp af gentagelsesrelationen

P(-n)=P(-n+3)-P(-n+1).

(dette svarer til at udvide Fibonacci-sekvensen til regionen med negative indekser af sekvensen). En sådan udvidelse af P ( n ) giver værdierne

…, −7, 4, 0, −3, 4, −3, 1, 1, −2, 2, −1, 0, 1, −1, 1, 0, 0, 1, 0, 1, 1, en, …

Medlemsbeløb

Summen af de første n led i sekvensen er 2 mindre end P ( n + 5), dvs.

\sum _{{m=0}}^{n}P(m)=P(n+5)-2.

Summen af lige/ulige led, hver tredje og summen af hver femte led er også udtrykt med visse formler:

\sum _{{m=0}}^{n}P(2m)=P(2n+3)-1

\sum _{{m=0}}^{n}P(2m+1)=P(2n+4)-1

\sum _{{m=0}}^{n}P(3m)=P(3n+2)

\sum _{{m=0}}^{n}P(3m+1)=P(3n+3)-1

\sum _{{m=0}}^{n}P(3m+2)=P(3n+4)-1

\sum _{{m=0}}^{n}P(5m)=P(5n+1).

Beløbene, inklusive produkterne af vilkårene, opfylder følgende forhold:

\sum _{{m=0}}^{n}P(m)^{2}=P(n+2)^{2}-P(n-1)^{2}-P(n-3 )^{2}

\sum _{{m=0}}^{n}P(m)^{2}P(m+1)=P(n)P(n+1)P(n+2)

\sum _{{m=0}}^{n}P(m)P(m+2)=P(n+2)P(n+3)-1.

Andre forhold

Padovan-sekvensen tilfredsstiller også afhængigheden

P(n)^{2}-P(n+1)P(n-1)=P(-n-7).

Det kan også udtrykkes i form af binomiale koefficienter :

\sum _{2m+n=k}{m \choose n}=P(k-2).

For eksempel, for k = 12, er værdierne af parret ( m ; n ), for hvilke 2 m + n = 12 giver ikke-nul binomiale koefficienter (6; 0), (5; 2) og (4; 4), og:

{6 \choose 0}+{5 \choose 2}+{4 \choose 4}=1+10+1=12=P(10).

Generel udtryksformel

Vilkårene for Padovan-sekvensen kan udtrykkes i form af styrkerne af ligningens rødder

x^{3}-x-1=0.

Denne ligning har tre rødder: en reel rod - det plastiske tal p ≈ 1,324718 og to komplekse konjugerede rødder q og r . Med deres hjælp kan du skrive en analog af Binets formel for det generelle udtryk for Padovan-sekvensen:

P\left(n\right)={\frac {p^{n}}{\left(3p^{2}-1\right)))+{\frac {q^{n}}{\left( 3q^{2}-1\højre)))+{\frac {r^{n}}{\venstre(3r^{2}-1\højre))).

Da den absolutte værdi af begge komplekse rødder q og r er mindre end 1, så har deres n'te potens en tendens til 0, når n vokser . Således er den asymptotiske formel gyldig:

P\left(n\right)\ca. {\frac {p^{n}}{\left(3p^{2}-1\right)))={\frac {p^{n}}{s} }\approx {\frac {p^{n}}{4.264632\ldots }},

hvor s er den reelle rod af ligningen . Denne formel kan bruges til hurtige beregninger for store n . $s^{3}-3s^{2}-23=0$ $P(n)$

Forholdet mellem naboled i Padova-sekvensen har en tendens til det plastiske tal p . Denne konstant spiller den samme rolle for Padovan- og Perrin-sekvenserne, som det gyldne snit gør for Fibonacci-sekvensen.

Kombinatoriske fortolkninger

P ( n ) er antallet af måder at skrive n + 2 på som summen af 2 og 3, givet rækkefølgen. For eksempel P (6) = 4, da der er 4 måder at skrive 8 som summen af toere og treere med forskellig rækkefølge af medlemmer:

2+2+2+2; 2 + 3 + 3; 3 + 2 + 3; 3+3+2

P (2 n - 2) er antallet af måder at skrive n på som en ordrefølsom sum, hvor ingen led er lig med 2. For eksempel P (6) = 4, da der er 4 måder at skrive 4 på som denne :

fire; 1+3; 3+1; 1+1+1+1

P ( n ) er antallet af måder at skrive n på som en ordensfølsom palindromsum, hvor ingen led er lig med 2. For eksempel er P (6) = 4, da der er 4 måder at skrive 6 på på ovenstående måde :

6; 3 + 3; 1+4+1; 1+1+1+1+1+1

P ( n − 4) er antallet af måder at skrive n på som en sum, givet den rækkefølge, hvor hver er kongruent med 2 modulo 3. For eksempel P (6) = 4, da der er 4 måder at skrive nummer 10 på denne måde:

8+2; 2+8; 5 + 5; 2+2+2+2+2

Genererer funktion

Genereringsfunktionen for Padovan-sekvensen er:

G(P(n);x)={\frac {1+x}{1-x^{2}-x^{3}}}.

Dette kan bruges til at bevise forhold, der involverer produkterne af Padovan-sekvensen og geometriske progressioner som denne:

\sum _{{m=0}}^{{\infty }}{\frac {P(n)}{2^{n}}}={\frac {12}{5}}.

Simple Padovana

Et Padovan-primtal er P ( n ), som er et primtal . De første par simple Padovaner er:

2, 3, 5, 7, 37, 151, 3329, 23833, … (sekvens A100891 i OEIS )

Generaliseringer

Padovan-polynomier

Ligesom Fibonacci-tallene , der generaliseres af et sæt polynomier ( Fibonacci-polynomier ), kan Padova-sekvensen også generaliseres af Padova-polynomier .

Padovans L-system

Hvis vi definerer denne simple grammatik:

variabler : ABC konstanter : ingen start : A regler : (A → B), (B → C), (C → AB)

så giver et sådant Lindenmeyer-system ( L-system ) følgende rækkefølge af linjer:

n = 0 : A n = 1: B n = 2: C n = 3: AB n = 4: f.Kr n = 5: CAB n = 6: ABBC n = 7: BCCAB n = 8: CABABBC

og hvis vi tæller længden af hver af dem, får vi Padovan-sekvensen:

1 1 1 2 2 3 4 5 7 …

Hvis vi tæller antallet af tegn A , B og C i hver linje, så vil der for den n'te linje være P ( n − 5) tegn A , P ( n − 3) tegn B og P ( n − 4) tegn C. _ Antallet af par BB , AA og CC er også Padovan-tal.

Padovans kubiske spiral

Padovan cuboid spiral kan bygges ved at samle hjørnerne af mange 3D cuboids. Længderne af på hinanden følgende sider af spiralen er vilkårene for Padovan-sekvensen ganget med kvadratroden af 2.

Noter

↑ Richard Padovan. Dom Hans van der Laan: moderne primitiv : Architectura & Natura Press, ISBN 9789071570407 .