نمط التبديل

في الرياضيات التوافقية وعلوم الحاسوب النظرية ، يُعد نمط التبديل (الكلاسيكي) تبديلاً فرعياً لتبديل أطول . يمكن كتابة أي تبديل في سطر واحد كسلسلة من العناصر التي تمثل نتيجة تطبيق التبديل على المتتالية 123...؛ على سبيل المثال، تمثل المتتالية 213 التبديل على ثلاثة عناصر الذي يبدل العنصرين 1 و2. إذا كان π وσ تبديلين ممثلين بهذه الطريقة (هذه الأسماء قياسية للتباديل ولا علاقة لها بالعدد π )، يُقال إن π يحتوي على σ كنمط إذا كان لبعض متتاليات عناصر π نفس الترتيب النسبي لجميع عناصر σ.

على سبيل المثال، يحتوي التبديل π على النمط 213 عندما يكون لـ π ثلاثة مدخلات x و y و z تظهر داخل π بالترتيب x ... y ... z ولكن يتم ترتيب قيمها على النحو التالي y  < x < z ، وهو نفس ترتيب القيم في التبديل 213.   

يحتوي التبديل 32415 على خمسة عناصر على 213 كنمط بعدة طرق مختلفة: 3··15، ··415، 32··5، 324··، و·2·15، جميعها تُشكّل ثلاثيات من العناصر بنفس ترتيب 213. لاحظ أن العناصر لا يشترط أن تكون متتالية. يُطلق على كل من المتتاليات الفرعية 315، 415، 325، 324، و215 اسم نسخة أو مثال أو ظهور للنمط. ويمكن كتابة حقيقة احتواء π على σ بشكل أكثر اختصارًا على النحو التالي: σ ≤ π.

إذا لم تحتوي التبديلة π على النمط σ، يُقال إن π تتجنب σ. التبديلة 51342 تتجنب 213؛ إذ تحتوي على عشر متتاليات فرعية من ثلاثة عناصر، ولكن لا يوجد أي من هذه المتتاليات العشر لها نفس ترتيب 213.

يُعقد مؤتمر دولي مخصص لأنماط التبديل والمواضيع ذات الصلة سنوياً منذ عام 2003، ويسمى أنماط التبديل .

يمكن القول إن بيرسي ماكماهون ( 1915 ) كان أول من أثبت نتيجة في هذا المجال من خلال دراسته لـ"تباديل الشبكة". ^{[ 1 ]} وعلى وجه الخصوص، يُبين ماكماهون أن التباديل التي يمكن تقسيمها إلى متتاليتين فرعيتين متناقصتين (أي التباديل التي تتجنب 123) تُحسب بواسطة أعداد كاتالان . ^{[ 2 ]} 

ومن النتائج البارزة الأخرى في هذا المجال نظرية إردوش-سيكيريس ؛ وبعبارة أخرى، تنص هذه النظرية على أنه لأي عددين صحيحين موجبين a و b، فإن كل تبديل بطول لا يقل عن ${\displaystyle (a-1)(b-1)+1}$يجب أن يحتوي على النمط${\displaystyle 1,2,3,\dots ,a}$أو النمط${\displaystyle b,b-1,\dots ,2,1}$.

بدأ البحث الجاد في أنماط التبديلات مع دراسة دونالد كنوث لفرز المكدس عام ١٩٦٨. ^{[ ٣ ]} بيّن كنوث أن التبديل π يمكن فرزه بواسطة مكدس إذا وفقط إذا كان π يتجنب العدد ٢٣١، وأن التبديلات القابلة للفرز بواسطة المكدس تُحصى بأعداد كاتالان . ^{[ ٤ ]} كما أثار كنوث تساؤلات حول الفرز باستخدام قوائم الانتظار المزدوجة . وعلى وجه الخصوص، لا يزال سؤال كنوث حول عدد التبديلات المكونة من n عنصرًا والتي يمكن الحصول عليها باستخدام قائمة انتظار مزدوجة مفتوحًا. ^{[ 5 ]} بعد ذلك بوقت قصير، درس روبرت تارجان ( 1972 ) الفرز بواسطة شبكات من المكدسات، ^{[ 6 ]} بينما أظهر فوغان برات ( 1973 ) أنه يمكن فرز التبديل π بواسطة قائمة انتظار مزدوجة إذا وفقط إذا كان لكل k ، يتجنب π التبديلات 5، 2، 7، 4، ...، 4k + 1 ، 4k - 2، 3، 4k ، 1، و5، 2، 7 ، 4، ...، 4k + 3 ، 4k، 1، 4k + 2، 3، وكل تبديل يمكن الحصول عليه من أي من هذين التبديلين عن طريق تبديل العنصرين الأخيرين أو العنصرين 1 و2. ^{[ 7 ]} ولأن هذه المجموعة من التبديلات لانهائية (في الواقع، إنها أول مثال منشور لسلسلة مضادة لانهائية من التبديلات)، فليس من الواضح على الفور المدة التي يستغرقها تحديد ما إذا كان يمكن فرز تبديل ما بواسطة قائمة انتظار مزدوجة. قدم روزنستيل وتارجان (1984) لاحقًا خوارزمية زمنية خطية (في طول π) تحدد ما إذا كان من الممكن فرز π بواسطة قائمة انتظار مزدوجة. ^{[ 8 ]}  

أشار برات في ورقته البحثية إلى أن ترتيب نمط التبديل هذا "يبدو أنه الترتيب الجزئي الوحيد للتبديل الذي ينشأ بطريقة بسيطة وطبيعية"، وخلص إلى القول بأنه "من وجهة نظر مجردة"، فإن ترتيب نمط التبديل "أكثر إثارة للاهتمام من الشبكات التي كنا نصفها". ^{[ 7 ]}

يتمثل أحد الأهداف الرئيسية في دراسة أنماط التبديل في حصر التبديلات التي تتجنب تبديلاً ثابتاً (وعادةً ما يكون قصيراً) أو مجموعة من التبديلات. لنرمز بـ Av _{_n} (B) إلى مجموعة التبديلات ذات الطول n التي تتجنب جميع التبديلات في المجموعة B. (في حالة كون B مجموعةً أحادية، ولتكن { β }، يُستخدم الاختصار Av _{_n} ( β ) بدلاً من ذلك). كما ذُكر سابقاً، أثبت ماكماهون وكنوث أن |Av_{_n} (123)| = |Av _{_n} (231)| = C _{_n} ، وهو العدد الكاتالاني النوني . وبالتالي، تُعدّ هذه فئات توافقية متماثلة .

كانت ورقة سيميون وشميدت (1985) أول ورقة بحثية تركز حصراً على التعداد. ومن بين نتائج أخرى، أحصى سيميون وشميدت التباديل الزوجية والفردية التي تتجنب نمطاً طوله ثلاثة، وأحصى التباديل التي تتجنب نمطين طولهما ثلاثة ، وقدموا أول برهان تقابلي على أن التباديل التي تتجنب النمطين 123 و231 متساوية في العدد. ^{[ 9 ]} ومنذ ذلك الحين، تم تقديم العديد من البراهين التقابلية الأخرى، انظر كلايسون وكيتايف (2008) للاطلاع على دراسة شاملة. ^{[ 10 ]}

بشكل عام، إذا كان |Av _n ( β )| = |Av _n ( σ )| لجميع قيم n ، فإن β و σ يُقال إنهما متكافئان وفقًا لمعيار ويلف . تنشأ العديد من تكافؤات ويلف من الحقيقة البديهية المتمثلة في أن |Av _n ( β )| = |Av _n ( β ^{− 1} )| = |Av _n ( β ^rev )| لجميع قيم n ، حيث يرمز β ^{− 1 إلى} معكوس β ، و β ^rev إلى معكوس β . (تُولد هاتان العمليتان المجموعة ثنائية السطوح D ₈ ذات التأثير الطبيعي على مصفوفات التبديل ). مع ذلك، توجد أيضًا أمثلة عديدة على تكافؤات ويلف غير البديهية (مثل تلك الموجودة بين 123 و 231).

• أثبتت ستانكوفا (1994) أن التبديلات 1342 و 2413 متكافئة وفقًا لـ Wilf. ^{[ 11 ]}
• أثبت ستانكوفا وويست (2002) أنه لأي تبديل β ، فإن التبديلين 231 ⊕ β و 312 ⊕ β متكافئان وفقًا لـ Wilf، حيث يرمز ⊕ إلى عملية الجمع المباشر . ^{[ 12 ]}
• أثبت باكيلين، ويست، وشين (2007) أنه لأي تبديل β وأي عدد صحيح موجب m ، فإن التبديلات 12... m ⊕ β و m ...21 ⊕ β متكافئة ويلف. ^{[ 13 ]}  

من خلال هذين التكافؤين لـ Wilf والتناظرات العكسية والمعكوسة، يتبين أن هناك ثلاث متتاليات مختلفة |Av _n ( β )| حيث β طولها أربعة:

في أواخر ثمانينيات القرن العشرين، افترض ريتشارد ستانلي وهربرت ويلف أنه لكل تبديل β ، يوجد ثابت K بحيث يكون |Av _n ( β )| < K ⁿ . عُرف هذا باسم حدسية ستانلي-ويلف حتى أثبته آدم ماركوس وغابور تاردوس . ^{[ 16 ]}

فئة التبديلات ، والمعروفة أيضًا بفئة الأنماط (خاصةً في الأعمال القديمة)، أو ببساطة فئة التبديلات، هي مجموعة فرعية في ترتيب أنماط التبديلات. يمكن تعريف كل فئة من خلال أصغر التبديلات التي لا تقع ضمنها، أي أساسها . وبالتالي، فإن أساس التبديلات القابلة للفرز باستخدام المكدس هو {231}، بينما من المعروف أن أساس التبديلات القابلة للفرز باستخدام قائمة الانتظار المزدوجة غير محدود. الدالة المولدة لفئة ما هي Σ x ^|π|، حيث يُحسب المجموع على جميع التبديلات π في الفئة.

بما أن مجموعة التباديل تحت ترتيب الاحتواء تُشكّل مجموعة مرتبة جزئيًا، فمن الطبيعي التساؤل عن دالة موبيوس الخاصة بها ، وهو هدف طرحه ويلف (2002) صراحةً لأول مرة . ^{[ 17 ]} يهدف هذا البحث إلى إيجاد صيغة لدالة موبيوس لفترة [σ, π] في مجموعة أنماط التباديل المرتبة جزئيًا، بحيث تكون هذه الصيغة أكثر كفاءة من التعريف التكراري البسيط. وقد توصل ساجان وفاتر (2006) إلى أول نتيجة من هذا القبيل ، حيث قدّما صيغة لدالة موبيوس لفترة من التباديل الطبقية . ^{[ 18 ]} لاحقًا، عمّم بورستين وآخرون (2011) هذه النتيجة لتشمل فترات من التباديل القابلة للفصل . ^{[ 19 ]}

من المعروف أنه، تقاربياً، ما لا يقل عن 39.95% من جميع التبديلات π ذات الطول n تحقق μ(1, π)=0 (أي أن دالة موبيوس الرئيسية تساوي صفرًا)، ^{[ 20 ]} ولكن لكل n توجد تبديلات π بحيث تكون μ(1, π) دالة أسية لـ n . ^{[ 21 ]}

بافتراض وجود تبديل${\displaystyle \tau }$(يسمى النص ) بطول${\displaystyle n}$وتباديل أخرى${\displaystyle \pi }$من الطول${\displaystyle k}$(المسمى بالنمط )، تطرح مشكلة مطابقة أنماط التبديل (PPM) سؤالاً حول ما إذا كان${\displaystyle \pi }$يحتوي على${\displaystyle \tau }$عندما يكون كلاهما${\displaystyle n}$و${\displaystyle k}$إذا اعتُبرت المتغيرات، فإن المسألة تُعرف بأنها مسألة NP-كاملة ، ومسألة حساب عدد هذه التطابقات هي مسألة P-كاملة . ^{[ 22 ]} ومع ذلك، يمكن حل مسألة PPM في وقت خطي عندما يكون k ثابتًا. في الواقع، أظهر غيليموت وماركس ^{[ 23 ]} أنه يمكن حل مسألة PPM في وقت${\displaystyle 2^{O(k^{2}\log k)}\cdot n}$مما يعني أنه قابل للمعالجة باستخدام معلمات ثابتة فيما يتعلق بـ${\displaystyle k}$.

توجد عدة صيغ لمسألة PPM، كما استعرضها برونر ولاكنر. ^{[ 24 ]} على سبيل المثال، إذا كان التطابق مطلوبًا أن يتكون من مدخلات متجاورة، فيمكن حل المسألة في وقت متعدد الحدود. ^{[ 25 ]} وتُحصل صيغة طبيعية مختلفة عندما يُقيد النمط بفئة تبديل مناسبة.${\displaystyle {\mathcal {C}}}$تُعرف هذه المشكلة باسم${\displaystyle {\mathcal {C}}}$تم تحديد نمط PPM، وثبت أنه قابل للحل في زمن متعدد الحدود للتباديل القابلة للفصل . ^{[ 22 ]} لاحقًا، قام جيلينك وكينكل ^{[ 26 ]} بحل تعقيد بشكل كامل${\displaystyle {\mbox{Av}}(\sigma )}$- نمط PPM من خلال إظهار أنه قابل للحل في وقت متعدد الحدود عندما${\displaystyle \sigma }$يساوي أحد الأرقام التالية: 1، 12، 21، 132، 231، 312 أو 213، ويكون NP-كاملًا فيما عدا ذلك.

وهناك شكل آخر يتمثل في تقييد كل من النمط والنص بفئة تبديل مناسبة.${\displaystyle {\mathcal {C}}}$وفي هذه الحالة تسمى المشكلة${\displaystyle {\mathcal {C}}}$-PPM. على سبيل المثال، أظهر غيليموت وفياليت ^{[ 27 ] أن}${\displaystyle {\mbox{Av}}(321)}$يمكن حل مشكلة -PPM في${\displaystyle O(k^{2}n^{6})}$الوقت. قام ألبرت ، ولاكنر، ولاكنر، وفاتير ^{[ 28 ]} لاحقًا بتخفيض هذا إلى${\displaystyle O(kn)}$وأظهروا أن الحد نفسه ينطبق على فئة التباديل المدمجة المائلة . وتساءلوا كذلك عما إذا كان${\displaystyle {\mathcal {C}}}$يمكن حل مشكلة PPM في وقت متعدد الحدود لكل فئة تبديل مناسبة ثابتة${\displaystyle {\mathcal {C}}}$أجاب جيلينك وكينشل على هذا السؤال بالنفي، موضحين أن${\displaystyle {\mbox{Av}}(4321)}$-PPM هو في الواقع NP-كامل. ^{[ 26 ]} في وقت لاحق، أظهر جيلينك وأوبلر وبيكاريك ^{[ 29 ]} ذلك${\displaystyle {\mbox{Av}}(\sigma )}$مسألة -PPM هي مسألة NP-كاملة لأي${\displaystyle \sigma }$بطول لا يقل عن 4 وليس متناظرًا مع أحد الأرقام 3412 أو 3142 أو 4213 أو 4123 أو 41352.

يُقال إن التبديل π هو الأمثل من النوع β إذا لم يكن هناك تبديل آخر بنفس طول π يحتوي على نسخ أكثر من β. في خطابه أمام اجتماع SIAM حول الرياضيات المتقطعة عام 1992، عرّف ويلف كثافة التعبئة للتبديل β ذي الطول k على النحو التالي:

${\displaystyle \lim _{n\rightarrow \infty }{\frac {{\text{عدد نسخ }}\beta {\text{ في تبديل }}\beta {\text{ الأمثل بطول }}n}{\displaystyle {n \choose k}}}.}$

تُبين حجة غير منشورة لفريد جالفين أن الكمية داخل هذه النهاية غير متزايدة لـ n ≥ k ، وبالتالي فإن النهاية موجودة. عندما تكون β رتيبة، فإن كثافة التعبئة الخاصة بها تساوي 1 بوضوح، وكثافات التعبئة ثابتة تحت مجموعة التناظرات المولدة بواسطة المعكوس والعكس، لذلك بالنسبة للتباديل ذات الطول ثلاثة، توجد كثافة تعبئة واحدة غير تافهة فقط. حسم والتر سترومكويست (غير منشور) هذه الحالة بإثبات أن كثافة التعبئة لـ 132 هي 2 √ 3 − 3   ، أي ما يقارب 0.46410.

بالنسبة للتباديل β ذات الطول أربعة، هناك (بسبب التناظرات) سبع حالات يجب مراعاتها:

بالنسبة للتباديل الثلاثة المجهولة، توجد حدود وتخمينات. استخدم برايس (1997) خوارزمية تقريبية تشير إلى أن كثافة التعبئة للعدد 1324 تبلغ حوالي 0.244. ^{[ 30 ]} أنشأ بيرجان باتكييف (غير منشور) مجموعة من التباديل تُظهر أن كثافة التعبئة للعدد 1342 هي على الأقل حاصل ضرب كثافتي التعبئة للعددين 132 و1432، أي ما يقارب 0.19658. ويُفترض أن هذه هي كثافة التعبئة الدقيقة للعدد 1342. قدم بريسوتي وسترومكويست (2010) حدًا أدنى لكثافة التعبئة للعدد 2413. هذا الحد الأدنى، الذي يمكن التعبير عنه بدلالة تكامل، يبلغ حوالي 0.10474، ويُفترض أنه كثافة التعبئة الحقيقية. ^{[ 32 ]}

النمط الفائق من الرتبة k هو تبديل يحتوي على جميع التبديلات التي طولها k . على سبيل المثال، 25314 هو نمط فائق من الرتبة 3 لأنه يحتوي على جميع التبديلات الستة التي طولها 3. من المعروف أن ^{طول الأنماط الفائقة من الرتبة} k يجب أن يكون على الأقل k² / e² ، حيث e ≈ 2.71828 هو عدد أويلر ، ^{[ 33 ]} وأنه توجد أنماط فائقة من ^الرتبة k بطول ⌈( ^k² + 1 )/2⌉. ^{[ 34 ]} يُعتقد أن هذا الحد الأعلى هو أفضل حد ممكن، حتى حدود الرتبة الأدنى. ^{[ 35 ]}   

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

هناك عدة طرق لتعميم مفهوم "النمط". على سبيل المثال، النمط المتقطع هو تبديل يحتوي على شرطات تشير إلى أزواج العناصر المتجاورة التي لا يشترط أن تظهر متتالية. على سبيل المثال، يحتوي التبديل 314265 على نسختين من النمط المتقطع 2 − 31 − 4، والمُعطى بالعنصرين 3426 و3425. بالنسبة للنمط المتقطع β وأي تبديل π، نكتب β(π) لعدد نسخ β في π. وبالتالي، فإن عدد الانعكاسات في π هو 2 − 1(π)، بينما عدد الانحدارات هو 21(π). علاوة على ذلك، فإن عدد الوديان في π هو 213(π) + 312(π)، بينما عدد القمم هو 231(π) + 132(π). قدم بابسون وستينغريمسون (2000) هذه الأنماط ، حيث أظهرا أن جميع إحصاءات ماهوني المعروفة تقريبًا يمكن التعبير عنها بدلالة التباديل الحلقية. ^{[ 36 ]} على سبيل المثال، الدليل الرئيسي لـ π يساوي 1 − 32(π) + 2 − 31(π) + 3 − 21(π) + 21(π).

من التعميمات الأخرى نمط الحجب ، حيث تُحجب بعض المدخلات. لكي يتجنب π نمط الحجب β، يعني ذلك أن كل مجموعة من مدخلات π التي تُشكل نسخة من المدخلات غير المحجوبة في β يمكن توسيعها لتُشكل نسخة من جميع مدخلات β. قدم ويست (1993) هذه الأنواع من الأنماط في دراسته للتباديل التي يمكن فرزها بتمريرها مرتين عبر مكدس. ^{[ 37 ]} (لاحظ أن تعريف ويست للفرز مرتين عبر مكدس لا يُطابق الفرز باستخدام مكدسين متتاليين). مثال آخر على أنماط الحجب يظهر في عمل بوسكيه-ميلو وباتلر (2007) ، اللذين أظهرا أن صنف شوبرت المُقابل لـ π يكون مضروبًا محليًا إذا وفقط إذا تجنب π العددين 1324 و21 3 54. ^{[ 38 ]}

• PermLab: برنامج لأنماط التبديل ، يتم صيانته بواسطة مايكل ألبرت .
• قاعدة بيانات لتجنب أنماط التبديل ، التي تتولى صيانتها بريدجيت تينر .
• PermPAL: مكتبة تجنب أنماط التبديل ، وهي قاعدة بيانات لنظريات مستمدة خوارزميًا حول فئات التبديل، ويتم صيانتها بواسطة كريستيان بين، وإميل نادو، وجاي بانتون، وهينينج أولفارسون.