فهرست مندرجات
جایگشت‌ها و تبدیل‌های دوری
برخی از جایگشت‌ها، روی عناصری تعریف می‌شود که حالت دوری و دایره‌ای دارند. این صفحه در مورد چنین جایگشت‌هایی است.
جایگشت‌های دوری
فرض کنید $n$ نفر را می‌خواهیم دور یک میز بچینیم. هم‌چنین فرض کنید مهم نیست چه کسی روی کدام صندلی می‌نشیند و درواقع چیزی که مهم است، وضعیت افراد نسبت به یک‌دیگر است. برای مثال جایگشت‌های زیر متفاوت نیستند و آن‌ها را یک‌سان در نظر می‌گیریم:
در تصویر زیر می‌توانید مشاهده کنید برای $n=3$، تنها ۲ جایگشت دوری و برای $n=4$، ۶ جایگشت دوری وجود دارد:
فرمول جایگشت‌های دوری
می‌خواهیم تعداد جایگشت‌های دوری $n$-عنصره را حساب کنیم.
روش اول: نفر اول را در نظر می‌گیریم. فرقی نمی‌کند روی کدام صندلی بنشیند. پس به ۱ حالت روی یکی از صندلی‌ها می‌نشیند. نفر سمت راست نفر گذاشته شده، $n-1$ حالت دارد. نفر سمت راست این فرد جدید، $n-2$ حالت دارد و به همین ترتیب تعداد حالات بقیه‌ی صندلی‌ها مشخص می‌شود. پس در کل $(n-1)!$ حالت داریم.
روش دوم: به ازای هر جایگشت خطی از این $n$ عنصر، $n$ حالت برای جایگشت دوری آن‌ها وجود دارد (با چرخاندن میز). برای درک بهتر می‌توانید به شکل ابتدای مطلب (توپ‌های رنگی) مراجعه کنید. پس $\frac{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$ روی وجه‌های آن قرار گرفته‌اند؛ طوری که مجموع اعداد دو وجه روبه‌رو برابر ۷ باشد. چند تاس متفاوت داریم؟
پاسخ
این مسئله نیز از این نظر که وجه‌ها متفاوت نیستند و تنها وضعیت اعداد نسبت به یک‌دیگر مهم است، شبیه جایگشت دوری است. عدد ۱ بالاخره باید روی یک وجه قرار بگیرد. به ۱ حالت آن را روی یکی از وجه‌ها می‌نویسیم و تاس را طوری می‌گذاریم که عدد ۱ روی زمین باشد. عدد ۶ باید به ۱ حالت روی وجه بالایی باشد. عدد ۲ باید روی یکی از ۴ وجه باقی‌مانده باشد و تفاوتی نمی‌کند کجا باشد؛ پس به ۱ حالت روی یکی از این ۴ وجه قرار می‌گیرد. وجه روی به روی آن نیز به ۱ حالت باید برابر ۵ باشد. حال برای ۲ وجه باقی‌مانده، ۲ حالت برای قرار گرفتن ۳ و ۴ داریم. پس تعداد تاس‌های متفاوت، تنها ۲ تاست!
مسائل نمونه
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
