فرمول جایگشت rتایی: نظم در انتخاب
جایگشت چیست؟ چیدمان با اهمیت ترتیب
در زندگی روزمره، بارها با موقعیتهایی مواجه میشویم که ترتیب قرار گرفتن اشیاء یا افراد برایمان اهمیت دارد. برای مثال، چیدن چند کتاب در یک قفسه، تعیین سه نفر اول یک مسابقه، یا حتی رمزگذاری با اعداد و حروف. در تمام این موارد، هر تغییر در ترتیب، یک حالت جدید و منحصربهفرد ایجاد میکند. در علم ریاضیات، به چنین چیدمانی که در آن ترتیب عناصر مهم باشد، جایگشت[1] گفته میشود .
وقتی صحبت از جایگشت rتایی میشود، به این معنی است که از میان n شیء متمایز، میخواهیم تعداد r شیء را انتخاب کنیم و سپس آنها را در کنار هم بچینیم. به عبارت دیگر، دنبال تعداد راههایی هستیم که میتوانیم r عضو را از یک مجموعه nتایی برگزینیم و آنها را به ترتیبهای مختلف مرتب کنیم. این مفهوم با نماد P(n, r) یا Prn نمایش داده میشود .
شهود فرمول: از اصل ضرب تا فاکتوریل
برای درک فرمول جایگشت، بهتر است از یک مثال ساده شروع کنیم. فرض کنید در یک مسابقه، ۸ شرکتکننده داریم و میخواهیم به سه نفر اول (نفرات اول، دوم و سوم) به ترتیب، مدالهای طلا، نقره و برنز بدهیم. به چند طریق میتوانیم این سه مقام را به افراد مختلف اختصاص دهیم؟
برای حل این مسئله از اصل ضرب استفاده میکنیم:
- مدال طلا: از آنجا که هیچ برندهای مشخص نیست، میتوانیم هر یک از ۸ نفر را برای دریافت مدال طلا انتخاب کنیم. بنابراین ۸ حالت داریم.
- مدال نقره: پس از انتخاب نفر اول، ۷ نفر باقی میمانند. برای هر انتخاب قبلی، ۷ حالت جدید برای انتخاب نفر دوم وجود دارد.
- مدال برنز: پس از تعیین دو نفر اول، ۶ نفر باقی میمانند. بنابراین برای هر یک از حالات دو مرحله قبل، ۶ حالت برای انتخاب نفر سوم داریم.
طبق اصل ضرب، تعداد کل حالتها برابر است با حاصلضرب حالات هر مرحله:
$P(8, 3) = 8 \times 7 \times 6 = 336$
همانطور که میبینید، ما سه عامل پشت سر هم از ۸ را در هم ضرب کردیم. اگر بخواهیم این حاصلضرب را بر حسب فاکتوریل بنویسیم، به شکل زیر عمل میکنیم:
$8 \times 7 \times 6 = \frac{8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{5 \times 4 \times 3 \times 2 \times 1} = \frac{8!}{5!}$
عدد ۵ در مخرج کسر از کجا آمد؟ از تفاوت n - r = 8 - 3 = 5. به این ترتیب، فرمول کلی جایگشت rتایی برای n شیء متمایز به دست میآید :
$P(n, r) = \frac{n!}{(n-r)!} \quad , \quad 0 \le r \le n$
حالتهای خاص و جدول مقایسه
فرمول جایگشت برای دو حالت خاص، نتایج جالبی دارد که درک ما را عمیقتر میکند. حالت اول وقتی است که r = n باشد (یعنی بخواهیم همه n شیء را در یک ردیف بچینیم). در این صورت داریم:
$P(n, n) = \frac{n!}{(n-n)!} = \frac{n!}{0!} = n!$
بنابراین، تعداد راههای چیدن n شیء متمایز در کنار هم، n! است. حالت دوم وقتی است که r = 1 باشد. در این حالت، ما فقط میخواهیم یک شیء را از میان n شیء انتخاب کنیم (بدون چیدمان خاصی). طبیعتاً n راه برای این کار وجود دارد:
$P(n, 1) = \frac{n!}{(n-1)!} = \frac{n \times (n-1)!}{(n-1)!} = n$
برای درک بهتر تفاوت جایگشت با مفهوم مشابه آن یعنی ترکیب (که در آن ترتیب مهم نیست)، جدول زیر میتواند مفید باشد.
| مفهوم | اهمیت ترتیب | فرمول | مثال (انتخاب ۳ نفر از ۵ نفر) |
|---|---|---|---|
| جایگشت | مهم | $P(n, r) = n!/(n-r)!$ | انتخاب نفرات اول، دوم و سوم (۵×۴×۳ = ۶۰) |
| ترکیب[2] | بیاهمیت | $C(n, r) = n!/(r!(n-r)!)$ | انتخاب یک تیم سه نفره (بدون اولویت) ((۵×۴×۳)/(۳×۲×۱) = ۱۰) |
کاربرد عملی: از رمز عبور تا چیدمان کتابها
فرمول جایگشت کاربردهای فراوانی در دنیای واقعی دارد. در اینجا دو مثال عینی را بررسی میکنیم:
مثال اول (رمزگذاری): فرض کنید میخواهید برای گوشی خود یک رمز ۴ رقمی انتخاب کنید و علاقه دارید که همه ارقام آن متفاوت باشند. از آنجا که ارقام ۰ تا ۹، ده رقم متمایز هستند (n=10) و ما میخواهیم ۴ رقم را به ترتیب خاصی (که همان رمز ماست) کنار هم قرار دهیم (r=4). تعداد این رمزها برابر است با:
$P(10, 4) = \frac{10!}{(10-4)!} = \frac{10!}{6!} = 10 \times 9 \times 8 \times 7 = 5040$
یعنی بیش از پنج هزار رمز ممکن با این شرط وجود دارد. این یعنی شکستن این رمز به روش امتحان کردن همه حالات، کار زمانبری است.
مثال دوم (چیدمان): یک دانشآموز میخواهد ۳ کتاب ریاضی، فیزیک و شیمی را که متمایز هستند، در قفسه کتاب خود بچیند. تعداد حالتهای چیدن این سه کتاب در کنار هم (r = n = 3) عبارت است از:
$P(3, 3) = 3! = 6$
این شش حالت عبارتند از: (ریاضی، فیزیک، شیمی)، (ریاضی، شیمی، فیزیک)، (فیزیک، ریاضی، شیمی)، (فیزیک، شیمی، ریاضی)، (شیمی، ریاضی، فیزیک) و (شیمی، فیزیک، ریاضی).
چالشهای مفهومی
? این شرط به این دلیل است که ما نمیتوانیم بیش از تعداد اشیاء موجود، چیزی انتخاب کنیم. اگر r > n باشد، یعنی میخواهیم از n شیء، بیش از n شیء را انتخاب کنیم که غیرممکن است. در این حالت، جایگشتی وجود نخواهد داشت یا به عبارتی P(n,r)=0.
? فرمول اصلی P(n,r) برای اشیاء کاملاً متمایز تعریف شده است. اگر در مجموعه خود اشیاء یکسان داشته باشیم (مثل حروف تکراری در یک کلمه)، تعداد جایگشتها کاهش مییابد. در این حالت باید تعداد جایگشتهای با تکرار را محاسبه کنیم. برای مثال، تعداد جایگشتهای حروف کلمه «باب» که دو حرف «ب» یکسان دارد، برابر 3!/2! = 3 است .
? کلید انتخاب بین جایگشت و ترکیب، پرسیدن این سؤال است: «آیا ترتیب در مسئله اهمیت دارد؟» اگر بله، مسئله از نوع جایگشت است (مانند تعیین اعضای هیئت مدیره با سمتهای مشخص). اگر خیر و فقط انتخاب گروه یا زیرمجموعه مطرح است، مسئله از نوع ترکیب خواهد بود (مانند انتخاب یک تیم سه نفره برای انجام یک کار بدون تعیین پست) .
پاورقیها
[1]جایگشت (Permutation): به هر نوع چیدمان یا مرتبسازی خطی از اعضای یک مجموعه که در آن ترتیب قرار گرفتن عناصر اهمیت داشته باشد، جایگشت گفته میشود. در جایگشت، دو آرایش که تنها در ترتیب عناصر با هم تفاوت دارند، متمایز در نظر گرفته میشوند .
[2]ترکیب (Combination): به انتخاب تعدادی از اعضای یک مجموعه بدون توجه به ترتیب آنها گفته میشود. در ترکیب، دو انتخاب که شامل اعضای یکسانی باشند، حتی با ترتیبهای متفاوت، یکسان در نظر گرفته میشوند .
[3]فاکتوریل (Factorial): فاکتوریل یک عدد طبیعی مانند n که با نماد n! نشان داده میشود، حاصلضرب تمام اعداد طبیعی از ۱ تا n است. برای مثال، !۵ = ۵ × ۴ × ۳ × ۲ × ۱ = ۱۲۰. طبق قرارداد، !۰ = ۱ در نظر گرفته میشود.
