التبديل الدوري

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

في الرياضيات ، وتحديدًا في نظرية الزمر ، يُعرَّف التبديل الدوري بأنه تبديل يتكون من دورة واحدة. [ 1 ] [ 2 ] في بعض الحالات، يُشار إلى التبديلات الدورية باسم الدورات ؛ [ 3 ] إذا احتوى التبديل الدوري على k عنصرًا، فقد يُسمى دورة من الرتبة k . يُوسِّع بعض المؤلفين هذا التعريف ليشمل التبديلات ذات النقاط الثابتة بالإضافة إلى دورة واحدة غير تافهة على الأكثر. [ 3 ] [ 4 ] في ترميز الدورات ، يُشار إلى التبديلات الدورية بقائمة عناصرها بين قوسين، بالترتيب الذي تُبدَّل به.

على سبيل المثال، يُعتبر التبديل (1 3 2 4) الذي يُبدّل 1 إلى 3، و3 إلى 2، و2 إلى 4، و4 إلى 1، دورةً رباعية، بينما يُعتبر التبديل (1 3 2)(4) الذي يُبدّل 1 إلى 3، و3 إلى 2، و2 إلى 1، و4 إلى 4، دورةً ثلاثيةً عند بعض الباحثين. من جهة أخرى، لا يُعتبر التبديل (1 3)(2 4) الذي يُبدّل 1 إلى 3، و3 إلى 1، و2 إلى 4، و4 إلى 2، تبديلاً دورياً لأنه يُبدّل الزوجين {1، 3} و{2، 4} على حدة.

بالنسبة للتعريف الأوسع للتبديل الدوري، الذي يسمح بوجود نقاط ثابتة، فإن كل نقطة ثابتة من هذه النقاط تُشكّل مدارًا تافهًا للتبديل، ويوجد مدار واحد غير تافه يحتوي على جميع النقاط المتبقية. ويمكن استخدام هذا التعريف على النحو التالي: التبديل الدوري (الذي يسمح بوجود نقاط ثابتة) هو تبديل له مدار واحد غير تافه. ويمكن تحليل أي تبديل على عدد محدود من العناصر إلى تبديلات دورية تكون مداراتها غير التافهة منفصلة. [ 5 ]

تُسمى الأجزاء الدورية الفردية للتبديل أيضًا بالدورات ، وبالتالي يتكون المثال الثاني من دورة 3 ودورة 1 (أو نقطة ثابتة ) ويتكون المثال الثالث من دورتين 2.

تعريف

تبديل دوري يتكون من دورة واحدة مكونة من 8.

لا يوجد إجماع واسع النطاق حول التعريف الدقيق للتبديل الدوري. يُعرّف بعض المؤلفين التبديل σ لمجموعة X بأنه دوري إذا كان "التطبيق المتتالي يُمرّر كل عنصر من عناصر المجموعة المُبدّلة تباعًا عبر مواقع جميع العناصر الأخرى"، [ 1 ] أو، بصورة مكافئة، إذا كان تمثيله في رمز الدورة يتكون من دورة واحدة. [ 2 ] بينما يُقدّم آخرون تعريفًا أكثر تساهلاً يسمح بالنقاط الثابتة. [ 3 ] [ 4 ]

المجموعة الجزئية غير الفارغة S من X هي دورة منσ{\displaystyle \sigma }إذا كان تقييدσ{\displaystyle \sigma }S هي تبديل دوري لـ S. إذا كانت X مجموعة منتهية ، فإن دوراتها منفصلة ، ​​واتحادها هو X. أي أنها تشكل تجزئة تسمى تجزئة الدورة لـσ.{\displaystyle \sigma .}لذا، وفقًا للتعريف الأكثر تساهلاً، فإن تبديل X يكون دوريًا إذا وفقط إذا كان X هو دورته الفريدة.

على سبيل المثال، التبديل، المكتوب بصيغة الدورة وصيغة السطرين (بطريقتين) كما يلي

(1 4 6 8 3 7)(2)(5)=(1234567842765813)=(1468372546837125){\displaystyle {\begin{aligned}(1\ 4\ 6\ &8\ 3\ 7)(2)(5)\\&={\begin{pmatrix}1&2&3&4&5&6&7&8\\4&2&7&6&5&8&1&3\end{pmatrix}}\\&={\begin{pmatrix}1&4&6&8&3&7&2&5\\4&6&8&3&7&1&2&5\end{pmatrix}}\end{aligned}}}

يحتوي على دورة واحدة من ست دورات ودورتين من دورة واحدة من واحد، ويظهر مخطط دورته على اليمين. يعتبر بعض المؤلفين هذا التبديل دوريًا، بينما لا يعتبره آخرون كذلك.

تبديل دوري في التعريف الموسع ولكنه ليس كذلك في التعريف المقيد، مع نقطتين ثابتتين (دورات من الدرجة 1) ودورة من الدرجة 6

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

بصورة أكثر رسمية، بالنسبة للتعريف الموسع، التبديلσ{\displaystyle \sigma }من مجموعة X ، يُنظر إليها كدالة تقابليةσ:X→X{\displaystyle \sigma :X\to X}يُطلق عليها اسم دورة إذا كان تأثير المجموعة الفرعية المولدة بواسطة على Xσ{\displaystyle \sigma }يحتوي على مدار واحد على الأكثر بأكثر من عنصر واحد. [ 6 ] يُستخدم هذا المفهوم عادةً عندما تكون X مجموعة منتهية؛ فحينها يكون أكبر مدار، S ، منتهيًا أيضًا. ليكنs0{\displaystyle s_{0}}ليكن أي عنصر من S ، وضعsأنا=σأنا(s0){\displaystyle s_{i}=\sigma ^{i}(s_{0})}لأيأنا∈Z{\displaystyle i\in \mathbf {Z} }إذا كانت S محدودة، فهناك عدد أدنىك≥1{\displaystyle k\geq 1}والتيsك=s0{\displaystyle s_{k}=s_{0}}. ثمS={s0،s1،...،sك-1}{\displaystyle S=\{s_{0},s_{1},\ldots ,s_{k-1}\}}، وσ{\displaystyle \sigma }التبديل المحدد بواسطة

σ(sأنا)=sأنا+1{\displaystyle \sigma (s_{i})=s_{i+1}}لـ 0 ≤ i < k

وσ(x)=x{\displaystyle \sigma (x)=x}لأي عنصر منX∖S{\displaystyle X\setminus S}العناصر غير الثابتة بواسطةσ{\displaystyle \sigma }يمكن تصويرها على النحو التالي

s0↦s1↦s2↦⋯↦sك-1↦sك=s0{\displaystyle s_{0}\mapsto s_{1}\mapsto s_{2}\mapsto \cdots \mapsto s_{k-1}\mapsto s_{k}=s_{0}}.

يمكن كتابة التبديل الدوري باستخدام تدوين الدورة المختصر.σ=(s0 s1 ... sك-1){\displaystyle \sigma =(s_{0}~s_{1}~\dots ~s_{k-1})}(لا توجد فواصل بين العناصر في هذه الصيغة، لتجنب الخلط مع مجموعة k ) . طول الدورة هو عدد عناصر أكبر مدار لها. وتُسمى الدورة التي طولها k أيضًا دورة k .

يُطلق على مدار الدورة الأحادية اسم نقطة ثابتة للتبديل، ولكن كل دورة أحادية، باعتبارها تبديلاً، هي تبديل محايد . [ 7 ] عند استخدام ترميز الدورة، غالبًا ما تُحذف الدورات الأحادية عندما لا ينتج عن ذلك أي لبس. [ 8 ]

الخصائص الأساسية

من النتائج الأساسية المتعلقة بالمجموعات المتناظرة أن أي تبديل يمكن التعبير عنه كحاصل ضرب دورات منفصلة (أو بتعبير أدق: دورات ذات مدارات منفصلة)؛ تتبادل هذه الدورات فيما بينها، ويكون التعبير عن التبديل فريدًا حتى رتبة الدورات. [ أ ] وبالتالي، فإن مجموعة أطوال الدورات في هذا التعبير ( نوع الدورة ) تُحدد بشكل فريد بواسطة التبديل، كما أن كلًا من توقيع التبديل وفئة اقترانه في المجموعة المتناظرة يُحددان به. [ 9 ]

يُعطى عدد الدورات من الرتبة k في المجموعة المتناظرة S n ، لـ1≤ك≤ن{\displaystyle 1\leq k\leq n}، وذلك باستخدام الصيغ المكافئة التالية: (نك)(ك-1)!=ن(ن-1)⋯(ن-ك+1)ك=ن!(ن-ك)!ك.{\displaystyle {\binom {n}{k}}(k-1)!={\frac {n(n-1)\cdots (n-k+1)}{k}}={\frac {n!}{(nk)!k}}.}

الدورة k لها توقيع (−1) k  −  1 .

عكس الدورة​σ=(s0 s1 ... sك-1){\displaystyle \sigma =(s_{0}~s_{1}~\dots ~s_{k-1})}يتم الحصول على ذلك عن طريق عكس ترتيب الإدخالات:σ-1=(sك-1 ... s1 s0){\displaystyle \sigma ^{-1}=(s_{k-1}~\dots ~s_{1}~s_{0})}على وجه الخصوص، بما أن(أ ب)=(ب أ){\displaystyle (a~b)=(b~a)}كل دورة ثنائية هي معكوسها. وبما أن الدورات المنفصلة تتبادل، فإن معكوس حاصل ضرب دورات منفصلة هو نتيجة عكس كل دورة على حدة.

عمليات النقل

مصفوفة منπ{\displaystyle \pi }

تُسمى الدورة التي تحتوي على عنصرين فقط بالتبديل . على سبيل المثال، التبديلπ=(12341432){\displaystyle \pi ={\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}}}هذا يُبدّل الرقمين 2 و4. وبما أنه دورة ثنائية، فيمكن كتابته على النحو التالي:π=(2 4){\displaystyle \pi =(2\ 4)}.

ملكيات

يمكن التعبير عن أي تبديل على أنه تركيب (حاصل ضرب) عمليات تبديل - وهي، بشكل رسمي، مولدات للمجموعة . [ 10 ] في الواقع، عندما تكون المجموعة المراد تبديلها هي {1، 2، ...، n } لعدد صحيح n ، فإنه يمكن التعبير عن أي تبديل على أنه حاصل ضربعمليات النقل المتجاورة(1 2)،(2 3)،(3 4)،{\displaystyle (1~2),(2~3),(3~4),}وهكذا دواليك. وينتج هذا عن إمكانية التعبير عن أي عملية تبديل كحاصل ضرب عمليات تبديل متجاورة. وبشكل ملموس، يمكن التعبير عن عملية التبديل(ك  ل){\displaystyle (k~~l)}أينك<ل{\displaystyle k<l}عن طريق نقل k إلى l خطوة واحدة في كل مرة، ثم إعادة l إلى المكان الذي كان فيه k ، مما يؤدي إلى تبديل هذين العنصرين دون إجراء أي تغييرات أخرى:

(ك  ل)=(ك  ك+1)⋅(ك+1  ك+2)⋯(ل-1  ل)⋅(ل-2  ل-1)⋯(ك  ك+1).{\displaystyle (k~~l)=(k~~k+1)\cdot (k+1~~k+2)\cdots (l-1~~l)\cdot (l-2~~l-1)\cdots (k~~k+1).}

يتم الحصول على تحليل التبديل إلى ناتج عمليات النقل، على سبيل المثال، عن طريق كتابة التبديل كناتج لدورات منفصلة، ​​ثم تقسيم كل دورة من الدورات التي يبلغ طولها 3 أو أكثر بشكل متكرر إلى ناتج عملية نقل ودورة طولها أقل بواحد:

(أ ب ج د ... y z)=(أ ب)⋅(ب ج د ... y z).{\displaystyle (a~b~c~d~\ldots ~y~z)=(a~b)\cdot (b~c~d~\ldots ~y~z).}

هذا يعني أن الطلب الأولي هو الانتقالأ{\displaystyle a}لب،{\displaystyle b,}ب{\displaystyle b}لج،{\displaystyle c,}y{\displaystyle y}لz،{\displaystyle z,}وأخيراًz{\displaystyle z}لأ.{\displaystyle a.}بدلاً من ذلك، يمكن للمرء أن يلف العناصر مع الحفاظ علىأ{\displaystyle a}حيث يتم ذلك عن طريق تنفيذ العامل الصحيح أولاً (كما هو معتاد في تدوين العمليات، واتباعًا للاتفاقية الواردة في مقالة التبديل ). وقد تم نقل هذاz{\displaystyle z}إلى منصبب،{\displaystyle b,}بعد التبديل الأول، العناصرأ{\displaystyle a}وz{\displaystyle z}لم تصل بعد إلى مواقعها النهائية.(أ ب)،{\displaystyle (a~b),}ثم يتم التنفيذ، ثم العناوينz{\displaystyle z}حسب فهرسب{\displaystyle b}لتبديل ما كان في البدايةأ{\displaystyle a}وz.{\displaystyle z.}

في الواقع، المجموعة المتناظرة هي مجموعة كوكسيتر ، مما يعني أنها تتولد بواسطة عناصر من الرتبة 2 (التبديلات المتجاورة)، وجميع العلاقات لها شكل معين.

تنص إحدى النتائج الرئيسية المتعلقة بالمجموعات المتناظرة على أن جميع تحليلات التبديل المعطى إلى تبديلات إما أن يكون لها عدد زوجي من التبديلات، أو أن يكون لها جميعًا عدد فردي من التبديلات. [ 11 ] وهذا يسمح بأن يكون مفهوم زوجية التبديل مفهومًا محددًا جيدًا .

انظر أيضاً

ملحوظات

  1. ↑ لاحظ أن ترميز الدورة ليس فريدًا:يمكن كتابة كل دورة من الرتبة k بطرق مختلفة k ، اعتمادًا على اختيارs0{\displaystyle s_{0}}في مدارها.

مراجع

  1. 1 2 غروس، جوناثان ل. (2008). الأساليب التوافقية مع تطبيقات الحاسوب . الرياضيات المتقطعة وتطبيقاتها. بوكا راتون، فلوريدا: تشابمان آند هول/سي آر سي. ص  29. ISBN 978-1-58488-743-0.
  2. 1 2 كنوت، دونالد إي. (2002). فن برمجة الحاسوب . أديسون-ويسلي. ص 35. 
  3. 1 2 3 بوغارت، كينيث ب. (2000). مقدمة في التوافقية ( الطبعة الثالثة). لندن: دار هاركورت الأكاديمية للنشر. ص 554. ISBN   978-0-12-110830-4.
  4. 1 2 روزن، كينيث هـ. (2000). دليل الرياضيات المتقطعة والتوافقية . بوكا راتون، لندن، نيويورك: مطبعة سي آر سي. ISBN 978-0-8493-0149-0.
  5. ↑ إيرليخ، جيرترود (2013). المفاهيم الأساسية للجبر المجرد . كتب دوفر في الرياضيات. شركة كورير. ص 69. ISBN  9780486291864.
  6. ↑ فرالي 1993 ، ص 103
  7. ↑ روتمان 2006 ، ص 108
  8. ↑ ساغان 1991 ، ص 2
  9. ↑ روتمان 2006 ، ص 117، 121
  10. ↑ روتمان 2006 ، ص 118، الاقتراح 2.35
  11. ↑ روتمان 2006 ، ص 122

مصادر

  • أندرسون، مارلو وفيل، تود (2005)، مدخل إلى الجبر المجرد ، تشابمان آند هول/سي آر سي؛ الطبعة الثانية. ISBN 1-58488-515-7.
  • فرالي ، جون (1993)، دورة أولى في الجبر التجريدي (  الطبعة الخامسة)، أديسون ويسلي، ISBN 978-0-201-53467-2
  • روتمان، جوزيف ج. (2006)، مدخل إلى الجبر المجرد مع تطبيقات (  الطبعة الثالثة)، برنتيس هول، رقم ISBN 978-0-13-186267-8
  • ساجان، بروس إي. (1991)، المجموعة المتناظرة / التمثيلات، الخوارزميات التوافقية والدوال المتناظرة ، وادزورث وبروكس/كول، ISBN 978-0-534-15540-7

تتضمن هذه المقالة مواد من موقع Cycle على PlanetMath ، وهو مرخص بموجب رخصة Creative Commons Attribution/Share-Alike .