Risoluzione di ricorrenze insolite con due variabili

Question

Ho la seguente relazione di ricorrenza:

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

Con i seguenti casi base (per una data costante$C$):

Per tutti$x \leq C$e per qualsiasi$k$:$T(x,k)=1$

Per tutti$y \geq C$e per qualsiasi$n$:$T(n,y)=1$

Voglio ottenere una formula per$T(n,0)$. Penso che si possa vedere che dopo$i$iterazioni otteniamo la seguente relazione:

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

Ma non so se aiuta e non posso procedere molto oltre.

La mia domanda è$-$quali sono le tecniche giuste per affrontare la ricorrenza con 2 variabili, e in particolare con questa ricorrenza (dove la seconda variabile è crescente)?

Answer 1

Nei casi$C\leq0$e$C\geq n$hai$T(n,0)=1$.

Supponiamo che$0<C<n$. Mostralo$$T(n,0)=\sum_{i=0}^{\color{red}{k}}\binom{\color{red}{k}}{i}T(n-\color{red}{k},i)$$per$0\leq k\leq n-C$e$n\leq 2C$. Sembra che questa sia la formula che hai menzionato nella domanda, tranne per il fatto che il coefficiente binomiale dovrebbe avere lo stesso importo che viene sottratto dalla prima voce di$T$.

Applicalo per$k=n-C$.

Noi abbiamo$$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$la formula che otteniamo è

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

Mettendo$k=n-C$noi abbiamo

$$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)$$

essendo un polinomio di grado$C$.

---

Questa volta non ne avevamo bisogno, ma una tecnica che potrebbe essere utile per lavorare con le ricorrenze è la generazione di funzioni .

Answer 2

Conosci T(n, C) per ogni n. Proverei a determinare T(n, C-1) per tutti gli n, quindi T(n, C-2) e così via.