۰
subtitle
سلام
در واقع سوال مجموع تعداد اعضایی اشتراک دوبه دوی زیر مجموعه های N را می خواهد (حتی اشتراک هر زیرمجموعه با خودش)
مثلا اشتراک بزرگترین زیر مجموعه با تمام زیر مجموعه ها را به صورت زیر بدست می اوریم
با خودش n عدد اشتراک دارد
با زیر مجموعه های n-1 عضوی n-1 تا عدد اشتراک دارد که تعداد این زیر مجموعه ها (nn−1)
.
.
با زیر مجموعه های ۱ عضوی هم یک عدد اشتراک دارد که تعداد این زیر مجموعه ها هم (n1)
پس جمع اشتراک بزرگترین زیرمجموعه با تمام مجموعه ها برابر با
n+(n−1)(nn−1)+(n−2)(nn−2)+....+2(n2)+(n1)=n2n−1 به کمک ∑nk=1k(nk)=n2n−1 وبرای زیرمجموعه های دیگربه این صورت عمل میکنم مثلا به جای اینکه مجموع اشتراک تک زیر مجموعه های n-1 عضوی با تمام زیرمجموعه ها را بیابم تمام زیرمجموعه های n-1 تایی را باهم اجتماع ولی تکرار را حذف نمی کنیم(می دونم تعریف مجموعه را نقض میکند ولی می تونیم مثلا از زیرین استفاده کنیم) بعد اشتراک این مجموعه زیرین دار را با تمام زیرمجموعه های دیگر بدست اوریم که روالی مثل قبل که برای بزرگترین زیرمجموعه حل کردیم داره ولی زیرین تکرار را باید در تمامی جملات ضرب کنیم مثلا برای مجموع اشتراک زیرمجموعه های n-1 عضوی با همه زیرین تکرار هر عدد در مجموعه زیرین برابر با (n−1n−2),و مجموع اشتراک های ان برابر با (n−1n−2)n2n−1 و به همین ترتیب برای همه ی زیرمجموعه ها محاسبه می کین پس مجموع کل برابر با
(n−10)n2n−1+(n−11)n2n−1+....+(n−1n−2)n2n−1+(n−1n−1)n2n−1=n22(n−1) یه نوع قرینگی هم وجود داره
حال مسئله را بازای n=5 حل می کنیم 5∗22∗4=5∗256=1280
در واقع سوال مجموع تعداد اعضایی اشتراک دوبه دوی زیر مجموعه های N را می خواهد (حتی اشتراک هر زیرمجموعه با خودش)
مثلا اشتراک بزرگترین زیر مجموعه با تمام زیر مجموعه ها را به صورت زیر بدست می اوریم
با خودش n عدد اشتراک دارد
با زیر مجموعه های n-1 عضوی n-1 تا عدد اشتراک دارد که تعداد این زیر مجموعه ها (nn−1)
.
.
با زیر مجموعه های ۱ عضوی هم یک عدد اشتراک دارد که تعداد این زیر مجموعه ها هم (n1)
پس جمع اشتراک بزرگترین زیرمجموعه با تمام مجموعه ها برابر با
n+(n−1)(nn−1)+(n−2)(nn−2)+....+2(n2)+(n1)=n2n−1 به کمک ∑nk=1k(nk)=n2n−1 وبرای زیرمجموعه های دیگربه این صورت عمل میکنم مثلا به جای اینکه مجموع اشتراک تک زیر مجموعه های n-1 عضوی با تمام زیرمجموعه ها را بیابم تمام زیرمجموعه های n-1 تایی را باهم اجتماع ولی تکرار را حذف نمی کنیم(می دونم تعریف مجموعه را نقض میکند ولی می تونیم مثلا از زیرین استفاده کنیم) بعد اشتراک این مجموعه زیرین دار را با تمام زیرمجموعه های دیگر بدست اوریم که روالی مثل قبل که برای بزرگترین زیرمجموعه حل کردیم داره ولی زیرین تکرار را باید در تمامی جملات ضرب کنیم مثلا برای مجموع اشتراک زیرمجموعه های n-1 عضوی با همه زیرین تکرار هر عدد در مجموعه زیرین برابر با (n−1n−2),و مجموع اشتراک های ان برابر با (n−1n−2)n2n−1 و به همین ترتیب برای همه ی زیرمجموعه ها محاسبه می کین پس مجموع کل برابر با
(n−10)n2n−1+(n−11)n2n−1+....+(n−1n−2)n2n−1+(n−1n−1)n2n−1=n22(n−1) یه نوع قرینگی هم وجود داره
حال مسئله را بازای n=5 حل می کنیم 5∗22∗4=5∗256=1280