A Partition-Based Generating Function for Row-Convex Polyominoes

ملخص تقني: دالة توليد قائمة على التقسيم للبوليمينو صفّي التحدب (Row-Convex Polyominoes)

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

المنهجية
يؤسس النهج المقترح ارتباطاً مباشراً بين البوليمينو صفي التحدب وتقسيمات الأعداد الصحيحة للمساحة الكلية $N$. يسير المنطق الجوهري كما يلي:

1. تفكيك التقسيم: يتم تفكيك كل بوليمينو صفي التحدب بمساحة $N$ إلى تسلسل من أطوال الصفوف $(\lambda_1, \lambda_2, \dots, \lambda_k)$ بحيث يكون $\sum \lambda_i = N$. يشكل هذا التسلسل تقسيماً لعدد صحيح لـ $N$.
2. المحاذاة الأفقية (الإزاحات): بالنسبة لتسلسل ثابت من أطوال الصفوف، يتم تحديد عدد المحاذات الأفقية الصالحة من خلال "الإزاحة" بين الصفوف المتتالية. إذا كان الصف $i$ طوله $L_i$ والصف $i+1$ طوله $L_{i+1}$، فإن عدد المواضع التي يمكن أن يتلامسا فيها (لضمان الاتصال الرباعي) هو $L_i + L_{i+1} - 1$. إجمالي التكوينات لتسلسل مرتب ثابت هو حاصل ضرب عوامل الإزاحة هذه: $\prod_{i=1}^{k-1} (\lambda_i + \lambda_{i+1} - 1)$.
3. عامل التبديل: بما أن ترتيب الصفوف مهم لشكل البوليمينو، فإن الطريقة تأخذ في الاعتبار التبديلات المتميزة لتقسيمات الأجزاء. يتم إدخال عامل $\Phi(\lambda)$ لعد عدد التبديلات المتميزة لتقسيم $\lambda$، مع تعديل حساب تكرارات أحجام الأجزاء.
4. صيغة التعداد: يتم الحصول على إجمالي عدد البوليمينو صفي التحدب من الحجم $N$، ويُرمز له بـ $S(N)$، عن طريق جمع حاصل ضرب عامل التبديل وحاصل ضرب الإزاحة عبر جميع تقسيمات العدد الصحيح $N$:
   $$S(N) = \sum_{\lambda \in P(N)} \Phi(\lambda) \prod_{i=1}^{\ell(\lambda)-1} (\lambda_i + \lambda_{i+1} - 1)$$
5. اشتقاق دالة التوليد: تترجم هذه الورقة هذا المجموع التوافقي إلى دالة توليد $G(x) = \sum S(N)x^N$. ومن خلال نمذجة المشكلة كسلسلة انتقال من التكوينات المرتبة وحل نظام المعادلات الخطية الناتج، يتم اشتقاق دالة التوليد العقلانية الدقيقة.

النتائج الرئيسية

• دالة التوليد الدقيقة: تشتق الورقة دالة التوليد للبوليمينو صفي التحدب كالتالي:
  $$G(x) = \frac{x(1-x)^3}{1 - 5x + 7x^2 - 4x^3}$$
  وقد أظهرت النتائج أن هذه الدالة تتطابق تماماً مع دالة التوليد للبوليمينو عمودي التحدب التي استنتجها كلارنر وهيكرسون سابقاً، مما يؤكد صحة النهج القائم على التقسيم.
• النمو التقاربي: يكشف تحليل أقطاب $G(x)$ عن السلوك التقاربي للتسلسل. الأقطاب المهيمنة هي أقطاب مركبة مترافقة عند $x = \frac{3 \pm i\sqrt{7}}{8}$، بمعيار قدره $1/2$. وبناءً على ذلك، ينمو عدد البوليمينو وفقاً لـ:
  $$S(N) \sim A \cdot 2^N \cos(N\theta + \phi)$$
  حيث $\theta = \arctan(\sqrt{7}/3)$. يشير هذا إلى نمو أسي بحت بقاعدة 2، وهو ما يتناقض مع النمو تحت-الأسي لتقسيمات الأعداد الصحيحة غير المقيدة.
• التحقق العددي: تم تنفيذ الصيغة باستخدام لغة بايثون (الخوارزمية 1) والتحقق منها مقابل قيم متتالية OEIS A001169 حتى $N=12$، مما أظهر تطابقاً تاماً.
• اختزال التماثل: تناقش الورقة حدود تقليل العدد عبر تحديد تكوينات المرآة، مع ملاحظة أنه بينما يمكن إجراء نصف العدد بدقة لحالات زوجية محددة، فإن استخراج اختزال مغلق عام للبوليمينو المتماثل أمر صعب الاشتقاق مباشرة من صيغة التقسيم.

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

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

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