- ارسال ها
- 119
- لایک ها
- 46
- امتیاز
- 0
صورت سوال:جایگشت x1x2x3...x2n از مجموعه {1,2,3,...,2n} را خوب می نامیم هرگاه i ای وجود داشته باشد که i بین 1 و 2n-1 باشد (و مساوی) و |xi - xi+1| = n و در غیر این صورت این جایگشت را بد می نامیم.ثابت کنید تعداد جایگشت های خوب بیشتر از تعداد جایگشت های بد است.
صفحه ی 54 ترکیبیات علیپور سوال 24.
...........................................................
خب تو ته کتاب راهنمایی شده ولی اونو نخوندم و یه ایده ای دیگه به ذهنم رسید که یجورایی تعمیم این سوال میشه.خب مطمئنا ما بدون محاسبه تعداد جایگشت های خوب شاید بتونیم حکم رو ثابت کنیم ولی ایده من اینه که با محاسبه تعداد جایگشت های خوب اگه (g(n) بنامیم و قرار دادن در فرمول g(n) > (2n)!/2 به جواب برسیم (در اینصورت تعداد جایگشت های خوب بیشتر از تعداد کل جایگشت ها تقسیم بر دو می شود و حکم ثابت می شود.)
برای حل ابتدا با مثالی مثل n=2 کار می کنیم:
تنها اعداد |3-1| = |1-3| = 2 و |4-2| = |2-4| =2 ویژگی مورد نظر رو دارن.یعنی دو گروه اعداد 1,3 و 2,4.با تصور نموداری ون می توان گفت g(2) برابر با جایگشت هایی که 1,3 دارند بعلاوه جایگشت هایی که 2و4 دارن منهای جایگشت هایی که هم 2,4 و هم 1,3 دارن(اصل شمول و عدم شمول با فرض دو مجموعه).
تعداد جایگشت هایی که 1,3 دارن: (3!)(2!) =12
تعداد جایگشت هایی که 2,4 دارن: 12
تعداد جایگشت هایی که هم 2,4 و هم 1,3 دارن: (2!)(2!)(2!) = 8
که g(2) = 24 - 8 = 18 که 18 هم بزرگ تر از 4!/2 یعنی 12 است.
واسه تعمیم هم میایم حالت بندی می کنیم:
2n,n
2n-1,n-1
2n-2,n-2
.
.
.
n+1,1
همون کار مشابه رو انجام می دیم ولی باید از اصل شمول و عدم شمول برای n مجموعه بالا استفاده کنیم.
پ.ن:می دونم خیلی راه سختی میشه ولی اگه تعمیم خوبی میشه و مشکلی نیست،ادامه دادنش عاقلانه است؟
صفحه ی 54 ترکیبیات علیپور سوال 24.
...........................................................
خب تو ته کتاب راهنمایی شده ولی اونو نخوندم و یه ایده ای دیگه به ذهنم رسید که یجورایی تعمیم این سوال میشه.خب مطمئنا ما بدون محاسبه تعداد جایگشت های خوب شاید بتونیم حکم رو ثابت کنیم ولی ایده من اینه که با محاسبه تعداد جایگشت های خوب اگه (g(n) بنامیم و قرار دادن در فرمول g(n) > (2n)!/2 به جواب برسیم (در اینصورت تعداد جایگشت های خوب بیشتر از تعداد کل جایگشت ها تقسیم بر دو می شود و حکم ثابت می شود.)
برای حل ابتدا با مثالی مثل n=2 کار می کنیم:
تنها اعداد |3-1| = |1-3| = 2 و |4-2| = |2-4| =2 ویژگی مورد نظر رو دارن.یعنی دو گروه اعداد 1,3 و 2,4.با تصور نموداری ون می توان گفت g(2) برابر با جایگشت هایی که 1,3 دارند بعلاوه جایگشت هایی که 2و4 دارن منهای جایگشت هایی که هم 2,4 و هم 1,3 دارن(اصل شمول و عدم شمول با فرض دو مجموعه).
تعداد جایگشت هایی که 1,3 دارن: (3!)(2!) =12
تعداد جایگشت هایی که 2,4 دارن: 12
تعداد جایگشت هایی که هم 2,4 و هم 1,3 دارن: (2!)(2!)(2!) = 8
که g(2) = 24 - 8 = 18 که 18 هم بزرگ تر از 4!/2 یعنی 12 است.
واسه تعمیم هم میایم حالت بندی می کنیم:
2n,n
2n-1,n-1
2n-2,n-2
.
.
.
n+1,1
همون کار مشابه رو انجام می دیم ولی باید از اصل شمول و عدم شمول برای n مجموعه بالا استفاده کنیم.
پ.ن:می دونم خیلی راه سختی میشه ولی اگه تعمیم خوبی میشه و مشکلی نیست،ادامه دادنش عاقلانه است؟