Но к доказательству формулы вкл\искл я так и не приблизился
Там, если делать в лоб, надо для каждого
написать перебор
вариантов. Чтобы не писать бесконечно много текста, используют какие-то общие рассуждения. Можете прочитать доказательство в какой-нибудь книжке, типа Дж. Андерсон, Дискретная математика и комбинаторика, теорема 12.7. Разумеется, там возникают какие-то суммы с биномиальными коэффициентами, их надо уметь считать. Вам вообще стоило бы прочитать побольше всяких теорем с доказательствами из дискретной математики (и порешать задач!), опыта набраться.
А вообще,можно было принять на веру эту формулу,ведь ее кто-то открыл и доказал
А потом ее доказывали еще очень много-много раз
Это я зачем-то полез в доказательства,хотя она уже доказана да и не один раз
-- 28.08.2024, 17:16 --Но к доказательству формулы вкл\искл я так и не приблизился
Но и ладно
Может так: посчитав сумму мощностей объединяемых множеств, все области с
чисто двойным пересечением учли дважды. Поэтому, вычитаем мощности
всевозможных двойных пересечений, но вместе с этим выкинули мощности
чисто тройных пересечений, так как
, поэтому добавляем мощности
всевозможных тройных пересечений. Теперь у нас чисто единичные
, чисто двойные и чисто тройные учтены правильно. А что с
чисто четвертыми? Так как
, оказывается, они учтены дважды. Чтобы справедливость восторжествовала, выкидываем
всевозможные четверные, теперь с чисто четверными полный порядок! Но не накосячили ли мы с чисто пятерными (это хорошо если их нет, а вдруг есть). Проверяем
, накосячили, они не учтены в мощности объединения! Ворочаем их назад добавлением мощностей
всевозможных пятерых пересечений. И т.д.
Это сочетания без повторений?
И как в таком случае доказать для n множеств?