طرح سوال ترکیبیات و گسسته

[Roamer]

http://fa.wikipedia.org/wiki/%D9%86%D8% ... 8%A7%D9%81

- چرا در هر گراف حتما دو راس هم درجه پیدا میشه ؟

[lebesgue]

چون در غیر اینصورت نتیجه میشود که گرافی با n رأس، تمام درجه های n-1,n-2,...,1,0 را داراست، در حالی فرض وجود درجه 0 و درجه n-1 بطور همزمان در یک گراف، منجر به تناقض می شود: وجود درجه 0 به این معناست که گراف رأسی دارد که به هیچ رأس دیگری متصل نیست، درحالی که وجود درجه n-1 به این معناست که گراف رأسی دارد که به همه رأسهای دیگر متصل است.

[jhvh]

الگوریتم برنامه:
1.عدد n را به تمام حالت های مجاز تقسیم میکنیم .
برای n=4 , k=2 مثلا میشه این:
1+1+1+1
1+1+2
2+2
(3و1) مجاز نیست. چون نباید مورد بیشتر از k رو بررسی کنیم.
2.تعداد جایگشت های هر حالت را حساب میکنیم.
تعداد حالتهای قسمتهای بالا میشه:
1
3
1
3.عدد تمام جایگشتها رو باهم جمع میکنیم.
1+3+1=5

ببینید برای من اسمها مهم نیستن ناسلامتی ریاضیدان هم نباشیم اداشونو که بلدیم در بیاریم



به اون بالاییه هم بگم که به جای اینکه جدا کنی فرمول منو یاد بگیر


متاسفانه حد احتمال همین جاست و اینجا تموم میشه

پس دیگه حرف نزنید