جایگشت

جایگشت (به انگلیسی: Permutation)، در قلمرو ترکیبیاتی آن به معنی مرتّب‌سازی یا تغییر ترتیب اعضای یک مجموعه می‌باشد. ممکن است این چیدمان خطی یا غیر خطی (مثلاً دور یک دایره، که در این حالت جایگشت دوری نامیده می‌شود) صورت گیرد. اعضای مجموعه نیز می‌توانند هر چیزی باشند؛ مثلاً شیء یا عدد یا حرف و همچنین می‌توانند تکراری باشند یا متمایز. در هر مورد، مهم، تعداد طرق چیدن این اعضا است.

در هر کدام از شش ردیف، یک جایگشت متفاوت از سه توپ مشخص شده‌است.

تعریف

جایگشت (خطی): هر ترتیب قرار گرفتن n شی در کنار هم را یک جایگشت می‌نامند.

رابطه عمومی جایگشت

چنانچه بخواهیم از میان n شیء، شمار r شیء را برگزینیم و در آن زیرمجموعه، ترتیب هم مهم باشد؛ شمار جایگشت‌ها چنین به‌دست می‌آید:

${P_{r}^{n}}={\frac {n!}{(n-r)!}}$

محاسبه

فرض کنید می‌خواهیم $n$ دانش آموز (به عنوان اشیا متمایز) را در یک صف قرار دهیم:

در جایگاه اول ممکن است هر یک از $n$ دانش آموز بایستند پس برای مکان اول (ابتدای صف) $n$ حالت مختلف وجود دارد. در جایگاه دوم $n-1$ دانش آموز باقی‌مانده (به جز دانش آموزی که در جایگاه اول صف ایستاده) می‌توانند قرار بگیرند پس تا اینجا به $n\times (n-1)$ حالت مختلف توانستیم دو مکان اول را با دو دانش‌آموز پر کنیم. به همین ترتیب برای جایگاه سوم:

$n\times (n-1)\times (n-2)$

حالت و برای $i$ امین جایگاه به تعداد:

$n\times (n-1)\times (n-2)\times \dots \times (n-i+1)$

حالت داریم. با همین روند تمام $n$ جایگاه را به:

$n\times (n-1)\times (n-2)\times \dots \times 2\times 1$

طریق می‌توان با $n$ دانش آموز پر کرد؛ که همان تعداد روش‌های ایستادن $n$ دانش آموز در یک صف می‌باشد. حاصل ضرب فوق را «جایگشت $n$ شی متمایز» می‌نامند و آن را با نماد $n!$ (خوانده می‌شود $n$ فاکتوریل) نشان می‌دهند.

جایگشت r تایی (تبدیل)

گاه جایگشت تنها $r$ عضو از کل $n$ عضو مجموعه مد نظر است. در این حالت می‌توان آن را تبدیل $r$ از $n$ نیز نامید.

تعریف

اگر مجموعه‌ای از $n$ شی در اختیار داشته باشیم، هر آرایش خطی متشکل از $r$ تا از این اشیا، را یک جایگشت $r$ شی از این $n$ شی می‌نامیم.

نماد

جایگشت $r$ شی از $n$ شی را با نمادهای $\mathbf {P} (n,r)=\mathbf {P} _{r}^{n}={(n)}_{r}$ نمایش می‌دهند.

محاسبه

درست مانند طریقه محاسبه جایگشت‌های $n$ تایی (مربوط به کل مجموعه $n$ تایی) که در بالا انجام گرفت عمل می‌کنیم، با این تفاوت که در اینجا تنها r جایگاه برای قرار گرفتن اشیا موجود است. پس تنها تا مرحله $r$ ام پیش می‌رویم یعنی فقط $r$ شی از $n$ شی را در $r$ مکان داده شده قرار می‌دهیم که با توجه به اثبات فوق، مقدار این جایگشت برابر خواهد بود با:

$P_{r}^{n}=n\times (n-1)\times \dots \times (n-r+1)=n\times (n-1)\times \dots \times (n-r+1)\times {\frac {(n-r)\times (n-r-1)\times \dots \times 2\times 1}{(n-r)\times (n-r-1)\times \dots \times 2\times 1}}={\frac {n!}{(n-r)!}}$

${P_{r}^{n}}={\frac {n!}{(n-r)!}}$

همان‌طور که مشاهده می‌شود داریم:

${P_{n}^{n}}={\frac {n!}{0!}}=n!$

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

جایگشت‌های با تکرار

گاهی اشیائی که می‌خواهیم جایگشت دهیم، همگی متمایز نیستند و اشیاء یکسان نیز در بین آنها وجود دارد.

فرض کنید، می‌خواهیم حروف کلمه HELLO را جایگشت دهیم. در نگاه اول پاسخ مسئله برابر $5!$ است زیرا ۵ حرف وجود دارد. اما در اینجا ما ۲ حرف L یکسان داریم و تفاوتی بین آنها قائل نمی‌شویم؛ بنابراین در $5!$ تعدادی از حالات نامطلوب هستند. با توجه به اینکه ۲ حرف L متمایز را می‌توان به $2!$ حالت جایگشت داد نتیجه می‌گیریم که در $5!$ هر کلمه $2!$ بار شمرده می‌شود. برای حذف حالات نامطلوب داریم : ${\frac {5!}{2!}}$

چند مثال دیگر

• ۱۰ پرتقال یکسان و ۵ سیب یکسان در اختیار داریم. می‌خواهیم تمام این ۱۵ میوه را در یک ردیف پشت سر هم قرار دهیم. به چند طریق این کار قابل انجام است؟

پاسخ: با توجه به اینکه تمام پرتقال‌ها و تمام سیب‌ها یکسان هستند، همانند توضیحات بالا حالات نامطلوب را از کل حالات کم می‌کنیم: ${\frac {15!}{10!\times 5!}}$

• سعید می‌خواهد ۲ پیتزای یکسان، ۳ همبرگر یکسان و ۵ نوشابه یکسان را برای شام بخورد. او به چند طریق می‌تواند این کار را انجام دهد؟

پاسخ: توجه کنید که تمام غذاهای هم نوع، یکسان هستند و فقط ترتیب خوردن غذاها مهم می‌باشد، همانند مسائل قبل داریم: ${\frac {10!}{2!\times 3!\times 5!}}$

مثال

• به چند طریق می‌توان ۴ کتاب فیزیک، شیمی، ریاضی و هندسه را کنار هم قرار داد؟ $4!=24$
• به چند طریق می‌توان ۵ پسر و ۴ دختر را در یک ردیف قرار داد، به طوری که تمام پسرها کنار هم و تمام دخترها کنار هم باشند؟ $2!\times 5!\times 4!$
• به چند روش می‌توان از بین ۵ نفر، ۳ نفر را انتخاب کرده و مدال‌های طلا، نقره و برنز را به آنها اهدا کرد؟${\frac {5!}{(5-3)!}}={\frac {5!}{2!}}={\binom {5}{3}}\times 3!$
• به چند روش می‌توان اعضای مجموعه $\{1,2,...,2n\}$را جایگشت داد، به طوری که اعداد زوج در مکان‌های زوج و اعداد فرد در مکان‌های فرد ظاهر شوند؟ $n!\times n!=(n!)^{2}$

جستارهای وابسته

• ترکیب (ریاضی)

منابع

• عباس ثروتی، سعید نعمتی (اول بهار 1384)، ترکیبیات، انتشارات خوشخوان، شابک ۹۶۴-۸۶۰۱-۳۶-۴
• علی رضا علیپور (اول 1382)، ترکیبیات، انتشارات فاطمی، شابک ۹۶۴-۳۱۸-۳۴۲-۴