جایگشت: تعداد چینشهای ممکن n شیء متمایز
قانون اساسی شمارش و معرفی جایگشت
برای درک جایگشت، ابتدا باید با یک اصل ساده به نام «اصل شمارش» یا «اصل ضرب» آشنا شویم. فرض کنید میخواهیم n کار را پشت سر هم انجام دهیم. اگر کار اول m1 حالت، کار دوم m2 حالت و ... داشته باشد، تعداد کل حالتهای انجام این کارها برابر است با حاصلضرب m1 × m2 × ... × mn. این اصل پایه و اساس محاسبه جایگشت است.
جایگشت1 به زبان ساده، به معنی «چیدن» اشیاء در کنار هم با در نظر گرفتن «ترتیب» آنهاست. به عنوان مثال، چیدن سه کتاب متفاوت در یک قفسه، یک جایگشت محسوب میشود. جابهجایی جای دو کتاب، یک جایگشت جدید ایجاد میکند. به همین دلیل است که در جایگشت، بر خلاف ترکیب2، ترتیب قرارگیری عناصر اهمیت دارد.
مثال: مسئله صف فرض کنید 3 نفر به نامهای علی، سارا و رضا میخواهند در یک صف بایستند. چند حالت مختلف برای ایستادن آنها وجود دارد؟ برای جای اول، 3 انتخاب داریم. پس از انتخاب نفر اول، برای جای دوم 2 انتخاب و در نهایت برای جای آخر 1 انتخاب باقی میماند. طبق اصل ضرب، تعداد حالتها برابر است با: $3 \times 2 \times 1 = 6$.
از ضرب متوالی تا نماد فاکتوریل (!n)
در مثال بالا، تعداد حالتها برابر حاصلضرب اعداد 1 تا 3 بود. اگر به جای 3 نفر، n نفر داشته باشیم، تعداد حالتهای چیدن آنها در یک صف (یعنی جایگشت n شیء متمایز) برابر است با حاصلضرب:
این حاصلضرب در ریاضیات با نماد !n نمایش داده میشود و آن را «فاکتوریل n» میخوانیم. به عبارت دقیقتر، تعداد جایگشتهای n شیء متمایز، برابر با !n است.
برای درک بهتر رشد سریع اعداد فاکتوریل، به جدول زیر توجه کنید:
| n (تعداد اشیاء) | محاسبه !n | نتیجه (تعداد جایگشتها) |
|---|---|---|
| 1 | $1$ | 1 |
| 2 | $2 \times 1$ | 2 |
| 3 | $3 \times 2 \times 1$ | 6 |
| 4 | $4 \times 3 \times 2 \times 1$ | 24 |
| 5 | $5 \times 4 \times 3 \times 2 \times 1$ | 120 |
کاربرد روزمره: رمزگشایی از قفلها و برنامهریزی
فرض کنید یک قفل دیجیتال دارید که برای باز شدن نیاز به وارد کردن یک رمز 4 رقمی با ارقام 1، 2، 3 و 4 (بدون تکرار) دارد. چند رمز مختلف میتوان برای این قفل تعریف کرد؟ این یک جایگشت از 4 رقم متمایز است. تعداد حالتها برابر است با:
یعنی 24 رمز احتمالی وجود دارد. مثال دیگر، برنامهریزی برای انجام کارهاست. اگر امروز 6 کار متفاوت برای انجام دادن داشته باشید و بخواهید ترتیب انجام آنها را مشخص کنید، با $6! = 720$ برنامهٔ مختلف روبرو هستید. به همین دلیل است که گاهی تصمیمگیری درباره ترتیب کارها میتواند گیجکننده باشد!
چالشهای مفهومی (پرسش و پاسخ)
پاسخ: چون اشیاء متمایز هستند و نمیتوانیم یک شیء را دوبار استفاده کنیم. برای اولین خانه، n انتخاب داریم. برای دومین خانه، از بین n-1 شیء باقیمانده انتخاب میکنیم و به همین ترتیب. این اصل ضرب، همان !n را نتیجه میدهد. اگر جایگزینی مجاز بود (مثل رمزهایی که ارقام میتوانند تکراری باشند)، آنگاه تعداد حالتها nn میشد.
پاسخ: خیر. گاهی ما فقط میخواهیم r شیء را از بین n شیء انتخاب کرده و آنها را با هم بچینیم. به این حالت «جایگشت r از n» میگویند و با نماد P(n,r) نشان داده میشود. فرمول آن $\frac{n!}{(n-r)!}$ است. مقاله ما روی حالت خاص $r=n$ تمرکز دارد که همان !n میشود.
پاسخ: چون رشد آن نمایی نیست، بلکه «ابرنمایی» (بیشتر از نمایی) است. هر بار که n یک واحد افزایش مییابد، حاصلضرب قبلی در عدد جدید (n) ضرب میشود. مثلاً $10! = 3,628,800$ در حالی که $15!$ حدود 1,300,000,000,000 (یک تریلیون و سیصد میلیارد) است! این رشد سریع نشان میدهد که حتی با تعداد کمی شیء، میتوان تنوع فوقالعاده زیادی در چیدمانها داشت.
پاورقی
- Permutation: به هر نوع چینش خطی از اشیاء که ترتیب آنها اهمیت دارد، جایگشت میگویند. در جایگشت، جابهجایی اشیاء یک حالت جدید ایجاد میکند.
- Combination: به انتخاب تعدادی از اشیاء از یک مجموعه، بدون توجه به ترتیب آنها، ترکیب میگویند. در ترکیب، بر خلاف جایگشت، ترتیب اهمیتی ندارد.
