جایگشت

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

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

تعریف

جایگشت (خطی): هر ترتیب dfsd (خطی) قرار گرفتن n شی در کنار هم را یک جایگشت می‌نامند. در مسایل ترکیبیاتی اکثراً تعداد جایگشت‌ها مد نظر است.

محاسبه

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

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

${\displaystyle n\times (n-1)\times (n-2)}$

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

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

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

${\displaystyle n\times (n-1)\times (n-2)\times \dots \times 2\times 1}$

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

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

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

تعریف

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

نماد

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

محاسبه

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

${\displaystyle 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)!}}}$

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

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

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

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

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

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

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

چند مثال دیگر

• 10 پرتقال یکسان و 5 سیب یکسان در اختیار داریم. می خواهیم تمام این 15 میوه را در یک ردیف پشت سر هم قرار دهیم. به چند طریق این کار قابل انجام است؟

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

• سعید می خواهد 2 پیتزای یکسان، 3 همبرگر یکسان و 5 نوشابه یکسان را برای شام بخورد. او به چند طریق می تواند این کار را انجام دهد؟

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

مثال

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

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

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

منابع

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