افتح القائمة الرئيسية
Applications-development current.svg
هذه المقالة قيد التطوير. إذا كان لديك أي استفسار أو تساؤل، فضلًا ضعه في صفحة النقاش قبل إجراء أي تعديل عليها. مَن يقوم بتحريرها يظهر اسمه في تاريخ الصفحة.
كل من الصفوف السته تمثل تبديلات مختلفة لثلاث كور مختلفة.

في الرياضيات، التبديلات (جمع التبديلة)[1] (بالإنجليزية: Permutation) هي عملية ترتيب عناصر مجموعة في متسلسلة او بترتيب معين. إذا كانت العناصر مرتبة، فعملية إعادة ترتيب عناصرها تسمى تبديل ( permuting ). تختلف التبديلات عن التوافيق والتي تعرف بأنها مختارات لعناصر من مجموعة ما بدون اعتبار الترتيب. على سبيل المثال: يوجد تبديلات للمجموعة وهي كالآتي:

. هذه هي جميع الترتيبات الممكنه لمجموعة من عناصر. تقليب ( ) كلمات لها حروف مختلفة أيضا تشكل نوع من التبديلات. فأي حروف في أي كلمة مرتبة بترتيب معين لكن تقليب أة اعارة ترتيب الحروف يعتبر تبديل. يعتبر دراسة تبديلات مجموعات منتهية من المةاضع المهمه في مجال combinatorics ونظرية الزمر.

تُدرس التبديلات في أغلب فروع الرياضيات وفي مجالات عديدة في العلوم. يتم استخدام التبديلات في علوم الحاسب لتحليل ترتيب خوارزمية و ميكانيكا الكم و أيضا في الأحياء.

عدد التبديلات ل من العناصر المختلفة يساوي مضروب ،والذي يكتب بالصيغة . المقصود هنا بمضروب هو عملية ضرب جميع الأعداد الصحيحة الموجبة الأقل من أو يساوي .

في الجبر وبالتحديد في نظرية الزمر، تبديل المجموعة هو تقابل من المجموعة لنفسها[2] [3]. والمقصود بالتقابل هنا هي دالة من إلى حيث يوجد صورة واحدة لكل عنصر. وهـذا مرتبط بإعادة ترتيب عناصر حيث يستبدل كل عنصر بالصورة المقابله له . فعلى سبيل المثال، ممكن كتابة التبديلة المذكورة اعلاه بالدالة المعرفة كالتالي:

.

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

في elementary combinatorics ، يُستخدم مصطلحي التبديلات الجزئية وتبديلات لـ (k-permutations) والتي تعني بترتيب عدد من العناصر المختلفة المختارة من مجموعة ما. وعندما تكون ( partial permutations ) تساوي عدد عناصر المجموعة فإن هذين التبديلين يعتبر تبديلات للمجموعة ككل.

نبذة تاريخيةعدل

كانت القاعدة التي تمكن من حساب عدد التبديلات لمجموعة ما، معروفة لدى الهنديين على الأقل في حوالي عام 1150م.


تعريفعدل

في مناهج الرياضيات يتم استخدام الحروف اليونانيه الصغيرة كرموز للتبديلات. وأكثر هذه الرموز استخداما هي الحروف   و   أو   و  و .

يمكن تعريف التبديلات كتقابلات من مجموعة   لنفسها . كل التبديلات على مجموعة بها   من العناصر تمثل زمرة متماثلة ويرمز لها بالرمز   ، حيث أن عملية الزمرة هنا هي عملية تحصيل الدوال. فبالتالي لأي تبديلين   و   من الزمرة   فإن خواص الزمرة الأربع متحققه هنا وهي كما يلي:

  1. الإغلاق: فإذا كان   و   عناصر في   فإن   أيضا ينتمي لـ  .
  2. التجميع: لأي ثلاث تبديلات   فإن  .
  3. عنصر محايد: يوجد تبديلة وحدة يرمز لها بالرمز   والمعرفه كما يلي   لكل  . بالتالي لأي   فإن  .
  4. المعكوس: لكل تبديلة   يوجد   والتي تحقق  .

بشكل عام فإن تحصيل أي تبديلتين  هي عملية ليست دائما إبدالية ، أي أن   .

مثالعدل

يراد سحب كرتين على التوالي من صندوق أسود يحوي أربع كرات ملونة سوداء وزرقاء وحمراء وصفراء. المطلوب حساب عدد الاحتمالات الممكنة لنتيجة السحب.

كون السحب يتم على التتالي فان هناك أهمية للترتيب لأنه إذا كانت الكرة الأولى على سبيل المثال سوداء والثانية حمراء هذه النتيجة تختلف عن الحالة التي يكون فيها الكرة الأولى حمراء والثانية سوداء. بتطبيق القانون نحصل على عدد الاحتمالات الممكنة ت(2,4)=4!\(4-2)!=4×3×2×1 /2×1 = 12 احتمال ممكن و هي بالتفصيل كالتالي: (سوداء، حمراء) (حمراء,سوداء) (زرقاء,سوداء) (صفراء,سوداء) (سوداء، زرقاء) (حمراء، زرقاء) (زرقاء، حمراء) (صفراء، حمراء) (سوداء، صفراء) (حمراء، صفراء) (زرقاء، صفراء) (صفراء، زرقاء).


طريقة كتابة التبديلة والرموز المستعملةعدل

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

الترميز بإستخدام صفينعدل

يستخدم رمزكوشي [4]صفين بحيث يتم وضع عناصر المجموعة بالصف الأول بينما صور كل من هذه العناصر توضح مباشرة اسفله بالصف السفلي. فمثلا، التبديلة للمجموعة   يمكن كتابتها كما يلي

 

وهذا يعني أن σ تحقق ما يلي : σ(1)=2 و σ(2)=5 و σ(3)=4 و σ(4)=3 و σ(5)=1. تظهر عناصر المجموعة   بأي ترتيب في الصف الأول. فبالتالي يمكن كتابة هذه التبديلة بطريقة اخرى كالتالي

 .


الترميز بإستخدام صف واحدعدل

في حالة وجود ترتيب طبيعي لعناصر المجموعة   [a]ولتكن   فإنه يمكن وضعها بالصف الأول من الترميز بصفين بشكل عام كالتالي:

 .

وبما أن عناصر المجموعة   تتخذ ترتيبا طبيعيا فإنه من الممكن حذف الصف الأول واستخدام التبديلة بترميز صف واحد كما يلي

 

كما في ترتيب عناصر المجموعة  .[5][6] يجب التفريق هنا بين الترميز بصف والترميز الدائري الذي سيوضح بالأسفل. فمن الشائع بالدراسات الرياضية حذف الأقواس بترميز بصف واحد بينما تستخدم الأقواس في الترميز الدائري. يسمى أيضا الترميز بصف واحد بممثل الكلمة ( word) في أي تبديلة.[7] ففي المثال السابق يمكن كتابة التبديلة بالشكل   حيث أن   تشكل ترتيب طبيعي للصف الأول. يستخدم هذا الرمز بالتراكيب وعلوم الحاسب خصوصا بالتطبيقات التي بها عناصر   او التبديلات كبيرة او صغيرة نوعا ما.

الترميز الدائريعدل

يمكن وصف الترميز الدائري بالتأثير المكرر للتبديلة على عناصر المجموعة . فهي تبين التبديلة كحاصل ضرب دوائر. وحيث أن هذه الدوائر منفصلة فإنها توصف بـ "decomposition into disjoint cycles".[b]

لكتابة التبديلة   بالترميز الدائري فإننا نتبع الخطوات التالية:

  1. نبدأ بكتابة قوس مفتوح ونختار أي عنصر   من المجموعة   ونكتبه كأول عنصر :  
  2. بعد ذلك نتابع التأثير المتتابع للتبديلة عالعنصر السابق ونكتبه كما يلي :  
  3. نكرر هذه الخطوات حتى الوصول لنفس العنصر الذي بدأنا به   بالتالي نغلق الأقواس بدون تكرار كتابة   :  
  4. لنواصل الأن بإختيار عنصر آخر  لم يسبق كتابته بالدائرة الأولى ونكرر نفس الخطوات هنا مع هذا العنصر :  
  5. نكرر هذه الخطوات حتى يتم كتابة جميع عناصر  بالدوائر.

حيث أن كل دائرة جديدة تبدأ بإختيار عنصر عشوائي من   فإنه يوجد طرق مختلفة لكتابة تبديلة ما بالترميز الدائري، ففي نفس المثال المذكور سابقا يمكن كتابة التبديلة كالتالي:

 


نلاحظ أيضا انه يتم حذف الدائرة التي بها عنصر واحد والتي يكون واضحا دون الحاجة لكتابته، فأي عنصر   لايظهر بأي دائرة بالترميز الدائري فهذا يعني أن  .[8] في تبديلة الوحدة والتي تتكون من دوائر بعنصر واحد يمكن كتابتها بدائرة واحدة بعنصر واحد   [c]، العنصر رقم أو بواسطة الرمز  [9] [10] .

من ضمن مميزات استخدام الترميز الدائري فإنه يسهل كتابة معكوس أي تبديلة بشكل أسهل بواسطة عكس ترتيب عناصر التبديلة بكل دوائره. فعلى سبيل المثال:

  .


الترميز الدائري التدريجي( Canonical cycle notation)عدل

في بعض الكتابات المختصة بالتراكيب فإنه من المهم استخدام ترتيب ثابت لعناصر أي دائرة بالترميز الدائري. فوضح الباحث Miklós Bóna أنه يوجد نوعين من الترتيب في الترميز الدائري التدريجي وهما:

  • بكل دائرة يتم البدء بأكبر عنصر بالمجموعة   بأول دائرة.
  • ترتب الدوائر بشكل متزايد بالنسبة لأول عنصر بكل منها.

فعلى سبيل المثال التبديلة بالشكل   هي بالرمز الدائري التدريجي.[11] بهذا الترميز لايتم حذف الدوائر ذوات العنصر الواحد. استخدم العالم Sergey Kitaev نفس المفهوم لكن بشكل عكسي حيث يتم ترتيب الدوائر بالبدء بالدائرة ذات العنصر الأصغر وترتيب بقية الدوائر بشكل متناقص حسب العنصر الأول بكل دائرة.[12]

تحصيل التبديلات ( Composition of permutations)عدل

يوجد طريقتين لكتابة تحصيل أي تبديلتين. يستخدم الرمز لتمثيل دالة تطبق من أي عنصر  إلى العنصر  . فالتبديلة التي بالطرف الأيمن تطبق أولا عالعنصر [13].


وحيث أن عملية تحصيل الدوال هي عملية تجميعية فإن عملية تحصيل التبديلات هي أيضا تجميعية أي أن :  . فبالتالي يمكن إيجاد تحصيل أي أكثر من تبديلتين بإستخدام خاصية التجميع والإستعانه بالأقواس. من الممكن أيضا كتابة تحصيل التبديلات بدون نقطة بينهم او أي علامة لتوضيح عملية التحصيل.

بعض الباحثين يفضلون تطبيق تأثير التبديلة التي بالطرق الأيسر أولا[14][15][16] ، لكن في هذه الحالة يتم كتابة عملية التحصيل بشكل أسس فمثلا لتمثيل تأثير   على   يكتب بالشكل  ، والتحصيل بهذه الحالة يكتب بالشكل  . لكن هذا التحصيل يعطي نتيجة مختلفة عن التحصيل المعرف سابقا والذي يطبق التبديلة اليمنى أولا.

استخدامات اخرى لمصطلح تبديلعدل

خصائصعدل


تبديلات لمجموعات مرتبة كلياعدل


تبديلات في الحسابعدل


تطبيقاتعدل

انظر أيضاعدل

مراجععدل

  1. ^ التبديل اسم ومصدر، ويقال التبديلة لبيان أن المقصود هو الاسم.
  2. ^ Nering(1970,p.86)
  3. ^ McCoy (1968, p. 152)
  4. ^ Wussing، Hans (2007)، The Genesis of the Abstract Group Concept: A Contribution to the History of the Origin of Abstract Group Theory، Courier Dover Publications، صفحة 94، ISBN 9780486458687، Cauchy used his permutation notation—in which the arrangements are written one below the other and both are enclosed in parentheses—for the first time in 1815. 
  5. ^ Bogart 1990, p. 17
  6. ^ Gerstein 1987, p. 217
  7. ^ Aigner، Martin (2007). A Course in Enumeration. Springer GTM 238. صفحات 24–25. ISBN 978-3-540-39035-0. 
  8. ^ Hall 1959, p. 54
  9. ^ Bogart 1990, p. 487
  10. ^ Rotman 2002, p. 41
  11. ^ Bona 2012, p.87 [Note that the book has a typo/error here, as it gives (45) instead of (54).]
  12. ^ Kitaev، Sergey (2011). Patterns in Permutations and Words. Springer Science & Business Media. صفحة 119. ISBN 978-3-642-17333-2. 
  13. ^ Biggs، Norman L.؛ White، A. T. (1979). Permutation groups and combinatorial structures. Cambridge University Press. ISBN 978-0-521-22287-7. 
  14. ^ Dixon، John D.؛ Mortimer، Brian (1996). Permutation Groups. Springer. ISBN 978-0-387-94599-6. 
  15. ^ Cameron، Peter J. (1999). Permutation groups. Cambridge University Press. ISBN 978-0-521-65302-2. 
  16. ^ Jerrum، M. (1986). "A compact representation of permutation groups". J. Algorithms. 7 (1): 60–78. doi:10.1016/0196-6774(86)90038-6. 


وسوم <ref> موجودة لمجموعة اسمها "lower-alpha"، ولكن لم يتم العثور على وسم <references group="lower-alpha"/> أو هناك وسم </ref> ناقص