====== جایگشت‌ها و تبدیل‌های دوری ======

برخی از جایگشت‌ها، روی عناصری تعریف می‌شود که حالت دوری و دایره‌ای دارند. این صفحه در مورد چنین جایگشت‌هایی است.

===== جایگشت‌های دوری =====

فرض کنید $n$ نفر را می‌خواهیم دور یک میز بچینیم. هم‌چنین فرض کنید مهم نیست چه کسی روی کدام صندلی می‌نشیند و درواقع چیزی که مهم است، وضعیت افراد نسبت به یک‌دیگر است. برای مثال جایگشت‌های زیر متفاوت نیستند و آن‌ها را یک‌سان در نظر می‌گیریم:
{{ circular-arrangement.png |}}
در تصویر زیر می‌توانید مشاهده کنید برای $n=3$، تنها ۲ جایگشت دوری و برای $n=4$، ۶ جایگشت دوری وجود دارد:
{{ circularpermutations_950.gif |}}

===== فرمول جایگشت‌های دوری =====

می‌خواهیم تعداد جایگشت‌های دوری $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$ روی وجه‌های آن قرار گرفته‌اند؛ طوری که مجموع اعداد دو وجه روبه‌رو برابر ۷ باشد. چند تاس متفاوت داریم؟

<پاسخ>
این مسئله نیز از این نظر که وجه‌ها متفاوت نیستند و تنها وضعیت اعداد نسبت به یک‌دیگر مهم است، شبیه جایگشت دوری است. عدد ۱ بالاخره باید روی یک وجه قرار بگیرد. به ۱ حالت آن را روی یکی از وجه‌ها می‌نویسیم و تاس را طوری می‌گذاریم که عدد ۱ روی زمین باشد. عدد ۶ باید به ۱ حالت روی وجه بالایی باشد. عدد ۲ باید روی یکی از ۴ وجه باقی‌مانده باشد و تفاوتی نمی‌کند کجا باشد؛ پس به ۱ حالت روی یکی از این ۴ وجه قرار می‌گیرد. وجه روی به روی آن نیز به ۱ حالت باید برابر ۵ باشد. حال برای ۲ وجه باقی‌مانده، ۲ حالت برای قرار گرفتن ۳ و ۴ داریم. پس تعداد تاس‌های متفاوت، تنها ۲ تاست!
</پاسخ>
===== مسائل نمونه =====