جایگشت-جایگشت خطی
جایگشت
مساله های آنالیز ترکیبی و شمارش سه دسته هستند
1-مساله هایی که هدفشان جابجایی است .یعنی آرایش چند شی در کنار هم.
2-مساله هایی که هدفشان انتخاب است . یعنی انتخاب r شی از بین n شی
3-مساله هایی که هدفشان انتخاب و جابجایی است.
هر جا سخن از کنار هم قرار دادن چند شی باشد.می توان از جایگشت نام برد.در واقع هدف جابجایی اشیا در کنار هم است .
تعریف جایگشت
طرز قرار گرفتن n شی در کنار هم (آرایش n شی) را بدون در نظر گرفتن تکرار آنها ،جایگشت آن n شی می گویند.(دقت کنید که ترتیب قرار گرفتن اینجا مهم است .)
پس در اینجا ما داریم مساله های نوع اول که هدفشان جابجایی است را بررسی می کنیم.
تعریفی که در بالا ذکر کردیم در واقع تعریف جایگشت خطی است .یعنی ما در تعریف بالا میخواهیم n شی را در کنار هم و در یک ردیف قرار دهیم .
جایگشتهای خطی
هر جا سخن از ترتیب چند شیء در کنار هم سخن گفته میشود، میتوان از جایگشت نام برد. این شیءها میتوانند در یک ردیف، دور یک دایره یا … باشند. اما
به هر روش قرار گرفتن چند شیء در یک ردیف، یک جایگشت خطی گفته میشود. برای مثال، هرگاه چند نفر در یک صف نانوایی ایستادهاند، یک جایگشت خطی تشکیل دادهاند.
مثال:فرض کنید حروف {a,b,c} هر کدامشان نشان دهنده یک فیش است که باید به دستگاه الکتریکی مثلا تلویزیون وصل شود. حالا میخواهیم تمام حالتهای وصل شدن این فیش ها را بررسی کنیم.
گام اول می دانیم که از هر فیش فقط یک عدد داریم . یعنی امکان ندارد یک فیش در دو جایگاه قرار بگیرد. پس اینجا هیچ گونه تکراری نخواهیم داشت .به زبان ریاضی در شمارش حالتهای حروف {a,b,c} تکرار نداریم.پس حالتهای قرار گرفتن فیش ها بصورت زیر خواهد بود :
c | b | a |
b | c | a |
c | a | b |
a | c | b |
b | a | c |
a | b | c |
بنابر این با توجه به اصل ضرب تعداد حالتها بصورت زیر محاسبه می شود :
1-در اولین جایگاه ما سه فیش برای قرار دادن داریم .پس در واقع سه انتخاب داریم.
2-در دومین جایگاه چون یکی از فیش ها در جایگاه قرار گرفته پس فقط 2 فیش برای ما باقی می ماند لذا فقط 2 انتخاب داریم .
3-و سرانجام وقتی به سومین جایگاه می رسیم فقط یک فیش باقی مانده پس در این مرحله فقط یک انتخاب داریم .
اکنون بنابر اصل ضرب تعداد حالتهای ما :
[math] 3 \times 2 \times 1 = 6[/math]
و این یعنی سه فاکتوریل [math]3![/math] چرا که
[math] 3!=3 \times 2 \times 1 = 6[/math]
تعریف کلی جایگشت
اگر n شی متمایز را در یک ردیف کنار هم قرار دهیم .طبق اصل ضرب تعداد جایگشت های n شی متمایز در کنار هم برابر است با [math]n![/math]
در واقع ما اینجا می خواهیم تعداد روش های قرار گرفتن n شی در یک ردیف را حساب کنیم.
شی اول ، n حالت دارد ،پس از آن شی دوم ردیف [math]n-1[/math] حالت دارد و پس از آن نیز شی سوم [math]n-2[/math] حالت دارد و به همین ترتیب تا آخرین شی پیش می رویم ، آنگاه طبق اصل ضرب پاسخ ما برابر با :
[math] n \times (n – 1) \times (n – 2) \times … \times 2 \times 1 = n![/math]
مثال 1: به چند حالت می توان چهار عدد {1,2,3,4} را در کنار هم قرار داد؟
جواب طبق تعریف کلی جایگشت ، چون ما اینجا 4 شی متمایز داریم پس تعداد حالتهای ما برابر است با [math]4![/math]
مثال 2: تعداد جایگشتهای 10 شی متمایز چندتاست ؟
جواب [math]10![/math]
مثال 3: تعداد کلمات هفت حرفی که بدون تکرار حروف با حروف {a,b,c,d,e,f,s,t} می توان نوشت؟
اینجا باید تعداد جایگشت های هفت شی متمایز را بدست آوریم که برابر [math]7![/math]
مثال 4: با حروف کلمه market
الف)چند جایگشت وجود دارد؟
ب)چند جایگشت وجود دارد که با حرف m شروع می شود؟
برای قسمت الف مشخصه که جواب برابر تعداد جایگشتهای 6 شی برابر [math]6![/math]
برای قسمت ب حرف m باید در ابتدا باشد ، و برای بقیه جایگاهها از بقیه حروف استفاده می کنیم یعنی 5 حرف برای ما باقی می ماند پس در واقع بقیه حرف به [math]5![/math] می توانند در کنار هم در یک ردیف قرار بگیرند.