Résoudre la récurrence inhabituelle avec deux variables

Question

J'ai la relation récurrence suivante:

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

Avec les cas de base suivants (pour une certaine constante $ C $ ):

pour tous $ x \ leq c $ et pour tout $ k $ : $ t (x, k)= 1 $

pour tous $ y \ geq c $ et pour tout $ n $ : $ t (n, y)= 1 $

Je veux obtenir une formule pour $ t (n, 0) $ . Je pense que cela peut être vu qu'après $ i $ itérations Nous obtenons la relation suivante:

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

Mais je ne sais pas si cela aide et ne peut pas continuer beaucoup plus loin que cela.

Ma question est $ - $ quelles techniques appropriées pour traiter de la récurrence avec 2 variables, et en particulier avec cette récurrence (où la deuxième variable augmente) ?

Answer 1

dans les cas $ c \ leq0 $ et $ c \ geq n $ vous avez $ T (n, 0)= 1 $ .

suppose que 0 $ . Montre CA $$ t (n, 0)=somm_ {i= 0} ^ {\ couleur {rouge} {k}} \ binom {\ couleur {rouge} {k}} { i} t (n- \ couleur {rouge} {k}, i) $$ pour $ 0 \ LEQ K \ LEQ N-C $ et $ n \ leq 2c $ . Il semble que ceci est la formule que vous avez mentionnée dans la question, sauf que le coefficient binomial devrait avoir le même montant soustrait de la première entrée de $ t $ .

Appliquer-le pour $ K= N-C $ .

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

si $ N> 2c $ La formule que nous obtenons est

$$ t (n, 0)=sum_ {i= 0} ^ {\ couleur {rouge} {c}} \ binom {\ couleur {rouge} {k }} {i} t (n- \ couleur {rouge} {k}, i) $$

mettre $ k= n-c $ nous obtenons

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

puisqu'il s'agit d'un polynôme de degré $ C $ .

---

Nous n'avons pas besoin de cela cette fois-ci, mais une technique qui pourrait être utile pour travailler avec des récurrences est Fonctions génératrices .

Answer 2

Vous savez t (n, c) pour tous n.J'essaierais de déterminer T (N, C-1) pour tous N, puis T (n, C-2) et ainsi de suite.