EssayAI
Блог
Блог
Математика и алгоритмы

Последовательность Падована: формула и примеры

8 ноября 2026Время чтения: 9 минут
#последовательность падована#рекуррентная формула#пластическое число#числовые последовательности#производящая функция
Последовательность Падована: формула и примеры

Последовательность Падована получается из трёх единиц по правилу, похожему на правило Фибоначчи, но с важным отличием: для следующего числа складывают не два соседних члена, а члены на два и три шага назад. Первые значения таковы: 1,1,1,2,2,3,4,5,7,9,12,…1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, \ldots. Из этого простого правила возникает пластическое число: к нему стремятся отношения соседних членов. В калькуляторе можно выбрать номер и проверить оба слагаемых, прежде чем разбирать формулы.

Определение и первые члены

Зафиксируем нумерацию с нуля и начальные условия:

P0=P1=P2=1,Pn=Pn−2+Pn−3(n≥3).P_0=P_1=P_2=1, \qquad P_n=P_{n-2}+P_{n-3}\quad(n\geq 3).

Рекуррентная формула задаёт новый член через уже известные. Например, P3=P1+P0=2P_3=P_1+P_0=2, а P4=P2+P1=2P_4=P_2+P_1=2. Повторяющиеся значения здесь естественны: правило использует слагаемые с одинаковыми начальными значениями. Затем P5=P3+P2=3P_5=P_3+P_2=3 и P6=P4+P3=4P_6=P_4+P_3=4.

Номер вычисляемого члена меняется: два выбранных слагаемых всегда отстоят от результата на два и три шага, а их сумма даёт новое число.

В литературе встречается другая нумерация: три начальные единицы могут обозначаться P1,P2,P3P_1,P_2,P_3, а не P0,P1,P2P_0,P_1,P_2. Тогда один и тот же список чисел сохраняется, но номер каждого его элемента меняется. В работе Alain Faisant о последовательности Падована используется запись рекурсии со сдвигом индексов; поэтому перед сравнением ответов всегда проверяйте начальные условия.

У чисел Фибоначчи сумма берётся по двум непосредственно предшествующим членам. У Падована предыдущий член Pn−1P_{n-1} в исходной формуле не участвует. Оба правила линейные, но порождают разные последовательности и разные предельные отношения.

Как вычислить число по номеру

Для ручного счёта удобно составить таблицу и не пропускать индексы:

nn012345678910
PnP_n111223457912

Пусть требуется найти P10P_{10}. По формуле нужны P8P_8 и P7P_7, а не P9P_9 и P8P_8. Из таблицы P8=7P_8=7 и P7=5P_7=5, поэтому

P10=P8+P7=7+5=12.P_{10}=P_8+P_7=7+5=12.

Для следующего шага снова меняем оба индекса: P11=P9+P8=9+7=16P_{11}=P_9+P_8=9+7=16. Такой порядок полезен и в программе: достаточно хранить три последние величины, вычислять сумму первой и второй из них и сдвигать окно на одну позицию. Для малых номеров таблица прозрачнее, а при больших последовательное вычисление избавляет от повторного пересчёта одних и тех же членов.

Начальные условия обязательны. Одна рекурсия сама по себе не определяет единственную последовательность: если заменить тройку единиц другой тройкой, дальнейшие значения тоже изменятся. Поэтому в задаче проверяют и правило, и стартовые числа.

Пластическое число и отношение соседних членов

Посмотрим на отношения Pn/Pn−1P_n/P_{n-1}. В начале они колеблются: P3/P2=2P_3/P_2=2, затем P4/P3=1P_4/P_3=1, а P10/P9=12/9≈1,3333P_{10}/P_9=12/9\approx1{,}3333. По мере роста номера колебания затухают, и отношение стремится к пластическому числу ρ≈1,324718\rho\approx1{,}324718.

Отношения соседних чисел Падована колеблются вокруг уровня 1,3247; для десятого члена отношение равно 12 к 9
Отношения соседних чисел Падована колеблются вокруг уровня 1,3247; для десятого члена отношение равно 12 к 9

Откуда берётся это число? Подставим пробное решение вида Pn=rnP_n=r^n в рекуррентную формулу и разделим на rn−3r^{n-3} при r≠0r\ne0:

r3=r+1,r3−r−1=0.r^3=r+1, \qquad r^3-r-1=0.

У этого уравнения один действительный корень ρ>1\rho>1 и два комплексно-сопряжённых корня. Их модули меньше единицы: произведение всех трёх корней равно единице, следовательно квадрат модуля комплексного корня равен 1/ρ1/\rho. Общее решение рекурсии складывается из степеней трёх корней. Для выбранных начальных условий коэффициент при ρn\rho^n положителен: иначе последовательность, которая неограниченно растёт, стремилась бы к нулю. Поэтому два остальных вклада затухают относительно главного, и Pn+1/Pn→ρP_{n+1}/P_n\to\rho.

Это объяснение сильнее одной лишь подстановки предполагаемого предела в формулу: подстановка показывает, какому уравнению предел обязан удовлетворять, но сама по себе не доказывает существование предела. Значение и связь пластического числа с последовательностью приводятся также в OEIS. В отличие от золотого сечения, возникающего у Фибоначчи, здесь определяющее уравнение кубическое.

Предельное отношение говорит о долговременном масштабе роста, а не об одинаковом процентном увеличении на каждом шаге. Ранние отношения то больше, то меньше предела; поэтому умножение текущего значения на 1,32471{,}3247 не заменяет точную рекурсию. При достаточно большом номере главный вклад имеет вид постоянного множителя на ρn\rho^n, но начальный множитель зависит от выбранных стартовых условий.

На графике каждая точка соответствует целому номеру, а отрезки между точками только помогают проследить порядок. Никаких промежуточных членов с дробными индексами это соединение не задаёт. Пунктир показывает предельный уровень, а не значение, которое обязано быть достигнуто в какой-либо конечной точке. Различие между приближением к числу и точным равенством важно и при округлении ответа: четыре десятичных знака описывают точность записи, а не точность всех конечных отношений.

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

Соберём все члены в формальный степенной ряд G(x)=∑n≥0PnxnG(x)=\sum_{n\geq0}P_nx^n. Умножим его на 1−x2−x31-x^2-x^3. Начиная с коэффициента при x3x^3, каждое выражение Pn−Pn−2−Pn−3P_n-P_{n-2}-P_{n-3} обращается в ноль благодаря рекурсии. Для первых трёх степеней остаются коэффициенты 11, 11 и 00. Значит,

G(x)=1+x1−x2−x3.G(x)=\frac{1+x}{1-x^2-x^3}.

Например, коэффициент при x5x^5 в разложении этого выражения равен P5=3P_5=3. Это не новое определение стартовых чисел, а компактная запись той же последовательности. Она полезна при выводе тождеств и сумм; общая техника описана в статье о методе производящих функций. Формальный ряд позволяет сравнивать коэффициенты без предположения о численном значении xx.

Комбинаторный смысл: дорожки из плиток

Есть модель, в которой числа Падована появляются при подсчёте. Пусть TmT_m - число способов покрыть дорожку длины mm плитками длины 2 и 3, если порядок плиток различается. Пустую дорожку считаем покрытой одним способом: T0=1T_0=1. Для отрицательных длин положим Tm=0T_m=0.

Последняя плитка имеет длину либо 2, либо 3. После её удаления остаётся покрытая дорожка длины m−2m-2 или m−3m-3, поэтому при m≥1m\geq1 выполняется Tm=Tm−2+Tm−3T_m=T_{m-2}+T_{m-3}. Начало ряда здесь: T0=1T_0=1, T1=0T_1=0, T2=1T_2=1, T3=1T_3=1, T4=1T_4=1. Значит, при нашей нумерации Pn=Tn+2P_n=T_{n+2} для всех n≥0n\geq0: три начальных значения совпадают и далее действует та же рекурсия.

Например, P5=T7=3P_5=T_7=3: длину 7 дают порядки плиток 2+2+32+2+3, 2+3+22+3+2 и 3+2+23+2+2. Разные порядки считаются разными покрытиями. Здесь применяется правило суммы в комбинаторике: два случая последней плитки не пересекаются и вместе исчерпывают все варианты.

Как организовать расчёт без таблицы

Для большого номера не обязательно хранить всю последовательность. Обозначим три соседних известных члена через aa, bb, cc: сначала это три единицы. Новый член равен a+ba+b, ведь именно эти два значения находятся на три и два шага от новой позиции. Затем заменяем тройку на b,c,a+bb,c,a+b и повторяем операцию. Порядок действий важен: сумму нужно вычислить до того, как старые значения будут заменены.

После первого сдвига получаем тройку 1,1,21,1,2, после второго - 1,2,21,2,2, после третьего - 2,2,32,2,3. Последний элемент каждой новой тройки и есть очередной член последовательности. Такой алгоритм выполняет по одному сложению на шаг и хранит только три числа. Для очень больших номеров в программе понадобится тип, поддерживающий длинные целые числа: обычный числовой тип может потерять точность, даже если сама рекурсия записана верно.

Калькулятор выше ограничен номером 25, поэтому использует точные целые значения в своём диапазоне. На последнем положении он показывает P25=816P_{25}=816. Если нужна не только величина, но и проверка хода решения, удобнее сохранить промежуточную таблицу: по ней легко увидеть, на каком шаге были выбраны неверные индексы.

Ещё один способ проверить вычисление

Из основного правила получается полезное равенство Pn=Pn−1+Pn−5P_n=P_{n-1}+P_{n-5} при n≥5n\geq5. В самом деле, Pn−1=Pn−3+Pn−4P_{n-1}=P_{n-3}+P_{n-4}, а Pn−2=Pn−4+Pn−5P_{n-2}=P_{n-4}+P_{n-5}. Подставляя второе равенство в исходную рекурсию и собирая первые два слагаемых, получаем нужную формулу. Например, P10=P9+P5=9+3=12P_{10}=P_9+P_5=9+3=12. Она даёт независимую проверку арифметики, хотя основана на том же определении.

Это равенство также объясняет, почему при нашей тройке единиц последовательность не убывает с пятого члена: разность Pn−Pn−1P_n-P_{n-1} равна положительному Pn−5P_{n-5}. Ранние члены проверяются непосредственно по таблице. В начальной части возможны равенства соседей, но начиная с указанного места каждое следующее число строго больше предыдущего. При работе с другими начальными условиями этот вывод заново проверяют: знак разности зависит от знака соответствующего более раннего члена.

Сравнение с другими последовательностями

Рекурсия задаёт зависимость между элементами, но сами элементы могут означать разные объекты. Числа Падована неотрицательны и со временем растут; в модели плиток они считают варианты покрытий. Последовательность Туэ - Морса, напротив, состоит из нулей и единиц и строится по другому правилу. При сравнении последовательностей важно смотреть не только на первые несколько совпавших членов, но и на определяющий закон.

Например, среди первых значений Падована встречаются 1,2,3,51,2,3,5, знакомые по Фибоначчи. Это не означает, что дальнейшие члены совпадут: в одном случае используется сумма соседей, в другом - членов с отступами два и три. Одинаковое значение при разных индексах также не делает правила эквивалентными.

Частые ошибки

  1. Складывать соседние члены. Для P10P_{10} нужны P8P_8 и P7P_7, а не P9P_9 и P8P_8.
  2. Забывать нулевой индекс. Если нумерация начинается с единицы, номер искомого элемента в той же записи чисел сдвигается.
  3. Считать раннее отношение равным пределу. 12/912/9 лишь приближает ρ\rho; на малых индексах отношения заметно колеблются.
  4. Применять модель плиток без сдвига. При принятом здесь определении Pn=Tn+2P_n=T_{n+2}, а не TnT_n.

FAQ

Почему нужны три начальных значения?

Первый вычисляемый член P3P_3 использует P1P_1 и P0P_0, а следующий - P2P_2 и P1P_1. Поэтому правило требует задать стартовое окно из трёх членов, прежде чем продолжать расчёт.

Могут ли два соседних числа совпадать?

Да. Уже в начале P3=P4=2P_3=P_4=2. Равенство соседей не нарушает рекурсию, поскольку ни один из них не обязан равняться сумме непосредственно предшествующих значений.

Является ли пластическое число рациональным?

Нет. По теореме о рациональных корнях возможные целые рациональные корни многочлена r3−r−1r^3-r-1 - только 11 и −1-1, и ни один не подходит. Поэтому его действительный корень иррационален.

Коротко

При P0=P1=P2=1P_0=P_1=P_2=1 последовательность задаётся правилом Pn=Pn−2+Pn−3P_n=P_{n-2}+P_{n-3}. Оно даёт, в частности, P10=12P_{10}=12, а отношения соседних членов стремятся к корню ρ3=ρ+1\rho^3=\rho+1. Та же рекурсия описывает покрытия плитками длины 2 и 3 после учёта сдвига индекса.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Числа Фибоначчи: рекуррентная формула и примеры

Числа Фибоначчи: рекуррентная формула и примеры

Числа Фибоначчи и рекуррентная формула: начальные значения, вычисление по шагам, пример со ступеньками, вычисление членов, формула Бине и связь последовательности с золотым сечением.

8 ноября 20269 минут
Числа Стирлинга первого рода: перестановки и циклы

Числа Стирлинга первого рода: перестановки и циклы

Числа Стирлинга первого рода: что считают знаковые и беззнаковые числа, рекуррентная формула, связь с циклами перестановок, факториалом и нисходящим факториалом, разбор примеров.

20 июня 20268 минут
Метод производящих функций: как ряд решает комбинаторику

Метод производящих функций: как ряд решает комбинаторику

Метод производящих функций: как закодировать последовательность в степенной ряд, вывести формулу общего члена, решить рекуррентность и сосчитать разбиения. Разбор с примерами и типовыми ошибками.

19 июня 20268 минут
Числа трибоначчи: формула и примеры вычисления

Числа трибоначчи: формула и примеры вычисления

Числа трибоначчи: три начальных значения, рекуррентная формула и расчёт по шагам. Как последовательность считает пути по ступенькам и как написать эффективный алгоритм.

8 ноября 20269 минут
Канонические преобразования и производящая функция

Канонические преобразования и производящая функция

Канонические преобразования и производящая функция: что сохраняет каноничность, четыре типа функций F1-F4, условие на скобки Пуассона и разбор на примерах гармонического осциллятора.

19 июня 20268 минут
Абсолютная и относительная погрешность числа

Абсолютная и относительная погрешность числа

Абсолютная и относительная погрешность приближённого числа: формулы, расчёт в процентах, оценка при округлении и подробные примеры сравнения точности.

8 ноября 20268 минут