التَّوافيقيَّات (نظرية ـ)

فارس أبو صالح، محمد خالد شاهين

أسس التَّوافيقيَّات

فروع نظرية التَّوافيقيّات

نظرية التَّوافيقِيَّات combinatorial theory هي فرع من علوم الرياضيات معني بدراسة تراتيب العناصر في مجموعات sets. ويهتم هذا العلم بدراسة المجموعات المنتهيةfinite sets والبنى المنتهية finite structures، من حيث حساب عدد العناصر elements في مجموعة ذات مواصفات معينة، أو عدد البنى الجبرية التي تحقق شروطاً معينة، أو عدد التشكيلات  configurationsالممكِنة لمسألة ما.

تظهر الحاجة إلى التَّوافيقيَّات في العديد من فروع الرياضيات كالجبر والهندسة المنتهية ونظرية المبيان Graph theory ونظرية الاحتمالات Probability theory والطبولوجيا Topology. وللتَّوافيقيَّات أيضاً تطبيقات مهمّة في فروع علمية أخرى كالمعلوماتية والحوسبة العلمية Scientific computing والفيزياء الإحصائية Statistical physics  والكيمياء.

أسس التَّوافيقيَّات

ثمّة طرائق تعدادmethods  counting شهيرة تستخدم بكثرة في مجال التَّوافيقيَّات لحساب عدد عناصر مجموعة معينة، أو حساب عدد التوابع الممكنة بين مجموعتين منتهيتين، والتي تحقق شروطاً محددة، ومن أهم هذه الطرائق:

1- مبدأ برج الحمام:

ينص مبدأ برج الحمام pigeonhole principle (أو مبدأ ديريخْليه Dirichlet&https://arab-ency.com.sy/scitech/details/169994#39;s principle) على أنّه إذا جزَّأنا مجموعة من العناصر عددها n إلى مجموعات جزئية عددها أقل m، فإن واحدة على الأقل من المجموعات الجزئية تحتوي على عنصرين على الأقل.

2- مبدأ الاحتواء والإقصاء:

يمكن إعادة صياغة الكثير من المسائل المدروسة في النظرية التوافيقية بحيث تؤول إلى مسألة تعداد عناصر اجتماع عدة مجموعات. ويمكن عندها استخدام مبدأ الاحتواء والإقصاء inclusion-exclusion principle الذي ينص على أنه بفرض المجموعة M، وبفرض    A₁,…A_n مجموعات جزئية منتهية من M؛ يمكن حساب عدد عناصر اجتماع هذه المجموعات باستخدام العلاقة (1):

وتُعطى فيها N_k بالعلاقة (2):

وتعبّر الأدلة  عن القيم الطبيعية الواقعة بين العددين 1 وn ، ويمثّل العدد N_k  مجموع عدد عناصر التقاطعات المشكّلة من k مجموعة مختلفة، أي:

ومن ثمَّ يعطى عدد عناصر اجتماع هذه المجموعات بالعلاقة (3):

3- عدد المجموعات الجزئية:

إذا كانتM مجموعة منتهية عدد عناصرها m يُرمز إلى مجموعة أجزاءM بالرمز، أي مجموعة كل المجموعات الجزئية subsets من M، ويُعطى عدد المجموعات الجزئية من M بالصيغة .

4- عدد المجموعات الجزئية المكوَّنة من عدد محدد من العناصر:

لتكنM مجموعة منتهية عدد عناصرها m؛ يُعطى عدد المجموعات الجزئية منM التي تعداد كل منها يساويn  بالعلاقة (4):

إذ إن:  

5- عدد الطرائق المختلفة لتباديل عناصر مجموعة منتهية:

يُرمز إلى عدد التباديل (التراتيب) number of permutations الممكنة لمجموعة Mعدد عناصرها بالرمز P(m, n) ، ويُعطى هذا العدد بالعلاقة (5):

من جهة أخرى فإنّ العدد   P(m, n) يساوي أيضاً عدد الدوالّ (التوابع) المتباينة injective functions من مجموعة تعدادها n إلى أخرى تعدادها

6- عدد التجزئات:

يُعطى عدد الطرائق الممكنة لتجزئة  partition مجموعة منتهية تعدادهاm  إلى n مجموعة جزئية غير خالية بالعلاقة (6):

ويُطلق على عدد الطرائق الممكنة للتجزئة S(m, n)  أعداد ستيرلِنْغ من النوع الثاني Stirling numbers of the second kind. ويبيّن الجدول (1) أعداد ستيرلينغ من النوع الثاني، ويمثل فيه العنصر الواقع في العمود n والسطر  mعدد التجزئات الممكنة لمجموعة من m عنصر إلى n  مجموعة جزئية غير خالية.

الجدول (1) أعداد ستيرلينغ من النوع الثاني

7- عدد الدوال الغامرة من مجموعة إلى أخرى:

 يُعطى عدد التوابع الغامرة subjective functions من المجموعةM  التي تعدادهاm  إلى المجموعة M'  التي تعدادهاn  بالصيغة n!S(m, n)؛ حيث S(m, n)  يرمز إلى أعداد ستيرلينغ من النوع الثاني.

8- العلاقات الارتداديّة:

تستخدم العلاقات الارتدادية  recurrence relationsبكثرة لحساب عدد الطرائق الممكنة لتشكيلة معينة؛ كحساب عدد الطرائق الممكنة لكتابة عدد كمجموع للعددين 1 و2 على سبيل المثال.

فإذا مثَّل الرمز r_n  عدد طرائق كتابة العدد n كمجموع للعددين 1 و2؛ فيكون  r₁=1 و r₂=2. ولكتابة العدد n+1 بالشكل المطلوب يُبدأ بكتابته بإحدى الطريقتين 2+(n-1) أو 1+n. وتعطي الطريقة الأولى r_n-1   كتابة مختلفة. أما الطريقة الثانية فتعطي r_n  كتابة مختلفة، ومن ثمَّ تكون العلاقة (7) محققة، وهي علاقة ارتداديّة خطية.

9- التوابع المولِّدة:

تظهر الحاجة في الكثير من مسائل التوافيقيات إلى تعيين قيم متتالية أعداد، غالباً ما تكون معرّفة بوساطة علاقة ارتدادية؛ ويمكن دراسة الكثير من هذه المتتاليات بربطها بدالة وفق الصيغة المبيّنة بالعلاقة (8):

وفيها يمثل X متغيراً (متحولاً) صوريّاً  formal(حقيقي أم عقدي)؛ ويطلق على الدالة F(X) مسمى الدالة المولّدة generating function للمتتالية. وبعد تعريف هذه الدالة تُدرس خواصّها، كالمعادلات التفاضلية differential equations التي يحققها مثلاً، والتي تسمح بالحصول على صيغ بسيطة له، ثم تُستنبط صيغة المتتالية نفسها.

10- صيغة موِبيوس التعاكسية:

تُعدّ صيغة موبيوس التعاكسية bius inversion formula MÖ تعميماً لمبدأ الاحتواء والإقصاء، ولهذه الصيغة تطبيقات كثيرة في الرياضيات وفي الفيزياء وبصورة خاصة في نظرية الأعداد، وفي حل الكثير من المسائل التَّوافيقيّة.

فروع نظرية التَّوافيقيّات

يمكن تقسيم المواضيع التي تُعنى بها التوافيقيات إلى عدة فروع، إلا أنّ هذه الفروع ليست منفصلة بعضها عن بعض بل تترابط فيما بينها وتتقاطع على نحو كبير، ويتمثل الهدف من هذا التصنيف في تسهيل الدراسة فحسب.

1- التوافيقيات الجبرية:  

يمكن تعريف التوافيقيات الجبرية  algebraic combinatoricsبأنها تنطوي على أغراض objects يمكن تفسيرها توافيقياً وجبرياً أيضاً، مثل كارديناليّة cardinality مجموعة معرّفة توافيقياً، وبعد فضاء شعاعي معرّف جبرياً. وفي بعض الأحيان يستعمل التفسير التوافيقي للحصول على نتيجة جبرية، وفي أحيان أخرى العكس بالعكس.  

أي إن التوافيقيات الجبرية algebraic combinatorics فرع من الرياضيات يهتم بدراسة مسائل التعداد والإنشاء التي تظهر في البنى الجبرية المختلفة، وكذلك حل مسائل التوافيقيات باستخدام التقنيات التي يوفرها الجبر.

2- التوافيقيات التحليلية:

التوافيقيات التحليلية analytic combinatorics فرع من الرياضيات يهدف إلى تمكين تنبؤات كمية دقيقة بخصائص بنى توافيقية كبيرة، وذلك بالربط بوساطة دوال مولّدة بين أوصاف صوريّة للبنى التوافيقية وطرائق من التحليل العقدي والتقاربي asymptotic.

وتسمح التوافيقيات التحليلية في إيجاد صيغ مقاربة  asymptotic formulaلتعداد مجموعات عدد عناصرها كبير، وذلك باستخدام تقنيات الاحتمالات والتحليل العقدي.

ومن الأمثلة على الصيغ المقاربة المسألة التي حلّها الرياضيّان مونمورتMontmort  وبرنولي Bernoulli في مطلع القرن الثامن عشر، وهي: بفرض دخول n من الأشخاص إلى مطعم، كل منهم يضع قبعة على رأسه، وقام كل شخص بتسليم القبعة إلى عامل الاستقبال في المطعم. وبفرض أنّ عامل الاستقبال نسي تسجيل كل قبعة باسم صاحبها، فقام بتسليم القبعات عشوائياً إلى الزبائن عند خروجهم من المطعم؛ ما هو احتمال ألّا يحصل أي من الزبائن على قبعته الأصلية؟

لحل هذه المسألة تعدّ الطرائق المختلفة لإعادة ترتيب مجموعةM  = {a₁, a₂, …, a_n}  مكوَّنة منn  من الأغراض بحيث لا يعود غرض إلى مكانه، ويسمى هذا النوع من إعادة الترتيب بالتبديل الفعلي derangement. ويُستخدم مبدأ الاحتواء والإقصاء لحساب عدد هذه التبديلات، والذي يُعطى بالعلاقة (9):

وعندما يكون العدد  n كبيراً يعطى احتمال ألّا يحصل أي زبون على قبعته الأصلية بالعلاقة (10):

3- التوافيقيات المتعلّقة بنظرية البيان:

البيان graph هو تمثيل مجرد abstract representation إلى حد ما لبعض الأغراض المرتبطة على نحو ما فيما بينها، ولعلاقات الارتباط هذه. وترسم الأغراض بصورة نقاط  dotsتدعى الرؤوس vertices، ويقوم خط line (أو منحني curve) بربط أي رأسين يمثلان أغراض مرتبطة أو متجاورة؛ ويطلق على هذا الخط اسم حافة edge. ويسمح عادة للحواف أن تتقاطع في رسم (نظراً لأنه قد يكون من المستحيل رسم خطوط لكل العلاقات من دون أن تتقاطع)؛ ويجري إظهار الرؤوس كنقاط ممتلئة fat dots باعتدال؛ للتمييز بينها وبين تقاطعات الحواف العشوائية.

تهتم نظرية التوافيقيات بحساب عدد البيانات graphs التي تحقق شروطاً معينة؛ كحساب عدد البيانات التي لا تحوي أي حلقة cycle، أو عدد البيانات التي تحوي حلقات من نوع خاص فقط كالحلقات الهاملتونية Hamiltonian cycles. ومن المسائل المهمّة في هذا الفرع:

أ- حساب عدد الشجرات الاثنانية

تستعمل بنى المعطيات الشجرية tree data structure، وهي بنى تراتبية لتمثيل المعطيات وتنظيمها على شكل علاقة آباء وأبناء parent child relationship. أما الشجرة الاثنانية binary tree فهي نوع من بنى المعطيات الشجرية يمكن فيه لكل عقدة امتلاك عدد عقد ابن child node لا يتجاوز اثنين، يطلق عليهما العقدة اليمنى والعقدة اليسرى. ويبيّن الشكل (1) مثالاً على شجرة اثنانية.

الشكل (1) مثال على شجرة إثنانية.

يُرمز بالرمز C_n  إلى عدد الشجرات الاثنانية الممكنة على n عقدة. ويمكن النظر لشجرة اثنانية على أنها رأس S تتفرّع منه شجرتان: شجرة يمنى R عدد عقدها K، وشجرة يسرى L عدد عناصرها n - k ؛ وتجدر الإشارة إلى أنه قد تكون إحداهما أو كلاهما خالية.

ويسمح التفريق decomposition إلى شجرتين بكتابة علاقة تدريجية تحققها الأعداد C_n التي تسمى أعداد كاتلان Catalan، كما هو مبيّن بالعلاقة (11):

ولإيجاد القيمC_n  يمكن استخدام مفهوم التوابع المولّدة للحصول على العلاقة (12):

ب- حساب عدد التلوينات الممكنة لبيان

يقصد بتلوين coloring البيان إسناد assignment لون لكل رأس vertex في البيان بحيث لا يسند إلى رأسين متجاورين اللون نفسه؛ مع مراعاة تصغير العدد الكلي للألوان المستخدمة. وتلوين البيان مسألة استمثال شائعة الدراسة في نظرية البيان، ولها تطبيقات متعددة في العالم الحقيقي، مثل الجدولة scheduling وتحصيص الترددات frequency allocation. 

وقد توصل الرياضي بوليا Polya في العام  1937إلى صيغة عامة لتعداد تلوينات بيان مع مراعاة التلوينات المتماثلة التي تنتج من بعضها باستخدام تحويلات معينة. وكان لبحث بوليا حول عدد التلوينات الممكنة أهمية كبيرة في مجالات عدّة منها الكيمياء؛ حيث يسهّل حساب الطرائق المختلفة لتكوّن جزيء ما من ارتباط ذرات مختلفة بعضها ببعض.

4- الاستمثال التوافيقي:

الاستمثال التوافيقي فرع من الاستمثال الرياضي في الرياضيات التطبيقية يعنى بإيجاد أفضل حل من ضمن مجموعة منتهية من الحلول الممكنة، وغالباً ما يتضمن المسائل المتعلقة بالبنى المتقطعة discrete structures. والاستمثال التوافيقي يؤدي دوراً مهمّاً في تطبيقات متنوعة منها تصميم الشبكات والجدولة وتحصيص الموارد بهدف تعظيم المردود efficiency وتصغير التكاليف أو الزمن. ومن أشهر المسائل التي تندرج تحت هذا الفرع مسألة حقيبة الظهر knapsack problem، وفيها يُراد اختيار عدد من الأغراض من ضمن مجموعة محددة من الأغراض، لكل منها وزن وتكلفة محددين. والبحث هو عن الاختيار الذي يحقق أكبر تكلفة ممكنة، شريطة ألا يتجاوز الوزن الكلي حداً معيناً. وتجدر الإشارة إلى توافر خوارزميات مختلفة لحل هذا النوع من المسائل.

5- التصميم التوافيقي:

التصميم التوافيقي combinatorial design هو ترتيب arrangement لأغراض مجموعة في مجموعات جزئية يحقق خاصيات محددة. ويعتمد الكثير من طرائق بناء التصاميم التوافيقية على البنية الجبرية المسماة الحقل المنتهي finite field.   

ويعدّ المربع اللاتيني Latin square نوع محدد من التصميم التوافيقي يتميز بشبكة grid أبعادها n×n عامرة برموز متمايزة distinct symbols عددها n، بحيث يظهر في الشبكة كل رمز مرة واحدة في كل عمود وفي كل سطر.

6- التوافيقيات الهندسية:

التوافيقيات الهندسية Geometric combinatorics فرع من الرياضيات يعنى بدراسة الأغراض الهندسية وبناها التوافيقية. وتعالج التوافقيات الهندسية مسائل العد التي تطرحها الهندسة المنتهية finite geometry أو المتقطعة discrete أو الهندسة المحدبةconvex ؛ كدراسة المضلعات وتعداد حروفها أو سطوحها.

7- التوافيقيات في نظرية اللغات الصورية:

تهتم التوافيقيات في نظرية اللغات الصورية formal languages بمسائل تخص الهندسة المعلوماتية، كحساب عدد الكلمات التي يمكن إنشاؤها انطلاقاً من حروف محددة ووفق قواعد محددة أيضاً، مثل عدد الكلمات التي طولها n، والتي يمكن تشكيلها من الحروف  {a, b, c} بحيث لا يتعاقب حرفان متشابهان.