مشكلة في العلاقة الزوجية

في الرياضيات التوافقية ، تُعرف مسألة ترتيب الأزواج ( أو مسألة ترتيب الأزواج) بأنها عدد الطرق المختلفة الممكنة لترتيب جلوس مجموعة من الأزواج (رجل وامرأة) حول مائدة طعام مستديرة، بحيث يتناوب الرجال والنساء على الجلوس، ولا يجلس أي شخص بجوار شريكه. ( كلمة " Ménage " الفرنسية تعني "الأسرة"، وتشير هنا إلى زوجين). صاغ هذه المسألة عام 1891 إدوارد لوكاس ، وبشكل مستقل قبل ذلك ببضع سنوات، بيتر غوثري تيت، وذلك في سياق نظرية العقد . ^{[ 1 ]} بالنسبة لعدد من الأزواج يساوي 3، 4، 5، ... يكون عدد ترتيبات الجلوس هو

12، 96، 3120، 115200، 5836320، 382072320، 31488549120، ... (التسلسل A059375 في OEIS ) .

طوّر علماء الرياضيات صيغًا ومعادلات تكرارية لحساب هذه الأعداد ومتتاليات الأعداد ذات الصلة. وإلى جانب تطبيقاتها في آداب السلوك ونظرية العقد، فإن لهذه الأعداد أيضًا تفسيرًا في نظرية الرسوم البيانية : فهي تحسب عدد التطابقات والدورات الهاميلتونية في عائلات معينة من الرسوم البيانية .

لنفترض أن M _n يمثل عدد ترتيبات الجلوس لـ n زوجًا. وقد اشتق توشارد (1934) الصيغة

${\displaystyle M_{n}=2\cdot n!\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(nk)!.}$

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

تم تقديم صيغة ظلية مختلفة لـ M _n تتضمن كثيرات حدود تشيبيشيف من النوع الأول بواسطة وايمان وموزر (1958) .

هناك 2 × n ! طريقة لترتيب جلوس النساء: هناك مجموعتان من المقاعد يمكن ترتيبهما للنساء، وهناك n ! طريقة لترتيب جلوسهن في مجموعة معينة من المقاعد. لكل ترتيب جلوس للنساء، هناك

${\displaystyle A_{n}=\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(nk)!}$

طرق جلوس الرجال؛ هذه الصيغة ببساطة تحذف العامل 2× ن ! من صيغة توشارد. الأعداد الأصغر الناتجة (مرة أخرى، بدءًا من ن  =  3)،

1، 2، 13، 80، 579، 4738، 43387، 439792، ... (التسلسل A000179 في OEIS )

تُسمى هذه الأرقام بأعداد الميناج . العامل${\displaystyle {\frac {2n}{2n-k}}{2n-k \choose k}}$يمثل عدد طرق تكوين k من أزواج المقاعد المتجاورة غير المتداخلة ، أو ما يعادله، عدد تطابقات k من الحواف في رسم بياني دوري مكون من 2n رأسًا . ويُعدّ التعبير عن A _n نتيجة مباشرة لتطبيق مبدأ الإدراج والاستبعاد على الترتيبات التي يُشترط فيها أن يكون الأشخاص الجالسون عند طرفي كل حافة من حواف التطابق زوجين.

حتى ظهور دراسة بوغارت ودويلي (1986) ، كانت حلول مشكلة الجلوس المختلط تتخذ شكل إيجاد جميع ترتيبات جلوس النساء أولاً، ثم حساب عدد طرق إكمال كل ترتيب جزئي من هذه الترتيبات بإجلاس الرجال بعيداً عن شريكاتهم. جادل بوغارت ودويلي بأن صيغة توشارد يمكن اشتقاقها مباشرةً من خلال النظر في جميع ترتيبات الجلوس دفعة واحدة بدلاً من استبعاد مشاركة النساء. ^{[ 2 ]} مع ذلك، توصل كيروسيس وكونتوغيورجيو (2018) إلى حل أبسط يضع النساء في المقام الأول، كما هو موضح أعلاه، وذلك باستخدام بعض أفكار بوغارت ودويلي (مع حرصهما على إعادة صياغة الحجة بلغة غير متحيزة جنسياً).

تحقق أعداد الأزواج العلاقة التكرارية ^{[ 3 ]}

${\displaystyle A_{n}=nA_{n-1}+{\frac {n}{n-2}}A_{n-2}+{\frac {4(-1)^{n-1}}{n-2}}}$

والتكرار الأبسط المكون من أربعة حدود ^{[ 4 ]}

${\displaystyle \displaystyle A_{n}=nA_{n-1}+2A_{n-2}-(n-4)A_{n-3}-A_{n-4},}$

ومنها يمكن حساب أعداد أفراد المجموعة بسهولة.

يمكن تفسير حلول مسألة الميناج من منظور نظرية المخططات ، باعتبارها دورات هاميلتونية موجهة في مخططات التاج . يتكون مخطط التاج من إزالة تطابق تام من مخطط ثنائي كامل K _{_n,n} ؛ يحتوي على 2 ⁿ رأسًا بلونين، ويرتبط كل رأس من أحد اللونين بجميع رؤوس اللون الآخر باستثناء رأس واحد. في حالة مسألة الميناج، تمثل رؤوس المخطط الرجال والنساء، وتمثل حوافه أزواجًا من الرجال والنساء يُسمح لهم بالجلوس بجانب بعضهم البعض. يتكون هذا المخطط من إزالة التطابق التام الذي تشكله الأزواج من الذكور والإناث من مخطط ثنائي كامل يربط كل رجل بكل امرأة. يمكن وصف أي ترتيب جلوس صحيح بتسلسل الأشخاص حول الطاولة، والذي يشكل دورة هاميلتونية في المخطط. مع ذلك، يُعتبر دورتان هاميلتونيتان متكافئتين إذا ربطتا الرؤوس نفسها بالترتيب الدوري نفسه بغض النظر عن رأس البداية، بينما في مسألة الترتيب المختلط، يُعتبر موضع البداية مهمًا: فإذا قام جميع الضيوف، كما في حفلة شاي أليس ، بتغيير أماكنهم بمقدار مقعد واحد، يُعتبر ذلك ترتيب جلوس مختلفًا حتى وإن كان موصوفًا بالدورة نفسها. لذلك، فإن عدد الدورات الهاميلتونية الموجهة في الرسم البياني التاجي أصغر بمعامل 2n من عدد ترتيبات الجلوس، ^{[ 5 ]} ولكنه أكبر بمعامل ( n - 1) من أعداد الترتيب المختلط. تسلسل أعداد الدورات في هذه الرسوم البيانية (كما في السابق، بدءًا من n = 3) هو    

2، 12، 312، 9600، 416880، 23879520، 1749363840، ... (التسلسل A094047 في OEIS ) .

يُمكن أيضًا تقديم وصف ثانٍ للمسألة باستخدام نظرية الرسم البياني. فبعد جلوس النساء، يُمكن وصف ترتيبات جلوس الرجال المتبقين بأنها تطابقات تامة في رسم بياني مُشكَّل بإزالة دورة هاميلتونية واحدة من رسم بياني ثنائي الأجزاء كامل؛ يحتوي الرسم البياني على حواف تربط المقاعد الشاغرة بالرجال، وتُقابل إزالة الدورة منع الرجال من الجلوس في أي من المقاعد الشاغرة المجاورة لزوجاتهم. يُمكن حل مسألة حساب التطابقات في رسم بياني ثنائي الأجزاء ، وبالتالي بالأحرى مسألة حساب عدد الأزواج، باستخدام عناصر ثابتة لبعض المصفوفات الثنائية (0-1) . في حالة مسألة الأزواج، تكون المصفوفة الناتجة عن هذا المنظور للمسألة هي المصفوفة الدائرية التي يكون فيها جميع عناصر الصف المُولِّد، باستثناء عنصرين متجاورين، مساويًا للواحد. ^{[ 6 ]}

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

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

1، 2، 5، 20، 87، 616، 4843، 44128، 444621، ... (التسلسل A002484 في OEIS ) .

• مسألة أوبرولفاخ ، وهي مسألة رياضية مختلفة تتعلق بترتيب رواد المطعم على الطاولات
• مشكلة اللقاءات ، وهي مشكلة مماثلة تنطوي على اختلالات جزئية

• وايسشتاين، إريك دبليو ، "مشكلة الأزواج المتزوجين" ، عالم الرياضيات
• وايسشتاين، إريك دبليو ، "صيغة لايسان التكرارية" ، عالم الرياضيات