التبديل الجزئي

📅 آخر تحديث: ١٨ يوليو ٢٠٢٦
✍️ نُشر في: ١٨ يوليو ٢٠٢٦
📷 يحتوي على 6 صور
الموسوعة الحرة

في الرياضيات التوافقية ، يُعرَّف التبديل الجزئي ، أو المتتالية الخالية من التكرار ، على مجموعة منتهية S بأنه تقابل بين مجموعتين جزئيتين محددتين من S. أي أنه يُعرَّف بمجموعتين جزئيتين U و V متساويتين في الحجم، ودالة تقابل من U إلى V. وبصورة مكافئة، هو دالة جزئية على S يمكن توسيعها لتصبح تبديلاً . [ 1 ] [ 2 ]

التمثيل

من الشائع النظر في الحالة التي تكون فيها المجموعة S هي ببساطة المجموعة {1، 2، ...، n } لأول n عدد صحيح موجب. في هذه الحالة، يمكن تمثيل التبديل الجزئي بسلسلة من n رمزًا ، بعضها أعداد مختلفة في النطاق من 1 إلىن{\displaystyle n}أما البقية منها فهي رمز "ثقب" خاص ◊. في هذه الصيغة، يتكون المجال U للتبديل الجزئي من المواضع في السلسلة التي لا تحتوي على ثقب، ويتم ربط كل موضع من هذه المواضع بالرقم الموجود فيه. على سبيل المثال، تمثل السلسلة "1 ◊ 2" التبديل الجزئي الذي يربط 1 بنفسه ويربط 3 بـ 2. [ 3 ] التبديلات الجزئية السبعة على عنصرين هي

◊◊, ◊1, ◊2, 1◊, 2◊, 12, 21.

التعداد التوافقي

يُعطى عدد التباديل الجزئية على n عنصرًا، حيث n = 0، 1، 2، ...، بواسطة متتالية الأعداد الصحيحة

1، 2، 7، 34، 209، 1546، 13327، 130922، 1441729، 17572114، 234662231، ... (التسلسل A002720 في OEIS )

حيث يُعطى العنصر رقم n في المتتالية بواسطة صيغة الجمع

∑أنا=0نأنا!(نأنا)2{\displaystyle \sum _{i=0}^{n}i!{\binom {n}{i}}^{2}}

حيث يحسب الحد i عدد التباديل الجزئية ذات الدعم بحجم i ، أي عدد التباديل الجزئية التي تحتوي على i من المدخلات غير المجوفة. ويمكن حسابه بدلاً من ذلك باستخدام علاقة تكرارية.

P(ن)=2نP(ن-1)-(ن-1)2P(ن-2).{\displaystyle P(n)=2nP(n-1)-(n-1)^{2}P(n-2).}

يتم تحديد ذلك على النحو التالي:

  1. P(ن-1){\displaystyle P(n-1)}التباديل الجزئية حيث يتم حذف العناصر الأخيرة من كل مجموعة:
  2. P(ن-1){\displaystyle P(n-1)}التباديل الجزئية حيث ترتبط العناصر النهائية لكل مجموعة ببعضها البعض.
  3. (ن-1)P(ن-1){\displaystyle (n-1)P(n-1)}التباديل الجزئية التي يتم فيها تضمين العنصر الأخير من المجموعة الأولى، ولكنه لا يرتبط بالعنصر الأخير من المجموعة الثانية
  4. (ن-1)P(ن-1){\displaystyle (n-1)P(n-1)}التباديل الجزئية التي يتم فيها تضمين العنصر الأخير من المجموعة الثانية، ولكن لا يتم تعيينه إلى العنصر الأخير من المجموعة الأولى
  5. -(ن-1)2P(ن-2){\displaystyle -(n-1)^{2}P(n-2)}، التباديل الجزئية المضمنة في كل من العددين 3 و 4، تلك التباديل التي يتم فيها تضمين العناصر النهائية لكلا المجموعتين، ولكنها لا تتطابق مع بعضها البعض.

التباديل الجزئية المقيدة

يُقيّد بعض المؤلفين التباديل الجزئية بحيث يُجبر مجال [ 4 ] أو مدى [ 3 ] الدالة التقابلية على أن يتألف من أول k عنصر في مجموعة العناصر n المراد تبديلها، وذلك لبعض قيم k . في الحالة الأولى، يكون التبديل الجزئي ذو الطول k من مجموعة n هو مجرد سلسلة من k عنصر من مجموعة n بدون تكرار. (في علم التوافيق الأساسي، تُسمى هذه الكائنات أحيانًا، على نحو مُربك، " تباديل k " لمجموعة n ).

مراجع

  1. ↑ ستراوبينغ، هوارد (1983)، "برهان توافقي لنظرية كايلي-هاميلتون"، الرياضيات المتقطعة ، 43 ( 2-3 ): 273-279 ، doi : 10.1016/0012-365X(83)90164-4 ، MR 0685635 .
  2. ↑ كو، سي واي؛ ليدر، آي. (2006)، "نظرية إردوش-كو-رادو للتباديل الجزئية"، الرياضيات المتقطعة ، 306 (1): 74-86 ، doi : 10.1016/j.disc.2005.11.007 ، MR 2202076 .
  3. 1 2 كلايسون، أندرس؛ جيلينك، فيت؛ جيلينكوفا، إيفا؛ كيتايف، سيرجي (2011)، “تجنب النمط في التباديل الجزئي”، المجلة الإلكترونية للتوافقيات ، 18 (1): ورقة 25، 41، أرخايف : 1005.2216 ، دوى : 10.37236/512 ، السيد 2770130 .
  4. ↑ بورستين، ألكسندر؛ لانكهام، إشعيا (2010)، "فرز الصبر المقيد وتجنب الأنماط المحظورة"، أنماط التبديل ، سلسلة محاضرات جمعية لندن الرياضية، المجلد 376، كامبريدج: مطبعة جامعة كامبريدج، الصفحات 233-257 ، arXiv : math/0512122 ، doi : 10.1017/CBO9780511902499.013 ، ISBN   978-0-521-72834-8MR 2732833​ .