ترتیب اهمیت دارد: جایگشت در شمارش
۱. مفهوم «ترتیب» در شمارش
در بسیاری از مسائل شمارش، تنها انتخاب اعضای یک مجموعه کافی نیست، بلکه چیدمان و ترتیب قرار گرفتن آنها نیز نتیجه را تغییر میدهد. به عنوان مثال، اگر بخواهید 3 کتاب متفاوت را در یک قفسه کنار هم قرار دهید، جابهجایی کتابها یک حالت جدید ایجاد میکند. به چنین حالتی که در آن «ترتیب قرار گرفتن عناصر مهم است»، جایگشت1 میگویند.
برای درک بهتر، فرض کنید میخواهید یک رمز دو رقمی با ارقام 1، 2 و 3 بسازید، بدون این که رقم تکراری داشته باشید. حالت 12 با 21 متفاوت است. در اینجا هر بار که ترتیب عوض شود، یک رمز جدید به دست میآید. این تفاوت اساسی بین جایگشت و ترکیب است؛ جایی که در ترکیب، ترتیب تأثیری در نتیجه نهایی ندارد.
۲. تعریف ریاضی و فرمول جایگشت
اگر n شیء متمایز داشته باشیم و بخواهیم r تای آنها را (r \le n) با در نظر گرفتن ترتیب انتخاب کنیم، تعداد حالتها برابر است با:
که در آن n! به معنای فاکتوریل2 است؛ حاصلضرب همه اعداد طبیعی از 1 تا n. حالت خاص جایگشت وقتی است که r = n باشد؛ یعنی همه اشیاء را مرتب میکنیم. در این صورت داریم:
مثال گامبهگام: فرض کنید 4 دانشآموز به نامهای علی، سارا، رضا و مریم میخواهند در یک ردیف 4 صندلی بنشینند. چند حالت ممکن وجود دارد؟
مرحله ۱: صندلی اول را میتوان به 4 روش پر کرد.
مرحله ۲: بعد از نشستن نفر اول، صندلی دوم 3 انتخاب دارد.
مرحله ۳: صندلی سوم 2 انتخاب.
مرحله ۴: صندلی آخر 1 انتخاب.
طبق اصل ضرب3، تعداد کل حالتها برابر $4 \times 3 \times 2 \times 1 = 24$ است که همان $4!$ میباشد.
| ویژگی | جایگشت | ترکیب |
|---|---|---|
| تأثیر ترتیب | مهم | بیاهمیت |
| فرمول اصلی | $P(n,r) = \frac{n!}{(n-r)!}$ | $C(n,r) = \frac{n!}{r!(n-r)!}$ |
| مثال | کد قفل 123 متفاوت از 321 | انتخاب 3 عضو برای یک کمیته |
۳. کاربرد عملی: طراحی رمز و چیدمان روزانه
فرض کنید مدیر یک فروشگاه اینترنتی هستید و میخواهید برای 5 قلم کالای پرفروش، یک بنر تبلیغاتی با 3 جایگاه طراحی کنید. ترتیب قرار گرفتن کالاها در بنر بسیار مهم است زیرا کالای اول بیشتر دیده میشود. تعداد حالتهای ممکن برابر است با:
یعنی 60 طرح متفاوت میتوانید داشته باشید. این مثال نشان میدهد که چگونه در بازاریابی و طراحی رابط کاربری، جایگشت به کمک میآید.
مثال دیگر: در مسابقات امدادی، ترتیب دوندهها تأثیر مستقیم در استراتژی تیم دارد. اگر 4 دونده داشته باشیم و بخواهیم برای 4 مرحله مسابقه، ترتیب آنها را مشخص کنیم، تعداد حالتها برابر $4! = 24$ است.
۴. چالشهای مفهومی
پاسخ: زیرا اصل ضرب را دنبال میکنیم. برای پر کردن جایگاه اول n انتخاب، دوم n-1 انتخاب و ... تا جایگاه rام که n-r+1 انتخاب دارد. حاصلضرب این اعداد همان $\frac{n!}{(n-r)!}$ میشود.
پاسخ: وقتی در مجموعه، بعضی از اشیاء تکراری باشند، از جایگشت با تکرار استفاده میشود. فرمول آن به صورت $\frac{n!}{n_1! \cdot n_2! \cdots n_k!}$ است که در آن n_1, n_2, ..., n_k تعداد تکرار هر عضو است. برای مثال، تعداد حالتهای چیدن حروف کلمه «کتاب» با دو حرف «ت» برابر $\frac{4!}{2!} = 12$ است.
پاسخ: بله، زیرا در جایگشت هر انتخاب از ترکیب، به تعداد جایگشتهای اعضای انتخابشده (یعنی r!) حالت جدید ایجاد میشود. پس همواره $P(n, r) = C(n, r) \times r!$ و از آنجایی که r! \ge 1 است، مقدار جایگشت بزرگتر یا مساوی ترکیب خواهد بود.
۵. جدول خلاصه فرمولهای کلیدی جایگشت
| نوع جایگشت | شرایط | فرمول (MathJax) |
|---|---|---|
| جایگشت معمولی (بدون تکرار) | انتخاب r از n متمایز، بدون تکرار، با ترتیب | $P(n,r)=\frac{n!}{(n-r)!}$ |
| جایگشت همه اعضا | مرتب کردن n شیء متمایز | $P(n,n)=n!$ |
| جایگشت با تکرار | مرتب کردن n شیء با اعضای تکراری | $\frac{n!}{n_1! n_2! ... n_k!}$ |
پاورقی
1جایگشت (Permutation): به هر ترتیب خطی از تعدادی از اعضای یک مجموعه، جایگشت گفته میشود. در جایگشت، تغییر ترتیب اعضا منجر به یک جایگشت جدید میشود.
2فاکتوریل (Factorial): حاصلضرب همه اعداد طبیعی از 1 تا آن عدد. مثلاً $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$. طبق قرارداد، $0! = 1$.
3اصل ضرب (Multiplication Principle): اگر کاری به k مرحله متوالی انجام شود و مرحله اول n_1 راه، مرحله دوم n_2 راه و ... داشته باشد، کل راههای انجام آن کار برابر $n_1 \times n_2 \times ... \times n_k$ است.