Ungewöhnliche Wiederholung mit zwei Variablen lösen
-
29-09-2020 - |
Frage
Ich habe folgende Rezidivrelation:
$$ t (n, k)= t (n-1, k) + t (n-1, k + 1) $$ .
mit den folgenden Basisfällen (für einige gegebene Konstante
für alle $ x \ leq c $ und für jeden $ k $ : $ t (x, k)= 1 $
für alle $ y \ geq c $ und für jeden $ n $ : $ t (n, y)= 1 $
Ich möchte eine Formel für $ t (n, 0) $ erhalten. Ich denke, dass es zu sehen ist, dass nach
$ t (n, 0)=sum_ {j= 0} ^ i {n \ Wählen Sie {j}} \ cdot t (ni, j) $
Aber ich weiß nicht, ob es hilft und nicht viel weiter vorgehen kann.
meine Frage ist $ - $ Was sind die richtigen Techniken für den Umgang mit 2 Variablen und insbesondere mit diesem Wiederauftreten (wo die zweite Variable zunimmt)
Lösung
in den Fällen $ c \ leq0 $ und $ c \ geq n $ Sie haben
Nehmen Sie an, dass $ 0
Anwenden Sie es für $ k= N-C $ .
wir erhalten $$ t (n, 0)=sum_ {i= 0} ^ {nc} \ binom {nc} {i} t (c, i)=sum_ {i= 0} ^ {nc} \ binom {nc} {i}= 2 ^ {nc} $$
wenn $ n> 2c $ die Formel, die wir bekommen, ist
$$ t (n, 0)=sum_ {i= 0} ^ {\ color {rot} {c}} \ Binom {\ color {rot} {k }} {i} t (n- \ color {rot} {k}, i) $$
Setzen
$$ t (n, 0)=sum_ {i= 0} ^ {c} \ binom {nc} {i} t (c, i)=sum_ {i= 0} ^ {c} \ binom {nc} {i} \ in o (n ^ c) $$
Da es sich um ein Polynom von Grad $ C $ handelt.
Wir brauchten es diesmal nicht, sondern eine Technik, die nützlich sein könnte, um mit Wiederholungen zu arbeiten, ist Funktionen erstellen .
Andere Tipps
Sie kennen t (n, c) für alle n.Ich würde versuchen, t (n, c-1) für alle n, dann t (n, c-2) usw.) und so weiter.