قسم غير متقاطع

في الرياضيات التوافقية ، اكتسب موضوع التقسيمات غير المتقاطعة بعض الأهمية بسبب (من بين أمور أخرى) تطبيقه على نظرية الاحتمال الحر . عدد التقسيمات غير المتقاطعة لمجموعة من n عنصر هو العدد الكاتالوني رقم n . يوجد عدد التقسيمات غير المتقاطعة لمجموعة مكونة من n عنصر مع k كتلة في مثلث نارايانا العددي .

تقسيم المجموعة S هو مجموعة من المجموعات الفرعية غير الفارغة والمتقطعة في أزواج من S ، والتي تسمى "أجزاء" أو "كتل"، والتي يكون اتحادها هو كل S. ضع في اعتبارك مجموعة منتهية مرتبة خطيًا، أو (على نحو مكافئ، لأغراض هذا التعريف) مرتبة في ترتيب دوري مثل رؤوس مضلع منتظم ذي n ضلع. لا تضيع العمومية بأخذ هذه المجموعة لتكون S = {1, ..., n }. التقسيم غير المتقاطع لـ S هو تقسيم لا تتقاطع فيه كتلتان، أي إذا كانت a و b تنتميان إلى كتلة واحدة و x و y تنتميان إلى أخرى، فلا يتم ترتيبهما بالترتيب axby . إذا رسم المرء قوسًا قائمًا على a و b ، وقوسًا آخر قائمًا على x و y ، فإن القوسين يتقاطعان مع بعضهما البعض إذا كان الترتيب axby ولكن ليس إذا كان axyb أو abxy . في الترتيبين الأخيرين، يكون القسم { { a , b }, { x , y } } غير متقاطع.

معبر:	اكسبي
غير متقاطع:	أكسيب
غير متقاطع:	أبكسي

على نحو مكافئ، إذا قمنا بتسمية رؤوس مضلع منتظم من نوع n بالأرقام من 1 إلى n ، فإن القشور المحدبة للكتل المختلفة للقسم تكون منفصلة عن بعضها البعض، أي أنها أيضًا لا "تتقاطع" مع بعضها البعض. مجموعة جميع الأقسام غير المتقاطعة لـ S يشار إليها بـ . هناك تماثل ترتيب واضح بين و لمجموعتين منتهيتين بنفس الحجم. أي أنها تعتمد بشكل أساسي فقط على حجم و نشير إلى الأقسام غير المتقاطعة على أي مجموعة بحجم n . ${\displaystyle {\text{NC}}(S)}$${\displaystyle {\text{NC}}(S_{1})}$${\displaystyle {\text{NC}}(S_{2})}$${\displaystyle S_{1},S_{2}}$${\displaystyle {\text{NC}}(S)}$${\displaystyle S}$${\displaystyle {\text{NC}}(n)}$

مثل مجموعة كل أقسام المجموعة {1, ..., n }، فإن مجموعة كل الأقسام غير المتقاطعة تكون شبكة عندما يتم ترتيبها جزئيًا بالقول إن القسم الأدق "أقل من" القسم الأكثر خشونة. ومع ذلك، على الرغم من أنها مجموعة فرعية من شبكة كل أقسام المجموعة، إلا أنها ليست شبكة فرعية، لأن المجموعة الفرعية ليست مغلقة بموجب عملية الانضمام في الشبكة الأكبر. بعبارة أخرى، فإن القسم الأدق الذي يكون أكثر خشونة من كلا القسمين غير المتقاطعين ليس دائمًا القسم غير المتقاطع الأدق الذي يكون أكثر خشونة من كليهما.

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

تلعب شبكة الأقسام غير المتقاطعة نفس الدور في تحديد المتراكمات الحرة في نظرية الاحتمالات الحرة التي تلعبها شبكة جميع الأقسام في تحديد المتراكمات المشتركة في نظرية الاحتمالات الكلاسيكية . لكي نكون أكثر دقة، دعونا نفترض أن تكون مساحة احتمالية غير تبادلية (انظر الاحتمالية الحرة للمصطلحات)، متغير عشوائي غير تبادلي مع متراكمات حرة . إذن ${\displaystyle ({\mathcal {A}},\phi )}$${\displaystyle a\in {\mathcal {A}}}$${\displaystyle (k_{n})_{n\in \mathbb {N} }}$

${\displaystyle \phi (a^{n})=\sum _{\pi \in {\text{NC}}(n)}\prod _{j}k_{j}^{N_{j}(\ باي )}}$

حيث يشير إلى عدد الكتل ذات الطول في القسم غير المتقاطع . أي أن لحظات المتغير العشوائي غير التبادلي يمكن التعبير عنها كمجموع من المتراكمات الحرة على مجموع الأقسام غير المتقاطعة. هذا هو النظير الحر لصيغة المتراكمات العزومية في الاحتمالات الكلاسيكية. انظر أيضًا توزيع نصف دائرة ويجنر . ${\displaystyle N_{j}(\pi )}$${\displaystyle j}$${\displaystyle \pi }$

• Germain Kreweras، “Sur les Partitions Non croisées d’uncycle”، الرياضيات المنفصلة ، ​​المجلد 1، العدد 4، الصفحات 333-350، 1972.
• روديكا سيميون ، "الأقسام غير المتقاطعة"، الرياضيات المنفصلة ، ​​المجلد 217، الأعداد 1-3، الصفحات 367-409، أبريل 2000.
• رولاند سبايكر، "الاحتمالات الحرة والأقسام غير المتقاطعة"، Séminaire Lotharingien de Combinatoire ، B39c (1997)، 38 صفحة، 1997