05 اسفند 1395, 04:54 ب.ظ
06 اسفند 1395, 05:13 ب.ظ
سلام
در واقع سوال مجموع تعداد اعضایی اشتراک دوبه دوی زیر مجموعه های N را می خواهد (حتی اشتراک هر زیرمجموعه با خودش)
مثلا اشتراک بزرگترین زیر مجموعه با تمام زیر مجموعه ها را به صورت زیر بدست می اوریم
با خودش n عدد اشتراک دارد
با زیر مجموعه های n-1 عضوی n-1 تا عدد اشتراک دارد که تعداد این زیر مجموعه ها [tex]\binom{n}{n-1}[/tex]
.
.
با زیر مجموعه های ۱ عضوی هم یک عدد اشتراک دارد که تعداد این زیر مجموعه ها هم [tex]\binom{n}{1}[/tex]
پس جمع اشتراک بزرگترین زیرمجموعه با تمام مجموعه ها برابر با
[tex]n+(n-1)\binom{n}{n-1}+(n-2)\binom{n}{n-2}+....+2\binom{n}{2}+\binom{n}{1}=n2^{n-1}\: [/tex] به کمک [tex]\sum_{k=1}^nk\binom{n}{k}=n2^{n-1}[/tex] وبرای زیرمجموعه های دیگربه این صورت عمل میکنم مثلا به جای اینکه مجموع اشتراک تک زیر مجموعه های n-1 عضوی با تمام زیرمجموعه ها را بیابم تمام زیرمجموعه های n-1 تایی را باهم اجتماع ولی تکرار را حذف نمی کنیم(می دونم تعریف مجموعه را نقض میکند ولی می تونیم مثلا از زیرین استفاده کنیم) بعد اشتراک این مجموعه زیرین دار را با تمام زیرمجموعه های دیگر بدست اوریم که روالی مثل قبل که برای بزرگترین زیرمجموعه حل کردیم داره ولی زیرین تکرار را باید در تمامی جملات ضرب کنیم مثلا برای مجموع اشتراک زیرمجموعه های n-1 عضوی با همه زیرین تکرار هر عدد در مجموعه زیرین برابر با [tex]\binom{n-1}{n-2}[/tex],و مجموع اشتراک های ان برابر با [tex]\binom{n-1}{n-2}n2^{n-1}[/tex] و به همین ترتیب برای همه ی زیرمجموعه ها محاسبه می کین پس مجموع کل برابر با
[tex]\binom{n-1}{0^{ }}n2^{n-1}+\binom{n-1}{1}n2^{n-1}+....+\binom{n-1}{n-2}n2^{n-1}+\binom{n-1}{n-1}n2^{n-1}=n2^{2(n-1)}[/tex] یه نوع قرینگی هم وجود داره
حال مسئله را بازای n=5 حل می کنیم [tex]5\ast2^{2\ast4}=5\ast256=1280[/tex]
در واقع سوال مجموع تعداد اعضایی اشتراک دوبه دوی زیر مجموعه های N را می خواهد (حتی اشتراک هر زیرمجموعه با خودش)
مثلا اشتراک بزرگترین زیر مجموعه با تمام زیر مجموعه ها را به صورت زیر بدست می اوریم
با خودش n عدد اشتراک دارد
با زیر مجموعه های n-1 عضوی n-1 تا عدد اشتراک دارد که تعداد این زیر مجموعه ها [tex]\binom{n}{n-1}[/tex]
.
.
با زیر مجموعه های ۱ عضوی هم یک عدد اشتراک دارد که تعداد این زیر مجموعه ها هم [tex]\binom{n}{1}[/tex]
پس جمع اشتراک بزرگترین زیرمجموعه با تمام مجموعه ها برابر با
[tex]n+(n-1)\binom{n}{n-1}+(n-2)\binom{n}{n-2}+....+2\binom{n}{2}+\binom{n}{1}=n2^{n-1}\: [/tex] به کمک [tex]\sum_{k=1}^nk\binom{n}{k}=n2^{n-1}[/tex] وبرای زیرمجموعه های دیگربه این صورت عمل میکنم مثلا به جای اینکه مجموع اشتراک تک زیر مجموعه های n-1 عضوی با تمام زیرمجموعه ها را بیابم تمام زیرمجموعه های n-1 تایی را باهم اجتماع ولی تکرار را حذف نمی کنیم(می دونم تعریف مجموعه را نقض میکند ولی می تونیم مثلا از زیرین استفاده کنیم) بعد اشتراک این مجموعه زیرین دار را با تمام زیرمجموعه های دیگر بدست اوریم که روالی مثل قبل که برای بزرگترین زیرمجموعه حل کردیم داره ولی زیرین تکرار را باید در تمامی جملات ضرب کنیم مثلا برای مجموع اشتراک زیرمجموعه های n-1 عضوی با همه زیرین تکرار هر عدد در مجموعه زیرین برابر با [tex]\binom{n-1}{n-2}[/tex],و مجموع اشتراک های ان برابر با [tex]\binom{n-1}{n-2}n2^{n-1}[/tex] و به همین ترتیب برای همه ی زیرمجموعه ها محاسبه می کین پس مجموع کل برابر با
[tex]\binom{n-1}{0^{ }}n2^{n-1}+\binom{n-1}{1}n2^{n-1}+....+\binom{n-1}{n-2}n2^{n-1}+\binom{n-1}{n-1}n2^{n-1}=n2^{2(n-1)}[/tex] یه نوع قرینگی هم وجود داره
حال مسئله را بازای n=5 حل می کنیم [tex]5\ast2^{2\ast4}=5\ast256=1280[/tex]
15 اسفند 1395, 03:28 ب.ظ
سلام. وقت بخیر.
عدد k زمانی توی اون جمع محاسبه میشه که توی A و B باشه. تعداد دوتایی هایی که k توی (A,B) هست رو حساب میکنیم و در k به ازای k از ۱ تا ۵ ضرب میکنیم. با این کار جواب محاسبه میشه. تعداد A و B هایی که k توی اونها هست برابره با تعداد حالات قرار گرفتن بقیه ۵ عدد غیر از k توی این مجموعه ها. هر عدد ۴ حالت داره. (تو هیچکدوم نباشه، فقط تو A باشه، فقط تو B باشه و توی هردو باشه) پس تعداد حالات قرار گرفتن k توی دو مجموعه A و B میشه [tex]4^4=256[/tex]. جواب مساله میشه:
[tex]256\times (1+2+3+4+5)=256\times 15=1280[/tex]
عدد k زمانی توی اون جمع محاسبه میشه که توی A و B باشه. تعداد دوتایی هایی که k توی (A,B) هست رو حساب میکنیم و در k به ازای k از ۱ تا ۵ ضرب میکنیم. با این کار جواب محاسبه میشه. تعداد A و B هایی که k توی اونها هست برابره با تعداد حالات قرار گرفتن بقیه ۵ عدد غیر از k توی این مجموعه ها. هر عدد ۴ حالت داره. (تو هیچکدوم نباشه، فقط تو A باشه، فقط تو B باشه و توی هردو باشه) پس تعداد حالات قرار گرفتن k توی دو مجموعه A و B میشه [tex]4^4=256[/tex]. جواب مساله میشه:
[tex]256\times (1+2+3+4+5)=256\times 15=1280[/tex]