جایگشت

آرایش اعضای یک مجموعه

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

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

تعریف

ویرایش

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

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

ویرایش

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

 

محاسبه

ویرایش

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

 

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

 

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

 

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

 

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

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

ویرایش

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

تعریف

ویرایش

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

جایگشت   شی از   شی را با نمادهای   نمایش می‌دهند.

محاسبه

ویرایش

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

 

 

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

 

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

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

ویرایش

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

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

چند مثال دیگر

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

پاسخ: با توجه به اینکه تمام پرتقال‌ها و تمام سیب‌ها یکسان هستند، همانند توضیحات بالا حالات نامطلوب را از کل حالات کم می‌کنیم:  

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

پاسخ: توجه کنید که تمام غذاهای هم نوع، یکسان هستند و فقط ترتیب خوردن غذاها مهم می‌باشد، همانند مسائل قبل داریم:  

  • به چند طریق می‌توان ۴ کتاب فیزیک، شیمی، ریاضی و هندسه را کنار هم قرار داد؟  
  • به چند طریق می‌توان ۵ پسر و ۴ دختر را در یک ردیف قرار داد، به طوری که تمام پسرها کنار هم و تمام دخترها کنار هم باشند؟  
  • به چند روش می‌توان از بین ۵ نفر، ۳ نفر را انتخاب کرده و مدال‌های طلا، نقره و برنز را به آنها اهدا کرد؟ 
  • به چند روش می‌توان اعضای مجموعه  را جایگشت داد، به طوری که اعداد زوج در مکان‌های زوج و اعداد فرد در مکان‌های فرد ظاهر شوند؟  

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

ویرایش

منابع

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