جایگشت با حروف تکراری؛ چرا تقسیم بر فاکتوریل لازم است؟
جایگشت با حروف تکراری زمانی مطرح می‌شود که چند شیء هم‌نوع یا چند حرف یکسان در آرایش وجود دارد؛ در این حالت شمردن همه اشیا به‌صورت متمایز پاسخ را بزرگ‌تر از مقدار واقعی می‌کند و باید فاکتوریل تعداد کل را بر فاکتوریل تکرار هر نوع تقسیم کرد.
جایگشت با حروف تکراری؛ از کجا شروع کنیم؟
اگر n شیء داشته باشیم و از میان آن‌ها r₁ شیء از نوع اول، r₂ شیء از نوع دوم و مانند آن همسان باشند، تعداد آرایش‌های متمایز برابر n!/(r₁!r₂!...) است. دلیل تقسیم این است که جابه‌جایی اعضای همسان آرایش ظاهری جدیدی ایجاد نمی‌کند. این فرمول فقط برای آرایش همهٔ اشیا به‌کار می‌رود؛ اگر فقط بخشی از حروف انتخاب شود یا جایگاه نخست محدودیت داشته باشد، باید مدل شمارش جداگانه نوشته شود.
روش گام‌به‌گام
- تعداد کل جایگاه‌ها و تعداد اشیای هر نوع را مشخص کنید؛ حروف هم‌شکل را یک گروه تکراری در نظر بگیرید.
- اگر همهٔ اشیا در آرایش استفاده می‌شوند، n! را برای تعداد کل اشیا بنویسید.
- برای هر گروه همسان، فاکتوریل تعداد تکرار آن گروه را در مخرج قرار دهید؛ جابه‌جایی اعضای همان گروه آرایش تازه‌ای نمی‌سازد.
- پیش از ساده‌سازی بررسی کنید که سؤال آرایش خطی می‌خواهد یا چیدمان دایره‌ای؛ فرمول n!/(r₁!r₂!...) برای ردیف خطی است.
- اگر شرطی مثل شروع‌شدن با حرف مشخص وجود دارد، ابتدا جایگاه محدود را تثبیت کنید و سپس تکرارهای باقی‌مانده را با فرمول مناسب بشمارید.
- اگر یک حرف در چند جایگاه خاص قرار می‌گیرد، حالت‌ها را بر اساس جایگاه‌های آن حرف جدا کنید تا یک آرایش چندبار شمرده نشود.
تعداد آرایش‌های متمایز حروف کلمهٔ «لاله» را بیابید. چهار حرف داریم و حرف «ل» دو بار تکرار شده است؛ «ا» و «ه» هرکدام یک‌بارند. بنابراین تعداد آرایش‌ها برابر ۴!/۲! = ۱۲ است. اگر آرایش باید با «ل» شروع شود، یک «ل» در جایگاه اول ثابت می‌ماند و سه حرف باقی‌مانده شامل یک «ل»، یک «ا» و یک «ه» هستند؛ پس تعداد آرایش‌های مجاز ۳! = ۶ می‌شود.
چطور این مبحث را مرور کنیم؟
برای کنترل پاسخ، ابتدا همهٔ حروف را متمایز فرض کنید و تعداد آرایش‌ها را ۴! = ۲۴ به دست آورید. چون دو «ل» همسان‌اند، هر آرایش واقعی دو بار در این شمارش ظاهر شده است: یک‌بار با جابه‌جایی فرضی دو «ل». تقسیم ۲۴ بر ۲ پاسخ ۱۲ را تأیید می‌کند. در حالت شروع با «ل» نیز سه حرف باقی‌مانده متمایزند و ۳! = ۶ با شرط سازگار است.
تقسیم بر فاکتوریل تکرارها را حذف نکنید؛ در غیر این صورت جابه‌جایی حروف یکسان را به‌اشتباه آرایش جدا حساب می‌کنید. خطای دیگر این است که پس از ثابت‌کردن جایگاه اول، هنوز تعداد کل چهار حرف را در صورت فرمول نگه دارید؛ جایگاه تثبیت‌شده دیگر نباید دوباره شمرده شود.
جمع‌بندی
در جایگشت خطیِ اشیای تکراری، ابتدا همهٔ آرایش‌های فرضی را با n! می‌شماریم و سپس اثر جابه‌جایی‌های بی‌تفاوتِ هر گروه همسان را با تقسیم بر فاکتوریل تکرارها حذف می‌کنیم. هر قید جایگاهی باید پیش از اعمال فرمول، تعداد اشیای باقی‌مانده و تکرارهای باقی‌مانده را تغییر دهد.
مطالعه مطلب آموزشی مرتبط ←