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