جایگشت

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

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

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

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

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

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

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

گاه جایگشت تنها ${\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}$  مکان داده شده قرار می‌دهیم که با توجه به اثبات فوق، مقدار این جایگشت برابر خواهد بود با:

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

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

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

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

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

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

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

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

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

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

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