التبديل

تُدرج صيغة كوشي ذات السطرين ^{[ 20 ] [ 21 ]} عناصر المجموعة S في الصف الأول، وصورة كل عنصر أسفله في الصف الثاني. على سبيل المثال، التبديل S = {1, 2, 3, 4, 5, 6} المُعطى بالدالة

${\displaystyle \sigma (1)=2,\ \ \sigma (2)=6,\ \ \sigma (3)=5,\ \ \sigma (4)=4,\ \ \sigma (5)=3,\ \ \sigma (6)=1}$

يمكن كتابتها على النحو التالي

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5&6\\2&6&5&4&3&1\end{pmatrix}}.}$

يمكن أن تظهر عناصر المجموعة S بأي ترتيب في الصف الأول، لذا يمكن كتابة هذا التبديل أيضًا على النحو التالي:

${\displaystyle \sigma ={\begin{pmatrix}2&3&4&5&6&1\\6&5&4&3&1&2\end{pmatrix}}={\begin{pmatrix}6&5&4&3&2&1\\1&3&4&5&6&2\end{pmatrix}}.}$

إذا كان هناك ترتيب "طبيعي" لعناصر المجموعة S ، ^{[ ب ]} لنقل${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ثم يستخدم المرء هذا للصف الأول من الترميز المكون من سطرين:

${\displaystyle \sigma ={\begin{pmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\sigma (x_{1})&\sigma (x_{2})&\sigma (x_{3})&\cdots &\sigma (x_{n})\end{pmatrix}}.}$

بناءً على هذا الافتراض، يمكن حذف الصف الأول وكتابة التبديل في سطر واحد على النحو التالي:

${\displaystyle \sigma =\sigma (x_{1})\;\sigma (x_{2})\;\sigma (x_{3})\;\cdots \;\sigma (x_{n})}$،

أي ، كترتيب مُنظّم لعناصر المجموعة S. ^{[ 22 ] [ 23 ]} يجب التمييز بين تدوين السطر الواحد وتدوين الدورة الموصوف أدناه: من الشائع حذف الأقواس أو علامات التحديد الأخرى في تدوين السطر الواحد، بينما تُستخدم الأقواس في تدوين الدورة. يُسمى تدوين السطر الواحد أيضًا بالتمثيل اللفظي . ^{[ 24 ]}

سيكون المثال أعلاه كالتالي:

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5&6\\2&6&5&4&3&1\end{pmatrix}}=265431.}$

(من المعتاد استخدام الفواصل لفصل هذه الإدخالات فقط إذا كان بعضها يحتوي على رقمين أو أكثر.)

يُعد هذا الشكل المختصر شائعًا في علم التوافيق الأساسي وعلوم الحاسوب . وهو مفيد بشكل خاص في التطبيقات التي تتطلب مقارنة التباديل من حيث كونها أكبر أو أصغر باستخدام الترتيب المعجمي .

يصف ترميز الدورة تأثير تطبيق التبديل بشكل متكرر على عناصر المجموعة S ، حيث يُطلق على المدار اسم دورة . يُكتب التبديل على شكل قائمة من الدورات؛ ولأن الدورات المتميزة تتضمن مجموعات منفصلة من العناصر، يُشار إلى ذلك باسم "التحليل إلى دورات منفصلة".

لكتابة التبديل${\displaystyle \sigma }$في تدوين الدورة، يتم اتباع الخطوات التالية:

1. اكتب قوسًا مفتوحًا متبوعًا بعنصر اختياري x من${\displaystyle S}$: ${\displaystyle (\,x}$
2. ارسم مسار x ، واكتب القيم تحت التطبيقات المتتالية لـ${\displaystyle \sigma }$:${\displaystyle (\,x,\sigma (x),\sigma (\sigma (x)),\ldots }$
3. كرر العملية حتى تعود القيمة إلى x، ثم أغلق القوس دون تكرار x :${\displaystyle (\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)}$
4. استمر مع عنصر y من S لم تتم كتابته بعد، وكرر العملية المذكورة أعلاه:${\displaystyle (\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)(\,y\,\ldots \,)}$
5. كرر ذلك حتى يتم كتابة جميع عناصر S في دورات.

كذلك، من الشائع حذف الدورات الأحادية، إذ يمكن استنتاجها: لأي عنصر x في S لا يظهر في أي دورة، يفترض المرء ضمنيًا${\displaystyle \sigma (x)=x}$[ ^{25 ]​}

باتباع اصطلاح حذف الدورات الأحادية، يمكن تفسير الدورة الفردية على أنها تبديل يُثبّت جميع العناصر غير الموجودة في الدورة ( تبديل دوري يحتوي على دورة واحدة فقط طولها أكبر من 1). عندئذٍ، يمكن اعتبار قائمة الدورات المنفصلة بمثابة تركيب لهذه التبديلات الدورية. على سبيل المثال، التبديل ذو السطر الواحد${\displaystyle \sigma =265431}$يمكن كتابتها باستخدام تدوين الدورة على النحو التالي: $${\displaystyle \sigma =(126)(35)(4)=(126)(35).}$$ يمكن اعتبار هذا بمثابة التكوين${\displaystyle \sigma =\kappa _{1}\kappa _{2}}$من التبديلات الدورية $${\displaystyle \kappa _{1}=(126)=(126)(3)(4)(5),\quad \kappa _{2}=(35)=(35)(1)(2)(4)(6).}$$ بينما لا تتبادل التباديل بشكل عام، فإن الدورات المنفصلة تتبادل؛ على سبيل المثال: $${\displaystyle \sigma =(126)(35)=(35)(126).}$$ كذلك، يمكن إعادة كتابة كل دورة من نقطة بداية مختلفة؛ على سبيل المثال، $${\displaystyle \sigma =(126)(35)=(261)(53).}$$ وبالتالي، يمكن كتابة الدورات المنفصلة لتبديل معين بعدة طرق مختلفة.

من الميزات المفيدة لترميز الدورة أن عكس التبديل يتم عن طريق عكس ترتيب العناصر في كل دورة. على سبيل المثال، $${\displaystyle \sigma ^{-1}=\left({\vphantom {A^{2}}}(126)(35)\right)^{-1}=(621)(53).}$$

لكل تبديل نمط معين من ترميز الدورات، وهو مفيد في العديد من السياقات التوافقية، وخاصةً تقابل فواتا الموصوف أدناه. يُعرَّف ترميز الدورات المتعارف عليه كما يلي:

• تحتوي كل دورة على أكبر عنصر مدرج أولاً؛
• يتم فرز الدورات بترتيب تصاعدي لعنصرها الأول، دون حذف الدورات المكونة من عنصر واحد.

على سبيل المثال،$${\displaystyle (513)(6)(827)(94)}$$هو تبديل لـ${\displaystyle S=\{1,2,\ldots ,9\}}$في تدوين الدورة المتعارف عليه ( مصطلحات ميكلوس بونا ). ^{[ 26 ]} يسمي ريتشارد ستانلي هذا التمثيل القياسي ، ^{[ 27 ]} ويستخدم مارتن أيغنر الشكل القياسي . ^{[ 24 ]} كما يستخدم سيرجي كيتايف مصطلح "الشكل القياسي"، لكنه يعكس كلا الخيارين؛ أي أن كل دورة تسرد عنصرها الأدنى أولاً، ويتم ترتيب الدورات بترتيب تنازلي لعناصرها الدنيا. ^{[ 28 ]}

هناك طريقتان لتمثيل تركيب تبديلين. في الصيغة الأكثر شيوعًا،${\displaystyle \sigma \cdot \tau }$هي الدالة التي تربط أي عنصر x بـ${\displaystyle \sigma (\tau (x))}$يتم تطبيق التبديل الأيمن على الوسيط أولاً، ^{[ 29 ]} لأن الوسيط مكتوب على يمين الدالة.

توجد قاعدة مختلفة لضرب التباديل، وهي كتابة الوسيط إلى يسار الدالة، بحيث يعمل التبديل الأيسر أولًا. ^{[ 30 ] [ 31 ] [ 32 ]} في هذه الصيغة، يُكتب التبديل غالبًا على شكل أس، لذا فإن σ الذي يؤثر على x يُكتب x ^σ ؛ ثم يُعرَّف الناتج بـ${\displaystyle x^{\sigma \cdot \tau }=(x^{\sigma })^{\tau }}$تستخدم هذه المقالة التعريف الأول، حيث يتم تطبيق التبديل الأيمن أولاً.

تُحقق عملية تركيب الدوال بديهيات المجموعة . وهي عملية تجميعية ، بمعنى${\displaystyle (\rho \sigma )\tau =\rho (\sigma \tau )}$وعادةً ما تُكتب نواتج أكثر من تبديلين بدون أقواس. كما أن لعملية التركيب عنصرًا محايدًا (التبديل المحايد).${\displaystyle {\text{id}}}$)، وكل تبديل${\displaystyle \sigma }$له عكس${\displaystyle \sigma ^{-1}}$( دالتها العكسية ) مع${\displaystyle \sigma ^{-1}\sigma =\sigma \sigma ^{-1}={\text{id}}}$.

في الأدبيات القديمة والكتب المدرسية الابتدائية، يُقصد بالتبديل k لمجموعة n (ويُسمى أحيانًا التبديل الجزئي ، أو التسلسل بدون تكرار ، أو التباين ، أو الترتيب ) ترتيبًا مُرتبًا (قائمة) لمجموعة فرعية مكونة من k عنصرًا من مجموعة n . ^{[ c ] [ 33 ] [ 34 ]} عدد هذه التبديلات k ( الترتيبات k ) لـ${\displaystyle n}$يُشار إليه بأشكال مختلفة مثل${\displaystyle P_{k}^{n}}$، ${\displaystyle _{n}P_{k}}$،${\displaystyle ^{n}\!P_{k}}$،${\displaystyle P_{n,k}}$،${\displaystyle P(n,k)}$، أو${\displaystyle A_{n}^{k}}$، ^{[ 35 ]} محسوبة بالصيغة: ^{[ 36 ]}$${\displaystyle P(n,k)=\underbrace {n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)} _{k\ \mathrm {factors} },}$$

وهي تساوي صفرًا عندما يكون k > n ، وفيما عدا ذلك تساوي $${\displaystyle {\frac {n!}{(nk)!}}.}$$

المنتج محدد جيدًا دون افتراض أن${\displaystyle n}$هو عدد صحيح غير سالب، وله أهمية خارج نطاق التوافقية أيضًا؛ وهو يُعرف باسم رمز بوخامر.${\displaystyle (n)_{k}}$أو كما هو الحال${\displaystyle k}$القوة العاملية المتناقصة رقم -th${\displaystyle n^{\underline {k}}}$: $${\displaystyle P(n,k)={_{n}}P_{k}=(n)_{k}=n^{\underline {k}}.}$$

يرتبط استخدام مصطلح التبديل هذا ارتباطًا وثيقًا بمصطلح التوافيق بمعنى مجموعة جزئية: أي أن التوافيق المكونة من k عنصرًا لمجموعة S هي مجموعة جزئية (غير مرتبة) من S مكونة من k عنصرًا . ويؤدي ترتيب التوافيق المكونة من k عنصرًا لمجموعة S بجميع الطرق الممكنة إلى إنتاج التباديل المكونة من k عنصرًا لمجموعة S. وبالتالي، يرتبط عدد التوافيق المكونة من k عنصرًا لمجموعة مكونة من n عنصرًا، C ( n , k )، بعدد التباديل المكونة من k عنصرًا لمجموعة n بالعلاقة التالية: $${\displaystyle C(n,k)={\frac {P(n,k)}{P(k,k)}}={\frac {n^{\underline {k}}}{k!}}={\frac {n!}{(nk)!\,k!}}.}$$

تُعرف هذه الأرقام أيضًا باسم معاملات ذات الحدين ، ويُشار إليها عادةً بـ${\displaystyle {\tbinom {n}{k}}}$: $${\displaystyle C(n,k)={_{n}}C_{k}={\binom {n}{k}}.}$$

تُسمى الترتيبات المرتبة لـ k عنصرًا من مجموعة S ، حيث يُسمح بالتكرار، بـ k -tuples . وقد أُشير إليها أحيانًا باسم التباديل مع التكرار ، على الرغم من أنها ليست تباديل بالمعنى المعتاد. كما تُسمى أيضًا كلمات أو سلاسل على الأبجدية S. إذا كانت المجموعة S تحتوي على n عنصرًا، فإن عدد k -tuples على S هو${\displaystyle n^{k}.}$

إذا كانت M مجموعة متعددة منتهية ، فإن تبديل المجموعة المتعددة هو ترتيب مُرتب لعناصر M بحيث يظهر كل عنصر عددًا من المرات يساوي تمامًا عدد مرات تكراره في M. يُعدّ الجناس التام لكلمة تحتوي على بعض الأحرف المتكررة مثالًا على تبديل المجموعة المتعددة. ^{[ د ]} إذا كانت مرات تكرار عناصر M (مرتبة ترتيبًا معينًا)${\displaystyle m_{1}}$،${\displaystyle m_{2}}$...${\displaystyle m_{l}}$ومجموعها (أي حجم M ) هو n ، فإن عدد تباديل المجموعات المتعددة لـ M يتم إعطاؤه بواسطة معامل متعدد الحدود : ^{[ 37 ]}$${\displaystyle {n \choose m_{1},m_{2},\ldots ,m_{l}}={\frac {n!}{m_{1}!\,m_{2}!\,\cdots \,m_{l}!}}={\frac {\left(\sum _{i=1}^{l}{m_{i}}\right)!}{\prod _{i=1}^{l}{m_{i}!}}}.}$$ على سبيل المثال، عدد الجناس المختلفة لكلمة MISSISSIPPI هو ^{[ 38 ]}$${\displaystyle {\frac {11!}{1!\,4!\,4!\,2!}}=34650.}$$

التبديل k لمجموعة متعددة M هو سلسلة من k عنصرًا من M ، حيث يظهر كل عنصر عددًا من المرات أقل من أو يساوي عدد مرات تكراره في M ( عدد تكرار العنصر ). في هذه الحالة، يمكن تحديد عدد التبديلات باستخدام الدوال المولدة .${\displaystyle k!}$مضروبًا في معامل${\displaystyle x^{k}}$في المنتج

${\displaystyle \prod _{i=1}^{l}\sum _{j=0}^{m_{i}}{\frac {x^{j}}{j!}}}$[ ^{39 ]​}

استكمالاً للمثال السابق، في حالة مجموعة الأحرف المتعددة في كلمة MISSISSIPPI، تكون الدالة المولدة الناتجة هي $$(1+x) ⋅ (1+x+x^2/2) ⋅ (1+x+x^2/2+x^3/6+x^4/24)^2 = 1+4x + 15/2!x^2 + 53/3!x^3 + 176/4!x^4 + 550/5!x^5 + 1610/6!x^6 + 4340/7!x^7 + 10430/8!x^8 + 21420/9!x^9 + ⋅ {34650}{10!}}x^{10}+{\frac {34650}{11!}}x^{11}.\end{aligned}}}$$ وبالتالي، فإن عدد التباديل المكونة من 11 هو 34650 (نفس النتيجة المذكورة أعلاه)، ولكن لدينا أيضًا عدد التباديل المكونة من k حيث يتراوح k من 0 إلى 11.

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

تكون التبديلات الدائرية متكافئة إذا أمكن تدوير إحداها إلى الأخرى. فيما يلي أربع تبديلات دائرية لأربعة أحرف تُعتبر متطابقة.

$${\displaystyle {\begin{matrix}&1&\\4&&3\\&2&\end{matrix}}\qquad {\begin{matrix}&4&\\2&&1\\&3&\end{matrix}}\qquad {\begin{matrix}&2&\\3&&4\\&1&\end{matrix}}\qquad {\begin{matrix}&3&\\1&&2\\&4&\end{matrix}}}$$

يجب قراءة الترتيبات الدائرية عكس اتجاه عقارب الساعة، لذا فإن الترتيبين التاليين ليسا متكافئين لأنه لا يمكن لأي دوران أن يجعل أحدهما مطابقًا للآخر.

$${\displaystyle {\begin{matrix}&1&\\4&&3\\&2&\end{matrix}}\qquad {\begin{matrix}&1&\\3&&4\\&2&\end{matrix}}}$$

يوجد ( ن - 1)! تبديل دائري لمجموعة تحتوي على ن عنصرًا.

دورات التبديل (بما في ذلك النقاط الثابتة)${\displaystyle \sigma }$يمكن تقسيم مجموعة تحتوي على n عنصرًا؛ لذا فإن أطوال هذه الدورات تُشكل تقسيمًا صحيحًا لـ n ، والذي يُسمى نوع الدورة (أو أحيانًا بنية الدورة أو شكل الدورة ).${\displaystyle \sigma }$يوجد الرقم "1" في نوع الدورة لكل نقطة ثابتة من${\displaystyle \sigma }$، و"2" لكل عملية نقل، وهكذا. نوع الدورة من${\displaystyle \beta =(1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)}$يكون${\displaystyle (3,2,2,1).}$

يمكن كتابة هذا أيضًا بشكل أكثر اختصارًا على النحو التالي: [1 ¹ 2 ² 3 ¹ ] . وبشكل أدق، فإن الشكل العام هو${\displaystyle [1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}]}$، أين${\displaystyle \alpha _{1},\ldots ,\alpha _{n}}$تمثل هذه الأرقام عدد الدورات ذات الأطوال المعنية. عدد التباديل لنوع دورة معين هو ^{[ 42 ].}

${\displaystyle {\frac {n!}{1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}\alpha _{1}!\alpha _{2}!\dotsm \alpha _{n}!}}}$.

عدد أنواع الدورات لمجموعة تحتوي على n عنصرًا يساوي قيمة دالة التقسيم${\displaystyle p(n)}$.

تعد دالة مؤشر الدورة لـ Polya دالة توليد تقوم بحساب التباديل حسب نوع الدورة.

بشكل عام، لا يتبع تركيب التباديل المكتوبة بصيغة الدورة نمطًا محددًا بوضوح - فقد تختلف دورات التركيب عن دورات التباديل المراد تركيبها. ومع ذلك، يُحفظ نوع الدورة في الحالة الخاصة لترافق التبديل.${\displaystyle \sigma }$عن طريق تبديل آخر${\displaystyle \pi }$وهذا يعني تشكيل المنتج${\displaystyle \pi \sigma \pi ^{-1}}$. هنا،${\displaystyle \pi \sigma \pi ^{-1}}$هو مرافق لـ${\displaystyle \sigma }$بواسطة${\displaystyle \pi }$ويمكن الحصول على رمز الدورة الخاص به عن طريق أخذ رمز الدورة لـ${\displaystyle \sigma }$وتطبيق${\displaystyle \pi }$إلى جميع المدخلات فيه. ^{[ 43 ]} ويترتب على ذلك أن التبديلين يكونان مترافقين تمامًا عندما يكون لهما نفس نوع الدورة.

ترتيب التبديل${\displaystyle \sigma }$هو أصغر عدد صحيح موجب m بحيث${\displaystyle \sigma ^{m}=\mathrm {id} }$هو المضاعف المشترك الأصغر لأطوال دوراته. على سبيل المثال، رتبة${\displaystyle \sigma =(152)(34)}$يكون${\displaystyle {\text{lcm}}(3,2)=6}$.

يمكن التعبير عن كل تبديل لمجموعة منتهية كحاصل ضرب عمليات تبديل. ^{[ 44 ]} على الرغم من وجود العديد من هذه التعبيرات لتبديل معين، إلا أنها إما تحتوي جميعها على عدد زوجي من عمليات التبديل أو تحتوي جميعها على عدد فردي من عمليات التبديل. وبالتالي، يمكن تصنيف جميع التبديلات على أنها زوجية أو فردية بناءً على هذا العدد.

يمكن توسيع هذه النتيجة بحيث يتم تعيين إشارة ، مكتوبة${\displaystyle \operatorname {sgn} \sigma }$لكل تبديل.${\displaystyle \operatorname {sgn} \sigma =+1}$لو${\displaystyle \sigma }$زوجي و${\displaystyle \operatorname {sgn} \sigma =-1}$لو${\displaystyle \sigma }$فردي. ثم بالنسبة لتباديلين${\displaystyle \sigma }$و${\displaystyle \pi }$

${\displaystyle \operatorname {sgn} (\sigma \pi )=\operatorname {sgn} \sigma \cdot \operatorname {sgn} \pi .}$

ويترتب على ذلك أن${\displaystyle \operatorname {sgn} \left(\sigma \sigma ^{-1}\right)=+1.}$

إشارة التبديل تساوي محدد مصفوفة التبديل الخاصة به (أدناه).

مصفوفة التبديل هي مصفوفة من الرتبة n × n تحتوي على عنصر واحد فقط قيمته 1 في كل عمود وفي كل صف، وباقي العناصر قيمتها 0. توجد عدة طرق لتعيين مصفوفة تبديل لتبديل المجموعة {1، 2، ...، n }. إحدى الطرق الطبيعية هي تعريف${\displaystyle L_{\sigma }}$أن يكون التحويل الخطي لـ${\displaystyle \mathbb {R} ^{n}}$والذي يبدل الأساس القياسي${\displaystyle \{\mathbf {e} _{1},\ldots ,\mathbf {e} _{n}\}}$بواسطة${\displaystyle L_{\sigma }(\mathbf {e} _{j})=\mathbf {e} _{\sigma (j)}}$، وتحديد${\displaystyle M_{\sigma }}$لتكون مصفوفة لها. أي،${\displaystyle M_{\sigma }}$عمودها j يساوي متجه العمود n × ¹${\displaystyle \mathbf {e} _{\sigma (j)}}$تكون قيمة العنصر ( i , j ) في المصفوفة 1 إذا كان i = σ ( j )، و0 فيما عدا ذلك. وبما أن تركيب الدوال الخطية يُوصف بضرب المصفوفات ، فإن هذا التركيب متوافق مع تركيب التباديل. $${\displaystyle M_{\sigma }M_{\tau }=M_{\sigma \tau }.}$$ على سبيل المثال، التباديل المكونة من سطر واحد${\displaystyle \sigma =213,\ \tau =231}$لدينا منتج${\displaystyle \sigma \tau =132}$والمصفوفات المقابلة هي: $${\displaystyle M_{\sigma }M_{\tau }={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}{\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}={\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix}}=M_{\sigma \tau }.}$$

ومن الشائع أيضاً في الأدبيات إيجاد الاصطلاح العكسي، حيث يتم ربط التبديل σ بالمصفوفة${\displaystyle P_{\sigma }=(M_{\sigma })^{-1}=(M_{\sigma })^{T}}$العنصر ( i , j ) فيه يساوي 1 إذا كان j = σ ( i )، ويساوي 0 فيما عدا ذلك. في هذا الاصطلاح، تُضرب مصفوفات التبديل بترتيب معاكس لترتيب التبديلات، أي${\displaystyle P_{\sigma }P_{\tau }=P_{\tau \sigma }}$في هذه المراسلة، تعمل مصفوفات التبديل على الجانب الأيمن من المعيار${\displaystyle 1\times n}$متجهات الصف${\displaystyle ({\bf {e}}_{i})^{T}}$:${\displaystyle ({\bf {e}}_{i})^{T}P_{\sigma }=({\bf {e}}_{\sigma (i)})^{T}}$.

يوضح جدول كايلي الموجود على اليمين هذه المصفوفات لتباديل 3 عناصر.

An ascent of a permutation σ of n is any position i < n where the following value is bigger than the current one. That is, i is an ascent if ${\displaystyle \sigma (i)<\sigma (i{+}1)}$. For example, the permutation 3452167 has ascents (at positions) 1, 2, 5, and 6.

Similarly, a descent is a position i < n with ${\displaystyle \sigma (i)>\sigma (i{+}1)}$, so every i with ${\displaystyle 1\leq i<n}$ is either an ascent or a descent.

An ascending run of a permutation is a nonempty increasing contiguous subsequence that cannot be extended at either end; it corresponds to a maximal sequence of successive ascents (the latter may be empty: between two successive descents there is still an ascending run of length 1). By contrast an increasing subsequence of a permutation is not necessarily contiguous: it is an increasing sequence obtained by omitting some of the values of the one-line notation. For example, the permutation 2453167 has the ascending runs 245, 3, and 167, while it has an increasing subsequence 2367.

If a permutation has k − 1 descents, then it must be the union of k ascending runs.^[45]

The number of permutations of n with k ascents is (by definition) the Eulerian number${\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }$; this is also the number of permutations of n with k descents. Some authors however define the Eulerian number ${\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }$ as the number of permutations with k ascending runs, which corresponds to k − 1 descents.^[46]

يُعرَّف تجاوز التبديل σ₁ _{σ₂ ...} σₙ بأنه فهرس j بحيث يكون _σₙ > j . إذا لم تكن المتباينة صارمة (أي _σₙ ≥ j )، يُسمى j تجاوزًا ضعيفًا . _يتطابق عدد التبديلات من الرتبة n التي تحتوي على k تجاوز مع عدد التبديلات من الرتبة n التي تحتوي على k انحدار . ^{[ 47 ]}

الرقم القياسي أو الحد الأقصى من اليسار إلى اليمين للتبديل σ هو عنصر i بحيث يكون σ ( j ) < σ ( i ) لجميع j < i .

يحوّل التناظر الأساسي لـ Foata التبديل σ ذي الشكل الدوري المتعارف عليه إلى التبديل${\displaystyle f(\sigma )={\hat {\sigma }}}$والتي تحتوي صيغتها المكونة من سطر واحد على نفس تسلسل العناصر مع إزالة الأقواس. ^{[ 27 ] [ 48 ]} على سبيل المثال: $${\displaystyle \sigma =(513)(6)(827)(94)={\begin{pmatrix}1&2&3&4&5&6&7&8&9\\3&7&5&9&1&6&8&2&4\end{pmatrix}},}$$

$${\displaystyle {\hat {\sigma }}=513682794={\begin{pmatrix}1&2&3&4&5&6&7&8&9\\5&1&3&6&8&2&7&9&4\end{pmatrix}}.}$$

هنا يصبح العنصر الأول في كل دورة أساسية من σ سجلاً (أقصى قيمة من اليسار إلى اليمين) لـ${\displaystyle {\hat {\sigma }}}$. منح${\displaystyle {\hat {\sigma }}}$يمكن للمرء العثور على سجلاتها وإدراج أقواس لإنشاء التحويل العكسي${\displaystyle \sigma =f^{-1}({\hat {\sigma }})}$. وضع خط تحت السجلات في المثال أعلاه:${\displaystyle {\hat {\sigma }}={\underline {5}}\,1\,3\,{\underline {6}}\,{\underline {8}}\,2\,7\,{\underline {9}}\,4}$، مما يسمح بإعادة بناء دورات σ .

يوضح الجدول التالي${\displaystyle {\hat {\sigma }}}$و σ للتباديل الستة لـ S = {1، 2، 3}، مع النص الغامق على كل جانب الذي يوضح الترميز المستخدم في التقابل: ترميز من سطر واحد لـ${\displaystyle {\hat {\sigma }}}$ورمز الدورة المتعارف عليها لـ σ .

$${\displaystyle {\begin{array}{l|l}{\hat {\sigma }}=f(\sigma )&\sigma =f^{-1}({\hat {\sigma }})\\\hline \mathbf {123} =(\,1\,)(\,2\,)(\,3\,)&123=\mathbf {(\,1\,)(\,2\,)(\,3\,)} \\\mathbf {132} =(\,1\,)(\,3\,2\,)&132=\mathbf {(\,1\,)(\,3\,2\,)} \\\mathbf {213} =(\,2\,1\,)(\,3\,)&213=\mathbf {(\,2\,1\,)(\,3\,)} \\\mathbf {231} =(\,3\,1\,2\,)&321=\mathbf {(\,2\,)(\,3\,1\,)} \\\mathbf {312} =(\,3\,2\,1\,)&231=\mathbf {(\,3\,1\,2\,)} \\\mathbf {321} =(\,2\,)(\,3\,1\,)&312=\mathbf {(\,3\,2\,1\,)} \end{array}}}$$ كنتيجة أولية، فإن عدد التبديلات من الرتبة n التي تحتوي على k سجلاً بالضبط يساوي عدد التبديلات من الرتبة n التي تحتوي على k دورة بالضبط : هذا العدد الأخير هو عدد ستيرلينغ من النوع الأول بدون إشارة .${\displaystyle c(n,k)}$. Furthermore, Foata's mapping takes an n-permutation with k weak exceedances to an n-permutation with k − 1 ascents.^[48] For example, (2)(31) = 321 has k = 2 weak exceedances (at index 1 and 2), whereas f(321) = 231 has k − 1 = 1 ascent (at index 1; that is, from 2 to 3).

An inversion of a permutation σ is a pair (i, j) of positions where the entries of a permutation are in the opposite order: ${\displaystyle i<j}$ and ${\displaystyle \sigma (i)>\sigma (j)}$.^[50] Thus a descent is an inversion at two adjacent positions. For example, σ = 23154 has (i, j) = (1, 3), (2, 3), and (4, 5), where (σ(i), σ(j)) = (2, 1), (3, 1), and (5, 4).

Sometimes an inversion is defined as the pair of values (σ(i), σ(j)); this makes no difference for the number of inversions, and the reverse pair (σ(j), σ(i)) is an inversion in the above sense for the inverse permutation σ⁻¹.

يُعدّ عدد الانعكاسات مقياسًا مهمًا لمدى عدم ترتيب عناصر التبديل؛ وهو نفسه بالنسبة لـ σ و σ ^{− 1.} لإعادة ترتيب تبديل يحتوي على k انعكاسًا (أي تحويله إلى تبديل محايد)، يُمكن دائمًا تطبيق عمليات تبديل متجاورة (الضرب من اليمين) بشكل متتابع ، ويتطلب ذلك سلسلة من k عملية من هذا النوع. علاوة على ذلك، يُمكن استخدام أي اختيار مناسب لعمليات التبديل المتجاورة: يكفي اختيار تبديل i و i + 1 في كل خطوة، حيث يُمثل i انحدارًا للتبديل بعد تعديله (بحيث يُزيل التبديل هذا الانحدار تحديدًا، مع أنه قد يُنشئ انحدارات أخرى). وذلك لأن تطبيق مثل هذا التبديل يُقلل عدد الانعكاسات بمقدار  1؛ وطالما أن هذا العدد لا يساوي صفرًا، فإن التبديل ليس تبديلًا محايدًا، وبالتالي يحتوي على انحدار واحد على الأقل. يُمكن تفسير فرز الفقاعات وفرز الإدراج على أنهما حالتان خاصتان من هذه العملية لإعادة ترتيب سلسلة من العناصر. بالمناسبة، تُثبت هذه العملية أن أي تبديل σ يُمكن كتابته كحاصل ضرب تبديلات متجاورة؛ ولتحقيق ذلك، يُمكن ببساطة عكس أي سلسلة من هذه التبديلات التي تُحوّل σ إلى التبديل المحايد. في الواقع، من خلال حصر جميع سلاسل التبديلات المتجاورة التي تُحوّل σ إلى التبديل المحايد، نحصل (بعد العكس) على قائمة كاملة بجميع التعبيرات ذات الطول الأدنى التي تُكتب σ كحاصل ضرب تبديلات متجاورة.

يُعبّر عن عدد تباديل العدد n مع k انعكاسًا بعدد ماهوني . ^{[ 51 ]} هذا هو معامل${\displaystyle q^{k}}$في توسيع المنتج

$${\displaystyle [n]_{q}!=\prod _{m=1}^{n}\sum _{i=0}^{m-1}q^{i}=1\left(1+q\right)\left(1+q+q^{2}\right)\cdots \left(1+q+q^{2}+\cdots +q^{n-1}\right),}$$

الترميز${\displaystyle [n]_{q}!}$يرمز إلى مضروب q . يظهر هذا التوسع بشكل شائع في دراسة القلائد .

يترك${\displaystyle \sigma \in S_{n},i,j\in \{1,2,\dots ,n\}}$بحيث${\displaystyle i<j}$و${\displaystyle \sigma (i)>\sigma (j)}$في هذه الحالة، لنفترض وزن الانعكاس${\displaystyle (i,j)}$يكون${\displaystyle \sigma (i)-\sigma (j)}$أثبت كوباياشي (2011) صيغة التعداد $${\displaystyle \sum _{i<j,\sigma (i)>\sigma (j)}(\sigma (i)-\sigma (j))=|\{\tau \in S_{n}\mid \tau \leq \sigma ,\tau {\text{ is bigrassmannian}}\}}$$

أين${\displaystyle \leq }$يشير إلى ترتيب بروهات في المجموعات المتناظرة . يظهر هذا الترتيب الجزئي المتدرج غالبًا في سياق مجموعات كوكسيتر .

إحدى طرق تمثيل تباديل n عنصرًا هي باستخدام عدد صحيح N حيث 0  ≤ N < n !، شريطة توفر طرق ملائمة للتحويل بين العدد وتمثيل التبديل كترتيب (متتالية). يُعطي هذا التمثيل الأكثر إيجازًا للتباديل العشوائية، وهو جذاب بشكل خاص في الحوسبة عندما يكون n صغيرًا بما يكفي بحيث يمكن تخزين N في كلمة واحدة من الذاكرة؛ بالنسبة للكلمات ذات 32 بت، يعني هذا n ≤ 12، وبالنسبة للكلمات ذات 64 بت، يعني هذا n ≤ 20. يمكن إجراء التحويل عبر الصيغة الوسيطة لمتتالية من الأعداد d _{_n} , d_{_{n -1}} , ..., d _₂ , d _₁ ، حيث d _{_i} عدد صحيح غير سالب أصغر من i (يمكن حذف d _₁، لأنه يساوي دائمًا 0، ولكن وجوده يُسهّل وصف التحويل اللاحق إلى التبديل). تتمثل الخطوة الأولى في التعبير عن N ببساطة في نظام الأعداد المضروبية ، وهو تمثيل أساسي مختلط خاص ، حيث تكون أسس الأرقام المتتالية (القيم المكانية أو عوامل الضرب) للأعداد الأقل من n ! هي ( n - 1)!، ( n - 2)!، ...، 2!، 1!. أما الخطوة الثانية فتفسر هذا التسلسل على أنه رمز ليمر أو (بشكل مكافئ تقريبًا) على أنه جدول عكسي.       

مخطط روث لـ${\displaystyle \sigma =(6,3,8,1,4,9,7,2,5)}$

σ i أنا	1	2	3	4	5	6	7	8	9	قانون ليمر
1	×	×	×	×	×	•				د 9 = 5
2	×	×	•							د 8 = 2
3	×	×		×	×		×	•		د 7 = 5
4	•									د 6 = 0
5		×		•						د ٥ = ١
6		×			×		×		•	د 4 = 3
7		×			×		•			د 3 = 2
8		•								د 2 = 0
9					•					د 1 = 0
طاولة الانقلاب	3	6	1	2	4	0	2	0	0

في شفرة ليمر للتبديل σ ، يُمثل العدد d_{_n} الاختيار المُتخذ للحد الأول σ _₁ ، ويُمثل العدد d _{_{n -1}} الاختيار المُتخذ للحد الثاني σ _₂ من بين العناصر المتبقية n -1 من المجموعة، وهكذا. بتعبير أدق، يُعطي كل d_{_{n +1- i}} عدد العناصر المتبقية الأقل من الحد σ_{_i} . بما أن هذه العناصر المتبقية ستظهر حتمًا كحد لاحق σ_{_j} ، فإن الرقم d_{_{n +1- i}} يحسب عدد الانعكاسات ( i , j ) التي تتضمن i كمؤشر أصغر (عدد القيم j التي يكون فيها i < j و σ _{_i} > σ_{_j}). جدول الانعكاسات لـ σ مشابه تمامًا، ولكن هنا d _{_{n +1- k}} يحسب عدد الانعكاسات ( i , j ) حيث k = σ_{_j} يظهر كأصغر القيمتين الظاهرتين بالترتيب المعكوس. ^{[ 52 ]}         

يمكن تمثيل كلا الترميزين بمخطط روث n  × n ^{[ 53 ]} (نسبةً إلى هاينريش أوغست روث ) ، حيث تشير النقاط عند ( i , σi ₎ إلى عناصر التبديل، بينما يشير الصليب عند ( i , σj ) إلى الانعكاس ( i , _{j ). وبحسب تعريف الانعكاسات ،} يظهر الصليب في أي مربع يسبق النقطة ( j , σj ) في عموده، ويسبق النقطة ( i , σi ₎ في صفه. يسرد رمز ليمر عدد الصلبان في الصفوف المتتالية، بينما يسرد جدول الانعكاس عدد الصلبان في الأعمدة المتتالية؛ وهو ببساطة رمز ليمر للتبديل العكسي، والعكس صحيح. 

لتحويل رمز ليمر d _{_n} , d _{_{n -1}} , ..., d _₂ , d_₁ إلى تبديل لمجموعة مرتبة S ، يمكن البدء بقائمة عناصر S مرتبة تصاعديًا، ثم لكل i من 1 إلى n، يتم تعيين σ _{_i} للعنصر في القائمة الذي يسبقه d _{_{n +1- i}} عنصرًا آخر، ثم يُحذف هذا العنصر من القائمة. ولتحويل جدول الانعكاس d _{_n} , d _{_{n -1}} , ..., d _₂ , d _₁ إلى التبديل المقابل، يمكن المرور على الأرقام من d _₁ إلى d _{_n} مع إدخال عناصر S من الأكبر إلى الأصغر في متتالية فارغة مبدئيًا؛ عند الخطوة التي تستخدم الرقم d من جدول الانعكاس، يُدخل العنصر من S في المتتالية عند النقطة التي يسبقه فيها d عنصرًا موجودًا مسبقًا. بدلاً من ذلك، يمكن معالجة الأرقام من جدول الانعكاس وعناصر S بترتيب عكسي، بدءًا من صف من n خانة فارغة، وفي كل خطوة يتم وضع العنصر من S في الخانة الفارغة التي تسبقها d خانات فارغة أخرى.

يؤدي تحويل الأعداد الطبيعية المتتالية إلى نظام الأعداد المضروبية إلى إنتاج تلك المتتاليات بترتيب معجمي (كما هو الحال مع أي نظام أعداد ذي أساس مختلط)، ويحافظ تحويلها لاحقًا إلى تباديل على الترتيب المعجمي، شريطة استخدام تفسير رمز ليمر (باستخدام جداول الانعكاس، نحصل على ترتيب مختلف، حيث نبدأ بمقارنة التباديل حسب موضع العنصر 1 بدلاً من قيمة أول عنصر فيها). يعطي مجموع الأعداد في تمثيل نظام الأعداد المضروبية عدد انعكاسات التبديل، وتعطي زوجية هذا المجموع إشارة التبديل . علاوة على ذلك، تعطي مواضع الأصفار في جدول الانعكاس قيم القيم القصوى من اليسار إلى اليمين للتبديل (في المثال 6، 8، 9)، بينما مواضع الأصفار في رمز ليمر هي مواضع القيم الدنيا من اليمين إلى اليسار (في المثال المواضع 4، 8، 9 للقيم 1، 2، 5). يُتيح ذلك حساب توزيع هذه القيم القصوى بين جميع التباديل. يكون للتباديل ذات رمز ليمر d _{_n} ، d _{_{n -1}} ، ...، d _₂ ، d_₁ صعود n - i إذا وفقط إذا كان d _{_i} ≥ d _{_{i +1}} .

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

إحدى الطرق الواضحة لتوليد تباديل العدد n هي توليد قيم لرمز ليمر (ربما باستخدام تمثيل نظام الأعداد المضروبية للأعداد الصحيحة حتى n !)، ثم تحويلها إلى التباديل المقابلة. مع ذلك، فإن الخطوة الأخيرة، رغم بساطتها، يصعب تنفيذها بكفاءة، لأنها تتطلب n عملية لكل من الاختيار من متتالية والحذف منها، في أي موضع. من بين التمثيلات الواضحة للمتتالية كمصفوفة أو قائمة مرتبطة ، يتطلب كلاهما (لأسباب مختلفة) حوالي n² /⁴ عملية لإجراء التحويل. مع احتمال أن يكون n صغيرًا نسبيًا (خاصةً إذا كانت هناك حاجة لتوليد جميع التباديل)، فإن ذلك لا يمثل مشكلة كبيرة، ولكن اتضح أن هناك بدائل بسيطة، سواء للتوليد العشوائي أو المنهجي، تُحقق نتائج أفضل بكثير. لهذا السبب، لا يبدو من المفيد، وإن كان ممكنًا بالتأكيد، استخدام بنية بيانات خاصة ^تسمح بإجراء التحويل من رمز ليمر إلى التبديل في زمن O ( n log n ) .

for i from n downto 2 do d i ← random element of { 0, ..., i − 1 } swap a [ d i ] and a [ i − 1]

لـ i من 0 إلى n − 1، نفّذ ما يلي: d( i + 1) ← عنصر عشوائي من المجموعة {0, ..., i } ، a [ i ] ← a [ d (i + 1 ) ] ، a [d ( i + 1 )] ← i

جيل بأقل قدر من التغييرات

تُعدّ خوارزمية شتاينهاوس-جونسون-تروتر بديلاً للخوارزمية المذكورة أعلاه، إذ تُنشئ ترتيبًا لجميع تباديل متتالية مُعطاة، بحيث يختلف أي تبديلين متتاليين في ناتجها بتبديل قيمتين متجاورتين. كان هذا الترتيب معروفًا لدى قارعي الأجراس الإنجليز في القرن السابع عشر، وكان يُعرف بينهم باسم "التغييرات البسيطة". من مزايا هذه الطريقة أن التغيير الطفيف بين كل تبديل وآخر يسمح بتنفيذها في وقت ثابت لكل تبديل. كما يُمكنها بسهولة توليد مجموعة فرعية من التباديل الزوجية، أيضًا في وقت ثابت لكل تبديل، وذلك بتجاوز تبديل واحد من كل تبديلين في الناتج. ^{[ 57 ]}

يُعد خوارزمية هيب بديلاً لخوارزمية شتاينهاوس-جونسون-تروتر ، ^{[ 59 ]} وقد وصفها روبرت سيدجويك في عام 1977 بأنها أسرع خوارزمية لتوليد التباديل في التطبيقات. ^{[ 56 ]}

يوضح الشكل التالي مخرجات الخوارزميات الثلاث المذكورة أعلاه لتوليد جميع التباديل ذات الطول${\displaystyle n=4}$وستة خوارزميات إضافية موصوفة في الأدبيات.

1. الترتيب المعجمي؛
2. خوارزمية ستاينهاوس-جونسون-تروتر ؛
3. خوارزمية الكومة ؛
4. خوارزمية إيرليخ للتبديل النجمي: ^{[ 57 ]} في كل خطوة، يتم تبديل الإدخال الأول للتبديل مع إدخال لاحق؛
5. خوارزمية عكس البادئة لزاكس: ^{[ 61 ]} في كل خطوة، يتم عكس بادئة التبديل الحالي للحصول على التبديل التالي؛
6. خوارزمية Sawada-Williams: ^{[ 62 ]} يختلف كل تبديل عن التبديل السابق إما عن طريق إزاحة دورية لليسار بمقدار موضع واحد، أو عن طريق تبديل أول مدخلين؛
7. خوارزمية كوربيت: ^{[ 63 ]} يختلف كل تبديل عن التبديل السابق بإزاحة دورية لليسار لبعض البادئة بمقدار موضع واحد؛
8. ترتيب المسار الواحد: ^{[ 64 ]} كل عمود هو إزاحة دورية للأعمدة الأخرى؛
9. رمز غراي أحادي المسار : ^{[ 64 ]} كل عمود هو إزاحة دورية للأعمدة الأخرى، بالإضافة إلى أن أي تبديلين متتاليين يختلفان فقط في تبديل واحد أو اثنين.
10. خوارزمية توليد التبديلات المتداخلة في خطوات متصلة بالمجموعات الفرعية المتداخلة${\displaystyle S_{k}\subset S_{k+1}}$يتم الحصول على كل تبديل من التبديل السابق عن طريق عملية ضرب تبديلية إلى اليسار. وترتبط الخوارزمية بنظام الأعداد المضروبية للفهرس.

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