جایگشت کیست؟ توضیح بده.
جایگشت ، در قلمرو ترکیبیاتی آن به معنی مرتّب‌سازی یا تغییر ترتیب اعضای یک مجموعه می‌باشد. ممکن است این چیدمان خطی یا غیر خطی (مثلاً دور یک دایره، که در این حالت جایگشت دوری نامیده می‌شود) صورت گیرد. اعضای مجموعه نیز می‌توانند هر چیزی باشند؛ مثلاً شیء یا عدد یا حرف و همچنین می‌توانند تکراری باشند یا متمایز. در هر مورد، مهم، تعداد طرق چیدن این اعضا است.تعریف.جایگشت (خطی): هر ترتیب قرار گرفتن n شی در کنار هم را یک جایگشت می‌نامند.رابطه عمومی جایگشت.چنانچه بخواهیم از میان n شیء، شمار r شیء را برگزینیم و در آن زیرمجموعه، ترتیب هم مهم باشد؛ شمار جایگشت‌ها چنین به‌دست می‌آید:formula_1محاسبه.فرض کنید می‌خواهیم formula_2 دانش آموز (به عنوان اشیا "متمایز") را در یک صف قرار دهیم:در جایگاه اول ممکن است هر یک از formula_2 دانش آموز بایستند پس برای مکان اول (ابتدای صف) formula_2 حالت مختلف وجود دارد. در جایگاه دوم formula_5 دانش آموز باقی‌مانده (به جز دانش آموزی که در جایگاه اول صف ایستاده) می‌توانند قرار بگیرند پس تا اینجا به formula_6 حالت مختلف توانستیم دو مکان اول را با دو دانش‌آموز پر کنیم. به همین ترتیب برای جایگاه سوم:formula_7حالت و برای formula_8 امین جایگاه به تعداد: formula_9حالت داریم.با همین روند تمام formula_2 جایگاه را به:formula_11طریق می‌توان با formula_2 دانش آموز پر کرد؛ که همان تعداد روش‌های ایستادن formula_2 دانش آموز در یک صف می‌باشد. حاصل ضرب فوق را «جایگشت formula_2 شیمتمایز» می‌نامند و آن را با نماد formula_15 (خوانده می‌شود formula_2 فاکتوریل) نشان می‌دهند.جایگشت r تایی (تبدیل).گاه جایگشت تنها formula_17 عضو از کل formula_2 عضو مجموعه مد نظر است. در این حالت می‌توان آن را "تبدیل formula_17 از formula_2" نیز نامید.تعریف.اگر مجموعه‌ای از formula_2 شی در اختیار داشته باشیم، هر آرایش خطی متشکل از formula_17 تا از این اشیا، را یک جایگشت formula_17 شی از این formula_2 شی می‌نامیم.نماد.جایگشت formula_17 شی از formula_2 شی را با نمادهای formula_27 نمایش می‌دهند.محاسبه.درست مانند طریقه محاسبه جایگشت‌های formula_2 تایی (مربوط به کل مجموعه formula_2 تایی) که در بالا انجام گرفت عمل می‌کنیم، با این تفاوت که در اینجا تنها r جایگاه برای قرار گرفتن اشیا موجود است. پس تنها تا مرحله formula_17 ام پیش می‌رویم یعنی فقط formula_17 شی از formula_2 شی را در formula_17 مکان داده شده قرار می‌دهیم که با توجه به اثبات فوق، مقدار این جایگشت برابر خواهد بود با:formula_34formula_1همان‌طور که مشاهده می‌شود داریم:formula_36که همان جایگشت n تایی می‌باشد که با جواب حاصل از انتخاب تمامی n عضو مجوعه n تایی و چیدن آنها در یک ردیف یعنی تبدیل n از n یکی است، که طبق تعاریف ذکر شده این امر واضح است.جایگشت‌های با تکرار.گاهی اشیائی که می‌خواهیم جایگشت دهیم، همگی متمایز نیستند و اشیاء یکسان نیز در بین آنها وجود دارد.فرض کنید، می‌خواهیم حروف کلمه HELLO را جایگشت دهیم. در نگاه اول پاسخ مسئله برابر formula_37 است زیرا ۵ حرف وجود دارد. اما در اینجا ما ۲ حرف L یکسان داریم و تفاوتی بین آنها قائل نمی‌شویم؛ بنابراین در formula_37 تعدادی از حالات نامطلوب هستند. با توجه به اینکه ۲ حرف L متمایز را می‌توان به formula_39 حالت جایگشت داد نتیجه می‌گیریم که در formula_37 هر کلمه formula_39 بار شمرده می‌شود. برای حذف حالات نامطلوب داریم : formula_42چند مثال دیگر.پاسخ: با توجه به اینکه تمام پرتقال‌ها و تمام سیب‌ها یکسان هستند، همانند توضیحات بالا حالات نامطلوب را از کل حالات کم می‌کنیم: formula_43پاسخ: توجه کنید که تمام غذاهای هم نوع، یکسان هستند و فقط ترتیب خوردن غذاها مهم می‌باشد، همانند مسائل قبل داریم: formula_44