Решение необычного рецидива с двумя переменными

Question

У меня есть следующие отношения рецидива:

$$ t (n, k)= t (n - 1, k) + t (n - 1, k + 1) $$

со следующими базовыми случаями (для некоторой данной постоянной $ C $ ):

Для всех $ x \ leq c $ и для любого $ k $ : $ t (x, k)= 1 $

Для всех $ y \ geq c $ и для любого $ n $ : $ T (n, y)= 1 $

Я хочу получить формулу для $ t (n, 0) $ . Я думаю, что видно, что после $ i $ iTerations Мы получаем следующее отношение:

$ t (n, 0)=sum_ {j= 0} ^ i {n \ Выберите {j}} \ cdot t (ni, j) $

Но я не знаю, помогает ли это и не может продолжаться намного дальше, чем это.

Мой вопрос - $ - $ Каковы правильные методы для решения рецидива с 2 переменными, и, в частности, с этим рецидивом (где растут вторая переменная) ?

Answer 1

в случаях $ c \ leq0 $ и $ c \ geq n $ у вас есть $ T (n, 0)= 1 $ .

Предположим, что $ 0 . Покажи это $$ t (n, 0)=sum_ {i= 0} ^ {\ color {RED} {k}} \ binom {\ color {красный} {k}} { i} t (n- \ color {красный} {k}, i) $$ Для $ 0 \ leq k \ leq n-c $ и $ n \ leq 2c $ . Похоже, что это формула, которую вы упомянули в этом вопросе, за исключением того, что биномиальный коэффициент должен иметь ту же сумму, которая вычитается из первой записи $ T $ ,

Примените его для $ k= n-c $ .

Мы получаем $$ t (n, 0)=sum_ {i= 0} ^ {nc} \ binom {nc} {i} t (c, i)=sum_ {i= 0} ^ {nc} \ binom {nc} {i}= 2 ^ {nc} $$

Если $ n> 2C $ Формула, которую мы получаем, это

$$ t (n, 0)=sum_ {i= 0} ^ {\ color {красный} {c}} \ binom {\ color {красный} {k }} {i} t (n- \ color {красный} {k}, i) $$

Помещение $ k= n-c $ Мы получаем

$$ t (n, 0)=sum_ {i= 0} ^ {c} \ binom {nc} {i} t (c, i)=sum_ {i= 0} ^ {c} \ binom {nc} {i} {nc} {i} \ in o (n ^ c) $$

Поскольку это полиномиальная степень $ C $ .

---

Нам не нужно было это время, но техника, которая может быть полезной для работы с рецидивами, является Генерация функций .

Answer 2

Вы знаете t (n, c) для всех n.Я бы попытался определить t (n, c-1) для всех n, то t (n, c-2) и т. Д.