زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۱۰:۰۷ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

انتخاب k راس از راسهای n ضلعی

ارسال:
  

ss311 پرسیده:

انتخاب k راس از راسهای n ضلعی

به چند طریق میتوان k راس از راسهای n ضلعی [tex]A_1A_2...A_n[/tex] را انتخاب کرد به طوریکه هیچ دو راسی مجاور نباشند؟(هیچ دو راس مجاوری انتخاب نشوند؟)
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

msour44 پاسخ داده:

RE: انتخاب k راس از راسهای n ضلعی

سلام
برای سادگی 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]
در لینک زیر هم یک روش دیگر بدست اوردن همین رابطه توضیح داده شده است که خواندش می تواند به شما کمک کند

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  حل یکی از تمرینات کروس راس Ha153 ۰ ۳۵۲ ۲۷ مهر ۱۴۰۲ ۰۱:۰۸ ب.ظ
آخرین ارسال: Ha153
  فاصله دو راس(دکتری ۹۷) ss311 ۱ ۱,۶۶۹ ۱۷ خرداد ۱۳۹۸ ۰۶:۱۱ ب.ظ
آخرین ارسال: Jooybari
  درخواست کتاب شبکه کراس راس ویرایش هفتم fallah_o68 ۱ ۳,۲۱۰ ۰۷ مهر ۱۳۹۷ ۱۲:۱۲ ق.ظ
آخرین ارسال: mraict@gmail.com
  تاثیر ترتیب انتخاب در انتخاب رشته ارشد milad72r ۳ ۳,۸۱۸ ۱۲ خرداد ۱۳۹۷ ۰۷:۲۶ ب.ظ
آخرین ارسال: The BesT
  رنگ آمیزی راسهای گراف ss311 ۲ ۲,۰۸۰ ۰۳ بهمن ۱۳۹۶ ۰۱:۲۳ ق.ظ
آخرین ارسال: ss311
  نوشتن کد (زبان 'Prolog) برای پیدا کردن تمام راسهای مجاور یک راس ss311 ۰ ۱,۳۵۸ ۱۸ آبان ۱۳۹۶ ۰۱:۱۹ ب.ظ
آخرین ارسال: ss311
  TCP رنو (راس کوروس) سوال آی تی ۹۴ Saman ۵ ۸,۷۹۴ ۰۶ اردیبهشت ۱۳۹۶ ۱۲:۱۶ ب.ظ
آخرین ارسال: erfan.wakka
  لایه شبکه سوال ۱۷ راس همیلا ۲ ۲,۲۷۲ ۱۷ بهمن ۱۳۹۵ ۱۲:۳۴ ق.ظ
آخرین ارسال: همیلا
  لایه شبکه ایپی سوال ۱۶ و ۱۷ راس همیلا ۲ ۲,۷۶۴ ۱۵ بهمن ۱۳۹۵ ۱۲:۲۱ ق.ظ
آخرین ارسال: همیلا
  دانلود حل المسایل ویرایش های چهارم و پنجم شبکه کراس و راس javad94 ۱۲ ۱۹,۷۱۱ ۲۷ دى ۱۳۹۵ ۰۲:۰۵ ب.ظ
آخرین ارسال: masada1909

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close