فئة توافقية

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
الموسوعة الحرة

في الرياضيات ، تُعرَّف الفئة التوافقية بأنها مجموعة قابلة للعد من الكائنات الرياضية، بالإضافة إلى دالة حجم تربط كل كائن بعدد صحيح غير سالب، بحيث يكون هناك عدد محدود من الكائنات من كل حجم. [ 1 ] [ 2 ]

عدّ المتتاليات والتماثل

تُعرَّف متتالية العد لفئة توافقية بأنها متتالية أعداد العناصر ذات الحجم i، حيث i  =  0، 1، 2، ...؛ ويمكن وصفها أيضًا بأنها دالة مولدة تأخذ هذه الأعداد كمعاملات لها. تُعدّ متتاليات العد للفئات التوافقية الموضوع الرئيسي لدراسة التوافقية التعدادية . يُقال إن فئتين توافقيتين متماثلتان إذا كان لهما نفس عدد العناصر من كل حجم، أو بصورة مكافئة، إذا كانت متتاليات العد الخاصة بهما متطابقة. [ 3 ] غالبًا، بمجرد معرفة أن فئتين توافقيتين متماثلتان، يُبحث عن برهان تقابلي لهذا التكافؤ؛ ويمكن تفسير هذا البرهان على أنه يُظهر أن العناصر في الفئتين المتماثلتين متماثلة ظاهريًا.

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

التوافقية التحليلية

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

أنماط التبديل

في دراسة أنماط التبديل ، تُسمى فئة توافقية من فئات التبديل ، يتم تعدادها حسب طول التبديل، فئة ويلف . [ 6 ] وقد كشفت دراسة تعدادات فئات تبديل محددة عن تكافؤات غير متوقعة في عد تسلسلات فئات التبديل التي تبدو غير مترابطة.

مراجع

  1. ↑ مارتينيز، كونرادو؛ مولينيرو، خافيير (2001)، "نهج عام لإلغاء ترتيب الفئات التوافقية المصنفة" (ملف PDF) ، الهياكل العشوائية والخوارزميات ، 19 ( 3-4 ): 472-497 ، doi : 10.1002/rsa.10025 ، MR 1871563 .
  2. ↑ دوشون، فيليب ؛ فلاجو، فيليب؛ لوشار، غي؛ شيفر، جيل (2004)، "عينات بولتزمان للتوليد العشوائي للهياكل التوافقية"، التوافقية، الاحتمالات والحوسبة ، 13 ( 4-5 ): 577-625 ، doi : 10.1017/S0963548304006315 ، MR 2095975 .
  3. 1 2 فلاجويه، فيليب ؛ سيدجويك، روبرت (2009)، التوافقية التحليلية ، مطبعة جامعة كامبريدج، التعريف الأول.3، ص 19، ISBN 9781139477161.
  4. ↑ دي لويرا، خيسوس أ .؛ رامباو، يورغ؛ سانتوس، فرانسيسكو (2010)، التثليثات: هياكل للخوارزميات وتطبيقاتها ، الخوارزميات والحساب في الرياضيات، المجلد 25، سبرينغر، النظرية 1.1.3، الصفحات 4-6، ISBN  9783642129711.
  5. ↑ بارد، غريغوري ف. (2009)، التحليل الجبري للتشفير ، سبرينغر، القسم 4.2.1، "الفئات التوافقية"، وما يليه، الصفحات 30-34، ISBN 9780387887579.
  6. ↑ ستاينغريمسون، إينار (2013)، "بعض المسائل المفتوحة حول أنماط التبديل"، دراسات في التوافقية 2013 ، سلسلة محاضرات جمعية لندن الرياضية، المجلد 409، مطبعة جامعة كامبريدج، كامبريدج، الصفحات 239-263 ، MR 3156932