Последовательность Падована (Hkvly;kfgmyl,ukvm, Hg;kfgug)
Последовательность Падована — это целочисленная последовательность P(n) с начальными значениями
и линейным рекуррентным соотношением
Первые значения 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 года.
Рекуррентные соотношения
[править | править код]Последовательность Падована подчиняется таким рекуррентным соотношениям:
Последовательность Перрина удовлетворяет таким же соотношениям, но имеет другие начальные значения. Последовательности Падована и Перрина также связаны соотношением:
Расширение на область отрицательных чисел
[править | править код]Последовательность Падована может быть расширена на область отрицательных чисел с помощью рекуррентного соотношения
(это похоже на расширение последовательности чисел Фибоначчи на область отрицательных индексов последовательности). Такое расширение 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), то есть
Суммы четных/нечетных членов, каждых третьих и суммы каждых пятых членов тоже выражаются определенными формулами:
Суммы, включающие произведения членов, удовлетворяют таким соотношениям:
Другие соотношения
[править | править код]Последовательность Падована также удовлетворяет зависимости
Также её можно выразить через биномиальные коэффициенты:
К примеру, для k = 12, значения пары (m; n), для которой 2m + n = 12, дающей ненулевые биномиальные коэффициенты, суть (6; 0), (5; 2) и (4; 4), и:
Формула общего члена
[править | править код]Члены последовательности Падована могут быть выражены через степени корней уравнения
Это уравнение имеет три корня: один действительный корень — пластическое число p ≈ 1,324718 и два комплексно-сопряженных корня q и r. С их помощью можно записать аналог формулы Бине для общего члена последовательности Падована:
Так как абсолютная величина обоих комплексных корней q и r меньше 1, то их n-я степень стремится к 0 с ростом n. Таким образом, справедлива асимптотическая формула:
где s — это действительный корень уравнения . Эта формула может быть использована для быстрого вычисления для больших 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
Производящая функция
[править | править код]Производящая функция для последовательности Падована такова:
Это может быть использовано для доказательства соотношений, включающих произведения последовательности Падована и геометрических прогрессий, таких как эта:
Простые Падована
[править | править код]Простое Падована это такое P(n), которое является простым числом. Первые несколько простых Падована таковы:
Обобщения
[править | править код]Полиномы Падована
[править | править код]Как и числа Фибоначчи, которые обобщаются множеством полиномов (полиномы Фибоначчи), последовательность Падована тоже может быть обобщена полиномами Падована.
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.
Примечания
[править | править код]- ↑ Richard Padovan. Dom Hans van der Laan: modern primitive: Architectura & Natura Press, ISBN 9789071570407.
Ссылки
[править | править код]- Weisstein, Eric W. Padovan Sequence (англ.) на сайте Wolfram MathWorld.
- Ричард Падован, Dom Hans Van Der Laan And The Plastic Number
- Ян Стюарт, Tales of a Neglected Number
- Калькулятор членов последовательности Падована