جایگشتها و تبدیلهای دوری یا دایره ای
جایگشت ها و تبدیلهای دوری یا دایره ای
تا اینجا بحث ما درباره جایگشتهای خطی بود ، یعنی جابجایی و چیدن اشیا در یک ردیف بود ، اما گاهی با مساله ای برخورد می کنیم که مجموعه ای از اشیا یا افراد را میخواهیم دور یک میز دایره ای بشینند.من برای فهم مطلب با چند مثال توضیح می دهم.
مثال 1: فرض کنید چهار نفر داریم که می خواهیم این چهار نفر را دور یک میز گرد بنشینند . این چهار نفر را من بصورت {a,b,c,d} نام گذاری می کنم .
در یک تبدیل دایره ای مکان اول و دوم و سوم معنا ندارد ، در واقع مکان قرار گرفتن اشیا اینجا معنا ندارد ، بلکه آنچه در جایگشت دایره ای معنا دارد ، قرار گرفتن دو به دو اشیا در کنار هم است. یعنی مهم اینکه بدانیم چه کسی کنار چه کسی دیگر قرار می گیرد .ما در شکل زیر ابتدا بصورت خطی چهار جایگشت را نشان داده این سپس آنها را بصورت دایره در زیر هم تبدیل شکل آن را بصورت دایره رسم کرده ایم.
جایگشتهای فوق بر روی یک دایره همگی یک نوع جایگشت هستند به عبارت دیگر همگی نشان دهنده یک حالت هستند . زیرا اگر هر دایره فوق را به اندازه ای بچرخانیم دقیقا همان حالت اول بدست می آید . در فیلم زیر هر کدام از حالتها را به اندازه 90 و180 و 270 درجه می چرخانیم و می بینیم دقیقا همان حالت اول بدست می آید .
در فیلم بالا دیدید که چگونه با چرخش دایره دقیقا همان حالت اول بدست آمد به تعبیری دیگر تمام چهار جایگشت زیر همگی با هم برابر و یک حالت هستند :
{a,b,c,d}={d,a,b,c}={c,d,a,b}={b,c,d,a}
چون در یک جایگشت دایره ای اگر دقت کنید در همه این چهار حالت همسایه های d ، افراد a,c بودند وهمیشه b بعد از a,d قرار گرفته است واگر چه این چهار جایگشت در حالت غیر دایره ای هر کدام نشان دهنده یک حالت مجزا هستند ، اما در یک جایگشت دایره ای همه اینها نشان دهنده دقیقا یک حالت هستند . پس تا اینجا بحث می توانیم بگوییم در یک جایگشت دایره ای از هر جایگشت دایره ای 4 شی و 4 جایگشت مختلف می توان داشت که دقیقا یک حالت را نشان می دهند .
خوب می دانیم جایگشت خطی برای 4 شی متفاوت برابر [math]4![/math] بود لذا جایگشت دایره ای در این حالت برابر با :
[math]\frac{{4!}}{4} = 3![/math]
در واقع فرمولی که برای یک جایگشت دایره ای بدست می آید :
اگر n شی داشته باشیم که بخواهیم دور یک میز دایره ای بچینیم ، به تعداد [math](n-1)![/math] می توانیم آنها را دور یک میز دایره ای شکل بچینیم .
روش دوم :در این روش ما ابتدا تک تک افراد را در نظر می گیریم من ابتدا جایگشت خطی را بررسی می کنم و سپس آن را با جایگشت دایره ای مقایسه می کنم.
مثال 2: به چند روش می توان 6 نفر را در یک ردیف قرار دهیم و همچنین همین افراد را با جند روش می توان دور یک میز بشینند؟
ابتدا جایگشت خطی را بررسی می کنم ، ما از مطالب قبلی (جایگشت خطی ) یاد گرفتیم که این شش نفر اگر بخواهند در یک ردیف قرار بگیرند به [math]6![/math] می توانند قرار بگیرند.
من اینجا نفرات خودم را با حروف {a,b,c,d,e,f} نمایش می دهم.
پس اکنون باید وضعیت این افراد را در یک دایره در نظر بگیریم . ببینید نفر اول (نفر اول a می باشد) وقتی میخواد روی یک صندلی بشیند دقیقا یک انتخاب داره؟ چرا ؟
چون ما گفتیم در یک دایره مکان اول و دوم و سوم اصلا معنا ندارد بلکه ترتیب قرار گرفتن افراد در کنار هم مهم است . لذا نفر اول روی هر صندلی که میخواد بشینه اهمیتی ندارد و در واقع می توان گفت روی هر صندلی که بشینه انتخابش یکسان است و فرقی نمی کنه ، بشه می توان گفت نفر اول به یک روش می تواند روی یک صندلی دور میز بشینه .
حالا نفر اول روی یکی از صندلیها نشست .
حالا می رسیم به نفر دوم ، خوب برای نفر دوم ما اینجا 5 صندلی داریم هر کدام از صندلی ها اینجا دیگر معنای متفاوتی دارن ؟ چرا ؟
چون دقت کنید وقتی نفر اول نشست از این به بعد دیگه صندلیها معنا دار می شن .و اینجا دیگه هر صندلی همانطور که در شکل بالا می بینید بر حسب موقعیت و فاصله از صندلی نفر اول (صندلی a) معنای متفاوتی خواهد داشت . پس با این حساب نفر دوم مثلا فرد b برای نشستن روی صندلی با 5 حالت و یا صندلی متفاوت مواجه است که می تواند روی هر کدام از آنها بنشیند .
پس تا اینجا برای نفر اول و نفر دوم روی میز دایره ای ، طبق اصل ضرب :
[math] 1 \times 5 = 5[/math]
5 حالت برای انتخاب وجود دارد . اکنون به عنوان مثال فرض می کنیم نفر دوم بر اساس تصویر زیر نشست است.
خوب نفر اول و دوم نشستن ، حالا می رسیم به نفر سوم . فرض کنید تصویر بالا نحوه نشستن نفر اول a و نفر دوم b باشد . خوب همانطور که می بیند چهار صندلی خالی دیگر وجود دارد . که باز بر اساس موقعیت a,b معنای متفاوتی دارند .یعنی نفر سوم باید 4 حالت برای انتخاب دارد . پس تا اینجا بنابر اصل ضرب
[math] 1 \times 5 \times 4 = 20[/math]
یعنی تا اینجا که نفر سوم روی میز نشست ما 20 حالت برای انتخاب نفر اول تا سوم داشتیم .به همین ترتیب ادامه می دهیم که خوب نفر چهارم که میاد در مقابل ش سه تا صندلی می بینه که فقط باید از میان انها روی یکی بشینه . و به همین ترتیب نر پنچم در مقابلش فقط دو صندلی خالی می بینه پس 2 حالت برای انتخاب دارد و سرانجام آخرین نفر یعنی نفر ششم دیگه در مقابلش فقط یک صندلی خواهد دید. بنابر این طبق اصل ضرب جدول حالتها برای هر نفر بصورت زیر خواهد بود .
نفر اول | 1 حالت | 1 حالت |
نفر دوم | 5 حالت | [math] 1 \times 5 = 5[/math] |
نفر سوم | 4 حالت | [math] 1 \times 5 \times 4 = 20[/math] |
نفر چهارم | 3 حالت | [math] 1 \times 5 \times 4 \times 3 = 60 [/math] |
نفر پنجم | 2 حالت | [math] 1 \times 5 \times 4 = 20[/math] |
نفر ششم | 1 حالت | [math] 1 \times 5 \times 4 \times 3 \times 2 = 120 [/math] |
خوب اگر به جدول بالا دقت کنید می بیند که تا نفر ششم که رسیدیم ، به ضرب زیر می رسیم :
[math] 1 \times 5 \times 4 \times 3 \times 2 \times 1 = 120[/math]
که این ضرب معادل همان 5 فاکتوریل [math]5![/math] است .
نتیجه گیری :
ما در دو مثال بالا و در دو روش متفاوت نشان دادیم که تعداد حالتهایی که [math]n[/math] دور یک میز بشینند ،اینکه ابتدا ما جای یک نفر را ثابت نگه می داریم و سپس [math]n-1[/math] نفر باقیمانده را به [math](n-1)![/math] روش جابجا می کنیم.پس تعداد حالتهای نشاندن [math]n[/math] نفر دور یک میز دایره ای برابر است با [math](n-1)![/math] .
مثال 3: به چند طریق 5 پسر بچه و 5 دختر بچه را می توان دور یک میز نشاند ؟
ب)به چند طریق می توان انها را یک در میان دور میز نشاند؟
پاسخ:
10 نفر را می توان به [math](10-1)![/math] یعنی [math]9![/math] روش دور میز نشاند .
برای پاسخ قسمت ب
5 پسر را می توان به [math](5-1)![/math] یعنی [math]4![/math] روش دور میز نشاند . چون بین هر دو پسر باید یک دختر بشینه لذا ما 5 جا خواهیم داشت که این 5 جا هر کدام معنای متفاوتی خواهد داشت و با [math]5![/math] حالت پر می شوند . پس بنابر اصل ضرب داریم :
[math] 5! \times 4![/math]