Последовательность Падована

Последовательность Падована — это целочисленнаяпоследовательность P(n) с начальными значениями

P(0)=P(1)=P(2)=1
 и линейным рекуррентным соотношением

P(n)=P(n2)+P(n3).
 Первые значения P(n) таковы

 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151,200, 265, \ldots
 Последовательность Падована названа в честь Ричарда Падована, который всвоем эссе Dom. Hans van der Laan : Modern Primitive 1994 годаприписал её открытие нидерландскому архитектору Гансу ван дер Лаану.Последовательность стала широко известной после того, как её описал ЯнСтюарт в колонке Mathematical Recreations в журнале ScientificAmerican в июне 1996 года.

Рекуррентныесоотношения


 Последовательность Падована подчиняется таким рекуррентным соотношениям:

P(n)=P(n1)+P(n5)


P(n)=P(n2)+P(n4)+P(n8)


P(n)=2P(n2)P(n7)


P(n)=P(n3)+P(n4)+P(n5)


P(n)=P(n3)+P(n5)+P(n7)+P(n8)+P(n9)


P(n)=P(n4)+P(n5)+P(n6)+P(n7)+P(n8)


P(n)=4P(n5)+P(n14).
 Последовательность Перрина удовлетворяет таким же соотношениям, но имеетдругие начальные значения. Последовательности Падована и Перрина такжесвязаны соотношением:

Perrin(n)=P(n+1)+P(n10).

Расширение на область отрицательныхчисел


 Последовательность Падована может быть расширена на областьотрицательных чисел с помощью рекуррентого соотношения

P(n)=P(n+3)P(n+1).
 (это похоже на расширение последовательности чисел Фибоначчи на областьотрицательных индексов последовательности). Такое расширениеP(n) дает значения

 \ldots, −7, 4, 0, −3, 4, −3, 1, 1, −2, 2, −1, 0, 1, −1, 1, 0, 0, 1, 0,1, 1, 1, \ldots

Суммычленов


 Сумма первых n членов последовательности на 2 меньше чемP(n + 5), то есть

m=0nP(m)=P(n+5)2.
 Суммы четных/нечетных членов, каждых третьих и суммы каждых пятых членовтоже выражаются определенными формулами:

m=0nP(2m)=P(2n+3)1


m=0nP(2m+1)=P(2n+4)1


m=0nP(3m)=P(3n+2)


m=0nP(3m+1)=P(3n+3)1


m=0nP(3m+2)=P(3n+4)1


m=0nP(5m)=P(5n+1).
 Суммы, включающие произведения членов, удовлетворяют таким соотношениям:

m=0nP(m)2=P(n+2)2P(n1)2P(n3)2


m=0nP(m)2P(m+1)=P(n)P(n+1)P(n+2)


m=0nP(m)P(m+2)=P(n+2)P(n+3)1.

Другиесоотношения


 Последовательность Падована также удовлетворяет зависимости

P(n)2P(n+1)P(n1)=P(n7).
 Также её можно выразить через биномиальные коэффициенты:

2m+n=k(mn)=P(k2).
 К примеру, для k = 12, значения пары (mn), длякоторой 2m + n = 12, дающей ненулевые биномиальныекоэффициенты, суть (6; 0), (5; 2) и (4; 4), и:

(60)+(52)+(44)=1+10+1=12=P(10).

Формула общегочлена


 Члены последовательности Падована могут быть выражены через степеникорней уравнения

x3x1=0.
 Это уравнение имеет три корня: один действительный корень —пластическое число p ≈ 1,324718 и два комплексно-сопряженныхкорня q и r. С их помощью можно записать аналог формулыБине для общего члена последовательности Падована:

P(n)=pn(3p21)+qn(3q21)+rn(3r21).
 Так как абсолютная величина обоих комплексных корней q и rменьше 1, то их n-я степень стремится к 0 с ростом n.Таким образом, справедлива асимптотическая формула:

P(n)pn(3p21)=pnspn4,264632,
 где s — это действительный корень уравнения s33s223=0.Эта формула может быть использована для быстрого вычисления P(n) длябольших n.
 Отношение соседних членов последовательности Падована стремится кпластическому числу p. Эта константа выполняет ту же роль дляпоследовательностей Падована и Перрина, что и золотое сечение дляпоследовательности Фибоначчи.

Комбинаторныеинтерпретации



  • P(n) это количество способов записать n + 2 как сумму 2 и 3 с учётом порядка. К примеру, P(6) = 4, так как есть 4 способа записать 8 как сумму двоек и троек с разным порядком следования членов:



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


  • P(2n − 2) это количество способов записи n в виде суммы с учётом порядка, в которой ни один член не равен 2. К примеру, P(6) = 4, так как есть 4 способа записать 4 подобным образом:



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


  • P(n) это количество способов записи n как сумму-палиндром с учётом порядка, в которой ни один член не равен 2. К примеру, P(6) = 4, так как есть 4 способа записать 6 вышеуказанным способом:



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


  • P(n − 4) это количество способов записать n в виде суммы с учётом порядка, в которой каждый конгруэнтен 2 по модулю 3. К примеру, P(6) = 4, так как есть 4 способа записать число 10 таким способом:



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

Производящаяфункция


 Производящая функция для последовательности Падована такова:

G(P(n);x)=1+x1x2x3.
 Это может быть использовано для доказательства соотношений, включающихпроизведения последовательности Падована и геометрических прогрессий,таких как эта:

m=0P(n)2n=125.

ПростыеПадована


Простое Падована это такое P(n), которое являетсяпростым числом. Первые несколько простых Падована таковы:

 2, 3, 5, 7, 37, 151, 3329, 23833, \ldots

Обобщения


ПолиномыПадована


 Как и числа Фибоначчи, которые обобщаются множеством полиномов (полиномыФибоначчи), последовательность Падована тоже может быть обобщенаполиномами Падована.

L-системаПадована


 Если определить такую простую грамматику:

переменные : A B C
константы : отсутствуют
начало : A
правила : (A → B), (B → C), (C → AB)
 тогда такая система Линденмейера (L-система) даёт такуюпоследовательность строк:

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
 и если мы посчитаем длину каждой из них, мы получим последовательностьПадована:

 1 1 1 2 2 3 4 5 7 \ldots
 Также, если посчитать количество символов A, B и Cв каждой строке, тогда для n-ной строки будетP(n − 5) символов A, P(n − 3)символов B и P(n − 4) символов C. Количествопар BB, AA и CC тоже является числами Падована.

Кубоидная спиральПадована


 Кубоидная спираль Падована может быть построена путём соединения угловмножества трёхмерных кубоидов. Длины последовательных сторон спиралисуть члены последовательности Падована, умноженные на квадратный кореньиз 2.