نظرية بوليا للعد (Pólya Enumeration Theorem)

<![CDATA[

مقدمة إلى نظرية بوليا

تتعامل نظرية بوليا مع المواقف التي نرغب فيها في حساب عدد التكوينات المميزة، ولكن ليس كل التكوينات تبدو مختلفة حقًا. لنأخذ مثالًا بسيطًا: لنفترض أننا نريد تلوين رؤوس مربع بألوان مختلفة، على سبيل المثال، الأحمر والأزرق. إذا لم نعتبر أي تناظر، فسيكون لدينا 2⁴ = 16 طريقة لتلوين الرؤوس. ومع ذلك، إذا كان بإمكاننا تدوير المربع، فإن بعض هذه الألوان ستصبح متطابقة. على سبيل المثال، إذا كانت جميع الرؤوس الأربعة زرقاء، فإنه لا يهم كيف ندور المربع، فستظل النتيجة هي نفسها. لكن ماذا عن التلوينات الأخرى؟ هنا يأتي دور نظرية بوليا.

توفر نظرية بوليا طريقة منهجية لأخذ هذه التناظرات في الاعتبار عند حساب عدد التكوينات المميزة. إنها تعتمد على مفهوم دورة المؤشر (cycle index) لمجموعة من التبديلات، والتي تمثل معلومات حول هيكل الدورة للتبديلات في المجموعة.

المفاهيم الأساسية

لفهم نظرية بوليا، نحتاج إلى فهم بعض المفاهيم الأساسية:

المجموعة (Group): المجموعة هي مجموعة من العناصر مع عملية ثنائية (مثل الضرب) التي تفي بشروط معينة، مثل التجميعية، ووجود عنصر محايد، ووجود معكوس لكل عنصر.
التبديل (Permutation): التبديل هو دالة تقوم بإعادة ترتيب عناصر مجموعة ما. يمكن تمثيل التبديل في شكل دورات، حيث تمثل كل دورة مجموعة من العناصر التي يتم تبديلها بشكل دوري.
دورة التبديل (Cycle of a Permutation): إذا كان لدينا تبديل ما، فإن الدورة هي سلسلة من العناصر حيث يتم إرسال كل عنصر إلى العنصر التالي في السلسلة، ويتم إرسال العنصر الأخير في السلسلة إلى العنصر الأول. على سبيل المثال، في التبديل (1 2 3)، يتم إرسال 1 إلى 2، و 2 إلى 3، و 3 إلى 1.
دورة المؤشر (Cycle Index): دورة المؤشر لمجموعة من التبديلات هي متعددة حدود في عدة متغيرات، حيث يمثل كل متغير عدد الدورات ذات الطول المقابل في التبديلات. على وجه التحديد، إذا كانت لدينا مجموعة G من التبديلات التي تعمل على مجموعة X، فإن دورة المؤشر يُعطى بالصيغة التالية:

Z(G) = (1/|G|) * Σ_g∈G x₁^c₁(g) * x₂^c₂(g) * … * x_n^c_n(g)

حيث:

|G| هو عدد العناصر في المجموعة G.
g هو عنصر في المجموعة G.
c_i(g) هو عدد الدورات ذات الطول i في التبديل g.
x_i هي متغير يمثل الدورات ذات الطول i.

صياغة نظرية بوليا

تنص نظرية بوليا على أنه إذا كانت لدينا مجموعة G من التبديلات التي تعمل على مجموعة X، وإذا أردنا تلوين عناصر المجموعة X بمجموعة من الألوان C، فإن عدد التكوينات المميزة (حتى التكافؤ) يُعطى بالصيغة التالية:

Number of distinct configurations = Z(G; |C|, |C|, …, |C|)

حيث Z(G) هو دورة المؤشر للمجموعة G، و |C| هو عدد الألوان المتاحة. بمعنى آخر، نستبدل كل متغير x_i في دورة المؤشر بعدد الألوان المتاحة.

مثال توضيحي: تلوين رؤوس المربع

دعونا نطبق نظرية بوليا لحساب عدد الطرق المختلفة لتلوين رؤوس مربع بألوان مختلفة، مع الأخذ في الاعتبار أننا يمكننا تدوير المربع. لدينا أربعة رؤوس، ولنفترض أن لدينا لونين: الأحمر والأزرق. المجموعة G من التبديلات هي مجموعة الدورات الناتجة عن تدوير المربع بزوايا 0، 90، 180، و 270 درجة.

التدوير بزاوية 0 درجة: هذا هو التبديل المحايد، ولا يغير ترتيب الرؤوس. يمكن تمثيله بالصورة (1)(2)(3)(4)، أي أربع دورات ذات الطول 1.
التدوير بزاوية 90 درجة: هذا التبديل يرسل الرأس 1 إلى الرأس 2، والرأس 2 إلى الرأس 3، والرأس 3 إلى الرأس 4، والرأس 4 إلى الرأس 1. يمكن تمثيله بالصورة (1 2 3 4)، أي دورة واحدة ذات الطول 4.
التدوير بزاوية 180 درجة: هذا التبديل يرسل الرأس 1 إلى الرأس 3، والرأس 2 إلى الرأس 4، والرأس 3 إلى الرأس 1، والرأس 4 إلى الرأس 2. يمكن تمثيله بالصورة (1 3)(2 4)، أي دورتين ذات الطول 2.
التدوير بزاوية 270 درجة: هذا التبديل يرسل الرأس 1 إلى الرأس 4، والرأس 4 إلى الرأس 3، والرأس 3 إلى الرأس 2، والرأس 2 إلى الرأس 1. يمكن تمثيله بالصورة (1 4 3 2)، أي دورة واحدة ذات الطول 4.

إذن، المجموعة G تحتوي على أربعة تبديلات: (1)(2)(3)(4)، (1 2 3 4)، (1 3)(2 4)، و (1 4 3 2). دورة المؤشر للمجموعة G هي:

Z(G) = (1/4) * (x₁⁴ + x₄ + x₂² + x₄)

الآن، لدينا لونين (الأحمر والأزرق)، لذا |C| = 2. نستبدل كل متغير x_i بـ 2:

Z(G; 2, 2, 2, 2) = (1/4) * (2⁴ + 2 + 2² + 2) = (1/4) * (16 + 2 + 4 + 2) = (1/4) * 24 = 6

إذن، هناك 6 طرق مختلفة لتلوين رؤوس مربع بلونين، مع الأخذ في الاعتبار التناظر الدوراني.

تطبيقات نظرية بوليا

تتمتع نظرية بوليا بمجموعة واسعة من التطبيقات في مختلف المجالات، بما في ذلك:

الكيمياء: حساب عدد الأيزومرات المختلفة لجزيء ما.
نظرية الرسوم البيانية: حساب عدد الرسوم البيانية المختلفة (حتى التكافؤ).
تصميم الدوائر: حساب عدد الطرق المختلفة لترتيب المكونات على لوحة الدوائر.
نظرية الأكواد: حساب عدد الأكواد المختلفة (حتى التكافؤ).
علم الأحياء: حساب عدد الطرق المختلفة لترتيب الأحماض الأمينية في سلسلة بروتينية.

نظرية ريدفيلد-بوليا

غالبًا ما يُشار إلى نظرية بوليا باسم نظرية ريدفيلد-بوليا، وذلك تكريمًا للعالمين الرياضيين جي هوارد ريدفيلد وجورج بوليا، اللذين ساهموا بشكل كبير في تطوير هذه النظرية. قدم ريدفيلد نسخة مبكرة من النظرية في عام 1927، ولكن عمله لم يحظ بالاهتمام الكافي في ذلك الوقت. قام بوليا بإعادة اكتشاف وتعميم النظرية في عام 1937، وقدمها بطريقة أكثر سهولة وفهمًا، مما أدى إلى انتشارها واستخدامها على نطاق واسع.

أمثلة أخرى

مثال 1: لنفترض أننا نريد تلوين وجوه مكعب بستة ألوان مختلفة. مجموعة التناظرات للمكعب تتكون من 24 عنصرًا (تدويرات مختلفة). حساب دورة المؤشر لمجموعة التناظرات هذه معقد بعض الشيء، ولكن باستخدام نظرية بوليا، يمكننا حساب عدد الطرق المختلفة لتلوين المكعب.

مثال 2: لنفترض أننا نريد حساب عدد القلائد المختلفة التي يمكننا صنعها باستخدام عدد معين من الخرزات بألوان مختلفة. يمكننا استخدام نظرية بوليا لحساب عدد القلائد المميزة، مع الأخذ في الاعتبار أننا يمكننا تدوير القلادة أو قلبها.

مزايا وعيوب نظرية بوليا

المزايا:

توفر طريقة منهجية لحساب عدد التكوينات المميزة في وجود التناظرات.
تتمتع بمجموعة واسعة من التطبيقات في مختلف المجالات.
يمكن استخدامها لحل مشاكل العد المعقدة التي يصعب حلها بطرق أخرى.

العيوب:

حساب دورة المؤشر للمجموعة قد يكون صعبًا في بعض الحالات.
قد تتطلب فهمًا جيدًا للمفاهيم الرياضية الأساسية، مثل نظرية المجموعات.

خاتمة

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

المراجع

]]>