جایگشت

سه نفر به چند صورت متفاوت می توانند در یک ردیف کنار هم ایستاده و عکس بگیرند؟ اگر این سه شخص را با حروف لاتین a و b و c نمایش دهیم، تمام حالات ممکنه در زیر آمده است:

abc, acb, bca, bac, cab, aba

هر یک از این ۶ حالت را یک جایگشت از سه حرف $\left\{ {a,b,c} \right\}$  گوییم. حال اگر ۴ نفر بخواهند در یک ردیف و کنار هم عکس بگیرند چند حالت متفاوت پدید می آید؟

abcd , abdc , acbd , acdb , adcb , adbc

bacd , badc , bcad , bcda , bdac , bdca

cabd , cadb , cbad , cbda , cdab , cdba

dabc , dacb , dbac , dbca , dcab , dcba

به کمک اصل ضرب می توان تعداد جایگشت ها را بدون رسم کردن بدست آورد. تعداد جایگشت های ۴ شیء برابر است با $4 \times 3 \times 2 \times 1 = 24$  و تعداد جایگشت های ٣ شیء برابر است با $3 \times 2 \times 1 = 6$ در حالت کلی اگر n شیء متمایز داشته باشیم در این صورت تعداد جایگشت های این n شیء برابر است با: $n \times \left( {n - 1} \right) \times \left( {n - 2} \right) \times ... \times 3 \times 2 \times 1$

معرفی یک نماد: حاصل ضرب $n \times \left( {n - 1} \right) \times \left( {n - 2} \right) \times ... \times 3 \times 2 \times 1$  را با نماد $n!$ نشان می دهیم و n فاکتوریل خوانده می شود.

حال تصور کنید هفت شیء متمایز ${a_7},{a_6},{a_5},...,{a_1}$  داشته باشیم. می خواهیم تعداد جایگشت های بطول ٣ ( یعنی با سه شیء) را که می توان از ٧ شیء فوق ساخت محاسبه کنیم. یک جایگشت بطول ٣ را بصورت زیر در نظر می گیریم:

اولین خانه به هفت طریق ، دومین خانه به ۶ طریق و سومین خانه به ۵ طریق پر می شود. پس طبق اصل ضرب تعداد چنین جایگشت هایی برابر $7 \times 6 \times 5$  است. می توان این عبارت را طور دیگری هم نوشت:

$7 \times 6 \times 5 = 7 \times 6 \times 5 \times \frac{{4!}}{{4!}} = \frac{{7!}}{{7!}} = \frac{{7!}}{{\left( {7 - 3} \right)!}}$

عدد ٣ و ٧ که نقشی اصلی در مسئله داشتند را در آخرین کسر می بینیم. در حالت کلی اگر  باشد و بخواهیم تعداد جایگشت های r شیء را از n شیء بیابیم همانند مثال بالا عمل می کنیم:

اولین خانه دارای n انتخاب،دومین خانه $\left( {n - 1} \right)$  انتخاب، سومین خانه $\left( {n - 2} \right)$  انتخاب .... و r امین خانه دارای $\left( {n - r + 1} \right)$  نتخاب است. حال حاصلضرب این اعداد برابر است با:

$n\left( {n - 1} \right)\left( {n - 2} \right)...\left( {n - r + 1} \right) = \frac{{n!}}{{\left( {n - r} \right)!}} = p\left( {n,r} \right)$

عبارت $p\left( {n,r} \right)$  را برای تعداد جایگشت های r شیء از n شیء انتخاب کرده ایم. پس تعداد جایگشت های rشیء از n شیء یا $p\left( {n,r} \right)$  برابر است با :

$p\left( {n,r} \right) = \frac{{n!}}{{\left( {n - r} \right)!}}$

به هر روش قرار گرفتن n شیء دور یک دایره یک جایگشت دوری آن n شیء گوییم،با این ویژگی که اگر یک آرایش از دوران یک آرایش دیگر بدست آید این دو آرایش را هم ارز گوییم. در شکل زیر آرایش های ١ و ٢ از جایگشت های دوری $E,D,E,B,A$  هم ارزند اما این دو با ٣ هم ارز نیست.

قضیه: تعداد جایگشت های دوری n شیء برابر است با $\left( {n - 1} \right)!$ .