2つの変数で異常な再発を解決する
私は次の漸化式を持っています：
$$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\choose{j}}\cdot T(n-i,j)$
しかし、それが役立つかどうかはわかりませんし、それ以上進むことはできません。
私の質問は $-$ 2つの変数、特にこの再発（2番目の変数が増加している場合）を処理するための適切な手法は何ですか？
回答
場合 $C\leq0$ そして $C\geq n$ あなたが持っている $T(n,0)=1$。
と仮定する $0<C<n$。それを示す$$T(n,0)=\sum_{i=0}^{\color{red}{k}}\binom{\color{red}{k}}{i}T(n-\color{red}{k},i)$$ にとって $0\leq k\leq n-C$ そして $n\leq 2C$。二項係数は、の最初のエントリから減算されるのと同じ量である必要があることを除いて、これは質問で言及した式のように見えます$T$。
にそれを適用します $k=n-C$。
我々が得る $$T(n,0)=\sum_{i=0}^{n-C}\binom{n-C}{i}T(C,i)=\sum_{i=0}^{n-C}\binom{n-C}{i}=2^{n-C}$$
場合 $n>2C$ 私たちが得る式は
$$T(n,0)=\sum_{i=0}^{\color{red}{C}}\binom{\color{red}{k}}{i}T(n-\color{red}{k},i)$$
パッティング $k=n-C$ 我々が得る
$$T(n,0)=\sum_{i=0}^{C}\binom{n-C}{i}T(C,i)=\sum_{i=0}^{C}\binom{n-C}{i}\in O(n^C)$$
次数の多項式なので $C$。
今回は必要ありませんでしたが、繰り返しを処理するのに役立つ可能性のある手法は、関数を生成することです。
あなたはすべてのnについてT（n、C）を知っています。すべてのnについてT（n、C-1）を決定し、次にT（n、C-2）などを決定しようとします。