جایگشتهای باتکرار و یک در میان
من در مطلب قبلی در مورد جایگشتهای بدون تکرار و در حالت کلی بحث کردیم ، در این مطلب می خواهیم چند حالت جایگشتها را بررسی کنیم .و دانستیم که جایگشتها در مورد اشیاء دو به دو متمایز بود.
1- جایگشتهای باتکرار
گاهی ممکن است با جایگشتهایی مواجه شویم که اشیاء آنها دو به دو متمایز نیستند. مثلا چند عدد از انها و یا چند حرف از آنها از یک نوع باشند ،چنین حالاتی را جایگشت با تکرار می گوییم.
من اینجا سعی می کنم با یک مثال ،این نوع جایگشت را توضیح دهم .
مثال 1: با حروف A,B,C} } چند کلمه سه حرفی می توان ساخت ؟
اینجا ما یک جایگشت خطی داریم که هیچ شی تکراری هم نداریم پس برابر [math]3![/math] می باشد و می توان تمام حالتها را به شکل زیر نمایش داد .
مثال 2: با حروف A,A,C} } چند کلمه سه حرفی می توان ساخت ؟
همانطور که در مثال اول دیدیم اگر متمایز بودن آنگاه ما [math]3![/math] حالت داشتیم ، اما در اینجا ما دو شی تکراری داریم . اول سعی می کنم تمام حالتها را با شکل نشان دهم.
اگر به شکل بالا دقت کنید می بینیم که دو حالت کاملا تکراری داریم که اینجا آنها را حذف کردیم و تعداد حالتهای باقی مانده ما شد 3 حالت .
چون ما با جایگشت سرو کار داریم تکرار مجاز نیست و باید حالتهای تکراری را حذف کنیم .حالا در مثال بالا با توجه به تکراری بودن دو حرف ، تعداد حالتهای ما بصورت زیر محاسبه می شود.
[math]\frac{{3!}}{{2!}} = \frac{{3 \times 2 \times 1}}{{2 \times 1}} = 3[/math]
بطور کلی تعداد جایگشتهای n شی که در آن [math]{a_1}[/math] شی مثل هم و [math]{a_2}[/math] شی مثل هم و [math]{a_k}[/math] شی مثل هم باشند برابر است با:
[math] \frac{{n!}}{{{a_1}! \times {a_2}! \times …{a_k}!}}[/math]
در واقع ما تعداد کل جایگشتها را تقسیم می کنیم (!تعداد حروف تکراری) تا حالتهای تکراری را حذف کنیم.
مثال 3:با ارقام {3,4,1,5,5,2,2,2} چند عدد هشت رقمی می توان نوشت ؟
تعداد کل اشیا یا همان ارقام داده شده هشت رقم است پس طبق فرمول بالا داریم :
[math] \frac{{8!}}{{2! \times 3!}}[/math]
مثال 4: با حروف کلمه Assassinations چند کلمه می تواند ساخت که همه حروف در آن بکار رفته باشد؟
این کلمه دارای 14 حرف می باشد.که حرف A 3 بار تکرار شده ،حرف s پنج بار تکرار شده و حروف I,n هر کدام دوبار تکرار شده اند پس تعداد کلمات برابر است با :
[math] \frac{{14!}}{{5! \times 3! \times 2! \times 2!}}[/math]
مثال 5:بار ارقام {3,4,1,0,0,2,2,2} چند عدد هشت رقمی می توان ساخت ؟
ابتدا دقت کنید که عدد هشت رقمی بصورت زیر هشت جایگاه دارد .
پس در واقع در جایگاه اول ما فقط شش حالت برای پر کردنش داریم .چون اعداد با صفر شروع نمی شوندپس این خانه اول فقط با شش عدد می توان پر کرد.همچنین برای جایگاههای بعدی طبق تصویر می توانیم از بقیه اعداد پر کنیم .دقت کنید که تکرار مجاز نیست . پس می توان گفت تعداد کل جایگشتها برابر با :
[math]6 \times 7![/math]
حال چون دو عدد تکراری داریم یکی عدد 2 هست که سه بار تکرار شده و دیگری عدد صفر هم دوبار تکرار شده و جایگشت اعداد تکراری تاثیری ندارد و باید حذف شود پس :
[math] \frac{{6 \times 7!}}{{2! \times 3!}} = \frac{{6 \times 7!}}{{2! \times 6}} = \frac{{7!}}{{2!}}[/math]
2-قرار گرفتن چند شیء در کنار هم
اگر در یک جایگشت چند شی باید در کنار هم باشند ، آنها را یک شیء در نظر می گیریم
اگر در جا دادن این اشیاء ترتیبی ذکر نشود ،جایگشت خود این اشیاء را نیز در جواب بدست آمده ضرب می کنیم.
فرض کنید چهار حرف {a,b,c,d} داده شده اند . می خواهیم تبدیلات از این 4 شی را مشخص کنیم که {a,c} حتما در کنار هم باشند .برای اینکار ما {a,c} را یک شی در نظر می گیریم پس در حقیقت ما اینجا 3 شی متمایز
را خواهیم داشت که با این سه شی تبدیلات زیر را می توان ساخت .
اما از هر تبدیل فوق دو تبدیل دیگر نیز می توان ساخت که با عوض کردن جای {a,c} بدست می آید .
بطور کلی اگر بخواهیم n شی متمایز را کنار هم قرار دهیم بطوریکه از این n شی دقیقا k شی کنار هم قرار بگیرند تعداد حالات آن از فرمول زیر حساب می شود:
[math] (n – k + 1)! \times k![/math]
در مثالی که ذکر کردیم ما جمعا چهار حرف داریم که میخواهیم دوتا آنها در کنار هم باشند پس
[math]\left\{ \begin{array}{l}(n – k + 1)! \times k!\\n = 4\\k = 2\end{array} \right\} \to (4 – 2 + 1)! \times 2! = 3! \times 2! = 6 \times 2 = 12[/math]
مثال: به چند روش میتوان ۴ دختر و ۵ پسر را در یک ردیف قرار دارد؛ طوری که
الف)دخترها، کنار هم باشند؟
ب) تمام پسرها کنار هم و تمام دخترها کنار هم باشند؟
الف) ما جمعا 9 شی داریم ، حالا اگر قراره دخترها در کنار هم قرار بگیرند پس
[math]\left\{ \begin{array}{l}(n – k + 1)! \times k!\\n = 9\\k = 4\end{array} \right\} \to (9 – 4 + 1)! \times 4! = 6! \times 4![/math]
ب) ابتدا پسرها را با هم یک شیء و دخترها را با هم یک شیء در نظر میگیریم. این ۲ شء، به 2! حالت میتوانند کنار هم قرار بگیرند. حال پسرها در میان خودشان به 5! حالت و دخترها در میان خودشان به 4! حالت میتوانند ترتیب بگیرند. پس پاسخ، برابر 2!×5!×4! است.
3-یک در میان چیدن اعضا
در برخی از مسائل از ما میخواهند دو نوع شی را یک در میان در کنار هم قرار دهیم مثلا چند نفر ایرانی و چند نفر آلمانی را در یک ردیف و بصورت یک در میان مرتب کنیم . ما در اینجا دو حالت خواهیم داشت
حالت اول :تعداد دو نوع شی که میخواهیم بصورت یک در میان کنار هم قرار دهیم مساوی نیست ، خوب مشخصه که یک مجموعه اشیا بیشتری دارد در چنین حالتی شی اول را از مجموعه ای انتخاب می کنیم که اعضای آن بیشتر است.
مثال :2 پسر و 3 دختر را به چند طریق می توان بصروت یک در میان کنار هم قرار داد؟
اگر پسرها را با حرف B و دخترها را با حرف G نمایش دهیم ترتیب قرار گرفتن آنها بصورت زیر خواهد بود
{G,B,G,B,G}
حال چون دخترها و پسرها با هم متفاوت هستندو در بین خود هم جابجایی دارند در واقع جایگشت دخترها در صورتی که پسرها ثابت باشند برابر [math]3![/math] و جایگشت پسرها در صورتی که دخترها ثابت باشند برابر [math]2![/math] و بنابر اصل ضرب روش چیدن آنها در کنار هم در هم ضرب می شود پس جایگشت کل :
[math] 3! \times 2! = 6 \times 2 = 12[/math]
حالت دوم : تعداد دو نوع شی که میخواهیم بصورت یک در میان کنار هم قرار دهیم مساوی هستند در این حالت افراد هر دو نوع می توانند در مکان اول قرار بگیرند
مثال :3 دختر و 3 پسر به چند طریق می توانند یک در میان کنار هم قرار بگیرند؟
اگر پسرها را با حرف B و دخترها را با حرف G نمایش دهیم ترتیب قرار گرفتن آنها بصورت زیر خواهد بود
{B,G,B,G,B,G}
یا
{G,B,G,B,G,B}
چون دخترها متفاوت هستند بین خودشون [math]3![/math]حالت برای ترتیب دارند ، پسرها هم همنیطور به [math]3![/math]حالت می توانند جابجا شوند .از طرف دیگر جابجایی کل دخترها به پسرها نیز هم 2 حالت دارد یعنی شروع از پسر باشد یا دختر که در این صورت ضربدر 2 می شود پس :
[math] 3! \times 3! \times 2 = 6 \times 6 \times 2 = 72[/math]