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

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

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

и линейным рекуррентным соотношением

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

Первые значения P(n) таковы

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, … (последовательность A000931 в OEIS)

Спираль равносторонних треугольников со сторонами равными членам последовательности Падована.

Последовательность Падована названа в честь Ричарда Падована^[англ.], который в своем эссе Dom. Hans van der Laan : Modern Primitive 1994 года приписал её открытие нидерландскому архитектору Гансу ван дер Лаану^{[англ.][1]}. Последовательность стала широко известной после того, как её описал Ян Стюарт в колонке Mathematical Recreations в журнале Scientific American в июне 1996 года.

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

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

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

${\displaystyle P(n)=P(n-2)+P(n-4)+P(n-8)}$

${\displaystyle P(n)=2P(n-2)-P(n-7)}$

${\displaystyle P(n)=P(n-3)+P(n-4)+P(n-5)}$

${\displaystyle P(n)=P(n-3)+P(n-5)+P(n-7)+P(n-8)+P(n-9)}$

${\displaystyle P(n)=P(n-4)+P(n-5)+P(n-6)+P(n-7)+P(n-8)}$

${\displaystyle P(n)=4P(n-5)+P(n-14).}$

Последовательность Перрина удовлетворяет таким же соотношениям, но имеет другие начальные значения. Последовательности Падована и Перрина также связаны соотношением:

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

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

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

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

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

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

Суммы членов

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

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

Суммы четных/нечетных членов, каждых третьих и суммы каждых пятых членов тоже выражаются определенными формулами:

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

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

${\displaystyle \sum _{m=0}^{n}P(3m)=P(3n+2)}$

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

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

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

Суммы, включающие произведения членов, удовлетворяют таким соотношениям:

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

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

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

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

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

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

Также её можно выразить через биномиальные коэффициенты:

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

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

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

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

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

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

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

${\displaystyle 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)}}.}$

Так как абсолютная величина обоих комплексных корней q и r меньше 1, то их n-я степень стремится к 0 с ростом n. Таким образом, справедлива асимптотическая формула:

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

где s — это действительный корень уравнения ${\displaystyle s^{3}-3s^{2}-23=0}$. Эта формула может быть использована для быстрого вычисления ${\displaystyle 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

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

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

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

Это может быть использовано для доказательства соотношений, включающих произведения последовательности Падована и геометрических прогрессий, таких как эта:

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

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

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

2, 3, 5, 7, 37, 151, 3329, 23833, … (последовательность A100891 в OEIS)

Обобщения

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

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

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 …

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

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

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