ЕГЭ 16 · Рекуррентные выражения
Рекуррентная сумма
(Д. Тараскин) Числа Каталана - числовая последовательность, которая часто встречается в задачах комбинаторики. В частности, этим числом можно охарактеризовать количество правильных скобочных последовательностей длины 2n.
Это значение можно посчитать по рекуррентному соотношению:
C_0=1
C_n=Σi=0n-1C_iCn-1-i для n≥ 1
Посчитайте значение функции C12
Подсказка
Начните с базового случая и направления изменения аргумента. Для выражения из нескольких значений сначала проверьте, можно ли сократить общую часть.
Идея решения
Искомая величина: Посчитайте значение функции C_{12}
Создайте таблицу значений C, начиная с C₀ = 1. Для каждого следующего n нужны только уже вычисленные элементы с индексами меньше n.
Для фиксированного n переберите i от 0 до n−1 включительно и сложите произведения Cᵢ · Cₙ₋₁₋ᵢ. Каждый индекс i соответствует отдельному слагаемому; симметричные произведения не нужно удалять как дубликаты.
Последовательно заполните таблицу до индекса, указанного в вопросе. Используйте целые числа: округление и деление здесь не требуются.
Ответ: 208012.