====== جایگشت‌های خطی ======

هر جا سخن از ترتیب چند شیء در کنار هم سخن گفته می‌شود، می‌توان از **جایگشت** نام برد. این شیء‌ها می‌توانند در یک ردیف، دور یک دایره یا ... باشند. به هر روش قرار گرفتن چند شیء در یک ردیف، یک **جایگشت خطی** گفته می‌شود. برای مثال، هرگاه چند نفر در یک صف نانوایی ایستاده‌اند، یک جایگشت خطی تشکیل داده‌اند.

===== تعداد جایگشت‌های خطی $n$ شیء متمایز =====

می‌خواهیم تعداد جایگشت‌های خطی $n$ شیء متمایز را بیابیم. در واقع می‌خواهیم تعداد روش‌های قرار گرفتن $n$ نفر در یک صف را حساب کنیم.

نفر اول صف، $n$ حالت دارد. پس از آن نفر دوم صف، $n-1$ حالت دارد (از $n-1$ نفر باقی‌مانده، باید یک نفر انتخاب شود). پس از آن نفر سوم صف، $n-2$ حالت دارد (از $n-2$ نفر باقی‌مانده، باید یک نفر انتخاب شود). اگر به همین ترتیب ادامه دهیم، نفر آخر صف، یک حالت دارد. پس طبق [[اصل_ضرب|اصل ضرب]]، پاسخ مسئله برابر $n\times{}(n-1)\times{}(n-2)\times...\times1=n!$ است.

بنابراین تعداد جایگشت‌های خطی $n$ شیء متمایز، برابر $n!$ است.

===== یک مثال =====

**مثال**:
با حروف کلمه‌ی pencil،
  - چند جایگشت وجود دارد؟
  - چند جایگشت وجود دارد که با حرف n شروع شود؟
  - چند جایگشت وجود دارد که با حرف صدادار شروع شود؟
  - چند جایگشت وجود دارد که در آن، عبارت pen دیده شود؟

<پاسخ>
پاسخ قسمت اول، تعداد جایگشت‌های ۶ عنصره است و برابر $6!$ است.

در قسمت دوم، حرف اول باید n باشد و برای تعیین بقیه‌ی حرف‌ها، باید تعداد جایگشت‌های ۵ عنصره را محاسبه کنیم که برابر $5!$ است.

در قسمت سوم، حرف اول ۲ حالت دارد (e یا i باید باشد). برای بقیه‌ی حرف‌ها، باید تعداد جایگشت‌های ۵ عنصره را محاسبه کنیم که برابر $5!$ است.

در قسمت چهارم، کمی باید دیدمان را عوض کنیم. ما در واقع ۴ شیء داریم. هر یک از حروف c, i, l یک شیء هستند و عبارت pen به تنهایی یک شیء است. پس در کل باید تعداد جایگشت‌های ۴ عنصره را محاسبه کنید که برابر $4!$ است.
</پاسخ>

===== سایر مثال‌ها =====

توجه: سعی کنید ابتدا خودتان روی مسائل به قدر کافی فکر کنید و سپس به پاسخ مراجعه کنید. 

**مثال**:
به چند روش می‌توان ۴ دختر و ۵ پسر را در یک ردیف قرار دارد؛ طوری که
  - شرط خاصی نداشته باشیم؟
  - در مکان اول یک پسر باشد؟
  - ۴ دختر، کنار هم باشند؟
  - هیچ ۲ پسری کنار هم نباشند؟
  - تمام پسرها کنار هم و تمام دخترها کنار هم باشند؟

<پاسخ>
در قسمت اول، ۹ شیء داریم که باید در یک ردیف قرار بگیرند. پس پاسخ $9!$ است.

در قسمت دوم، پسری که باید در مکان اول قرار گیرد، به ۵ حالت مشخص می‌شود. بقیه ۸ شیء هستند که باید در یک ردیف قرار گیرند. پس طبق [[اصل_ضرب|اصل ضرب]]، پاسخ برابر $5\times8!$ است.

در قسمت سوم، ابتدا تمام دخترها با هم را یک شیء در نظر می‌گیریم. به این ترتیب، ۶ شیء (۵ پسر هر کدام یک شیء و دخترها با هم یک شیء) داریم. تعداد روش‌های قرار گرفتن این شیء‌ها کنار هم، $6!$ است. آیا پاسخ تمام شده است؟ خیر. دخترها نیز میان خود ترتیب دارند. دخترها در میان خودشان به $4!$ حالت می‌توانند ترتیب بگیرند. پس طبق [[اصل_ضرب|اصل ضرب]] پاسخ برابر $6! \times 4!$ است.

در قسمت چهارم به وضوح افراد باید یک در میان پسر و دختر باشند. پس جایگشت ما به صورت پسر، دختر، پسر، دختر، پسر، دختر، پسر، دختر، پسر خواهد بود. حال که جای دخترها و پسرها مشخص شده است، پسرها در جاهای‌شان به $5!$ حالت و دخترها در جاهای‌شان به $4!$ حالت می‌توانند ترتیب بگیرند. پس پاسخ، برابر $4! \times 5!$ است.

در قسمت آخر، ابتدا پسرها را با هم یک شیء و دخترها را با هم یک شیء در نظر می‌گیریم. این ۲ شء، به $2!$ حالت می‌توانند کنار هم قرار بگیرند. حال پسرها در میان خودشان به $5!$ حالت و دخترها در میان خودشان به $4!$ حالت می‌توانند ترتیب بگیرند. پس پاسخ، برابر $2! \times 5! \times 4!$ است.
</پاسخ>

**مثال**:
به چند روش می‌توان اعداد $1, 2, ..., 2n$ را جایگشت داد؛ طوری که اعداد زوج در مکان‌های زوج و اعداد فرد در مکان‌های فرد ظاهر شوند؟

<پاسخ>
جای‌گاه اعداد زوج در مکان‌های زوج است. پس تعداد روش‌های جایگشت دادن آن‌ها، $n!$ است. به همین ترتیب برای اعداد فرد نیز، $n!$ حالت داریم. پس در کل $n!\times{}n!=(n!)^2$ حالت داریم.
</پاسخ>

**مثال**:
$2n$
نفر در یک گروه داریم. به چند طریق می‌توان این افراد را به $n$ گروه دو نفره تقسیم کرد؟

<پاسخ>
ما این مسئله را در [[اصل_ضرب|اصل ضرب]] دیده بودیم. می‌خواهیم روشی دیگر ارائه کنیم.

ابتدا $2n$ نفر را به $(2n)!$ حالت جایگشت می‌دهیم. سپس نفر اول و دوم ردیف را در گروه اول، نفر سوم و چهارم ردیف را در گروه دوم و ... می‌گذاریم. آیا پاسخ تمام شده است؟ خیر.

توجه کنید در هر تیم، ۲ نفر با یک‌دیگر تفاوتی ندارند؛ در حالی که ما به آن‌ها ترتیب داده‌ایم. پس به ازای هر حالت مسئله، ما $2^n$ حالت را شمرده‌ایم (در هر یک از $n$ تیم، به ۲ نفر جایگشت داده‌ایم). پس باید $(2n)!$ را بر $2^n$ تقسیم کنیم. آیا پاسخ تمام شده است؟ باز هم خیر.

توجه کنید ما به تیم‌ها شماره و ترتیب داده‌ایم در حالی که تیم‌ها با یک‌دیگر تفاوتی ندارند. پس به ازای هر حالت مسئله‌، ما $n!$ حالت را شمرده‌ایم. پس باید در انتها پاسخ را بر $n!$ تقسیم کنیم.

پس پاسخ برابر $\frac{(2n)!}{n! \times 2^n}$ است.
</پاسخ>