جایگشت: هنر شمارش چیدمانهای معنادار
مفهوم جایگشت: چیدمان با ترتیب
فرض کنید سه کتاب متفاوت داریم: ریاضی، فیزیک و شیمی. میخواهیم آنها را در یک قفسه بچینیم. چند حالت مختلف برای این کار وجود دارد؟ اگر کتابها را به ترتیب (ریاضی، فیزیک، شیمی) بچینیم، یک حالت به حساب میآید. اما حالت (فیزیک، ریاضی، شیمی) با حالت قبلی متفاوت است، چون ترتیب کتابها عوض شده است. در علم آمار و احتمال، به هر یک از این چیدمانهای ممکن که در آن ترتیب اشیاء اهمیت دارد، یک جایگشت میگویند.
برای محاسبه تعداد جایگشتهای n شیء متمایز، از رابطه زیر استفاده میکنیم:
معنی: تعداد راههای چیدن n شیء متمایز در کنار هم (با احتساب ترتیب) برابر است با فاکتوریل n.
در مثال کتابها، n=3 است، بنابراین تعداد جایگشتها برابر است با $3! = 3 \times 2 \times 1 = 6$ . این ۶ حالت عبارتند از:
جایگشت جزئی: انتخاب و چیدن
گاهی اوقات با تعدادی شیء متمایز روبرو هستیم، اما فقط میخواهیم تعداد مشخصی از آنها را انتخاب کرده و پشت سر هم بچینیم. برای مثال، از میان 5 دونده، میخواهیم به سه نفر اول (طل، نقره، برنز) مدال بدهیم. تعداد حالتهای تعلق مدالها چند است؟ در اینجا ترتیب اهمیت دارد (نفر اول با نفر دوم فرق میکند) و همه 5 نفر را نمیچینیم، بلکه فقط 3 نفر را انتخاب و مرتب میکنیم. به این حالت، جایگشت جزئی(n, r) میگویند.
معنی: تعداد راههای انتخاب و چیدن r شیء از بین n شیء متمایز (با اهمیت ترتیب).
برای مسابقهدوندگان ما، $P(5, 3) = \frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{120}{2} = 60$ حالت مختلف برای تعلق مدالها وجود دارد.
کاربرد عملی: رمز عبور و مسابقات
مفهوم جایگشت در زندگی روزمره کاربردهای فراوانی دارد. دو مثال زیر درک شما را عمیقتر میکند:
- رمزگذاری: فرض کنید میخواهید یک رمز 4 رقمی با اعداد 1 تا 7 بسازید، به شرطی که هیچ رقمی تکراری نباشد. تعداد رمزهای ممکن برابر است با جایگشت 4 عدد از 7 عدد: $P(7, 4) = 7 \times 6 \times 5 \times 4 = 840$ . این یعنی یک هکر برای حدس زدن رمز باید حداقل 840 حالت را امتحان کند.
- مسابقات ورزشی: در یک مسابقه فوتبال با 8 تیم، تعداد حالتهای مختلف تیمهای اول تا سوم (سکوی قهرمانی) برابر است با $P(8, 3) = 8 \times 7 \times 6 = 336$ . این عدد به ما میگوید که پیشبینی سه تیم اول کار بسیار دشواری است.
| مفهوم | تعریف | فرمول | مثال (انتخاب ۲ کتاب از ۳) |
|---|---|---|---|
| جایگشت | ترتیب مهم است. | $P(3,2)=\frac{3!}{1!}=6$ | (ریاضی، فیزیک) با (فیزیک، ریاضی) متفاوت است. |
| ترکیبمقایسه | ترتیب مهم نیست. | $C(3,2)=\frac{3!}{2!1!}=3$ | مجموعه {ریاضی، فیزیک} با {فیزیک، ریاضی} یکی است. |
جایگشت با اعضای تکراری
گاهی اوقات اشیاء مورد نظر کاملاً متمایز نیستند و بعضی از آنها شبیه هم هستند. مثلاً اگر بخواهیم حروف کلمه «باب» را مرتب کنیم، دو حرف «ب» تکراری داریم. در این حالت، اگر از فرمول ساده جایگشت استفاده کنیم، حالتهای تکراری زیادی محاسبه میکنیم. برای رفع این مشکل از فرمول جایگشت با تکرار استفاده میکنیم.
معنی: تعداد جایگشتهای n شیء که در آنها n_1 شیء از نوع اول، n_2 شیء از نوع دوم و ... وجود دارند.
برای کلمه «باب» (یک «الف» و دو «ب»)، تعداد جایگشتها برابر است با: $\frac{3!}{2!} = \frac{6}{2} = 3$ . این سه حالت عبارتند از: باب، ابد، ببا. (توجه کنید که جابجایی دو «ب» حالت جدیدی ایجاد نمیکند).
چالشهای مفهومی
❓ چرا جایگشت n شیء متمایز برابر n! است؟
برای جایگذاری اولین شیء، n انتخاب داریم. پس از آن، برای دومین شیء (n-1) انتخاب، و به همین ترتیب تا آخرین شیء که تنها یک انتخاب باقی میماند. طبق اصل ضرب، تعداد کل حالات برابر است با $n \times (n-1) \times \dots \times 1 = n!$ .
❓ تفاوت اصلی جایگشت و ترکیب در چیست؟
در جایگشت، ترتیب قرارگیری اشیاء مهم است و دو چیدمان با اشیاء یکسان اما ترتیب متفاوت، دو حالت جداگانه محسوب میشوند. اما در ترکیب، تنها انتخاب اشیاء مهم است و ترتیب آنها در نظر گرفته نمیشود. به عبارت دیگر، جایگشت به «چیدمان» و ترکیب به «انتخاب» توجه دارد.
❓ چه زمانی باید از جایگشت با تکرار استفاده کنیم؟
هرگاه در مجموعه اشیاء مورد نظر، چند شیء کاملاً شبیه به هم (غیرقابل تشخیص) وجود داشته باشند، استفاده از جایگشت ساده، حالتهای تکراری را محاسبه میکند. برای حذف این حالتهای تکراری، باید تعداد جایگشتها را بر فاکتوریل تعداد اشیاء تکراری تقسیم کنیم. این همان جایگشت با تکرار است.
پاورقی
[۱] جایگشت (Permutation): به هر نوع ترتیببندی یا چیدمان مجموعهای از اشیاء متمایز در یک خط (یا دایره) که در آن ترتیب قرار گرفتن عناصر اهمیت دارد، یک جایگشت گفته میشود.
[۲] فاکتوریل (Factorial): حاصلضرب تمام اعداد طبیعی مثبت از ۱ تا n که با نماد $n!$ نمایش داده میشود. برای مثال $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ .
[۳] ترکیب (Combination): انتخابی از اعضای یک مجموعه بدون در نظر گرفتن ترتیب آنها. نماد آن $C(n, r)$ یا $\binom{n}{r}$ است.
