Падованская последовательность

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

$P(0)=P(1)=P(2)=1,$

и рекуррентное соотношение

$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 в ОЭИС )

Простое число Падована — это число Падована, которое является простым . Первые простые числа Падована:

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

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

Последовательность Падован названа в честь Ричарда Падована «Дом» приписал ее открытие голландскому архитектору Хансу ван дер Лаану , который в своем эссе 1994 года . Ханс ван дер Лаан: Современный примитив . Последовательность в была описана Яном Стюартом в его журнале Scientific American колонке «Математические развлечения» в июне 1996 года. Об этом он также пишет в одной из своих книг «Математическая истерия: веселые игры с математикой».

Приведенное выше определение дано Яном Стюартом и MathWorld . Другие источники могут начинать последовательность с другого места, и в этом случае некоторые идентификаторы в этой статье необходимо скорректировать с помощью соответствующих смещений.

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

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

$P(n)=P(n-1)+P(n-5)$

Исходя из этого, определяющий рецидив и другие рецидивы по мере их обнаружения:можно создать бесконечное количество дальнейших повторений, неоднократно заменяя $P(m)$ к $P(m-2)+P(m-3)$

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

Последовательность Перрена может быть получена из последовательности Падована с помощью следующая формула:

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

Расширение на отрицательные параметры

Как и в случае с любой последовательностью, определяемой рекуррентным соотношением, числа Падована P ( m ) для m <0 можно определить, переписав рекуррентное соотношение как

$P(m)=P(m+3)-P(m+1),$

Начиная с m = −1 и двигаясь в обратном направлении, мы расширяем P ( m ) до отрицательных индексов:

П −20

П −19

П −18

П −17

П −16

П −15

П −14

П −13

П −12

П −11

П −10

Р −9

П −8

П −7

П −6

П −5

П −4

П -3

П -2

Р -1

PP0

PП1

П 2

7

−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), т.е.

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

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

$\sum _{m=0}^{n}P(2m)=P(2n+3)-1$ ОЭИС : A077855

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

$\sum _{m=0}^{n}P(3m)=P(3n+2)$ ОЭИС : A034943

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

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

$\sum _{m=0}^{n}P(5m)=P(5n+1).$ ОЭИС : A012772

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

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

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

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

Другие личности

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

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

Последовательность Падована связана с суммами биномиальных коэффициентов следующим тождеством:

$P(k-2)=\sum _{2m+n=k}{m \choose n}=\sum _{m=\lceil k/3\rceil }^{\lfloor k/2\rfloor }{m \choose k-2m}.$

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

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

Формула типа Бине

Треугольники со сторонами, относящимися к 1/ ρ, образуют замкнутую спираль.

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

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

Это уравнение имеет 3 корня; один действительный корень p (известный как коэффициент пластичности ) и два комплексно-сопряженных корня q и r . Учитывая эти три корня, последовательность Падована можно выразить формулой, включающей p , q и r :

$P(n)=ap^{n}+bq^{n}+cr^{n}$

где a , b и c — константы.

Поскольку абсолютные значения комплексных , корней q и r меньше 1 (и, следовательно, p — число Писо–Виджаярагхавана ), степени этих корней приближаются к 0 при больших n и $P(n)-ap^{n}$ стремится к нулю.

Для всех $n\geq 0$, P ( n ) — целое число, ближайшее к ${\frac {p^{5}}{2p+3}}p^{n}$. Действительно, ${\frac {p^{5}}{2p+3}}$ — значение константы a , указанной выше, а b и c получаются заменой p на q и r соответственно.

Отношение последовательных членов последовательности Падована приближается к p , которое имеет значение примерно 1,324718. Эта константа имеет такое же отношение к последовательности Падована и последовательности Перрена , как золотое сечение к последовательности Фибоначчи .

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

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

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

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

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

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

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

• Число способов записи n в виде упорядоченной суммы, в которой каждый член нечетен и больше 1, равно P ( n − 5). Например, P (6) = 4, и существует 4 способа записать 11 в виде упорядоченной суммы, в которой каждое слагаемое нечетно и больше 1:

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

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

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

Генерирующая функция

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

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

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

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

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

Обобщения

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

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

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

переменные : ABC

константы : нет

начало : А

правила : (A → B), (B → C), (C → AB)

тогда эта система Линденмайера или L-система создает следующую последовательность строк:

п = 0: А

п = 1: Б

п = 2 : С

п = 3: АБ

п = 4: до нашей эры

n = 5: КАБИНА

п = 6: АБВС

n = 7: BCCAB

n = 8: КАБАББК

и если мы посчитаем длину каждой строки, мы получим числа Падована:

1, 1, 1, 2, 2, 3, 4, 5, ...

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

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

Основная статья: кубовидная спираль Падована

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

Треугольник Паскаля

Эрв Уилсон в своей статье «Весы горы Меру». наблюдал определенные диагонали в треугольнике Паскаля (см. диаграмму) и нарисовал их на бумаге в 1993 году. Числа Падована были открыты в 1994 году. Пол Барри (2004) заметил, что эти диагонали порождают последовательность Падована путем суммирования диагональных чисел.

Ссылки

• Ян Стюарт, Руководство по компьютерным знакомствам (обратная связь), Scientific American, Vol. 275, № 5, ноябрь 1996 г., стр. 118.

Внешние ссылки

• Последовательность OEIS A000931 (последовательность Падована)
• Калькулятор последовательности Падована