(۰۷ مهر ۱۳۹۳ ۰۳:۰۸ ق.ظ)fatemeh69 نوشته شده توسط:  

(06 مهر ۱۳۹۳ ۱۰:۳۲ ب.ظ)ldns0098 نوشته شده توسط:  تعداد چهارتایی های (a,b,c,d) به ازای عدد صحیح و مثبت n.
طوری کهn>=d >=c>=b >=a>=0
تست ۴۲ صفحه ۵۵ پوران.
من متوجه نمیشم چطور میشه جوابو بدست اوورد.

ما می خواهیم چهار تا عدد از بین ۰ تا n انتخاب کنیم که این اعداد می تونن با هم مساوی باشن یا اعداد کنار هم مساوی باشن یا این که هر عدد از عدد چپی خودش بزرگتر باشه
خب اینا هر کدوم چندین وضعبت ختلف ایجاد می کنه (۴ تا عدد یکسان- سه تا عدد یکسان و یکی متفاوت- دوتا عدد یکسان و دوتا متفاوت و...)
که بررسی هر کدوم باز حالت های جدیدی تولید می کنه مثلا اگه قرار باشه سه تا عدد یکسان و یک عدد متفوات باشه
می توان حالت های زیر را در نظر گرفت:
a<b=c=d
a=b=c<d


پس اگر بخواهیم مسئله را در حالت داده شده بررسی کنیم مشکله و چیی که مشکل ایجادم یکنه اینه که ما ننمی دونیم بالاخره a<b است یا a=b و اینکه b<c است یا b=c واینکه c<d است یا c=d .
خب ما کمی مسئله را تغییر می دیهم و به یک مساله ی هم ارز با پیچیدگی کمتر تبدیل می کنیم یعنی این مساله را به مساله ی دیگری تبدیل می کنیم که هم ارز است یعنی هر جواب برای مسئله ی جدید متناظر با یک ج.اب برای مساله ی اصلی است و بالعکس منتها حل کردن مساله ی جدید راحت تر است و دیگر این دردسرهارا ندارد
می داینم که اگر a<=b باشد حتما a<b+1 است. (چرا؟ با عدد گذاری به جای a و b امتحان کنید)
پس ما هر علامت "کوچکتر مساوی" که می بینیم می توانیم با اضافه کردن یک واحد به سمت راستی علاکت را به "کوچکتر" تبدیل کنیم
[tex]0<=a<=b<=c<=d<=n[/tex]
حالا a را دست نمی زینم و به سمت راستی ها یک واحد می افزاییم
می شه
[tex]0<=a<b 1<=c 1<=d 1<=n 1[/tex]
(قبوله ؟ بله چون اگه b<=c باشه b+1<=c+1 است )
حالا به b+1 دست نمی زینم و به سمت راستی های آن یک واحد می افزاییم
[tex]0<a<b 1<c 2<=d 2<=n 2[/tex]
و همین طور جلو می رویم:
[tex]0<a<b 1<c 2<d 3<=n 3[/tex]
خب این یعنی چی؟ یعنی از بین اعداد ۰ تا n+3 چهار تا عدد متفاوت انتخاب کن
چند تا نکته: اولا اعدا می تواندد خود ۰ یا خود n+3 باشند پس ما باید از بین n+4 تا عدد ، ۴ عدد انتخاب کنیم
ثانیا هر چهار عددی که انتخاب کنیم می توانیم آن را به یک ترتیب بنویسیم و به فرم (a,b,c,d) بنویسیم
مثلا فرض کنید اعداد ۵ و ۹و ۱و ۶ انتخاب شده اند این ها رو مرتب می کنیم می شه (۹و۶و۵و۱)
پس مسئله را تبدیل کردیم به انخاب ۴ عضو از میان n+4 عضو که می شه
[tex]\binom{n 4}{4}[/tex]

(۰۷ مهر ۱۳۹۳ ۰۲:۵۰ ق.ظ)Jooybari نوشته شده توسط:  سلام. کافیه ۴ عدد با تکرار بین ۰ تا n پیدا کنید و صعودی مرتبش کنید. درنظر بگیرید [tex]c_i[/tex] باشه تعداد دفعات انتخاب عدد i. مجموع [tex]c_0[/tex] تا [tex]c_n[/tex] میشه ۴ پس تعداد حالاتش میشه [tex]\binom{n 4}{4}[/tex].