جایگشت: هنر چیدمان اشیاء متمایز با ترتیب اهمیت
مفهوم پایه: فاکتوریل و ترتیب
برای درک جایگشت، ابتدا باید با مفهوم فاکتوریلFactorial آشنا شویم. فاکتوریل یک عدد طبیعی مانند n که با نماد n! نمایش داده میشود، حاصلضرب تمام اعداد طبیعی از 1 تا n است. به عبارت دیگر:
به عنوان مثال:
- $1! = 1$
- $3! = 3 \times 2 \times 1 = 6$
- $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$
حال تصور کنید میخواهیم n شیء متمایز (مثلاً n کتاب متفاوت) را در یک قفسه و در کنار هم بچینیم. تعداد حالتهای ممکن برای این چیدمان برابر است با n!. دلیل آن هم ساده است: برای اولین مکان، n انتخاب داریم. بعد از انتخاب کتاب اول، برای مکان دوم n-1 انتخاب، برای مکان سوم n-2 انتخاب و الی آخر. طبق اصل شمارش، تعداد کل حالتها برابر حاصلضرب این اعداد خواهد بود.
جایگشت بدون تکرار: چیدمان همه اشیاء موجود
رایجترین نوع جایگشت، زمانی است که همه اشیاء متمایز بوده و بخواهیم همه آنها را در یک ردیف بچینیم. در این حالت، تعداد جایگشتهای ممکن برابر با n! است. به مثال زیر توجه کنید:
جایگشت r تایی از n شیء متمایز
گاهی اوقات ما همه اشیاء را در نظر نمیگیریم، بلکه میخواهیم از بین n شیء متمایز، تعداد r تایی را انتخاب کرده و آنها را با در نظر گرفتن ترتیب، کنار هم بچینیم ($r \le n$). به این ترتیب، جایگشت r تایی از n شیء میگویند و با نمادهای $P(n, r)$ یا $_nP_r$ نمایش میدهند. فرمول آن به صورت زیر است:
برای درک بهتر، فرض کنید میخواهیم از بین 5 کتاب متفاوت، 2 کتاب را انتخاب کرده و آنها را در یک ردیف بچینیم (ترتیب مهم است). طبق فرمول:
$P(5,2) = \frac{5!}{(5-2)!} = \frac{5!}{3!} = \frac{120}{6} = 20$
یعنی 20 حالت مختلف برای چیدن 2 کتاب از 5 کتاب وجود دارد.
| نوع جایگشت | شرایط | فرمول | مثال |
|---|---|---|---|
| تمام اشیاء | چیدن n شیء متمایز در کنار هم | $n!$ | چیدن 4 کتاب در قفسه: $4! = 24$ |
| جزئی از اشیاء | انتخاب و چیدن r شیء از n شیء متمایز | $P(n, r) = \frac{n!}{(n-r)!}$ | انتخاب و چیدن 2 کتاب از 3 کتاب: $P(3,2)=6$ |
| با تکرار مجاز | هر یک از n شیء میتوانند بیش از یک بار استفاده شوند | $n^r$ | تعداد اعداد 2 رقمی با ارقام {1,2}: $2^2=4$ |
جایگشت با تکرار: وقتی اشیاء یکسان هستند
در برخی مسائل، همه اشیاء متمایز نیستند و تعدادی از آنها یکسان هستند. به عنوان مثال، بخواهیم حروف کلمه «بابا» را کنار هم بچینیم. در اینجا دو حرف «ب» و دو حرف «الف» داریم. تعداد جایگشتهای n شیء که در آنها $n_1$ شیء از نوع اول، $n_2$ شیء از نوع دوم و ... $n_k$ شیء از نوع kام وجود داشته باشد، از فرمول زیر پیروی میکند:
برای کلمه «بابا» (n=4، $n_1=2$ برای حرف «ب»، $n_2=2$ برای حرف «الف»)، تعداد جایگشتها برابر است با:
$\frac{4!}{2! \times 2!} = \frac{24}{2 \times 2} = \frac{24}{4} = 6$
کاربردهای عملی جایگشت در زندگی روزمره
مفهوم جایگشت فقط محدود به کتابهای درسی نیست. در بسیاری از موقعیتهای روزمره با آن سروکار داریم:
- رمزهای عبور: فرض کنید میخواهید یک رمز 4 رقمی با اعداد 0 تا 9 بسازید که تکرار مجاز است. این یک جایگشت با تکرار از 10 شیء در 4 مکان است: $10^4 = 10000$ رمز مختلف.
- چیدن میز غذاخوری: چیدن 6 نفر مهمان دور یک میز گرد (جایگشت دورانی) یا در یک صف (جایگشت خطی).
- برنامهریزی: تعیین تقدم انجام 5 کار مختلف در طول روز ($5! = 120$ برنامه مختلف).
- مسابقات ورزشی: پیشبینی سه تیم اول از بین 10 تیم ($P(10,3) = 720$ حالت مختلف).
چالشهای مفهومی (پرسش و پاسخ)
پاسخ: در جایگشت، ترتیب قرار گرفتن اشیاء اهمیت دارد (مثلاً AB با BA متفاوت است)، در حالی که در ترکیبCombination، ترتیب مهم نیست و AB و BA یک حالت محسوب میشوند. جایگشت برای مسائلی مانند چیدن کتاب در قفسه و ترکیب برای مسائلی مانند انتخاب تیم از بین افراد به کار میرود.
پاسخ: این تعریف برای سازگاری فرمولها انجام شده است. مثلاً در فرمول $P(n, n) = \frac{n!}{(n-n)!} = \frac{n!}{0!}$، میدانیم که $P(n, n) = n!$ است. برای اینکه این دو با هم برابر باشند، باید $0! = 1$ باشد. همچنین از نظر مفهومی، فقط یک راه برای چیدن صفر شیء وجود دارد: «هیچ کاری نکنیم».
پاسخ: بله، در جایگشت بدون تکرار پایه محاسبات بر مبنای فاکتوریل است. اما در جایگشت با تکرار (مثلاً رمزهای عبور) از فرمول $n^r$ استفاده میشود که نتیجه مستقیم اصل ضرب است و نیازی به فاکتوریل ندارد.
پاورقی
- 1جایگشت (Permutation): به هر ترتیب خاصی از چیدن تعدادی شیء متمایز در کنار هم گفته میشود. به عبارت دیگر، جایگشتها حالتهای مختلف چیدمان با در نظر گرفتن توالی هستند.
- 2فاکتوریل (Factorial): حاصلضرب تمام اعداد طبیعی مثبت از 1 تا عدد مورد نظر. فاکتوریل صفر برابر با 1 تعریف میشود.
- 3ترکیب (Combination): انتخاب تعدادی شیء از یک مجموعه بدون در نظر گرفتن ترتیب. برخلاف جایگشت، در ترکیب {a,b} و {b,a} یکسان فرض میشوند.
- 4اصل ضرب (Multiplication Principle): اگر عملی را بتوان به a روش و عمل دیگری را پس از آن به b روش انجام داد، کل روشهای انجام هر دو عمل به ترتیب برابر $a \times b$ است.