Secvența Padovan

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 10 august 2019; verificarea necesită 1 editare .

Secvența Padovan este o secvență întreagă P ( n ) cu valori inițiale

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

și relația de recurență liniară

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

Primele valori ale lui P ( n ) sunt

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

Secvența Padovan poartă numele lui Richard Padovan , care în eseul său Dom. Hans van der Laan: Modern Primitive din 1994 și-a atribuit descoperirea arhitectului olandez Hans van der Laan [1] . Secvența a devenit cunoscută pe scară largă după ce Ian Stuart a descris-o în coloana Mathematical Recreations din Scientific American în iunie 1996 .

Relații recurente

Secvența Padovan respectă următoarele relații recursive:

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).

Secvența Perrin satisface aceleași relații, dar are valori inițiale diferite. Secvențele Padovan și Perrin sunt, de asemenea, legate prin:

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

Extindere la regiunea numerelor negative

Secvența Padovan poate fi extinsă la regiunea numerelor negative folosind relația de recurență

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

(acest lucru este similar cu extinderea secvenței Fibonacci la regiunea indicilor negativi ai secvenței). O astfel de extindere a lui P ( n ) dă valorile

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

Sumele membrilor

Suma primilor n termeni ai secvenței este cu 2 mai mică decât P ( n + 5), adică.

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

Sumele termenilor pari/impari, fiecare treime și suma fiecărui cincilea termeni sunt exprimate și prin anumite formule:

\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).

Sumele, inclusiv produsele termenilor, satisfac următoarele relații:

\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.

Alte rapoarte

Sirul Padovan satisface si dependenta

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

Poate fi exprimat și în termeni de coeficienți binomi :

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

De exemplu, pentru k = 12, valorile perechii ( m ; n ) pentru care 2 m + n = 12 care oferă coeficienți binomi nenuli sunt (6; 0), (5; 2) și (4); 4), și:

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

Formula generală a termenului

Termenii șirului Padovan pot fi exprimați în termeni de puteri ale rădăcinilor ecuației

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

Această ecuație are trei rădăcini: o rădăcină reală - numărul plastic p ≈ 1,324718 și două rădăcini conjugate complexe q și r . Cu ajutorul lor, puteți scrie un analog al formulei lui Binet pentru termenul general al secvenței Padovan:

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

Deoarece valoarea absolută a ambelor rădăcini complexe q și r este mai mică decât 1, atunci puterea lor a n- a tinde spre 0 pe măsură ce n crește . Astfel, formula asimptotică este valabilă:

P\left(n\dreapta)\aprox {\frac {p^{n}}{\left(3p^{2}-1\right))))={\frac {p^{n}}{s} }\aprox {\frac {p^{n}}{4,264632\ldots }},

unde s este rădăcina reală a ecuației . Această formulă poate fi utilizată pentru calcule rapide pentru n mare . $s^{3}-3s^{2}-23=0$ $P(n)$

Raportul termenilor învecinați ai șirului Padovan tinde la numărul plastic p . Această constantă joacă același rol pentru secvențele Padovan și Perrin ca și raportul de aur pentru șirul Fibonacci.

Interpretări combinatorii

P ( n ) este numărul de moduri de a scrie n + 2 ca sumă a lui 2 și 3, dată fiind ordinea. De exemplu, P (6) = 4, deoarece există 4 moduri de a scrie 8 ca sumă a doi și trei cu ordine diferită a membrilor:

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

P (2 n - 2) este numărul de moduri de a scrie n ca sumă sensibilă la ordine în care niciun termen nu este egal cu 2. De exemplu, P (6) = 4, deoarece există 4 moduri de a scrie 4 astfel :

patru; 1+3; 3+1; 1+1+1+1

P ( n ) este numărul de moduri de a scrie n ca sumă palindrom sensibilă la ordine în care niciun termen nu este egal cu 2. De exemplu, P (6) = 4, deoarece există 4 moduri de a scrie 6 în modul de mai sus :

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

P ( n − 4) este numărul de moduri de a scrie n ca sumă, dată fiind ordinea, în care fiecare este congruent cu 2 modulo 3. De exemplu, P (6) = 4, deoarece există 4 moduri de a scrie numărul 10 în felul acesta:

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

Funcție de generare

Funcția generatoare pentru secvența Padovan este:

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

Aceasta poate fi folosită pentru a demonstra relații care implică produsele succesiunii Padovan și progresii geometrice precum aceasta:

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

Simplu Padovana

Un prim padovan este P ( n ), care este un număr prim . Primii câțiva padoveni simpli sunt:

2, 3, 5, 7, 37, 151, 3329, 23833, … (secvența A100891 în OEIS )

Generalizări

Polinoame padovenești

La fel ca numerele Fibonacci , care sunt generalizate printr-un set de polinoame (polinoame Fibonacci ), șirul Padovan poate fi generalizat și prin polinoame Padovan .

Sistemul L al lui Padovan

Dacă definim această gramatică simplă:

variabile : ABC constante : niciuna începe : A reguli : (A → B), (B → C), (C → AB)

atunci un astfel de sistem Lindenmeyer (sistemul L ) dă următoarea secvență de linii:

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

iar dacă numărăm lungimea fiecăruia dintre ele, obținem succesiunea Padovan:

1 1 1 2 2 3 4 5 7 …

De asemenea, dacă numărăm numărul de caractere A , B și C din fiecare rând, atunci pentru a n- a linie vor exista P ( n − 5) caractere A , P ( n − 3) caractere B și P ( n − 4) caracterele C. _ Numărul de perechi BB , AA și CC sunt, de asemenea, numere de Padovan.

Spirala cuboidă a lui Padovan

Spirala cuboidă Padovan poate fi construită prin unirea colțurilor multor cuboide 3D. Lungimile laturilor succesive ale spiralei sunt termenii șirului Padovan înmulțiți cu rădăcina pătrată a lui 2.

Note

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

Link -uri

Weisstein, Eric W. Padovan Sequence (engleză) pe site-ul Wolfram MathWorld .
Richard Padovan, Dom Hans Van Der Laan și numărul de plastic
Ian Stewart, Poveștile unui număr neglijat
Calculator de termeni ai secvenței Padovan