Padovanská sekvence

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 10. srpna 2019; ověření vyžaduje 1 úpravu .

Padovanská posloupnost je celočíselná posloupnost P ( n ) s počátečními hodnotami

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

a lineární rekurentní vztah

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

První hodnoty P ( n ) jsou

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

Padovanská sekvence je pojmenována po Richardu Padovanovi , který ve svém eseji Dom. Hans van der Laan: Modern Primitive z roku 1994 připsal svůj objev nizozemskému architektovi Hans van der Laan [1] . Tato sekvence se stala široce známou poté , co ji Ian Stuart popsal ve sloupci Mathematical Recreations ve Scientific American v červnu 1996 .

Opakující se vztahy

Padovanská sekvence se řídí následujícími rekurzivními vztahy:

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

Perrinova sekvence splňuje stejné vztahy, ale má různé počáteční hodnoty. Padovanovy a Perrinovy sekvence jsou také příbuzné:

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

Rozšíření na oblast záporných čísel

Padovanská posloupnost může být rozšířena na oblast záporných čísel pomocí vztahu opakování

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

(toto je podobné rozšíření Fibonacciho sekvence do oblasti negativních indexů sekvence). Takové rozšíření P ( n ) dává hodnoty

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

Členské částky

Součet prvních n členů sekvence je o 2 menší než P ( n + 5), tzn.

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

Součty sudých/lichých členů, každý třetí a součet každého pátého členu jsou také vyjádřeny určitými vzorci:

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

Součty včetně součinů podmínek splňují následující vztahy:

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

Jiné poměry

Padovanská sekvence také splňuje závislost

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

Může být také vyjádřen pomocí binomických koeficientů :

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

Například pro k = 12 jsou hodnoty páru ( m ; n ), pro které 2 m + n = 12 poskytující nenulové binomické koeficienty, (6; 0), (5; 2) a (4; 4) a:

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

Obecný termínový vzorec

Členy Padovanovy posloupnosti lze vyjádřit pomocí mocnin kořenů rovnice

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

Tato rovnice má tři kořeny: jeden reálný kořen - plastické číslo p ≈ 1,324718 a dva komplexně sdružené kořeny q a r . S jejich pomocí můžete napsat analogii Binetova vzorce pro obecný termín Padovanovy sekvence:

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

Protože absolutní hodnota obou komplexních kořenů q a r je menší než 1, pak jejich n-tá mocnina inklinuje k 0, jak n roste . Platí tedy asymptotický vzorec:

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

kde s je skutečný kořen rovnice . Tento vzorec lze použít pro rychlé výpočty pro velké n . $s^{3}-3s^{2}-23=0$ $P(n)$

Poměr sousedních členů Padovanovy posloupnosti směřuje k plastickému číslu p . Tato konstanta hraje stejnou roli pro Padovanovy a Perrinovy sekvence jako zlatý řez pro Fibonacciho sekvenci.

Kombinatorické interpretace

P ( n ) je počet způsobů, jak zapsat n + 2 jako součet 2 a 3 v daném pořadí. Například P (6) = 4, protože existují 4 způsoby, jak napsat 8 jako součet dvojek a trojek s různým pořadím členů:

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

P (2 n - 2) je počet způsobů, jak zapsat n jako řádově citlivý součet, ve kterém žádný člen není roven 2. Například P (6) = 4, protože existují 4 způsoby, jak zapsat 4 takto :

čtyři; 1+3; 3+1; 1+1+1+1

P ( n ) je počet způsobů, jak zapsat n jako řádově citlivý součet palindromu, ve kterém žádný člen není roven 2. Například P (6) = 4, protože existují 4 způsoby, jak zapsat 6 výše uvedeným způsobem :

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

P ( n − 4) je počet způsobů, jak zapsat n jako součet, daným pořadím, ve kterém je každý shodný s 2 modulo 3. Například P (6) = 4, protože existují 4 způsoby, jak zapsat číslo 10 takto:

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

Generující funkce

Funkce generování Padovanovy sekvence je:

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

To lze použít k prokázání vztahů zahrnujících součiny Padovanovy sekvence a geometrické posloupnosti, jako je tato:

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

Jednoduchá Padovana

Padovanské prvočíslo je P ( n ), což je prvočíslo . Prvních několik jednoduchých Padovanů je:

2, 3, 5, 7, 37, 151, 3329, 23833, … (sekvence A100891 v OEIS )

Zobecnění

Padovanské polynomy

Jako Fibonacci čísla , který být zobecněn souborem polynomials ( Fibonacci polynomials ), Padovan posloupnost může také být zobecněna Padovan polynomials .

Padovanův L-systém

Pokud definujeme tuto jednoduchou gramatiku:

proměnné : ABC konstanty : žádné začátek : A pravidla : (A → B), (B → C), (C → AB)

pak takový Lindenmeyerův systém ( L-systém ) dává následující posloupnost řádků:

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

a pokud spočítáme délku každého z nich, dostaneme Padovanovu posloupnost:

1 1 1 2 2 3 4 5 7 …

Také, pokud spočítáme počet znaků A , B a C v každém řádku, pak pro n-tý řádek bude P ( n − 5) znaků A , P ( n − 3) znaků B a P ( n − 4) znaky C. _ Počet párů BB , AA a CC jsou také padovská čísla.

Padovanova kvádrová spirála

Padovanská kvádrová spirála může být postavena spojením rohů mnoha 3D kvádrů. Délky po sobě jdoucích stran spirály jsou členy Padovanovy posloupnosti vynásobené druhou odmocninou ze 2.

Poznámky

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

Odkazy

Weisstein, Eric W. Padovan Sequence (anglicky) na webových stránkách Wolfram MathWorld .
Richard Padovan, Dom Hans Van Der Laan a Plastové číslo
Ian Stewart, Příběhy zanedbaného čísla
Kalkulačka sekvenčních termínů Padovan