Solução incomum recorrência com duas variáveis

Question

Eu tenho a seguinte relação de recorrência:

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

Com a seguinte base de casos (por algum dado constante $C$):

Para todos $x \leq C$ e para qualquer $k$: $T(x,k)=1$

Para todos $y \geq C$ e para qualquer $n$: $T(n,y)=1$

Eu quero começar uma fórmula para $T(n,0)$.Eu acho que ele pode ser visto que, depois de $i$ iterações obtemos a seguinte relação:

$T(n,0) = \sum_{j=0}^i {n\choose{j}}\cdot T(n-i,j)$

Mas eu não sei se isso ajuda e não pode continuar muito mais do que isso.

A minha pergunta é $-$ quais são as técnicas para lidar com a recorrência com 2 variáveis, e em particular com a recorrência (onde a segunda variável é crescente)?

Answer 1

Nos casos $C\leq0$ e $C\geq n$ você tem $T(n,0)=1$.

Suponha que R $0.Mostrar que $$T(n,0)=\sum_{i=0}^{\color{red}{k}}\binom{\color{red}{k}}{i}T(n-\color{red}{k},i)$$ para R $0\leq k\leq n-C$ e $n\leq 2C$.Parece que essa é a fórmula que você mencionou na questão, exceto que o coeficiente binário deve ter a mesma quantidade que está a ser deduzido a partir da primeira entrada de $T$.

Aplicá-lo para $k=n-C$.

Temos $$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}$$

Se $n>2C$ a fórmula que temos é

$$T(n,0)=\sum_{i=0}^{\color{red}{C}}\binom{\color{red}{k}}{i}T(n-\color{red}{k},i)$$

Colocar $k=n-C$ temos

$$T(n,0)=\sum_{i=0}^{C}\binom{n-C}{i}T(C,i)=\sum_{i=0}^{C}\binom{n-C}{i}\em O(n^C)$$

uma vez que é um polinômio de grau $C$.

---

Nós não precisamos desta vez, mas uma técnica que pode ser útil para o trabalho com recorrências funções geradoras de.

Answer 2

Você sabe que T(n, C) para todo n.Eu ia tentar determinar T(n, C-1) para todo n, então T(n, C-2) e assim por diante.