تم النشر اليوم 2024/05/16 | تبديل (رياضيات)

التاريخ

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

الملاحظات

^ 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. ^ Due to the likely possibility of confusion, cycle notation is not used in conjunction with one-line notation (sequences) for permutations. ^ 1 is frequently used to represent the عنصر محايد in a non-commutative group

تطبيقات

المقالة الرئيسة: زمرة متماثلة

خصائص

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

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

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

يوجد عدة طرق لكتابة التبديله. وأكثرها إستخداما هو الترميز الدائري والذي يستخدم بكثرة بين الرياضيين لوضوح صياغة التبديلة فيه. الترميز باستخدام صفين
يستخدم رمزكوشي صفين بحيث يتم وضع عناصر المجموعة بالصف الأول بينما صور كل من هذه العناصر توضح مباشرة اسفله بالصف السفلي. فمثلا، التبديلة للمجموعة S
=
{
1
,
2
,
3
,
4
,
5
}
{displaystyle S={1,2,3,4,5}} يمكن كتابتها كما يلي: σ
=
( 1
2
3
4
5
2
5
4
3
1 )
;
{displaystyle sigma ={begin{pmatrix}1&2&3&4&5\2&5&4&3&1end{pmatrix}};} وهذا يعني أن σ تحقق ما يلي: σ(1)=2 و σ(2)=5 و σ(3)=4 و σ(4)=3 و σ(5)=1. تظهر عناصر المجموعة S
{displaystyle S} بأي ترتيب في الصف الأول. فبالتالي يمكن كتابة هذه التبديلة بطريقة أخرى كالتالي S
=
( 3
2
5
1
4
4
5
1
2
3 )
{displaystyle S={begin{pmatrix}3&2&5&1&4\4&5&1&2&3end{pmatrix}}} . الترميز باستخدام صف واحد
في حالة وجود ترتيب طبيعي لعناصر المجموعة S
{displaystyle S} [أ]ولتكن
x 1
, x 2
,
…
, x n
{displaystyle x_{1},x_{2},ldots ,x_{n}} فإنه يمكن وضعها بالصف الأول من الترميز بصفين بشكل عام كالتالي: σ
=
(
x 1 x 2 x 3
… x n
σ
( x 1
)
σ
( x 2
)
σ
( x 3
)
…
σ
( x n
) )
{displaystyle 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}}} . وبما أن عناصر المجموعة S
{displaystyle S} تتخذ ترتيبا طبيعيا فإنه من الممكن حذف الصف الأول واستخدام التبديلة بترميز صف واحد كما يلي (
σ
( x 1
)
σ
( x 2
)
σ
( x 3
)
…
σ
( x n
)
)
{displaystyle (sigma (x_{1}),,sigma (x_{2}),,sigma (x_{3}),,ldots sigma (x_{n}))} كما في ترتيب عناصر المجموعة S
{displaystyle S} . يجب التفريق هنا بين الترميز بصف والترميز الدائري الذي سيوضح بالأسفل. فمن الشائع بالدراسات الرياضية حذف الأقواس بترميز بصف واحد بينما تستخدم الأقواس في الترميز الدائري. يسمى أيضا الترميز بصف واحد بممثل الكلمة (word) في أي تبديلة. ففي المثال السابق يمكن كتابة التبديلة بالشكل 2
5
4
3
1
{displaystyle 2,,5,,4,,3,,1} حيث أن 1
2
3
4
5
{displaystyle 1,,2,,3,,4,,5} تشكل ترتيب طبيعي للصف الأول. يستخدم هذا الرمز بالتراكيب وعلوم الحاسب خصوصا بالتطبيقات التي بها عناصر S
{displaystyle S} أو التبديلات كبيرة أو صغيرة نوعا ما. الترميز الدائري
يمكن وصف الترميز الدائري بالتأثير المكرر للتبديلة على عناصر المجموعة. فهي تبين التبديلة كحاصل ضرب دوائر. وحيث أن هذه الدوائر منفصلة فإنها توصف بـ “decomposition into disjoint cycles”.[ب] لكتابة التبديلة σ
sigma بالترميز الدائري فإننا نتبع الخطوات التالية: نبدأ بكتابة قوس مفتوح ونختار أي عنصر x
x من المجموعة S
{displaystyle S} ونكتبه كأول عنصر: (
x
{displaystyle (x}
بعد ذلك نتابع التأثير المتتابع للتبديلة عالعنصر السابق ونكتبه كما يلي: (
x σ
(
x
) σ
(
σ
(
x
)
)
…
{displaystyle (xquad sigma (x)quad sigma (sigma (x))ldots }
نكرر هذه الخطوات حتى الوصول لنفس العنصر الذي بدأنا به x
x بالتالي نغلق الأقواس بدون تكرار كتابة x
x : (
x σ
(
x
) σ
(
σ
(
x
)
)
…
)
{displaystyle {displaystyle (xquad sigma (x)quad sigma (sigma (x))ldots })}
لنواصل الآن باختيار عنصر آخر y
∈
S
{displaystyle yin S} لم يسبق كتابته بالدائرة الأولى ونكرر نفس الخطوات هنا مع هذا العنصر: (
x σ
(
x
) σ
(
σ
(
x
)
)
…
)
(
y
…
{displaystyle (xquad sigma (x)quad sigma (sigma (x))ldots )(yldots }
نكرر هذه الخطوات حتى يتم كتابة جميع عناصر S
{displaystyle S} بالدوائر.
حيث أن كل دائرة جديدة تبدأ باختيار عنصر عشوائي من S
{displaystyle S} فإنه يوجد طرق مختلفة لكتابة تبديلة ما بالترميز الدائري، ففي نفس المثال المذكور سابقا يمكن كتابة التبديلة كالتالي: ( 1
2
3
4
5
2
5
4
3
1 )
=
( 1
2
5 )
( 3
4 )
=
( 3
4 )
( 1
2
5 )
=
( 3
4 )
( 5
1
2 )
.
{displaystyle {begin{pmatrix}1&2&3&4&5\2&5&4&3&1end{pmatrix}}={begin{pmatrix}1&2&5end{pmatrix}}{begin{pmatrix}3&4end{pmatrix}}={begin{pmatrix}3&4end{pmatrix}}{begin{pmatrix}1&2&5end{pmatrix}}={begin{pmatrix}3&4end{pmatrix}}{begin{pmatrix}5&1&2end{pmatrix}}.}
نلاحظ أيضا انه يتم حذف الدائرة التي بها عنصر واحد والتي يكون واضحا دون الحاجة لكتابته، فأي عنصر x
x لايظهر بأي دائرة بالترميز الدائري فهذا يعني أن σ
(
x
)
=
x
{displaystyle sigma (x)=x} . في تبديلة الوحدة والتي تتكون من دوائر بعنصر واحد يمكن كتابتها بدائرة واحدة بعنصر واحد (
x
)
{displaystyle (x)} [ج]، العنصر رقم أو بواسطة الرمز
i
d {displaystyle mathbb {id} } . من ضمن مميزات استخدام الترميز الدائري فإنه يسهل كتابة معكوس أي تبديلة بشكل أسهل بواسطة عكس ترتيب عناصر التبديلة بكل دوائره. فعلى سبيل المثال: [
( 1 2 5 )
( 3 4 ) ] −
1
=
( 5 2 1 )
( 4 3 )
{displaystyle [(,1,2,5,)(,3,4,)]^{-1}=(,5,2,1,)(,4,3,)} . الترميز الدائري التدريجي (Canonical cycle notation)
في بعض الكتابات المختصة بالتراكيب فإنه من المهم استخدام ترتيب ثابت لعناصر أي دائرة بالترميز الدائري. فوضح الباحث Miklós Bóna أنه يوجد نوعين من الترتيب في الترميز الدائري التدريجي وهما: بكل دائرة يتم البدء بأكبر عنصر بالمجموعة S
{displaystyle S} بأول دائرة.
ترتب الدوائر بشكل متزايد بالنسبة لأول عنصر بكل منها.
فعلى سبيل المثال التبديلة بالشكل (
3
1
2
)
(
5
4
)
(
8
)
(
9
7
6
)
{displaystyle (3,,1,,2)(5,,4)(8)(9,,7,,6)} هي بالرمز الدائري التدريجي. بهذا الترميز لايتم حذف الدوائر ذوات العنصر الواحد. استخدم العالم Sergey Kitaev نفس المفهوم لكن بشكل عكسي حيث يتم ترتيب الدوائر بالبدء بالدائرة ذات العنصر الأصغر وترتيب بقية الدوائر بشكل متناقص حسب العنصر الأول بكل دائرة. تركيب التبديلات
توجد طريقتان لكتابة تركيب أي تبديلتين. يستخدم الرمز لتمثيل دالة تطبق من أي عنصر x
∈
S
{displaystyle xin S} إلى العنصر σ
(
π
(
x
)
)
{displaystyle sigma (pi (x))} . فالتبديلة التي بالطرف الأيمن تطبق أولا على العنصر.
وحيث أن عملية تحصيل الدوال هي عملية تجميعية فإن عملية تحصيل التبديلات هي أيضا تجميعية أي أن: (
σ
π
)
τ
=
τ
(
σ
π
)
{displaystyle (sigma pi )tau =tau (sigma pi )} . فبالتالي يمكن إيجاد تحصيل أي أكثر من تبديلتين باستخدام خاصية التجميع والاستعانة بالأقواس. من الممكن أيضا كتابة تحصيل التبديلات بدون نقطة بينهم أو أي علامة لتوضيح عملية التحصيل. يفضل بعض الباحثين تطبيق تأثير التبديلة التي بالطرق الأيسر أولا ، لكن في هذه الحالة تُكتب عملية التحصيل بشكل أسس فمثلا لتمثيل تأثير σ
{displaystyle sigma } على x
x يكتب بالشكل
x σ
{displaystyle x^{sigma }} ، والتحصيل بهذه الحالة يكتب بالشكل
x σ
π
=
( x σ ) π
{displaystyle x^{sigma pi }=(x^{sigma })^{pi }} . لكن هذا التحصيل يعطي نتيجة مختلفة عن التحصيل المعرف سابقا والذي يطبق التبديلة اليمنى أولا.

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

تعريف

في مناهج الرياضيات، تُستخدم الحروف اليونانية الصغيرة رموزا للتبديلات. وأكثر هذه الرموز استخداما هي الحروف α
alpha و β
{displaystyle beta } و σ
sigma و τ
{displaystyle tau } و π
{displaystyle pi } . يمكن تعريف التبديلات تقابلاتٍ من مجموعة S
{displaystyle S} نحو نفسها. كل التبديلات على مجموعة بها n
n من العناصر تمثل زمرة متماثلة ويرمز لها بالرمز
S n
{displaystyle S_{n}} ، حيث أن عملية الزمرة هنا هي عملية تركيب الدوال. فبالتالي لأي تبديلين π
{displaystyle pi } و σ
sigma من الزمرة
S n
{displaystyle S_{n}} فإن خواص الزمرة الأربع متحققة وهي كما يلي: الانغلاق: فإذا كان π
{displaystyle pi } و σ
sigma عناصر في
S n
{displaystyle S_{n}} فإن π
σ
{displaystyle pi sigma } أيضا ينتمي لـ
S n
{displaystyle S_{n}} .
التجميع: لأي ثلاث تبديلات π ,
σ ,
τ
∈ S n
{displaystyle pi ,,sigma ,,tau in S_{n}} فإن (
π
σ
)
τ
=
π
(
σ
τ
)
{displaystyle (pi sigma )tau =pi (sigma tau )} .
عنصر محايد: يوجد تبديلة وحدة يرمز لها بالرمز
i
d {displaystyle mathbb {id} } والمعرفة كما يلي
i
d (
x
)
=
x
{displaystyle mathbb {id} (x)=x} لكل x
∈
S
{displaystyle xin S} . بالتالي لأي σ
∈ S n
{displaystyle sigma in S_{n}} فإن
i
d
σ
=
σ
i
d =
σ
{displaystyle mathbb {id} ,sigma =sigma ,mathbb {id} =sigma } .
المعكوس: لكل تبديلة π
∈ S n
{displaystyle pi in S_{n}} يوجد
π −
1
∈ S n
{displaystyle pi ^{-1}in S_{n}} والتي تحقق π π −
1
= π −
1
π
= i
d {displaystyle pi pi ^{-1}=pi ^{-1}pi =mathbb {id} } .
بشكل عام فإن تحصيل أي تبديلتين π
,
σ
∈ S n
{displaystyle pi ,sigma in S_{n}} هي عملية ليست دائما إبدالية، أي أن π
σ
≠
σ
π
{displaystyle pi sigma neq sigma pi } .
مثال
يراد سحب كرتين على التوالي من صندوق أسود يحوي أربع كرات ملونة سوداء وزرقاء وحمراء وصفراء. المطلوب حساب عدد الاحتمالات الممكنة لنتيجة السحب. كون السحب يتم على التتالي فان هناك أهمية للترتيب لأنه إذا كانت الكرة الأولى على سبيل المثال سوداء والثانية حمراء هذه النتيجة تختلف عن الحالة التي يكون فيها الكرة الأولى حمراء والثانية سوداء.
بتطبيق القانون نحصل على عدد الاحتمالات الممكنة
ت (2,4)=4!(4-2)!=4×3×2×1 /2×1 = 12 احتمال ممكن
و هي بالتفصيل كالتالي: (سوداء، حمراء) (حمراء، سوداء) (زرقاء، سوداء) (صفراء، سوداء) (سوداء، زرقاء) (حمراء، زرقاء) (زرقاء، حمراء) (صفراء، حمراء) (سوداء، صفراء) (حمراء، صفراء) (زرقاء، صفراء) (صفراء، زرقاء).

شرح مبسط

تعديل – تعديل مصدري – تعديل ويكي بيانات