جایگشت rتایی از n شیء متمایز: اصول، فرمولها و کاربردها
۱. مفهوم پایه: انتخاب همراه با ترتیب
تصور کنید صاحب یک کتابخانه کوچک هستید و میخواهید از میان ۵ کتاب متفاوت، ۳ کتاب را انتخاب کرده و در قفسه بچینید. آیا فقط انتخاب کتابها مهم است یا نحوه چیدن آنها در کنار هم نیز برای شما اهمیت دارد؟ اگر ترتیب چیدن (کتاب اول، دوم و سوم) مهم باشد، با پدیدهای به نام جایگشت rتایی روبرو هستیم. در ریاضیات، به هر چیدمان مرتبی از r عنصر متمایز از یک مجموعه n عنصری، یک جایگشت rتایی از n شیء میگویند1. نکته کلیدی در اینجا واژه "مرتب" است: یعنی {الف، ب، ج} با {ب، الف، ج} متفاوت است.
برای درک بهتر، حالتی سادهتر را در نظر بگیرید: میخواهیم از میان ۴ دانشآموز (علی، سارا، رضا و نگار) یک نفر را به عنوان رئیس و یک نفر دیگر را به عنوان نایبرئیس انتخاب کنیم. انتخاب (علی، سارا) به معنای رئیس علی و نایبرئیس سارا است، در حالی که (سارا، علی) نشاندهنده ریاست سارا و نایبرئیسی علی است. این دو حالت دو جایگشت متفاوت از ۲ نفره از مجموعه ۴ نفره هستند.
۲. فرمول محاسبه جایگشت rتایی
تعداد جایگشتهای rتایی از n شیء متمایز را با نماد P(n, r)، P_{n,r} یا _nP_r نشان میدهند. این مقدار برابر است با حاصلضرب r عدد متوالی نزولی از n شروع میشود. منطق آن ساده است:
- برای انتخاب اولین شیء، n انتخاب داریم.
- برای انتخاب دومین شیء، از میان n-1 شیء باقیمانده انتخاب میکنیم.
- برای سومین شیء، n-2 انتخاب داریم.
- این کار را تا انتخاب rامین شیء ادامه میدهیم که در آن مرحله n - r + 1 انتخاب داریم.
بنابراین فرمول به صورت زیر خواهد بود:
$P(n, r) = \frac{n!}{(n-r)!}$
در اینجا $n!$ (خوانده میشود n فاکتوریل) برابر است با حاصلضرب همه اعداد طبیعی از ۱ تا n. دقت کنید که در اینجا اشیاء متمایز هستند و تکرار مجاز نیست.
۳. مثال عینی: مسابقه دوومیدانی
در یک مسابقه دوومیدانی با ۸ شرکتکننده، به نفرات اول، دوم و سوم به ترتیب مدالهای طلا، نقره و برنز تعلق میگیرد. تعداد حالتهای مختلف توزیع این سه مدال چقدر است؟ در اینجا انتخاب افراد برای مقامهای اول تا سوم مهم است و ترتیب (اینکه چه کسی طلا و چه کسی نقره بگیرد) اهمیت دارد. پس با یک جایگشت ۳تایی از ۸ نفر مواجهیم:
یعنی ۳۳۶ حالت متفاوت برای اهدای مدالها وجود دارد.
۴. مقایسه با ترکیب (ترتیبنادیده)
بزرگترین چالش دانشآموزان، تفاوت بین جایگشت (ترتیب مهم است) و ترکیب (ترتیب مهم نیست) میباشد. جدول زیر این تفاوت را بهصورت شفاف نشان میدهد.
| ویژگی | جایگشت (Permutation) | ترکیب (Combination) |
|---|---|---|
| نقش ترتیب | مهم است. (الف، ب) با (ب، الف) متفاوت است. | مهم نیست. {الف، ب} با {ب، الف} یکی است. |
| فرمول | $P(n,r) = \frac{n!}{(n-r)!}$ | $C(n,r) = \frac{n!}{r!(n-r)!}$ |
| مثال کلیدی | تعیین رتبههای اول تا سوم در یک مسابقه | انتخاب سه نفر برای تشکیل یک کمیته (بدون سمت) |
| مقدار برای n=4, r=2 | $P(4,2)=12$ (جابهجاییها شمرده میشوند) | $C(4,2)=6$ (جابهجاییها یکی هستند) |
۵. کاربرد عملی: رمز عبور و کدگذاری
فرض کنید میخواهید برای گوشی خود یک رمز ۴ رقمی با ارقام ۰ تا ۹ انتخاب کنید، به شرطی که هیچ رقمی تکرار نشود. تعداد رمزهای ممکن چقدر است؟ در اینجا از میان ۱۰ رقم، ۴ رقم را انتخاب کرده و آنها را به ترتیب (به عنوان رقم اول تا چهارم رمز) میچینیم. این یک جایگشت ۴تایی از ۱۰ است:
بنابراین ۵۰۴۰ رمز عبور ۴رقمی بدون تکرار وجود دارد.
۶. چالشهای مفهومی (پرسش و پاسخ)
❓ چرا در فرمول جایگشت، $(n-r)!$ در مخرج میآید؟
پاسخ:$n!$ تمام راههای مرتب کردن n شیء است. از آنجا که ما فقط به چیدمان r شیء اول علاقه داریم و چیدمان n-r شیء باقیمانده برای ما مهم نیست، با تقسیم بر $(n-r)!$ آن حالتهای اضافی را حذف میکنیم. به عبارت دیگر، $P(n,r) = \frac{n!}{(n-r)!}$ معادل $n \times (n-1) \times ... \times (n-r+1)$ است.
❓ تفاوت جایگشت با جایگشت دوری چیست؟
پاسخ: در جایگشت معمولی (خطی) که در این مقاله بررسی شد، چیدمان عناصر در یک خط انجام میشود و شروع و پایان مشخصی دارد. اما در جایگشت دوری (چرخشی) عناصر روی یک دایره قرار میگیرند و چرخشها معادل در نظر گرفته میشوند. برای مثال، چیدن ۳ نفر دور یک میز گرد، جایگشت دوری است و تعداد آن $(n-1)!$ میباشد.
❓ اگر در انتخاب r شیء از n، اشیاء یکسان (غیرمتمایز) باشند، باز هم از جایگشت استفاده میکنیم؟
پاسخ: خیر. فرمول جایگشت ارائهشده صرفاً برای اشیاء متمایز کاربرد دارد. اگر اشیاء یکسان باشند، مسئله به «جایگشت با تکرار» تبدیل میشود و فرمول آن متفاوت است ($\frac{n!}{n_1! \times n_2! \times ...}$). تاکید مقاله ما بر روی اشیاء متمایز است.
پاورقی
1جایگشت (Permutation): به هر ترتیببندی مشخصی از عناصر یک مجموعه گفته میشود. در جایگشت، جابهجایی عناصر، حالتی جدید ایجاد میکند.
2ترکیب (Combination): به انتخاب تعدادی عنصر از یک مجموعه بدون توجه به ترتیب آنها گفته میشود. رابطه آن با جایگشت $C(n,r) = P(n,r) / r!$ است.
3فاکتوریل (Factorial): حاصلضرب تمام اعداد طبیعی مثبت از ۱ تا n که با نماد $n!$ نمایش داده میشود. به عنوان مثال $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$.
