عرض مصدر تبديل (توافيقيات)

{{عن|3=تبديل (توضيح)}}
{{بطاقة عامة}}
{{ميز|توفيق (رياضيات)}}

[[ملف:Permutations RGB.svg|تصغير|150px|كل من الصفوف السته تمثل تبديلات مختلفة لثلاث كور مختلفة.]]

في [[رياضيات|الرياضيات]] وتحديدًا في [[تحليل توافيقي|التوافيقيات]]، '''التبديل'''<ref>{{ترقيم استشهادات|نمط=محرف عربي
|م1={{استشهاد بويكي بيانات|Q108593221|ص=523}}
|م2={{استشهاد بويكي بيانات|Q125363697|ص=289}}}}</ref> {{جمع|تباديل}} {{إنج|Permutation}} هي عملية ترتيب عناصر مجموعة في متسلسلة أو بترتيب معين. إذا كانت العناصر مرتبة، فعملية إعادة ترتيب عناصرها تسمى تبديلا.
تختلف التباديل عن التوافيق والتي تعرف بأنها مختارات لعناصر من مجموعة ما بدون اعتبار الترتيب. على سبيل المثال: يوجد <math>6</math> تبديلات للمجموعة <math>\{ 1,2,3\}</math> وهي كالآتي:

<math>(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2) , (3,2,1)</math>.
هذه هي جميع الترتيبات الممكنة لمجموعة من <math>3</math> عناصر. قلب كلمات لها حروف مختلفة أيضا تشكل نوعا من التباديل. فأي حروف في أي كلمة مرتبة بترتيب معين لكن قلب أو إعادة ترتيب الحروف يعتبر تبديلا.
دراسة تبديلات المجموعات المنتهية موضوع مهم في مجال [[تركيبات|التوافقيات]] و[[نظرية الزمر]].

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

عدد التباديل التي يمكن أن تخضع لها مجموعة عدد عناصرها هو <math>n</math> يساوي [[عاملي|مضروب]] <math>n</math> ، والذي يكتب بالصيغة <math>n!</math>. مضروب <math>n</math> هو عملية ضرب جميع الأعداد الصحيحة الموجبة الأقل من أو يساوي <math>n</math> .

في [[جبر|الجبر]] وبالتحديد في [[نظرية الزمر]]، تبديل المجموعة <math>S</math>هو تقابل من المجموعة <math>S</math> نحو نفسها.<ref>Nering(1970,p.86)</ref><ref>{{Harvard citation text|McCoy|1968|p=152}}</ref> والمقصود بالتقابل هو دالة من <math>S</math> إلى <math>S</math> حيث يوجد صورة واحدة لكل عنصر. وهـذا مرتبط بإعادة ترتيب عناصر <math>S</math> حيث يستبدل كل عنصر <math>s</math> بالصورة المقابلة له <math>f(s)</math>. فعلى سبيل المثال، ممكن كتابة التبديلة <math>(3,1,2)</math> المذكورة اعلاه بالدالة <math>\alpha </math> المعرفة كالتالي:

<math>\alpha(1)=3, \alpha(2)=1, \alpha(3)=2</math>.

تشكل مجموعة جميع التباديل الممكنة لمجموعة ما زمرة تُدعى [[زمرة تبديلات]].
المهم في هذه الزمرة هو أن عملية تحصيل أي تبديلتين ينتج عنها تبديلة جديدة. ممكن أن تُشكل أي تبديلة لمجموعة عناصر بإحدى طريقتين: إما بترتيب مركباته أو باستخدام اسلوب التعويض لأحد الرموز. بالغالب نستخدم المجموعة <math>S=N_n =\{1,2,\ldots,n \}</math> لكن لايوجد أيضا مانع لإستخدام أي مجموعة.

في إطار [[تركيبات|التركيبات]] الابتدائية، يُستخدم مصطلحي التباديل الجزئية وتبديلات لـ <math>k</math> ({{تعبير رياضي|''k''}}-permutations) والتي تعني بترتيب عدد <math>k</math>من العناصر المختلفة المختارة من مجموعة ما. وعندما تكون ([[:en:Partial permutation|partial permutations]]) تساوي عدد عناصر المجموعة فإن هذين التبديلين يعتبر تبديلات للمجموعة ككل.

== التاريخ ==

[[الخليل بن أحمد الفراهيدي]] وهو عالم رياضيات عربي، كتب كتابا حول [[علم التعمية|تشفير]] الرسائل. يحتوي الكتاب على أول استعمال للتبديلات من أجل سرد جميع الكلمات العربية [[حروف العلة|بحروف العلة]] وبدونهن.

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

== تعريف ==
في مناهج الرياضيات، تُستخدم الحروف اليونانية الصغيرة رموزا للتبديلات. وأكثر هذه الرموز استخداما هي الحروف <math>\alpha</math> و <math>\beta </math> و <math>\sigma</math> و <math>\tau</math> و <math>\pi</math>.

يمكن تعريف التباديل تقابلاتٍ من مجموعة <math>S</math> نحو نفسها. كل التباديل على مجموعة بها <math>n</math> من العناصر تمثل [[زمرة متناظرة|زمرة متماثلة]] ويرمز لها بالرمز <math>S_n</math> ، حيث أن عملية الزمرة هنا هي عملية [[تركيب الدوال]]. فبالتالي لأي تبديلين <math>\pi</math> و <math>\sigma</math> من الزمرة <math>S_n</math> فإن خواص الزمرة الأربع متحققة وهي كما يلي:

# الانغلاق: فإذا كان <math>\pi</math> و <math>\sigma</math> عناصر في <math>S_n</math> فإن <math>\pi \sigma</math> أيضا ينتمي لـ <math>S_n</math>.
# التجميع: لأي ثلاث تبديلات <math>\pi \, ,\sigma \,, \tau \in S_n</math> فإن <math>(\pi \sigma) \tau = \pi (\sigma \tau)</math>.
# عنصر محايد: يوجد تبديلة وحدة يرمز لها بالرمز <math>\mathbb{id}</math> والمعرفة كما يلي <math>\mathbb{id}(x)=x</math> لكل <math>x \in S</math>. بالتالي لأي <math>\sigma \in S_n</math> فإن <math>\mathbb{id} \, \sigma = \sigma \, \mathbb{id}=\sigma</math>.
# المعكوس: لكل تبديلة <math>\pi \in S_n</math> يوجد <math>\pi^{-1} \in S_n</math> والتي تحقق <math>\pi \pi^{-1}=\pi^{-1} \pi =\mathbb{id}</math>.

بشكل عام فإن تحصيل أي تبديلتين <math>\pi , \sigma \in S_n</math>هي عملية ليست دائما [[عملية تبديلية|إبدالية]]، أي أن <math>\pi \sigma \neq \sigma \pi</math> .
<br />
=== مثال ===
يراد سحب كرتين على التوالي من صندوق أسود يحوي أربع كرات ملونة سوداء وزرقاء وحمراء وصفراء. المطلوب حساب عدد الاحتمالات الممكنة لنتيجة السحب.

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

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

=== الترميز باستخدام صفين ===
يستخدم رمزكوشي <ref>{{استشهاد|عنوان=The Genesis of the Abstract Group Concept: A Contribution to the History of the Origin of Abstract Group Theory|الأول=Hans|الأخير=Wussing|ناشر=Courier Dover Publications|سنة=2007|isbn=9780486458687|صفحة=94|مسار=https://books.google.com/books?id=Xp3JymnfAq4C&pg=PA94|اقتباس=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.| مسار أرشيف = https://web.archive.org/web/20200103005207/https://books.google.com/books?id=Xp3JymnfAq4C&pg=PA94 | تاريخ أرشيف = 3 يناير 2020 }}</ref> صفين بحيث يتم وضع عناصر المجموعة بالصف الأول بينما صور كل من هذه العناصر توضح مباشرة اسفله بالصف السفلي. فمثلا، التبديلة للمجموعة <math>S=\{ 1,2,3,4,5\}</math> يمكن كتابتها كما يلي: <math>\sigma=\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
2 & 5 & 4 & 3 & 1\end{pmatrix};</math>

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

<math>S=
\begin{pmatrix}
3&2&5&1&4\\
4&5&1&2&3
\end{pmatrix}</math>.

=== الترميز باستخدام صف واحد ===
في حالة وجود ترتيب طبيعي لعناصر المجموعة <math>S</math> {{ملا|The order is often implicitly understood. A set of integers is naturally written from smallest to largest; a set of letters is written in lexicographic order. For other sets, a natural order needs to be specified explicitly.}}ولتكن <math>x_1,x_2,\ldots,x_n</math> فإنه يمكن وضعها بالصف الأول من الترميز بصفين بشكل عام كالتالي:

<math>\sigma =
\begin{pmatrix}
x_1&x_2&x_3&\ldots&x_n\\
\sigma(x_1)&\sigma(x_2)&\sigma(x_3)&\ldots&\sigma(x_n)
\end{pmatrix}</math>.

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

<math>(\sigma(x_1) \,\, \sigma(x_2) \,\, \sigma(x_3) \,\, \ldots \sigma(x_n))</math>

كما في ترتيب عناصر المجموعة <math>S</math>.<ref>{{استشهاد بهارفارد دون أقواس|Bogart|1990|p=17}}</ref><ref>{{استشهاد بهارفارد دون أقواس|Gerstein|1987|p=217}}</ref> يجب التفريق هنا بين الترميز بصف والترميز الدائري الذي سيوضح بالأسفل. فمن الشائع بالدراسات الرياضية حذف الأقواس بترميز بصف واحد بينما تستخدم الأقواس في الترميز الدائري. يسمى أيضا الترميز بصف واحد بممثل الكلمة (''[[:en:Word (mathematics)|word]]'') في أي تبديلة.<ref name="Aigner2007">{{استشهاد بكتاب|الأول=Martin|الأخير=Aigner|عنوان=A Course in Enumeration|مسار= https://archive.org/details/courseenumeratio00aign_007|سنة=2007|ناشر=Springer GTM 238|isbn=978-3-540-39035-0|صفحات=[https://archive.org/details/courseenumeratio00aign_007/page/n32 24]–25|مسار أرشيف= https://web.archive.org/web/20201003221406/https://archive.org/details/courseenumeratio00aign_007|تاريخ أرشيف=2020-10-03}}</ref> ففي المثال السابق يمكن كتابة التبديلة بالشكل <math>2\,\,5\,\,4\,\,3\,\,1</math> حيث أن <math>1\,\,2\,\,3\,\,4\,\,5</math> تشكل ترتيب طبيعي للصف الأول. يستخدم هذا الرمز ب<nowiki/>[[تركيبات|التراكيب]] و[[علم الحاسوب|علوم الحاسب]] خصوصا بالتطبيقات التي بها عناصر <math>S</math> أو التباديل كبيرة أو صغيرة نوعا ما.

=== الترميز الدائري ===
يمكن وصف الترميز الدائري بالتأثير المكرر للتبديلة على عناصر المجموعة. فهي تبين التبديلة كحاصل ضرب دوائر. وحيث أن هذه الدوائر [[مجموعات متفارقة|منفصلة]] فإنها توصف بـ "decomposition into disjoint cycles".{{ملا|Due to the likely possibility of confusion, cycle notation is not used in conjunction with one-line notation (sequences) for permutations.}}

لكتابة التبديلة <math>\sigma</math> بالترميز الدائري فإننا نتبع الخطوات التالية:

# نبدأ بكتابة قوس مفتوح ونختار أي عنصر <math>x</math> من المجموعة <math>S</math> ونكتبه كأول عنصر: <math>(x</math>
# بعد ذلك نتابع التأثير المتتابع للتبديلة عالعنصر السابق ونكتبه كما يلي: <math>(x \quad \sigma(x) \quad \sigma(\sigma(x)) \ldots</math>
# نكرر هذه الخطوات حتى الوصول لنفس العنصر الذي بدأنا به <math>x</math> بالتالي نغلق الأقواس بدون تكرار كتابة <math>x</math> : <math>{\displaystyle (x\quad \sigma (x)\quad \sigma (\sigma (x))\ldots })</math>
# لنواصل الآن باختيار عنصر آخر<math>y \in S</math> لم يسبق كتابته بالدائرة الأولى ونكرر نفس الخطوات هنا مع هذا العنصر: <math>(x \quad \sigma (x)\quad \sigma (\sigma (x))\ldots ) (y \ldots </math>
# نكرر هذه الخطوات حتى يتم كتابة جميع عناصر<math>S</math> بالدوائر.

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

:<math>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\
2 & 5 & 4 & 3 & 1\end{pmatrix}=\begin{pmatrix}1 & 2 & 5 \end{pmatrix} \begin{pmatrix}3 & 4 \end{pmatrix} = \begin{pmatrix}3 & 4 \end{pmatrix} \begin{pmatrix}1 & 2 & 5 \end{pmatrix} = \begin{pmatrix}3 & 4 \end{pmatrix} \begin{pmatrix}5 & 1 & 2 \end{pmatrix}.</math>

<br />نلاحظ أيضا انه يتم حذف الدائرة التي بها عنصر واحد والتي يكون واضحا دون الحاجة لكتابته، فأي عنصر <math>x</math> لايظهر بأي دائرة بالترميز الدائري فهذا يعني أن <math>\sigma(x)=x</math>.<ref>{{استشهاد بهارفارد دون أقواس|Hall|1959|p=54}}</ref> في تبديلة الوحدة والتي تتكون من دوائر بعنصر واحد يمكن كتابتها بدائرة واحدة بعنصر واحد <math>(x)</math> {{ملا|1 is frequently used to represent the [[عنصر محايد]] in a non-commutative group}}، العنصر رقم أو بواسطة الرمز <math>\mathbb{id}</math>.<ref>{{استشهاد بهارفارد دون أقواس|Bogart|1990|p=487}}</ref><ref>{{استشهاد بهارفارد دون أقواس|Rotman|2002|p=41}}</ref>

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

<math>[(\,1\,2\,5\,)(\,3\,4\,)]^{-1} = (\,5\,2\,1\,)(\,4\,3\,)</math> .

=== الترميز الدائري التدريجي (Canonical cycle notation) ===
في بعض الكتابات المختصة بالتراكيب فإنه من المهم استخدام ترتيب ثابت لعناصر أي دائرة بالترميز الدائري. فوضح الباحث [[:en:Miklós Bóna|Miklós Bóna]] أنه يوجد نوعين من الترتيب في الترميز الدائري التدريجي وهما:

* بكل دائرة يتم البدء بأكبر عنصر بالمجموعة <math>S</math> بأول دائرة.
* ترتب الدوائر بشكل متزايد بالنسبة لأول عنصر بكل منها.

فعلى سبيل المثال التبديلة بالشكل <math>(3 \,\, 1\,\,2) (5\,\,4) (8) (9\,\,7 \,\,6)</math> هي بالرمز الدائري التدريجي.<ref>{{استشهاد بهارفارد دون أقواس|Bona|2012|loc=p.87}} [Note that the book has a typo/error here, as it gives (45) instead of (54).]</ref> بهذا الترميز لايتم حذف الدوائر ذوات العنصر الواحد. استخدم العالم Sergey Kitaev نفس المفهوم لكن بشكل عكسي حيث يتم ترتيب الدوائر بالبدء بالدائرة ذات العنصر الأصغر وترتيب بقية الدوائر بشكل متناقص حسب العنصر الأول بكل دائرة.<ref name="Kitaev2011">{{استشهاد بكتاب|الأول=Sergey|الأخير=Kitaev|عنوان=Patterns in Permutations and Words|مسار=https://archive.org/details/patternsinpermut0000kita|سنة=2011|ناشر=Springer Science & Business Media|isbn=978-3-642-17333-2|صفحة=[https://archive.org/details/patternsinpermut0000kita/page/119 119]}}</ref>

=== تركيب التباديل ===
توجد طريقتان لكتابة تركيب أي تبديلتين. يستخدم الرمز لتمثيل دالة تطبق من أي عنصر<math>x\in S</math> إلى العنصر <math>\sigma(\pi (x))</math>. فالتبديلة التي بالطرف الأيمن تطبق أولا على العنصر.<ref>{{استشهاد بكتاب|الأخير1=Biggs|الأول1=Norman L.|الأخير2=White|الأول2=A. T.|سنة=1979|ناشر=Cambridge University Press|عنوان=Permutation groups and combinatorial structures|isbn=978-0-521-22287-7}}</ref>
وحيث أن عملية تحصيل الدوال هي [[عملية تجميعية]] فإن عملية تحصيل التباديل هي أيضا تجميعية أي أن: <math>(\sigma \pi ) \tau = \tau (\sigma \pi)</math>. فبالتالي يمكن إيجاد تحصيل أي أكثر من تبديلتين باستخدام خاصية التجميع والاستعانة بالأقواس. من الممكن أيضا كتابة تحصيل التباديل بدون نقطة بينهم أو أي علامة لتوضيح عملية التحصيل.

يفضل بعض الباحثين تطبيق تأثير التبديلة التي بالطرق الأيسر أولا<ref>{{استشهاد بكتاب|الأخير1=Dixon|الأول1=John D.|الأخير2=Mortimer|الأول2=Brian|عنوان=Permutation Groups|isbn=978-0-387-94599-6|ناشر=Springer|سنة=1996|التسجيل=registration|مسار=https://archive.org/details/permutationgroup0000dixo| مسار أرشيف = https://web.archive.org/web/20200102213152/https://archive.org/details/permutationgroup0000dixo | تاريخ أرشيف = 2 يناير 2020 }}</ref><ref>{{استشهاد بكتاب|الأخير1=Cameron|الأول1=Peter J.|سنة=1999|ناشر=Cambridge University Press|عنوان=Permutation groups|مسار=https://archive.org/details/permutationgroup0000came|isbn=978-0-521-65302-2}}</ref><ref>{{استشهاد بدورية محكمة|الأول1=M.|الأخير1=Jerrum|صحيفة=J. Algorithms|المجلد=7|العدد=1|عنوان=A compact representation of permutation groups|صفحات=60–78|سنة=1986|doi=10.1016/0196-6774(86)90038-6}}</ref> ، لكن في هذه الحالة تُكتب عملية التحصيل بشكل أسس فمثلا لتمثيل تأثير <math>\sigma </math> على <math>x</math> يكتب بالشكل <math>x^{\sigma}</math>، والتحصيل بهذه الحالة يكتب بالشكل <math>x^{\sigma \pi} = (x^{\sigma})^{\pi}</math>. لكن هذا التحصيل يعطي نتيجة مختلفة عن التحصيل المعرف سابقا والذي يطبق التبديلة اليمنى أولا.

== تطبيقات ==
{{مفصلة|زمرة متماثلة}}

== انظر أيضا ==
<div style="column-count:4;-moz-column-count:4;-webkit-column-count:4">
* [[نظرية الاحتمال|الاحتمال]]
* [[الطي (رياضيات)|التفاف (رياضيات)]]
* [[تبديل دائري|التبديل الدائري]]
* [[تعمية استبدال]]
* [[تركيبات|التوافقيات]]
* [[توفيق (رياضيات)]]
* [[زمرة تبديلات]]
* [[زمرة متناظرة|زمرة متماثلة]]
* [[قائمة المواضيع المتعلقة بالتباديل|لائحة المواضيع المتعلقة بالتباديل]]
* [[معامل ذات الحدين|معامل ثنائي]]
</div>

== الملاحظات ==
{{ملاحظات}}
== مراجع ==

{{مراجع}}
{{شريط بوابات|رياضيات}}
{{ضبط استنادي}}

[[تصنيف:اختراعات عربية]]
[[تصنيف:تبديلات]]
[[تصنيف:موضوعات حاسمة وذات حدين]]