جایگشت: هنر چیدمان اشیاء با ترتیب
جایگشت خطی: سادهترین نوع چیدمان
سادهترین نوع جایگشت، چیدن چند شیء متمایز در یک خط راست است. فرض کنید میخواهیم 3 کتاب با عنوانهای متفاوت را در یک قفسه بچینیم. چند حالت مختلف برای چیدن این کتابها وجود دارد؟ برای قفسه اول، 3 انتخاب داریم. پس از قرار دادن یک کتاب، برای قفسه دوم 2 انتخاب باقی میماند و برای آخرین قفسه فقط 1 انتخاب. بنابراین تعداد کل حالتها برابر است با 3 × 2 × 1 = 6. به این حاصلضرب، در ریاضیات ! (فاکتوریل[2]) میگویند و آن را به صورت 3! نمایش میدهند.
برای درک بهتر، به یک مثال عینی توجه کنید: در یک مسابقه دوومیدانی با 8 شرکتکننده، تعداد حالتهای ممکن برای اهدای مدالهای طلا، نقره و برنز (بدون تساوی) برابر است با تعداد جایگشتهای 8 نفر گرفتهشده 3 تایی. این حالت که همه اشیاء را برای چیدمان انتخاب نمیکنیم، با فرمول زیر محاسبه میشود: $P(8,3) = \frac{8!}{(8-3)!} = 8 \times 7 \times 6 = 336$.
جایگشت با تکرار: وقتی اشیاء یکسان هستند
گاهی اوقات، اشیایی که میچینیم همه متمایز نیستند. مثلاً میخواهیم حروف کلمه «بابا» را در کنار هم قرار دهیم. اینجا دو حرف «ب» و دو حرف «الف» داریم. اگر همه حروف را متمایز در نظر بگیریم، تعداد جایگشتها 4! = 24 میشود. اما چون حروف یکسان هستند، بسیاری از این حالتها تکراری و غیرقابل تشخیص هستند. برای محاسبه تعداد حالتهای واقعی، باید جایگشتهای تکراری را حذف کنیم.
در علم آمار، از این فرمول برای محاسبه تعداد حالتهای ممکن در پرتاب چند سکه یا تاس یکسان استفاده میشود. برای مثال، تعداد حالتهای حاصل از پرتاب همزمان 5 سکه، که 2 سکه «شیر» و 3 سکه «خط» بیایند، برابر است با $\frac{5!}{2!3!} = 10$.
کاربرد جایگشت در دنیای واقعی و رمزنگاری
مفاهیم جایگشت تنها محدود به کتابهای ریاضی نیستند. یکی از مهمترین کاربردهای آن در علم رایانه و به خصوص در رمزنگاری[3] است. رمزهای عبوری که ما هر روز از آنها استفاده میکنیم، نمونههایی از جایگشت هستند. فرض کنید یک رمز 4 رقمی با اعداد 0 تا 9 میخواهید بسازید. اگر تکرار مجاز نباشد، تعداد رمزهای ممکن برابر است با $P(10,4) = 10 \times 9 \times 8 \times 7 = 5040$. اما اگر تکرار مجاز باشد (که معمولاً هست)، این تعداد به $10^4 = 10000$ حالت افزایش مییابد که به آن جایگشت با تکرار گفته میشود.
در حوزه برنامهریزی و زمانبندی نیز از جایگشت استفاده میشود. یک فروشنده دورهگرد که باید به 10 شهر سفر کند، برای انتخاب بهترین مسیر، ابتدا باید تمام مسیرهای ممکن را بررسی کند. تعداد این مسیرها برابر 10! = 3,628,800 مسیر است که نشان میدهد چرا یافتن بهترین مسیر برای تعداد شهرهای بالا به کمک رایانه هم کار دشواری است (مسئله فروشنده دورهگرد).
| نوع جایگشت | شرایط | فرمول | مثال عددی |
|---|---|---|---|
| خطی (تمامی اشیاء) | چیدن n شیء متمایز در کنار هم | $n!$ | $5! = 120$ |
| جزئی (خارج از n) | انتخاب و چیدن r شیء از n متمایز | $\frac{n!}{(n-r)!}$ | $P(10,3) = 720$ |
| با تکرار (اشیاء یکسان) | چیدن n شیء با گروههای تکراری | $\frac{n!}{n_1!n_2!...}$ | $\frac{6!}{3!2!1!} = 60$ |
| دایرهای | چیدن اشیاء دور یک دایره | $(n-1)!$ | $(5-1)! = 24$ |
چالشهای مفهومی در جایگشت
پاسخ: در جایگشت، ترتیب قرار گرفتن اشیاء مهم است، اما در ترکیب[4]، ترتیب اهمیتی ندارد و فقط انتخاب اشیاء مطرح است. برای مثال، انتخاب 3 نماینده از بین 10 نفر (ترکیب) با انتخاب 3 نفر برای پستهای مدیر، معاون و منشی (جایگشت) متفاوت است.
پاسخ: این تعریف برای سازگاری فرمولها انجام شده است. اگر بخواهیم $n! = n \times (n-1)!$ برای $n=1$ برقرار باشد، داریم: $1! = 1 \times 0!$. از آنجایی که $1! = 1$، پس $0!$ باید برابر $1$ باشد. همچنین، تنها یک راه برای چیدن صفر شیء وجود دارد: دست خالی!
پاسخ: بله. در چیدمان دایرهای، چرخش کل مجموعه، یک حالت جدید محسوب نمیشود. برای مثال، چیدن 4 نفر دور یک میز گرد، $(4-1)! = 6$ حالت دارد، در حالی که اگر در یک صف بایستند، $4! = 24$ حالت دارد.
پاورقیها
1جایگشت (Permutation): به هر نوع ترتیببندی یا چیدمان مجموعهای از اشیاء گویند که در آن ترتیب قرار گرفتن عناصر اهمیت داشته باشد.
2فاکتوریل (Factorial): حاصلضرب تمام اعداد طبیعی از 1 تا n را فاکتوریل n مینامند و با نماد n! نشان میدهند.
3رمزنگاری (Cryptography): علم و هنر ایجاد ارتباطی امن در حضور اشخاص ثالث و دشمنان که از روشهای ریاضی برای رمز کردن و رمزگشایی اطلاعات استفاده میکند.
4ترکیب (Combination): انتخاب تعدادی شیء از یک مجموعه بزرگتر، بهطوریکه ترتیب انتخاب اهمیتی نداشته باشد.
