به چند طریق میتوان k راس از راسهای n ضلعی [tex]A_1A_2...A_n[/tex] را انتخاب کرد به طوریکه هیچ دو راسی مجاور نباشند؟(هیچ دو راس مجاوری انتخاب نشوند؟)
سلام
برای سادگی n نفر را در نظر بگیرد که در یک خط قرار دارند و می خواهیم از بین انها k نفر را انتخاب کنیم.می دانیم که به [tex]\binom{n}{k}[/tex] حالت امکان پذیر است.حال اگر به این n نفر شماره بدیم و بخواهیم k نفر را انتخاب کنیم چون ترتیب مهم نیست شماره های k نفر را می توانیم به صورت زیر بنویسیم.[tex]1\le a_1< a_2< a_3<...< a_k\le n[/tex]. که کافی است k نفرانتخاب کنیم و شماره های انها را به ترتیب صعودی قرار دهیم.
اگر بخواهیم هیچ کدام از این k نفر مجاور هم نباشند باید اختلاف شماره های انها حداقل ۲ باشد یعنی داریم[tex]1\le a_1< a_2-1< a_3-2<...\le a_k-k+1\le n-k+1[/tex] که همان [tex]\binom{n-k+1}{k}[/tex] است.این زمانی بود که ما برای سادگی n نفر را به صورت خطی فرض کردیم حال اگر انها را به صورت دایره ای فرض کنیم یعنی دو سر خط را به هم نزدیک کنیم تا یک دایره ایجاد شود در این حالت ممکن حالت های اتفاق بیقتد که اشخاص دو سر خط که در حالت قبل انتخاب شده اند مجاور هم می شوند که قابل قبول نیست.پس ما حالت های که این دو نفر مجاور هم هستند را بدست اورده و از مقدار قبلی کم می کنیم[tex]2<a_2-1<a_3-2<...<a_{k-1}-k+2\le(n-1)-(k-2)[/tex] که همان [tex]\binom{n-k-1}{k-2}[/tex] است.
حالا کافیه این n نفر که دور یک میز گرد نشسته اند را هر کدام یک راس در نظر بگیرد تا یک n ضلعی داشته باشیم که تعداد راه های انتخاب k راس از بین انها که هیج کدام مجاور نیستند برابر است با [tex]\binom{n-k+1}{k}-\binom{n-k-1}{k-2}[/tex]
در لینک زیر هم یک روش دیگر بدست اوردن همین رابطه توضیح داده شده است که خواندش می تواند به شما کمک کند
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.