جایگشت با تکرار: جایگشت اشیایی که بعضی از آنها یکسان هستند
۱. مفاهیم پایه: جایگشت، فاکتوریل و اشیای یکسان
در علم آمار و ترکیبیات، جایگشت به چیدمان مرتب تعدادی شیء در یک ردیف گفته میشود. اگر تمام اشیا متمایز باشند، تعداد جایگشتهای $n$ شیء برابر است با $n!$ (فاکتوریل $n$). اما در بسیاری از مسائل واقعی، بعضی از اشیا با یکدیگر یکسان هستند. برای نمونه، اگر بخواهیم حروف کلمه «کتاب» را به ترتیبهای مختلف بنویسیم، حرف «ت» دو بار تکرار شده است. در چنین شرایطی، جایگشتهای متفاوتی که ناشی از جابجایی اشیای یکسان هستند، یک چیدمان محسوب میشوند.
فرض کنید از بین $n$ شیء، $n_1$ شیء از نوع اول، $n_2$ شیء از نوع دوم، ... و $n_k$ شیء از نوع $k$-ام باشند، به طوری که $n_1 + n_2 + ... + n_k = n$. در این حالت، تعداد جایگشتهای متمایز (جایگشت با تکرار) از فرمول زیر به دست میآید:
نکته مهم این فرمول به ما اجازه میدهد بدون این که همه حالتها را یکیک بنویسیم، تعداد چیدمانهای متفاوت را محاسبه کنیم.
۲. مقایسه جایگشت معمولی و جایگشت با تکرار
| ویژگی | جایگشت معمولی (بدون تکرار) | جایگشت با تکرار |
|---|---|---|
| شرط اشیا | همه اشیا متمایز و یکتا | بعضی از اشیا با هم یکسان هستند |
| فرمول | $n!$ | $\frac{n!}{n_1! n_2! ... n_k!}$ |
| مثال عددی | ۳ حرف متمایز A,B,C → $3! = 6$ حالت | حروف A,A,B → $\frac{3!}{2!} = 3$ حالت |
برای درک بهتر این تفاوت، یک مثال عملی را بررسی میکنیم. فرض کنید کیسهای شامل ۳ توپ داریم: دو توپ قرمز (یکسان) و یک توپ آبی. میخواهیم این سه توپ را در یک ردیف کنار هم قرار دهیم. اگر توپهای قرمز را به صورت $q_1$ و $q_2$ نامگذاری کنیم، $3! = 6$ حالت به دست میآید. اما چون $q_1$ و $q_2$ برای ما قابل تشخیص نیستند، حالتهایی که فقط جای دو توپ قرمز عوض شده باشد، تکراری محسوب میشوند. بنابراین تعداد واقعی چیدمانها $\frac{3!}{2!} = \frac{6}{2} = 3$ میشود که همانهای (قرمز, قرمز, آبی)، (قرمز, آبی, قرمز) و (آبی, قرمز, قرمز) هستند.
۳. حل گامبهگام با مثال کلمه «آمار»
یکی از نمونههای کلاسیک برای جایگشت با تکرار، شمارش چیدمانهای مختلف حروف یک کلمه است. کلمه «آمار» را در نظر بگیرید. حروف این کلمه عبارتند از: آ، م، ا، ر. مشاهده میکنید که حرف «الف» با صدای کشیده (آ) یک بار و حرف «الف» معمولی (ا) نیز یک بار آمده است. آیا این دو «الف» یکسان هستند؟ بله، در مسئله جایگشت با تکرار هر دو «الف» یکسان فرض میشوند. بنابراین ما دو حرف یکسان (دو الف) و دو حرف متفاوت (م و ر) داریم. تعداد کل حروف $n = 4$ است. تعداد تکرار برای الف برابر $n_1 = 2$ و برای م و ر هر کدام $1$ است.
طبق فرمول داریم:
بنابراین کلمه «آمار» را میتوان به ۱۲ شکل متفاوت نوشت. برای درک بهتر، چند نمونه از این جایگشتها عبارتند از: آمــار، آرمــا، مــاآر، راآم، مــارآ و ... . توجه کنید که در همه اینها، دو الف تکرار شدهاند و جابهجایی آنها حالت جدیدی ایجاد نمیکند.
۴. کاربرد عملی: چیدمان کارتهای تکراری در بازی
فرض کنید در یک بازی رومیزی، ۵ کارت داریم که روی آنها اعداد ۱، ۱، ۲، ۳، ۳ نوشته شده است (عدد ۱ دو بار و عدد ۳ دو بار و عدد ۲ یک بار تکرار شده است). میخواهیم بدانیم این ۵ کارت را به چند ترتیب مختلف میتوان کنار هم چید.
در اینجا $n = 5$، $n_1 = 2$ (برای عدد ۱)، $n_2 = 1$ (برای عدد ۲)، $n_3 = 2$ (برای عدد ۳). محاسبه به صورت زیر است:
یعنی ۳۰ چیدمان متفاوت وجود دارد. این مثال نشان میدهد که چگونه در مسائل عملی مانند مرتبسازی دادههای تکراری یا تحلیل الگوریتمهای مرتبسازی، از جایگشت با تکرار استفاده میشود.
۵. چالشهای مفهومی (پرسش و پاسخ)
پاسخ: زیرا $n!$ فرض میکند همه اشیا متمایز هستند. وقتی چند شیء یکسان داریم، جایگزینی آنها با یکدیگر چیدمان جدیدی ایجاد نمیکند. برای حذف این جایگشتهای اضافی، باید حاصل را بر فاکتوریل تعداد اشیای تکراری تقسیم کنیم.
پاسخ: فرمول به همان شکل کلی $\frac{n!}{n_1! n_2! ... n_k!}$ باقی میماند. به عنوان مثال برای کلمه «مـــــــــــمکن» که سه «م» تکراری و بقیه حروف یک بار آمدهاند، تعداد جایگشتها برابر $\frac{5!}{3!} = \frac{120}{6}=20$ خواهد بود.
پاسخ: بله. جایگشت (برخلاف ترکیب) به ترتیب چیدمان اهمیت میدهد. تفاوت جایگشت با تکرار با ترکیب با تکرار در همین نکته است. در جایگشت با تکرار، ما به دنبال چیدمان خطی اشیا هستیم، نه انتخاب یک زیرمجموعه بدون توجه به ترتیب.
۶. جمعبندی
پاورقی
2 فاکتوریل (Factorial): حاصلضرب تمام اعداد طبیعی از $1$ تا $n$ که به صورت $n!$ نمایش داده میشود. مثلاً $3! = 1 \times 2 \times 3 = 6$.
3 اشیای یکسان (Identical Objects): اشیایی که از نظر ویژگیهای مورد نظر در مسئله، غیرقابل تشخیص و همارز هستند.
4 ترکیبیات (Combinatorics): شاخهای از ریاضیات که به مطالعه اشیاء گسسته و روشهای شمارش آنها میپردازد.