−فهرست مندرجات
جایگشت‌ها و تبدیل‌های دوری
برخی از جایگشت‌ها، روی عناصری تعریف می‌شود که حالت دوری و دایره‌ای دارند. این صفحه در مورد چنین جایگشت‌هایی است.
جایگشت‌های دوری
فرض کنید n نفر را می‌خواهیم دور یک میز بچینیم. هم‌چنین فرض کنید مهم نیست چه کسی روی کدام صندلی می‌نشیند و درواقع چیزی که مهم است، وضعیت افراد نسبت به یک‌دیگر است. برای مثال جایگشت‌های زیر متفاوت نیستند و آن‌ها را یک‌سان در نظر می‌گیریم:
در تصویر زیر می‌توانید مشاهده کنید برای n=3، تنها ۲ جایگشت دوری و برای n=4، ۶ جایگشت دوری وجود دارد:
فرمول جایگشت‌های دوری
می‌خواهیم تعداد جایگشت‌های دوری n-عنصره را حساب کنیم.
روش اول: نفر اول را در نظر می‌گیریم. فرقی نمی‌کند روی کدام صندلی بنشیند. پس به ۱ حالت روی یکی از صندلی‌ها می‌نشیند. نفر سمت راست نفر گذاشته شده، n−1 حالت دارد. نفر سمت راست این فرد جدید، n−2 حالت دارد و به همین ترتیب تعداد حالات بقیه‌ی صندلی‌ها مشخص می‌شود. پس در کل (n−1)! حالت داریم.
روش دوم: به ازای هر جایگشت خطی از این n عنصر، n حالت برای جایگشت دوری آن‌ها وجود دارد (با چرخاندن میز). برای درک بهتر می‌توانید به شکل ابتدای مطلب (توپ‌های رنگی) مراجعه کنید. پس n!n=(n−1)! حالت داریم.
پس تعداد جایگشت‌های دوری n-عنصره برابر (n−1)! است.
یک مثال
مثال: ۷ پسر و ۴ دختر می‌خواهند دور یک میز بنشینند.
- به چند طریق این کار ممکن است؟
- به چند طریق این کار ممکن است؛ طوری که تمام پسرها کنار هم باشند؟
- به چند طریق این کار ممکن است؛ طوری که هیچ دو دختری کنار هم نباشند؟
پاسخ
- پاسخ برابر تعداد جایگشت‌های دوری ۱۱ نفره و برابر 10! است.
- تمام پسرها با هم را یک شیء و ۴ دختر را ۴ نفر در نظر می‌گیریم. حال این ۵ شیء، به 4! طریق می‌توانند جایگشت دوری پیدا کنند. پسرها نیز در بین خود 7! حالت برای جایگشت گرفتن دارند. توجه کنید پسرها میان خودشان جایگشت دوری ندارند و باید جایگشت خطی آن‌ها محاسبه شود. پس پاسخ برابر 4!7! است.
- ابتدا پسرها را با 6! حالت جایگشت دوری می‌دهیم. حال در هر یک از ۷ فضای ایجاد شده بین پسرها، حداکثر یک دختر می‌تواند قرار بگیرد. ۴ تا از این فضاها را به \binom{7}{4} حالت برای دخترها انتخاب می‌کنیم و دخترها را به 4! حالت در این ۴ جایگاه می‌نشانیم. باز هم توجه کنید این ۴ جایگاه با یک‌دیگر تفاوت دارند و باید جایگشت خطی آن‌ها حساب شود نه جایگشت دوری! پس پاسخ برابر \binom{7}{4}6!4! است.
تبدیل‌های دوری
مانند تبدیل‌های خطی، تبدیل‌های دوری نیز تعریف می‌شود. فرض کنید n نفر داریم. می‌خواهیم r نفر از آن‌ها را انتخاب کنیم و آن‌ها را جایگشت دوری بدهیم. تعداد روش‌های انجام این کار را با Q_r^n یا Q(n, r) نشان می‌دهند. به راحتی به دست می‌آید: Q_r^n=\binom{n}{r}\times (r-1)! = \frac{n!(r-1)!}{r!(n-r)!} = \frac{n!}{r(n-r)!}
سایر مثال‌ها
توجه: ابتدا سعی کنید به اندازه‌ی کافی روی مسئله‌ها فکر کنید، سپس به پاسخ مراجعه کنید.
مثال: n زن و شوهر داریم. به چند طریق می‌توانیم این 2n نفر را، دور یک دایره بنشانیم؛ طوری که هر زن کنار شوهر خود باشد؟
پاسخ
هر زوج را یک شیء در نظر می‌گیریم. این n شیء به (n-1)! می‌توانند جایگشت بگیرند. حال برای هر زوج، ۲ حالت داریم. پس پاسخ برابر 2^n\times (n-1)! است.
مثال: می‌خواهیم با n مهره‌ی متفاوت، یک گردن‌بند بسازیم. به چند طریق این کار ممکن است؟
پاسخ
شاید در ابتدا بگویید پاسخ برابر جایگشت‌های دوری n-عنصره و برابر (n-1)! است؛ اما توجه کنید که با برگرداندن گردن‌بند، به گردن‌بند جدیدی نمی‌رسیم! پس به ازای هر ۲ جایگشت دوری، ۱ گردن‌بند وجود دارد. پس پاسخ برابر \frac{(n-1)!}{2} است.
مثال: یک تاس، یک مکعب است که اعداد 1, 2, 3, 4, 5, 6 روی وجه‌های آن قرار گرفته‌اند؛ طوری که مجموع اعداد دو وجه روبه‌رو برابر ۷ باشد. چند تاس متفاوت داریم؟
پاسخ
این مسئله نیز از این نظر که وجه‌ها متفاوت نیستند و تنها وضعیت اعداد نسبت به یک‌دیگر مهم است، شبیه جایگشت دوری است. عدد ۱ بالاخره باید روی یک وجه قرار بگیرد. به ۱ حالت آن را روی یکی از وجه‌ها می‌نویسیم و تاس را طوری می‌گذاریم که عدد ۱ روی زمین باشد. عدد ۶ باید به ۱ حالت روی وجه بالایی باشد. عدد ۲ باید روی یکی از ۴ وجه باقی‌مانده باشد و تفاوتی نمی‌کند کجا باشد؛ پس به ۱ حالت روی یکی از این ۴ وجه قرار می‌گیرد. وجه روی به روی آن نیز به ۱ حالت باید برابر ۵ باشد. حال برای ۲ وجه باقی‌مانده، ۲ حالت برای قرار گرفتن ۳ و ۴ داریم. پس تعداد تاس‌های متفاوت، تنها ۲ تاست!
مسائل نمونه
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
