Padovan sekvens

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 augusti 2019; verifiering kräver 1 redigering .

Padovan-sekvensen är en heltalssekvens P ( n ) med initiala värden

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

och den linjära återfallsrelationen

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

De första värdena av P ( n ) är

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 är uppkallad efter Richard Padovan , som i sin uppsats Dom. Hans van der Laan: Modern Primitive från 1994 tillskrev sin upptäckt till den holländska arkitekten Hans van der Laan [1] . Sekvensen blev allmänt känd efter att Ian Stuart beskrev den i spalten Mathematical Recreations i Scientific American i juni 1996 .

Återkommande relationer

Padovan-sekvensen följer följande rekursiva 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 uppfyller samma relationer men har olika initiala värden. Sekvenserna Padovan och Perrin är också relaterade till:

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

Utvidgning till området med negativa tal

Padovan-sekvensen kan utökas till regionen med negativa tal med hjälp av återfallsrelationen

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

(detta liknar att utöka Fibonacci-sekvensen till regionen med negativa index för sekvensen). En sådan expansion av P ( n ) ger värdena

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

Medlemssummor

Summan av de första n termerna i sekvensen är 2 mindre än P ( n + 5), dvs.

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

Summorna av jämna/udda termer, var tredje och summan av var femte term uttrycks också med vissa formler:

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

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

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

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

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

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

Summorna, inklusive produkterna från villkoren, uppfyller följande relationer:

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

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

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

Andra förhållanden

Padovan-sekvensen tillfredsställer också beroendet

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

Det kan också uttryckas i termer av binomialkoefficienter :

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

Till exempel, för k = 12, är värdena för paret ( m ; n ) för vilka 2 m + n = 12 ger binomialkoefficienter som inte är noll (6; 0), (5; 2) och (4; 4), och:

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

Formel för allmän term

Termerna för Padovan-sekvensen kan uttryckas i termer av krafterna i ekvationens rötter

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

Denna ekvation har tre rötter: en reell rot - det plastiska talet p ≈ 1,324718 och två komplexa konjugerade rötter q och r . Med deras hjälp kan du skriva en analog av Binets formel för den allmänna termen för Padovan-sekvensen:

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

Eftersom det absoluta värdet av båda komplexa rötter q och r är mindre än 1, tenderar deras n:te potens till 0 när n växer . Således är den asymptotiska formeln giltig:

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

där s är den verkliga roten av ekvationen . Denna formel kan användas för snabba beräkningar för stora n . $s^{3}-3s^{2}-23=0$ $P(n)$

Förhållandet mellan närliggande termer i Padova-sekvensen tenderar till plasttalet p . Denna konstant spelar samma roll för Padovan- och Perrin-sekvenserna som det gyllene snittet gör för Fibonacci-sekvensen.

Kombinatoriska tolkningar

P ( n ) är antalet sätt att skriva n + 2 som summan av 2 och 3, givet ordningen. Till exempel, P (6) = 4, eftersom det finns 4 sätt att skriva 8 som summan av tvåor och treor med olika ordningsföljd:

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

P (2 n - 2) är antalet sätt att skriva n som en ordningskänslig summa där ingen term är lika med 2. Till exempel P (6) = 4, eftersom det finns 4 sätt att skriva 4 så här :

fyra; 1+3; 3+1; 1+1+1+1

P ( n ) är antalet sätt att skriva n som en ordningskänslig palindromsumma där ingen term är lika med 2. Till exempel P (6) = 4, eftersom det finns 4 sätt att skriva 6 på ovanstående sätt :

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

P ( n − 4) är antalet sätt att skriva n som en summa, givet ordningen, där var och en är kongruent med 2 modulo 3. Till exempel, P (6) = 4, eftersom det finns 4 sätt att skriva nummer 10 på detta sätt:

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

Genererande funktion

Genereringsfunktionen för Padovan-sekvensen är:

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

Detta kan användas för att bevisa samband som involverar produkterna från Padovan-sekvensen och geometriska progressioner som denna:

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

Enkel Padovana

Ett Padovan primtal är P ( n ), vilket är ett primtal . De första enkla Padovana är:

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

Generaliseringar

Padova polynom

Liksom Fibonacci-talen , som generaliseras av en uppsättning polynom ( Fibonacci-polynom ), kan Padova-sekvensen också generaliseras av Padovan-polynom .

Padovans L-system

Om vi definierar denna enkla grammatik:

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

då ger ett sådant Lindenmeyer-system ( L-system ) följande radföljd:

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

och om vi räknar längden på var och en av dem får vi Padovan-sekvensen:

1 1 1 2 2 3 4 5 7 …

Dessutom, om vi räknar antalet tecken A , B och C i varje rad, kommer det för den n :e raden att finnas P ( n − 5) tecken A , P ( n − 3) tecken B och P ( n − 4) tecken C . Antalet par BB , AA och CC är också Padovantal.

Padovans kubiska spiral

Padovan kuboid spiral kan byggas genom att sammanfoga hörnen på många 3D cuboids. Längden på på varandra följande sidor av spiralen är termerna för Padova-sekvensen multiplicerat med kvadratroten ur 2.

Anteckningar

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

Länkar

Weisstein, Eric W. Padovan Sequence (engelska) på Wolfram MathWorld- webbplatsen .
Richard Padovan, Dom Hans Van Der Laan och plastnumret
Ian Stewart, Tales of a neglected number
Padovan Sequence Term Calculator