مقالات

3.6: الأعداد الكاتالونية - الرياضيات


أ شجرة ثنائية متجذرة هو نوع من الرسم البياني له أهمية خاصة في بعض مجالات علوم الكمبيوتر. يتم عرض الشجرة الثنائية النموذجية ذات الجذور في الشكل ( PageIndex {1} ). الرؤوس الموجودة أسفل الرأس والمتصلة بها بواسطة حافة هي أبناء الرأس. إنها شجرة ثنائية لأن كل الرؤوس بها 0 أو 1 أو 2 طفل. كم عدد الأشجار الثنائية ذات الجذور المختلفة الموجودة مع (n ) رؤوس؟

الشكل ( PageIndex {1} ): شجرة ثنائية متجذرة.

دعونا نشير إلى هذا الرقم من خلال (C_n ) ؛ هؤلاء هم الأرقام الكاتالونية. للراحة ، نسمح بأن تكون الشجرة الثنائية ذات الجذور فارغة ، ونترك (C_0 = 1 ). ثم من السهل رؤية (C_1 = 1 ) و (C_2 = 2 ) ، وليس من الصعب رؤية ذلك (C_3 = 5 ). لاحظ أن أي شجرة ثنائية متجذرة على رأس واحد على الأقل يمكن اعتبارها شجرتين ثنائيتين (ربما فارغتين) مرتبطان بشجرة جديدة عن طريق إدخال قمة جذر جديدة وجعل أطفال هذا الجذر هما جذري الأشجار الأصلية ؛ انظر الشكل ( PageIndex {1} ). (لجعل الشجرة الفارغة تابعة للقمة الجديدة ، ببساطة لا تفعل شيئًا ، أي حذف الطفل المقابل.)

الشكل ( PageIndex {1} ): إنتاج شجرة جديدة من الأشجار الصغيرة.

وبالتالي ، لجعل جميع الأشجار الثنائية الممكنة ذات (n ) رؤوسًا ، نبدأ برأس جذر ، ثم بالنسبة لطفليها ، ندرج أشجارًا ثنائية متجذرة على رؤوس (ك ) و (ل ) ، مع ( k + l = n-1 ) ، لجميع الخيارات الممكنة للأشجار الصغيرة. الآن يمكننا الكتابة

$$ C_n = sum_ {i = 0} ^ {n-1} C_iC_ {n-i-1}. $$

على سبيل المثال ، بما أننا نعلم أن (C_0 = C_1 = 1 ) و (C_2 = 2 ) ،

$$ C_3 = C_0C_2 + C_1C_1 + C_2C_0 = 1 cdot2 + 1 cdot1 + 2 cdot1 = 5 ، $$

كما ذكر أعلاه. بمجرد أن نعرف الأشجار الموجودة على رؤوس 0 و 1 و 2 ، يمكننا دمجها بكل الطرق الممكنة لسرد الأشجار على 3 رؤوس ، كما هو موضح في الشكل ( PageIndex {3} ). لاحظ أن الشجرتين الأوليين ليس لهما طفل يسار ، حيث إن الشجرة الوحيدة الموجودة على رأس 0 فارغة ، وبالمثل ، فإن الشجرتين الأخيرين ليس لهما طفل صحيح.

الشكل ( PageIndex {3} ):الأشجار ذات الجذور الثنائية ثلاثية الرؤوس.

نستخدم الآن دالة توليد لإيجاد صيغة لـ (C_n ). دعونا (f = sum_ {i = 0} ^ infty C_ix ^ i ). الآن ضع في اعتبارك (f ^ 2 ): معامل المصطلح (x ^ n ) في توسيع (f ^ 2 ) هو ( sum_ {i = 0} ^ {n} C_iC_ {ni } ) ، المقابلة لجميع الطرق الممكنة لمضاعفة شروط (f ) للحصول على مصطلح (x ^ n ): $$ C_0 cdot C_nx ^ n + C_1x cdot C_ {n-1} x ^ {n-1} + C_2x ^ 2 cdot C_ {n-2} x ^ {n-2} + cdots + C_nx ^ n cdot C_0. $$ الآن نحن ندرك أن هذا هو بالضبط المجموع الذي يعطي (C_ {n + 1} ) ، لذلك (f ^ 2 = sum_ {n = 0} ^ infty C_ {n + 1} x ^ n ). إذا ضربنا هذا في (x ) وأضفنا 1 (وهو (C_0 )) نحصل بالضبط على (f ) مرة أخرى ، أي (xf ^ 2 + 1 = f ) أو (xf ^ 2-و + 1 = 0 ) ؛ هنا 0 هي دالة الصفر ، أي (xf ^ 2-f + 1 ) هي 0 لكل x. باستخدام نظرية فيثاغورس ،

$$ f = {1 pm sqrt {1-4x} أكثر من 2x} ، $$

طالما (س لا = 0 ). ليس من الصعب رؤية أن (س ) يقترب من الصفر ،

$$ {1+ sqrt {1-4x} أكثر من 2x} $$

يذهب إلى ما لا نهاية حين

$$ {1- sqrt {1-4x} over 2x} $$

يذهب إلى 1. بما أننا نعلم (f (0) = C_0 = 1 ) ، هذا هو (f ) الذي نريده.

الآن من خلال نظرية ذات الحدين لنيوتن ، يمكننا التوسع

$$ sqrt {1-4x} = (1 + (- 4x)) ^ {1/2} = sum_ {n = 0} ^ infty {1/2 Choose n} (- 4x) ^ n. $$

ثم

$$ {1- sqrt {1-4x} over 2x} = sum_ {n = 1} ^ infty - {1 over 2} {1/2 Choose n} (- 4) ^ nx ^ { n-1} = sum_ {n = 0} ^ infty - {1 over 2} {1/2 Choose n + 1} (- 4) ^ {n + 1} x ^ n. $$

توسيع المعامل ذي الحدين (1/2 اختر n + 1 ) وإعادة تنظيم التعبير ، نكتشف ذلك

$$ C_n = - {1 أكثر من 2} {1/2 اختر n + 1} (- 4) ^ {n + 1} = {1 over n + 1} {2n Choose n}. $$

في التمرين 7 في قسم 1.2، رأينا أن عدد التسلسلات المتطابقة بشكل صحيح لأقواس الطول (2n ) هو ({2n Choose n} - {2n Choose n + 1} ) ، وسميت هذا (C_n ). ليس من الصعب رؤية ذلك

$$ {2n Choose n} - {2n Choose n + 1} = {1 over n + 1} {2n Choose n}، $$

لذا فإن الصيغ متفق عليها.

اسمح مؤقتًا بـ (A_n ) أن يكون عدد التسلسلات المتطابقة بشكل صحيح لأقواس الطول (2n ) ، لذلك من التمرين نعرف (A_n = {2n Choose n} - {2n Choose n + 1} ). من الممكن أن ترى مباشرةً أن (A_0 = A_1 = 1 ) وأن الأرقام (A_n ) تفي بنفس علاقة التكرار مثل (C_n ) ، مما يعني أن (A_n = C_n ) ، دون التلاعب بوظيفة التوليد.

هناك العديد من مسائل العد التي تبين أن إجاباتها هي الأرقام الكاتالونية. التوافقية العددية: المجلد 2بقلم ريتشارد ستانلي ، يحتوي على عدد كبير من الأمثلة.


شاهد الفيديو: الرياضيات. الأعداد النسبية (ديسمبر 2021).