حل تكرار غير عادي مع اثنين من المتغيرات

Question

لدي العلاقة المتكررة التالية:

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

مع الحالات الأساسية التالية (لبعضها البعض ثابت $ C $ ):

لجميع $ x \ leq c $ ولأي $ k $ : $ t (x، k)= 1 $

لجميع $ y \ geq c $ ولأي $ n $ : $ t (n، y)= 1 $

أريد الحصول على صيغة ل $ t (n، 0) $ . أعتقد أنه يمكن أن ينظر إليه بعد $ i $ التكرار نحصل على العلاقة التالية:

$ t (n، 0)=sum_ {j= 0} ^ i {n \ اختر {j}} \ cdot t (ni، j) $

لكنني لا أعرف إذا كان ذلك يساعد ولا يمكنك متابعة أبعد من ذلك.

سؤالي هو $ - $ ما هي التقنيات المناسبة للتعامل مع تكرار مع 2 متغيرات، ولا سيما مع هذا التكرار (حيث يتزايد المتغير الثاني)

Answer 1

في الحالات $ c \ leq0 $ و $ c \ geq n $ لديك $ t (n، 0)= 1 $ .

افترض أن $ 0 . اظهر ذلك $$ t (n، 0)=sum_ {i= 0} {{red} {red} {}} {\ color {red} {k}} { i} t (n- \ color {red} {k}، i) $ ل $ 0 \ leq k \ leq n-c $ و $ n \ leq 2c $ . يبدو أن هذه هي الصيغة التي ذكرتها في السؤال، إلا أن المعامل ذو الحدين يجب أن يكون له نفس المبلغ الذي يتم طرحه من الدخول الأول من $ t $ .

تطبيقه ل $ k= n-c $ .

نحصل على $$ t (n، 0)=sum_ {i= 0}} {nc} \ binom {nc} {i} t (c، i)=sum_ {i= 0} ^ {nc} \ binom {nc} {i}= 2 ^ {nc} $$

إذا كان $ n> 2c $ الصيغة التي نحصل عليها هي

$$ T (N، 0)=sum_ {i= 0} {{red} {c}} {c}} \ binom {red} {k }} {I} t (n- \ color {red} {k}، I) $

وضع $ k= n-c $ نحصل على

$$ T (N، 0)=sum_ {i= 0} ^ {c} \ binom {nc} {i} t (c، i)=sum_ {i= 0} ^ {c} \ binom {nc} {I} \ in O (n ^ c) $

لأنه كثير الحدود من درجة $ c $ .

---

لم نحتاج إليها هذه المرة، ولكن تقنية قد تكون مفيدة للعمل مع تكرار هي توليد الوظائف .

Answer 2

تعرف t (n، c) للجميع n.سأحاول تحديد T (N، C-1) للجميع N، ثم T (N، C-2) وما إلى ذلك.