المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:جایگشت‌های خطی

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

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

تعداد جایگشت‌های خطی $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،

  1. چند جایگشت وجود دارد؟
  2. چند جایگشت وجود دارد که با حرف n شروع شود؟
  3. چند جایگشت وجود دارد که با حرف صدادار شروع شود؟
  4. چند جایگشت وجود دارد که در آن، عبارت pen دیده شود؟

پاسخ

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

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

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

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

سایر مثال‌ها

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

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

  1. شرط خاصی نداشته باشیم؟
  2. در مکان اول یک پسر باشد؟
  3. ۴ دختر، کنار هم باشند؟
  4. هیچ ۲ پسری کنار هم نباشند؟
  5. تمام پسرها کنار هم و تمام دخترها کنار هم باشند؟

پاسخ

در قسمت اول، ۹ شیء داریم که باید در یک ردیف قرار بگیرند. پس پاسخ $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}$ است.


ابزار صفحه