Combinations and Permutations
التبديلة: عبارة عن تطبيق[م] function تقابل[م] من مجموعة منتهية \{ x_1 ,x_2 , \ldots ,x_n \} إلى نفسها ويعبر عنها بالشكل
\left( \begin{array}{l} x_1 x_2 \ldots x_n \\ x_3 x_5 \ldots x_2 \\ \end{array} \right)
حيث تحت كل عنصر صورته, أحيانا نسميها تبديلة على المجموعة. بما أن العناصر في الصف العلوي تكتب بطريقة مرتبة فإنه يمكن الاكتفاء بالسطر الثاني (سطر صور العناصر) للتعبير عن التبديلة فنكتب x_3 ,x_5 , \ldots ,x_2 للدلالة على التبديلة السابقة.
في بعض الأحيان لا نهتم بنوع عناصر المجموعة فنعتبرها أعداد من 1 إلى n
{1,2,3,...,n}
وبالتالي التبديلة (2431) مثلا هي تعبير مختصرعن التبديلة
\left( \begin{array}{l} \begin{array}{*{20}c} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{*{20}c} 2 & 4 & 3 & 1 \\ \end{array} \\ \end{array} \right)
التبديلة تطلق أيضا على كل ترتيب في سلسلة لعناصر من مجموعة منتهية. مثلا السلسلة abde عبارة عن تبديلة مكونة من 4 عناصر مأخوذة من المجموعة
{a,b,c,d,e,f,,g,h}
نفس هذه العناصر الأربعة عندما يعاد ترتيبها بشكل آخر فإنها تعطي تبديلة مختلفة. مثلا التبديلة abed تختلف عن الأولى abde لإختلاف ترتيب عناصرهما.
إذا كانت X مجموعة منتهية عدد عناصرها n فإن P(n,r) ترمز لعدد التبديلات الممكنة من هذه المجموعة والتي في كل واحدة r عنصر ويعطى هذا العدد بالقانون
P(n,r) = n(n - 1)(n - 2) \cdots (n - r + 1)
وهو ناتج مباشرة من مبدأ العد. يمكن كتابة هذا القانون بشكل آخر سهل التذكر وهو
P(n,r) = \frac{{n!}}{{\left( {n - r} \right)!}}
للتبديلة رموز أخرى مثل {}^nP_r أو P_r ^n .
مثال: عدد التبديلات التي بكل واحدة 3 عناصر المأخوذة من المجموعة {a,b,c,d} هو
P(4,3) = \frac{{4!}}{{1!}} = \frac{{4 * 3 * 2 * 1}}{1} = 24
كيف نوجد هذه التبديلات بدون أن نقع في التكرار؟
رتب كل العناصر في شكل دائري, ثم نبدأ في إيجاد التبديلات الأساسية إن جاز التعبير وسيتضح الآن ماذا نقصد.
التبديلة الأساسية الأولى: ابدأ من أحد العناصر وليكن a واختر اتجاه معين[م] وليكن الاتجاه الموجب وسجل العنصرين الذين ستقابلهما في هذا الاتجاه الى جانب العنصر a لينتج التبديله abc.التبديلةالتبديلة
التبديلة الأساسية الثانية: نبدا من العنصر الذي بعد a في نفس الاتجاه وهو b وبنفس الطريقة سنحصل على bcd.
التبديلة الأساسية الثالثة: هي cda
التبديلة الأساسية الرابعة: dab
الآن أي تبديلة ثلاثية أخرى ستكون مرتبطة بواحدة من هذه التبديلات الأساسية. بمعنى أن عناصرها ستكون نفس العناصر لإحدى هذه التبديلات الأربع.
كل تبديلة أساسية تعطي 6 تبديلات. إذا لدينا 6×4=24 تبديلة مختلفة.
بهذه الطريقة تستطيع إيجاد التبديلات من مجموعة ما دون الوقوع في الخلط والتكرار, لاحظ التبديلات الأساسية هي بالضبط عدد المجموعات ذات الأربعة عناصر من المجموعة المعطاة. نؤكد مرة أخرى على أن التسمية "تبديلة أساسية" ليست اصطلاح رياضي وإنما موضعي فقط لإيصال الفكرة.
التبديلات الناتجة هي:
abc, acb, bca, bac, cab, cba
bcd, bdc, cbd, cdb, dbc, dcb
cda, cad, acd, adc, dca, dac
dab, dba, abd, adb, bad,bda
ماذا لو طلبنا عدد السلاسل من هذا النوع بدون مراعاة للترتيب؟ في هذه الحالة فإن كل صف هنا سيعطى سلسلة واحدة, وتسمى توفيق كما تعلم, ويكتب التوفيق على شكل مجموعة. إذا لدينا 4 توافيق فقط وهي
{a,b,c}, {b,c,d}, {c,d,a}, {d,a,b}
كل واحدة من هذه المجموعات تسمى توفيقة combination أو توفيقا. وبشكل عام إذا X مجموعة ذات n عنصر فإن أي مجموعة من X ذات r عنصرا نسميها توفيقة أو توفيق رائي, r-combination.
لاحظ المثال السابق فيه 6 توفيقات مأخوذة ثلاثة ثلاثة. كل واحدة تنتج ما عدده 3×2×1 من التباديل وبشكل عام فإذا كان M يمثل عدد التوافيق الرائية فإن كل توفيق به r عنصرا ولذلك سيولد ! r تبديلة مختلفة. إذا
M \times r! = P(n,r)
فإذا رمزنا لعدد التوافيق المأخوذة راءا راء من مجموعة ذات n عنصر بالرمز C(n,r) فإن
C(n,r) = \frac{{P(n,r)}}{{r!}} = \frac{{n!}}{{r!\left( {n - r} \right)!}}
للتوافيق رموز متعددة منها nCr,\;C_n^r و \left( \begin{array}{l} n \\ r \\ \end{array} \right) وهذا الأخير هو ما نستخدمه في كتابة معاملات نظرية[م] ذات الحدين وسنأتي على مناقشتها.
عدد الطرق المختلفة للاختيار عناصر عددها r بدون مراعاة للترتيب يمثل عدد التوافيق أما عدد التباديل فيمثل عدد الطرق لاختيار عناصر مع مراعاة الترتيب.
مثلا: من مجموعة بها 6 موظفين في أحد الأقسام.
بكم طريقة تستطيع اختيار رئيس ونائب له؟
بكم طريقة تستطيع اختيار اثنان منهم لحضور ندوة في هذه الليلية؟
هذا المثال يوضح الفرق, في المطلوب الأول اختيار اثنين لا يكفي بل يجب أن تحدد من منهم الرئيس ومن هو النائب ولذلك للترتيب أهمية وبالتالي عدد الطرق هو P(6,2) = \frac{{6!}}{{\left( 4 \right)!}} = 30 في حين أن اختيار اثنين لحضور الاجتماع لا نهتم فيه بالترتيب ولذلك عدد الطرق هو P(6,2) = \frac{{6!}}{{2!\left( 4 \right)!}} = 15.
قاعدة: وضع r شيئا متطابقا في n موضعا بحيث كل موضع يحتوى على شيء واحد على الأكثر يتم بطرق عددها C(n,r).
مثلا يمكن وضع 6 كرات بيضاء متطابقة في 8 صناديق بحيث لا تزيد عدد الكرات في الصندوق الواحد عن كرة واحدة بطرق عددها C(8,6).
إثبات هذه القاعدة سهل بملاحظة أن توزيع هذه الأشياء على المواضع هو بمثابة اختيار r موضعا من هذه المواضع.
التبديلة: عبارة عن تطبيق[م] function تقابل[م] من مجموعة منتهية \{ x_1 ,x_2 , \ldots ,x_n \} إلى نفسها ويعبر عنها بالشكل
\left( \begin{array}{l} x_1 x_2 \ldots x_n \\ x_3 x_5 \ldots x_2 \\ \end{array} \right)
حيث تحت كل عنصر صورته, أحيانا نسميها تبديلة على المجموعة. بما أن العناصر في الصف العلوي تكتب بطريقة مرتبة فإنه يمكن الاكتفاء بالسطر الثاني (سطر صور العناصر) للتعبير عن التبديلة فنكتب x_3 ,x_5 , \ldots ,x_2 للدلالة على التبديلة السابقة.
في بعض الأحيان لا نهتم بنوع عناصر المجموعة فنعتبرها أعداد من 1 إلى n
{1,2,3,...,n}
وبالتالي التبديلة (2431) مثلا هي تعبير مختصرعن التبديلة
\left( \begin{array}{l} \begin{array}{*{20}c} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{*{20}c} 2 & 4 & 3 & 1 \\ \end{array} \\ \end{array} \right)
التبديلة تطلق أيضا على كل ترتيب في سلسلة لعناصر من مجموعة منتهية. مثلا السلسلة abde عبارة عن تبديلة مكونة من 4 عناصر مأخوذة من المجموعة
{a,b,c,d,e,f,,g,h}
نفس هذه العناصر الأربعة عندما يعاد ترتيبها بشكل آخر فإنها تعطي تبديلة مختلفة. مثلا التبديلة abed تختلف عن الأولى abde لإختلاف ترتيب عناصرهما.
إذا كانت X مجموعة منتهية عدد عناصرها n فإن P(n,r) ترمز لعدد التبديلات الممكنة من هذه المجموعة والتي في كل واحدة r عنصر ويعطى هذا العدد بالقانون
P(n,r) = n(n - 1)(n - 2) \cdots (n - r + 1)
وهو ناتج مباشرة من مبدأ العد. يمكن كتابة هذا القانون بشكل آخر سهل التذكر وهو
P(n,r) = \frac{{n!}}{{\left( {n - r} \right)!}}
للتبديلة رموز أخرى مثل {}^nP_r أو P_r ^n .
مثال: عدد التبديلات التي بكل واحدة 3 عناصر المأخوذة من المجموعة {a,b,c,d} هو
P(4,3) = \frac{{4!}}{{1!}} = \frac{{4 * 3 * 2 * 1}}{1} = 24
كيف نوجد هذه التبديلات بدون أن نقع في التكرار؟
رتب كل العناصر في شكل دائري, ثم نبدأ في إيجاد التبديلات الأساسية إن جاز التعبير وسيتضح الآن ماذا نقصد.
التبديلة الأساسية الأولى: ابدأ من أحد العناصر وليكن a واختر اتجاه معين[م] وليكن الاتجاه الموجب وسجل العنصرين الذين ستقابلهما في هذا الاتجاه الى جانب العنصر a لينتج التبديله abc.التبديلةالتبديلة
التبديلة الأساسية الثانية: نبدا من العنصر الذي بعد a في نفس الاتجاه وهو b وبنفس الطريقة سنحصل على bcd.
التبديلة الأساسية الثالثة: هي cda
التبديلة الأساسية الرابعة: dab
الآن أي تبديلة ثلاثية أخرى ستكون مرتبطة بواحدة من هذه التبديلات الأساسية. بمعنى أن عناصرها ستكون نفس العناصر لإحدى هذه التبديلات الأربع.
كل تبديلة أساسية تعطي 6 تبديلات. إذا لدينا 6×4=24 تبديلة مختلفة.
بهذه الطريقة تستطيع إيجاد التبديلات من مجموعة ما دون الوقوع في الخلط والتكرار, لاحظ التبديلات الأساسية هي بالضبط عدد المجموعات ذات الأربعة عناصر من المجموعة المعطاة. نؤكد مرة أخرى على أن التسمية "تبديلة أساسية" ليست اصطلاح رياضي وإنما موضعي فقط لإيصال الفكرة.
التبديلات الناتجة هي:
abc, acb, bca, bac, cab, cba
bcd, bdc, cbd, cdb, dbc, dcb
cda, cad, acd, adc, dca, dac
dab, dba, abd, adb, bad,bda
ماذا لو طلبنا عدد السلاسل من هذا النوع بدون مراعاة للترتيب؟ في هذه الحالة فإن كل صف هنا سيعطى سلسلة واحدة, وتسمى توفيق كما تعلم, ويكتب التوفيق على شكل مجموعة. إذا لدينا 4 توافيق فقط وهي
{a,b,c}, {b,c,d}, {c,d,a}, {d,a,b}
كل واحدة من هذه المجموعات تسمى توفيقة combination أو توفيقا. وبشكل عام إذا X مجموعة ذات n عنصر فإن أي مجموعة من X ذات r عنصرا نسميها توفيقة أو توفيق رائي, r-combination.
لاحظ المثال السابق فيه 6 توفيقات مأخوذة ثلاثة ثلاثة. كل واحدة تنتج ما عدده 3×2×1 من التباديل وبشكل عام فإذا كان M يمثل عدد التوافيق الرائية فإن كل توفيق به r عنصرا ولذلك سيولد ! r تبديلة مختلفة. إذا
M \times r! = P(n,r)
فإذا رمزنا لعدد التوافيق المأخوذة راءا راء من مجموعة ذات n عنصر بالرمز C(n,r) فإن
C(n,r) = \frac{{P(n,r)}}{{r!}} = \frac{{n!}}{{r!\left( {n - r} \right)!}}
للتوافيق رموز متعددة منها nCr,\;C_n^r و \left( \begin{array}{l} n \\ r \\ \end{array} \right) وهذا الأخير هو ما نستخدمه في كتابة معاملات نظرية[م] ذات الحدين وسنأتي على مناقشتها.
عدد الطرق المختلفة للاختيار عناصر عددها r بدون مراعاة للترتيب يمثل عدد التوافيق أما عدد التباديل فيمثل عدد الطرق لاختيار عناصر مع مراعاة الترتيب.
مثلا: من مجموعة بها 6 موظفين في أحد الأقسام.
بكم طريقة تستطيع اختيار رئيس ونائب له؟
بكم طريقة تستطيع اختيار اثنان منهم لحضور ندوة في هذه الليلية؟
هذا المثال يوضح الفرق, في المطلوب الأول اختيار اثنين لا يكفي بل يجب أن تحدد من منهم الرئيس ومن هو النائب ولذلك للترتيب أهمية وبالتالي عدد الطرق هو P(6,2) = \frac{{6!}}{{\left( 4 \right)!}} = 30 في حين أن اختيار اثنين لحضور الاجتماع لا نهتم فيه بالترتيب ولذلك عدد الطرق هو P(6,2) = \frac{{6!}}{{2!\left( 4 \right)!}} = 15.
قاعدة: وضع r شيئا متطابقا في n موضعا بحيث كل موضع يحتوى على شيء واحد على الأكثر يتم بطرق عددها C(n,r).
مثلا يمكن وضع 6 كرات بيضاء متطابقة في 8 صناديق بحيث لا تزيد عدد الكرات في الصندوق الواحد عن كرة واحدة بطرق عددها C(8,6).
إثبات هذه القاعدة سهل بملاحظة أن توزيع هذه الأشياء على المواضع هو بمثابة اختيار r موضعا من هذه المواضع.
