آیا فرمولی برای بدست آوردن تعداد روابط هم ارزی (یا تعداد افرازهای ممکن) روی مجموعه‌ی n عضوی وجود داره؟
رابطه دوتایی منظورتونه؟
(۱۲ شهریور ۱۳۸۹ ۱۲:۲۰ ق.ظ)admin نوشته شده توسط: رابطه دوتایی منظورتونه؟
رابطه‌ی هم‌ارزی رابطه‌ای است که هم بازتابی هم متقارن و هم تعدی باشه
افراز هم که فکر کنم می‌دونید چیه!
خوب می شه تمام روابط منهای روابط متقارن و تعدی یا به عبارتی
۲ به توان n(n+1)/2 تعداد روابط متقارن هست.
برای تعدی نیاز به محاسبه ماتریس Rn وجود داره.
بنابراین هیچ فرمولی برای هم ارزی وجود نداره!! و مسئله هم از نوع np هست!
فکر می کنم یه چنین فرمولی داشته باشه! لطفا اگه درست بود بگو
کد:
sigma(j=1 to n )S(n,j)که(S(n,jفرمول استرلینگ نوع ۲ هست.
کد:
]}S(n,m)=(1)/(m!) sigma(k=0 to m){[(-1)^m] [m choose k] [(m-k)^n.پیچیدگی این فرمول چقدره؟
جالب شد!
فکر کنم نمایی
به این اعداد bell numbers می گن فکر کنم این سایت اطلاعات خوبی در موردش داشته باشه:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
البته اگه عدد n کوچک باشه می تونیم بجای فرمول استرلینگ از مثلث استرلینگ هم استفاده کنیم....
تعداد افرازها برای مجموعه n عضوی عدد کاتالان هست
(۱۲ شهریور ۱۳۸۹ ۰۲:۴۳ ق.ظ)luna نوشته شده توسط: فکر می کنم یه چنین فرمولی داشته باشه! لطفا اگه درست بود بگو
کد:
sigma(j=1 to n )S(n,j)
که(S(n,jفرمول استرلینگ نوع ۲ هست.
کد:
]}S(n,m)=(1)/(m!) sigma(k=0 to m){[(-1)^m] [m choose k] [(m-k)^n.
دستت درد نکنه اینم درسته
البته تازه امروز تو یه کتاب خوندم قبلا نمی‌دونستم واسه همین پرسیدم
لونا تو چی می‌خونی ارشدی دکتری چه رشته‌ای، که همه چیزو بلدی
(۱۲ شهریور ۱۳۸۹ ۰۱:۰۷ ب.ظ)leilast نوشته شده توسط: تعداد افرازها برای مجموعه n عضوی عدد کاتالان هست
عدد کاتالان تا ۴= n درسته ازون بیشتر جواب اشتباه می‌ده
مثلا واسه ۵ جواب کاتالان ۴۲ میشه و در اصل ۵۲
من سال پیش کنکور دادم.شما هم سال دیگه همه اینا رو بلدین!
در کل عدد استرلینگ نوع دوم میشه تعداد راههایی که میتونیم یک مجموعه n عضوی رو دقیقه به m زیر مجموعه غیر تهی افراز کرد.
اینجا بحث ترکیبیاتیش هم هست که جالبه:
تعریف بالا معادل اینه که تعداد راههایی که n شی متمایز رو در m جعبه متمایز توزیع کنیم بطوری که هیچ جعبه ای خالی نمونه!
و حالا نباید با این مسئله آشنای ترکیبیاتی قاطی کنیم:
تعداد راههای توزیع n شی یکسان در بین m جعبه متمایز که اون جواب معادله x1+x2+...+xm = n هست که فرمولش سادست.من تو حل یک تست اشتباها از این روش رفتم و جواب غلط رو زدم در حالی که دقت نکرده بودم جعبه‌ها متمایزند.