Задача
COM-B2-M02-P017 Вклад одного объекта
#17
★★★★☆ Уровень 4 из 5
Докажите общую формулу включений-исключений, объяснив вклад одного объекта, который принадлежит ровно \(r\) из множеств \(A_1,\ldots,A_m\).
Его вклад равен \(\binom r1-\binom r2+\binom r3-\cdots\).
В формуле для \(|A_1\cup\cdots\cup A_m|\) объект, лежащий ровно в \(r\) множествах, учитывается \(\binom r1\) раз в одиночных суммах, \(\binom r2\) раз в попарных пересечениях, и так далее. Его общий вклад равен \(\binom r1-\binom r2+\cdots+(-1)^{r+1}\binom rr\). Это равно \(1-(1-1)^r=1\). Значит, каждый объект объединения учитывается ровно один раз.
Концептуальная задача, не вычислительная.