Padovan dizisi - Padovan sequence

İçinde sayı teorisi, Padovan dizisi ... sıra nın-nin tamsayılar P(n) tanımlanmış^[1] başlangıç ​​değerlerine göre

${ displaystyle P (0) = P (1) = P (2) = 1,}$

ve Tekrarlama ilişkisi

${ displaystyle P (n) = P (n-2) + P (n-3).}$

İlk birkaç değeri P(n)

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, ... (sıra A000931 içinde OEIS )

Padovan sırasını izleyen yan uzunluklara sahip eşkenar üçgen sarmal.

Padovan dizisi adını Richard Padovan keşfini kim bağladı Flemenkçe mimar Hans van der Laan 1994 denemesinde Dom. Hans van der Laan: Modern İlkel.^[2] Dizi tarafından açıklandı Ian Stewart onun içinde Bilimsel amerikalı sütun Matematiksel Rekreasyonlar Haziran 1996'da.^[3] Ayrıca kitaplarından biri olan "Matematik Histeri: Matematikle Eğlenceli Oyunlar" da yazıyor.^[4]

Yukarıdaki tanım, Ian Stewart ve tarafından verilen tanımdır. MathWorld. Diğer kaynaklar diziyi farklı bir yerde başlatabilir, bu durumda bu makaledeki kimliklerin bazılarının uygun kaydırmalarla ayarlanması gerekir.

Tekrarlama ilişkileri

Spiralde, her üçgenin diğer iki yanını paylaşması, Padovan dizisinin de yineleme ilişkisini sağladığına dair görsel bir kanıt sağlar

${ Displaystyle P (n) = P (n-1) + P (n-5)}$

Bundan yola çıkarak, tanımlayıcı yinelemeler ve keşfedildikçe diğer yinelemeler, tekrar tekrar değiştirilerek sonsuz sayıda başka yineleme yaratılabilir. ${ displaystyle P (m)}$ tarafından ${ displaystyle P (m-2) + P (m-3)}$

Perrin dizisi farklı başlangıç ​​değerlerine sahip olmasına rağmen, Padovan dizisi ile aynı tekrarlama ilişkilerini karşılar.

Perrin dizisi aşağıdaki formülle Padovan dizisinden elde edilebilir:

${ displaystyle mathrm {Perrin} (n) = P (n + 1) + P (n-10). ,}$

Negatif parametrelere uzantı

Yineleme ilişkisi ile tanımlanan herhangi bir dizide olduğu gibi, Padovan sayıları P(m) için m <0 yineleme ilişkisini şu şekilde yeniden yazarak tanımlanabilir:

${ displaystyle P (m) = P (m + 3) -P (m + 1),}$

İle başlayan m = −1 ve geriye doğru çalışarak, P(m) negatif endekslere:

P−20

P−19

P−18

P−17

P−16

P−15

P−14

P−13

P−12

P−11

P−10

P−9

P−8

P−7

P−6

P−5

P−4

P−3

P−2

P−1

P0

P1

P2

7

−7

4

0

−3

4

−3

1

1

−2

2

−1

0

1

−1

1

0

0

1

0

1

1

1

Terimlerin toplamları

İlkinin toplamı n Padovan dizisindeki terimler 2 küçüktür P(n + 5) yani

${ displaystyle toplamı _ {m = 0} ^ {n} P (m) = P (n + 5) -2.}$

Alternatif terimlerin toplamları, her üç terimin toplamları ve her beşinci terimin toplamları da dizideki diğer terimlerle ilişkilidir:

${ displaystyle toplamı _ {m = 0} ^ {n} P (2m) = P (2n + 3) -1}$ OEIS: A077855

${ displaystyle toplamı _ {m = 0} ^ {n} P (2m + 1) = P (2n + 4) -1}$

${ displaystyle toplamı _ {m = 0} ^ {n} P (3m) = P (3n + 2)}$ OEIS: A034943

${ displaystyle toplamı _ {m = 0} ^ {n} P (3m + 1) = P (3n + 3) -1}$

${ displaystyle toplamı _ {m = 0} ^ {n} P (3m + 2) = P (3n + 4) -1}$

${ displaystyle toplam _ {m = 0} ^ {n} P (5m) = P (5n + 1).}$ OEIS: A012772

Padovan dizisindeki terimlerin ürünlerini içeren toplamlar aşağıdaki kimlikleri karşılar:

${ displaystyle toplamı _ {m = 0} ^ {n} P (m) ^ {2} = P (n + 2) ^ {2} -P (n-1) ^ {2} -P (n- 3) ^ {2}}$

${ displaystyle toplamı _ {m = 0} ^ {n} P (m) ^ {2} P (m + 1) = P (n) P (n + 1) P (n + 2)}$

${ displaystyle toplamı _ {m = 0} ^ {n} P (m) P (m + 2) = P (n + 2) P (n + 3) -1.}$

Diğer kimlikler

Padovan dizisi aynı zamanda kimliği de karşılar

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

Padovan dizisi toplamları ile ilgilidir iki terimli katsayılar aşağıdaki kimlikle:

${ displaystyle P (k-2) = toplam _ {2m + n = k} {m seçin n} = toplamı _ {m = lceil k / 3 rceil} ^ { lfloor k / 2 rfloor } {m k-2m'yi seçin}.}$

Örneğin, k = 12, çiftin değerleri (m, n) 2 ilem + n = 12 sıfır olmayan binom katsayıları verir (6, 0), (5, 2) ve (4, 4) ve:

${ displaystyle {6 0} + {5 seç 2} + {4 seç 4} = 1 + 10 + 1 = 12 = P (10). ,}$

Binet benzeri formül

Yanları 1 / oranında olan üçgenlerρ kapalı bir sarmal oluşturmak

Padovan sıra numaraları, denklemin köklerinin kuvvetleri cinsinden yazılabilir.^[1]

${ displaystyle x ^ {3} -x-1 = 0. ,}$

Bu denklemin 3 kökü vardır; bir gerçek kök p (olarak bilinir plastik numara ) ve iki karmaşık eşlenik kök q ve r.^[5] Bu üç kök göz önüne alındığında, Padovan dizisi aşağıdakileri içeren bir formülle ifade edilebilir: p, q ve r:

${ displaystyle P sol (n sağ) = ap ^ {n} + bq ^ {n} + cr ^ {n}}$

nerede a, b ve c sabitler.^[1]

Karmaşık köklerin büyüklüklerinden beri q ve r her ikisi de 1'den küçüktür (ve dolayısıyla p bir Pisot – Vijayaraghavan numarası ), bu köklerin güçleri büyük için 0'a yaklaşır n, ve ${ displaystyle P sol (n sağ) -a {p ^ {n}}}$ sıfıra meyillidir.

Hepsi için ${ displaystyle n geq 0}$, P (n) en yakın tam sayıdır ${ displaystyle { frac {p ^ {n-1}} {s}}}$, nerede s = p/a = 1.0453567932525329623 ... tek gerçek köküdür s³ − 2s² + 23s - 23 = 0. Padovan dizisi yaklaşımlarında ardışık terimlerin oranı p, yaklaşık 1.324718 değerine sahiptir. Bu sabit, Padovan dizisi ve Perrin dizisi olarak altın Oran yapar Fibonacci Dizisi.

Kombinatoryal yorumlar

• P(n) yazma yollarının sayısıdır n + 2, her terimin 2 veya 3 olduğu sıralı bir toplam olarak (yani kompozisyonlar nın-nin n Her terimin 2 veya 3 olduğu + 2). Örneğin, P(6) = 4 ve 8'i sıralı olarak 2 ve 3'lerin toplamı olarak yazmanın 4 yolu vardır:

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

• Yazma yolu sayısı n hiçbir terimin 2 olmadığı sıralı bir toplam olarak P(2n - 2). Örneğin, P(6) = 4 ve hiçbir terimin 2 olmadığı sıralı bir toplam olarak 4 yazmanın 4 yolu vardır:

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

• Yazma yolları sayısı n hiçbir terimin 2 olmadığı palindromik sıralı bir toplam olarak P(n). Örneğin, P(6) = 4 ve 6'yı hiçbir terimin 2 olmadığı palindromik sıralı toplam olarak yazmanın 4 yolu vardır:

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

• Yazma yolları sayısı n her terimin tek ve 1'den büyük olduğu sıralı bir toplam olarak P(n - 5). Örneğin, P(6) = 4 ve her terimin tek ve 1'den büyük olduğu sıralı toplam olarak 11 yazmanın 4 yolu vardır:

11 ; 5 + 3 + 3 ; 3 + 5 + 3 ; 3 + 3 + 5

• Yazma yolları sayısı n her terimin 2'ye uygun olduğu sıralı bir toplam olarak mod 3'e eşittir P(n - 4). Örneğin, P(6) = 4 ve 10'u sıralı toplam olarak yazmanın 4 yolu vardır ve her terim 2 mod 3 ile uyumludur:

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

İşlev oluşturma

oluşturma işlevi Padovan sekansının

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

Bu, Padovan dizisinin ürünlerini içeren kimlikleri geometrik terimlerle kanıtlamak için kullanılabilir, örneğin:

${ displaystyle toplamı _ {n = 0} ^ { infty} { frac {P (n)} {2 ^ {n}}} = { frac {12} {5}}.}$

${ displaystyle sum _ {n = 0} ^ { infty} { frac {P (n)} { alpha ^ {n}}} = { frac { alpha ^ {2} ( alpha +1 )} { alpha ^ {3} - alpha -1}}.}$

Genellemeler

Benzer şekilde Fibonacci sayıları bu, bir polinom kümesine genelleştirilebilir. Fibonacci polinomları Padovan sıra numaraları genelleştirilebilir. Padovan polinomları.

Padovan L sistemi

Aşağıdaki basit grameri tanımlarsak:

değişkenler : A B C

sabitler : Yok

Başlat : Bir

kurallar : (A → B), (B → C), (C → AB)

sonra bu Lindenmayer sistemi veya L sistemi aşağıdaki dizi dizisini üretir:

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

ve her dizenin uzunluğunu sayarsak, Padovan sayı dizisini elde ederiz:

1 1 1 2 2 3 4 5 ...

Ayrıca, sayısını sayarsanız Birs, Bs ve Cher dizede s, sonra nthstring, sahipsin P(n − 5) Birs, P(n − 3) Bs ve P(n − 4) Cs. Sayısı BB çiftler CC çiftler de Padovan sayılarıdır.

Küboid sarmal

Bir dizi 3 boyutlu küpün köşelerini birleştirerek bir spiral oluşturulabilir. Padovan küboid sarmal. Bu sarmalın birbirini izleyen taraflarının uzunlukları Padovan sıra numaralarının çarpı 2'nin karekökü.

Pascal üçgeni

Erv Wilson onun kağıdında Mt.'nin Ölçekleri Meru^[6] bazı köşegenleri gözlemledi Pascal üçgeni (diyagrama bakınız) ve 1993'te kâğıda çizdi. Padovan sayıları 1994'te keşfedildi. Paul Barry (2004), bu köşegenlerin çapraz sayıları toplayarak Padovan dizisini oluşturduğunu gösterdi.^{[kaynak belirtilmeli ]}

Referanslar

• Ian Stewart, Bilgisayarla Arkadaş Bulma Rehberi (Geri Bildirim), Scientific American, Cilt. 275, No.5, Kasım 1996, Sf. 118.

Dış bağlantılar

• OEIS dizi A000931 (Padovan dizisi)
• Padovan sıra hesaplayıcı