解决两个变量的异常再次发生

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 $ 迭代之后，我们得到以下关系：

$ 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 {红色} {k}} \ binom {\ color {红色} {k}} { i} t（n- \ color {红色} {k}，i）$$ 对于 $ 0 \ leq k \ leq n-c $ 和 $ n \ leq 2c $ 。它看起来这是你在问题中提到的公式，除了二项系系数应该具有与<跨度类=“math-container”> $ 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）$$

putting $ k= n-c $ 我们得到

$$ t（n，0）=sum_ {i= 0} ^ {c} \ binom {nc} {i} t（c，i）=sum_ {i= 0} ^ {c} \ binom {nc} {i} \ in o（n ^ c）$$

由于它是一个程度 $ c $ 。

的多项式

---

我们这个时候不需要它，但是一种可以使用重复使用的技术是生成函数。

Answer 2

你知道所有n的t（n，c）。我会尝试为所有n确定t（n，c-1），然后是t（n，c-2）等。