WikiSort.ru - Не сортированное

Последовательность Падована — это целочисленная последовательность 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 года приписал её открытие нидерландскому архитектору Гансу ван дер Лаану. Последовательность стала широко известной после того, как её описал Ян Стюарт в колонке 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)

Обобщения

Ссылки

• Weisstein, Eric W. Padovan Sequence (англ.) на сайте Wolfram MathWorld.
• Ричард Падован, Dom Hans Van Der Laan And The Plastic Number
• Ян Стюарт, Tales of a Neglected Number
• Калькулятор членов последовательности Падована