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

В теории чисел , то Padovan последовательность представляет собой последовательность из целых чисел Р ( п ) определяется ^[1] начальными значениями

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

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

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

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

Отношения повторения [ править ]

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

${\ Displaystyle P (N) = P (N-1) + P (N-5)}$

Начиная с этого определяющего повторения и других повторений по мере их обнаружения, можно создать бесконечное количество дальнейших повторений, неоднократно заменяя их на${\ Displaystyle P (м)}$${\ Displaystyle Р (м-2) + Р (м-3)}$

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

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

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

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

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

${\displaystyle P(m)=P(m+3)-P(m+1),}$

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

P −20

P −19

P −18

P −17

P −16

P −15

P −14

P −13

P −12

P −11

P −10

P −9

P −8

P −7

P −6

P −5

P −4

P −3

P −2

P −1

P 0

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

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

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

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

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

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

${\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).}$ OEIS :  A012772

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

${\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 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) , и:

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

Формула Бине [ править ]

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

Порядковые номера Падована можно записать в терминах степеней корней уравнения ^[1]

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

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

${\displaystyle P\left(n\right)=ap^{n}+bq^{n}+cr^{n}}$

где a , b и c - константы. ^[1]

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

Для всех P (n) - это ближайшее к целому числу , где s = p / a = 1.0453567932525329623 ... - единственный действительный корень из s ³  - 2 s ²  + 23 s  - 23 = 0. Отношение последовательных членов в последовательность Падована приближается к p , которое имеет значение приблизительно 1,324718. Эта константа имеет такое же отношение к последовательности Падована и последовательности Перрина, как золотое сечение к последовательности Фибоначчи .${\displaystyle n\geq 0}$${\displaystyle {\frac {p^{n-1}}{s}}}$

Комбинаторные интерпретации [ править ]

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

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

Функция генерации [ править ]

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

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

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

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

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

Обобщения [ править ]

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

Падованская L-система [ править ]

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

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

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

начало : A

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

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

п = 0: А

п = 1: B

п = 2: С

n = 3: AB

п = 4: BC

n = 5: КАБИНА

n = 6: ABBC

n = 7: BCCAB

n = 8: CABABBC

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

1 1 1 2 2 3 4 5 ...

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

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

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

Треугольник Паскаля [ править ]

Эрв Уилсон в своей статье The Scales of Mt. Меру ^[6] наблюдал определенные диагонали в треугольнике Паскаля (см. Диаграмму) и нарисовал их на бумаге в 1993 году. Числа Падована были открыты в 1994 году. Пол Барри (2004) показал, что эти диагонали образуют последовательность Падована путем суммирования диагональных чисел. ^{[ необходима цитата ]}

Ссылки [ править ]

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

Внешние ссылки [ править ]

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