Risolvere la ricorrenza insolita 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 di base (per qualche dato costante $ c $ ):

per tutti $ x \ leq c $ e per qualsiasi classe $ k $ : $ t (x, k)= 1 $

per tutte le $ y \ geq c $ e per qualsiasi classe $ N $ : $ t (n, y)= 1 $

Voglio ottenere una formula per $ t (n, 0) $ . Penso che possa essere visto che dopo $ i $ iterazioni otteniamo la seguente relazione:

$ t (n, 0)=sum_ {j= 0} ^ i {n \ Scegli {j}} \ clot t (ni, j) $

Ma non so se aiuta e non può procedere molto oltre.

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

Answer 1

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

Supponiamo che $ 0 . Mostralo $$ T (N, 0)=Sum_ {i= 0} ^ {\ Color {RED} {K}} \ BINOM {\ Color {RED} {K}} { I} t (n- \ colore {rosso} {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 che il coefficiente binomiale dovrebbe avere la stessa quantità che viene sottratta dalla prima voce di $ T $ .

Applicalo per $ k= n-c $ .

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

Se $ n> 2c $ La formula che otteniamo è

$$ t (n, 0)=sum_ {i= 0} ^ {\ color {rosso} {c}} \ binom {\ color {rosso} {k }} {i} t (n- \ colore {rosso} {k}, i) $$

Mettere $ k= n-c $ Otteniamo

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

Poiché è un polinomio di grado $ c $ .

---

.

Non avevamo bisogno questa volta, ma una tecnica che potrebbe essere utile lavorare con le recidive è Generazione di funzioni .

Answer 2

Conosci t (n, c) per tutto n.Proverò a determinare t (n, c-1) per tutti n, quindi t (n, c-2) e così via.