التوافيق العددية

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 22 صور
الموسوعة الحرة
3 من أصل 4638576 [ 1 ] أو من أصل 580717 [ 2 ] إذا لم تُحتسب الدورانات والانعكاسات كعمليات منفصلة، ​​دورات هاميلتونية على رسم بياني شبكي مربع 8×8

التوافيق العددية هي فرع من فروع التوافيق يهتم بعدد الطرق الممكنة لتكوين أنماط معينة. ومن الأمثلة على هذا النوع من المسائل: عدّ التوافيق وعدّ التباديل . وبشكل أعم، إذا كان لدينا مجموعة لانهائية من المجموعات المنتهية S<sub> i</sub> المفهرسة بالأعداد الطبيعية ، فإن التوافيق العددية تسعى إلى وصف دالة عدّ تحسب عدد العناصر في S <sub>n</sub> لكل قيمة n . ورغم أن حساب عدد العناصر في مجموعة ما يُعدّ مسألة رياضية واسعة النطاق، إلا أن العديد من المسائل التي تظهر في التطبيقات لها وصف توافقي بسيط نسبيًا . توفر الطريقة الاثني عشرية إطارًا موحدًا لحساب التباديل والتوافيق والتقسيمات .

أبسط هذه الدوال هي الصيغ المغلقة ، والتي يمكن التعبير عنها كتركيب لدوال أولية مثل المضروب والقوى وما إلى ذلك. على سبيل المثال، كما هو موضح أدناه، فإن عدد الترتيبات المختلفة الممكنة لمجموعة أوراق لعب مكونة من n ورقة هو f ( n ) = n !. تُعرف مسألة إيجاد صيغة مغلقة بالتعداد الجبري ، وغالبًا ما تتضمن اشتقاق علاقة تكرارية أو دالة مولدة واستخدامها للوصول إلى الصيغة المغلقة المطلوبة.

في كثير من الأحيان، لا تُقدّم الصيغة المغلقة المعقدة سوى القليل من المعلومات حول سلوك دالة العد مع ازدياد عدد العناصر المعدودة. في هذه الحالات، قد يكون التقريب التقاربي البسيط أفضل.ز(ن){\displaystyle g(n)}هو تقريب تقاربي لـو(ن){\displaystyle f(n)}لوو(ن)/ز(ن)→1{\displaystyle f(n)/g(n)\rightarrow 1}مثلن→∞{\displaystyle n\rightarrow \infty }في هذه الحالة، نكتبو(ن)∼ز(ن).{\displaystyle f(n)\sim g(n).\,}

الدوال المولدة

تُستخدم الدوال المولدة لوصف عائلات الكائنات التوافقية. ليكنF{\displaystyle {\mathcal {F}}}لنرمز إلى عائلة الكائنات ولنرمز إلى دالة توليدها F ( x ). عندئذٍ

F(x)=∑ن=0∞ونxن{\displaystyle F(x)=\sum _{n=0}^{\infty }f_{n}x^{n}}

أينون{\displaystyle f_{n}}يرمز إلى عدد العناصر التوافقية ذات الحجم n . وبالتالي، يُعطى عدد العناصر التوافقية ذات الحجم n بمعامل .xن{\displaystyle x^{n}}سنتناول الآن بعض العمليات الشائعة على عائلات الكائنات التوافقية وتأثيرها على الدالة المولدة. تُستخدم الدالة المولدة الأسية أحيانًا، وفي هذه الحالة يكون شكلها كالتالي:

F(x)=∑ن=0∞ونxنن!{\displaystyle F(x)=\sum _{n=0}^{\infty }f_{n}{\frac {x^{n}}{n!}}}

بمجرد تحديد الدالة المولدة، فإنها تُعطي المعلومات التي توفرها الطرق السابقة. إضافةً إلى ذلك، فإن العمليات الطبيعية المختلفة على الدوال المولدة، كالجمع والضرب والتفاضل ، لها دلالة توافقية؛ مما يسمح بتعميم نتائج مسألة توافقية واحدة لحل مسائل أخرى.

الاتحاد

بالنظر إلى عائلتين توافقيتين،F{\displaystyle {\mathcal {F}}}وجي{\displaystyle {\mathcal {G}}}باستخدام الدالتين المولدتين F ( x ) و G ( x ) على التوالي، فإن الاتحاد المنفصل للعائلتين (F∪جي{\displaystyle {\mathcal {F}}\cup {\mathcal {G}}}) لها دالة توليد F ( x ) + G ( x ).

أزواج

بالنسبة لعائلتين توافقيتين كما هو موضح أعلاه، فإن حاصل الضرب الديكارتي (زوج) للعائلتين (F×جي{\displaystyle {\mathcal {F}}\times {\mathcal {G}}}) لها دالة توليد F ( x ) G ( x ).

التسلسلات

تُعمّم المتتالية (المنتهية) فكرة الزوج كما عُرّفت أعلاه. المتتاليات هي حاصل ضرب ديكارتي عشوائي لكائن توافقي مع نفسه. رسميًا:

التسلسل(F)=ϵ ∪ F ∪ F×F ∪ F×F×F ∪⋯{\displaystyle {\mbox{Seq}}({\mathcal {F}})=\epsilon \ \cup \ {\mathcal {F}}\ \cup \ {\mathcal {F}}\!\times \!{\mathcal {F}}\ \cup \ {\mathcal {F}}\!\times \!{\mathcal {F}}\!\times \!{\mathcal {F}}\ \cup \cdots }

لتوضيح ما سبق بالكلمات: سلسلة فارغة، أو سلسلة من عنصر واحد، أو سلسلة من عنصرين، أو سلسلة من ثلاثة عناصر، إلخ. ستكون الدالة المولدة كالتالي:

1+F(x)+[F(x)]2+[F(x)]3+⋯=11-F(x).{\displaystyle 1+F(x)+[F(x)]^{2}+[F(x)]^{3}+\cdots ={\frac {1}{1-F(x)}}.}

الهياكل التوافقية

يمكن الآن استخدام العمليات المذكورة أعلاه لحصر الكائنات التوافقية الشائعة، بما في ذلك الأشجار ( الثنائية والمستوية)، ومسارات ديك، والدورات. يتكون الهيكل التوافقي من ذرات. على سبيل المثال، في الأشجار، تمثل الذرات العقد. يمكن أن تكون الذرات المكونة للكائن إما مُصنفة أو غير مُصنفة. الذرات غير المُصنفة لا يمكن تمييزها عن بعضها البعض، بينما الذرات المُصنفة متميزة. لذلك، بالنسبة لكائن توافقي يتكون من ذرات مُصنفة، يمكن تكوين كائن جديد ببساطة عن طريق تبديل ذرتين أو أكثر.

الأشجار الثنائية والأشجار المستوية

الأشجار الثنائية والأشجار المستوية أمثلة على بنية تركيبية غير مصنفة. تتكون الأشجار من عقد متصلة بحواف بحيث لا توجد دورات . يوجد عادةً عقدة تُسمى الجذر، وليس لها عقدة أب. في الأشجار المستوية، يمكن أن يكون لكل عقدة عدد غير محدد من الأبناء. في الأشجار الثنائية، وهي حالة خاصة من الأشجار المستوية، يمكن أن يكون لكل عقدة إما ابنان أو لا شيء.P{\displaystyle {\mathcal {P}}}لنرمز إلى عائلة جميع الأشجار المستوية. ويمكن تعريف هذه العائلة بشكل متكرر كما يلي:

P={∙}×التسلسل(P){\displaystyle {\mathcal {P}}=\{\bullet \}\times \,{\mbox{Seq}}({\mathcal {P}})}

في هذه الحالة{∙}{\displaystyle \{\bullet \}}يمثل هذا مجموعة من الكائنات المكونة من عقدة واحدة. ولها دالة توليد x . لنرمز إلى دالة التوليد بـ P ( x ).P{\displaystyle {\mathcal {P}}}بتعبير أدق، تتكون الشجرة المستوية من عقدة متصلة بعدد غير محدد من الأشجار الفرعية، كل منها شجرة مستوية أيضاً. وباستخدام العملية على عائلات البنى التوافقية التي طُورت سابقاً، يُترجم هذا إلى دالة توليد تكرارية.

P(x)=x11-P(x){\displaystyle P(x)=x\,{\frac {1}{1-P(x)}}}

بعد حل المعادلة لإيجاد قيمة P ( x ):

P(x)=1-1-4x2{\displaystyle P(x)={\frac {1-{\sqrt {1-4x}}}{2}}}

يمكن الآن تحديد صيغة صريحة لعدد الأشجار المستوية ذات الحجم n عن طريق استخراج معامل x n :

صن=[xن]P(x)=[xن]1-1-4x2=[xن]12-[xن]121-4x=-12[xن]∑ك=0∞(12ك)(-4x)ك=-12(12ن)(-4)ن=1ن(2ن-2ن-1){\displaystyle {\begin{aligned}p_{n}&=[x^{n}]P(x)=[x^{n}]{\frac {1-{\sqrt {1-4x}}}{2}}\\[6pt]&=[x^{n}]{\frac {1}{2}}-[x^{n}]{\frac {1}{2}}{\sqrt {1-4x}}\\[6pt]&=-{\frac {1}{2}}[x^{n}]\sum _{k=0}^{\infty }{{\frac {1}{2}} \choose k}(-4x)^{k}\\[6pt]&=-{\frac {1}{2}}{{\frac {1}{2}} \choose n}(-4)^{n}\\[6pt]&={\frac {1}{n}}{2n-2 \choose n-1}\end{aligned}}}

ملاحظة: يشير الرمز [ xⁿ ] f ( x ) إلى معامل xⁿ في f ( x ). يعتمد مفكوك متسلسلة الجذر التربيعي على تعميم نيوتن لنظرية ذات الحدين . وللانتقال من السطر الرابع إلى الخامس، يلزم إجراء عمليات حسابية باستخدام معامل ذات الحدين المعمم .

العبارة في السطر الأخير تساوي العدد الكاتالاني ( ن - ١) . لذلك، فإن p ن = c ن - ١ .  

انظر أيضاً

مراجع

  1. ↑ (التسلسل A003763 في OEIS )
  2. ↑ (التسلسل A209077 في OEIS )