اگر {A={1,2,3,4,5,6,7 ،چندتا از روابط موجود روی A رابطه هم ارزی بوده و درانها اعداد ۱و۲ درکلاس عدد۴ قراردارند؟؟؟؟؟جواب=۵۲
توضیح میخوام
چون اگه ۱ و ۲ توی کلاس هم ارزی ۴ باشن مسلماً توی کلاس هم ارزی ۱ اعداد ۲ و ۴ هستن. طبیعیه. رابطمون یه رابطه هم ارزیه و اگه داشته باشیم ۴R1 و ۴R2 حتماً ۱R4 و ۱R2 رو داریم و به همین شکل برای کلاس هم ارزی ۲ مجموعه ای (حداقل) شامل ۱ و ۴ داریم. (بر اساس اصل بازتاب و تعدی) پس برای شمارش تعداد کلاس های هم ارزی میشه این ۳ کلاس هم ارزی رو یکی درنظر گرفت.
حالا میخاهیم تعداد کلاسهای هم ارزی روی مجموعه ۵ عضوی بدون هیچ شرطی رو حساب کنیم. (۳ عضو ۱ و ۲ و ۴ یکی درنظر گرفته شدند.) یک راه سخت و مفهوم و یک راه ساده و نامفهوم سراغ دارم.
میدونیم کلاس هم ارزیه پس اگه a با b رابطه داشته باشه برعکسش هم هست. پس باید مجموعه ۵عضویمونو به تمام حالات ممکن به حداقل ۱ و حداکثر ۵ زیرمجموعه که اجتماعشون مجموعه ۱ تا ۵ باشه و هیچ دو مجموعه ای باهم اشتراک نداشته باشن بشکنیم. ولی توجه کنیم که اعضامون متفاوت و مجموعه هامون مشابه هستن. راه حل هامون تا اینجاش مشترک بود. ولی اینجا با دو راه جداگانه بررسی میشن:
راه سخت تر:
حالتهای مختلف افراز و تعدادشونو میشماریم:
فقط یک مجموعه ۵ عضوی داشته باشیم:
[tex]\binom{5}{5}=1[/tex]
یک مجموعه ۴ عضوی و یک ۱ عضوی:
[tex]\binom{5}{4}\binom{1}{1}=5[/tex]
یکی ۳ عضوی و یکی ۲ عضوی:
[tex]\binom{5}{3}\binom{2}{2}=10[/tex]
یکی ۳ عضوی و ۲تا تک عضوی
تقسیم بر !۲ بخاطر مشابه بودن دو مجموعه تک عضویه. این تقسیم برای موارد مشابه بعدی نیز تکرار خواهد شد.)[tex]\binom{5}{3}\binom{2}{1}\binom{1}{1}/2!=10[/tex]
دوتا ۲ عضوی و یکی تک عضوی:
[tex]\binom{5}{2}\binom{3}{2}\binom{1}{1}/2!=15[/tex]
یکی دو عضوی و ۳تا تکی عضوی:
[tex]\binom{5}{2}\binom{3}{1}\binom{2}{1}\binom{1}{1}/3!=10[/tex]
۵تا تک عضوی:
[tex]\binom{5}{1}\binom{4}{1}\binom{3}{1}\binom{2}{1}\binom{1}{1}/5!=1[/tex]
جواب جمع این حالاته که همون ۵۲ میشه.
راه راحت تر:
استفاده از مثلت استرلینگ. چون مهره‌ها متفاوت و ظروف مشابه هستن. یعنی جمع اعضای سطر پنجم که داریم:
[tex]S=S_{5,1} S_{5,2} S_{5,3} S_{5,4} S_{5,5}=1 15 25 10 1=52[/tex]
توی حالت قبل هم همین استرلینگ رو شمردیم. فقط باید حالاتی رو که تعداد مجموعه هامون برابرن رو با هم جمع کنیم.