How to Use Counting Methods and Inclusion-Exclusion for Subsets?

[Dinheiro]

Homework Statement

Let Ω be the universe and A1, A2, A3, ..., An the subsets of Ω.
Prove that the number of elements of Ω that belongs to exactly p (p≤n) of the sets A1, A2, A3, ..., An is
\sum_{k=0}^{n-p}(-1)^k\binom{p+k}{k}S_{p+k}

in which
S_{0} = |\Omega|
S_{1} = \sum_{i=1}^{n}|A_{i}|
S_{2} = \sum_{1\leq i<j}^{n}|A_{i}\cap A_{j}|

...

And
|A| is the number of elements that belongs to A

Homework Equations

Counting methods and the principle of inclusion and exclusion

The Attempt at a Solution

The equation demanded to be proved is very useful for solving problems such as counting the numbers of integers between 0 and 1001 that are divisible by exactly two of the numbers 2, 3, 7 and 10. How should I demonstrate it?

 

[Ray Vickson]

Homework Statement

Let Ω be the universe and A1, A2, A3, ..., An the subsets of Ω.
Prove that the number of elements of Ω that belongs to exactly p (p≤n) of the sets A1, A2, A3, ..., An is
\sum_{k=0}^{n-p}(-1)^k\binom{p+k}{k}S_{p+k}

in which
S_{0} = |\Omega|
S_{1} = \sum_{i=1}^{n}|A_{i}|
S_{2} = \sum_{1\leq i<j}^{n}|A_{i}\cap A_{j}|

...

And
|A| is the number of elements that belongs to A

Homework Equations

Counting methods and the principle of inclusion and exclusion

The Attempt at a Solution

The equation demanded to be proved is very useful for solving problems such as counting the numbers of integers between 0 and 1001 that are divisible by exactly two of the numbers 2, 3, 7 and 10. How should I demonstrate it?

Do what Feller does in his Probability Theory Volume I, where he does something similar for probabilities. Just look at an element $w$ that is in exactly $p$ of the subsets $A_i$. Let
B_p = \{ x \in \Omega: x \text{ is in exactly}\:p\: \text{of the sets} \: A_i \}
and let $M_p = |B_p|.$

Pick any $w \in B_p$. How much does $w$ contribute to the right-hand-side?

For example, if $p=2$, $w$ appears in two of the $A_i$ so contributes 2 to $S_1$ (but this is irrelevant, since $S_1$ does not appear on the right-hand-side for $p \geq 2$). The element $w$ appears in just one doublet $A_i \cap A_j$, so contributes 1 to $S_2$. It does not contribute anything to $S_3, S_4, \ldots, S_n$. So, its contribution on the right-hand-side is
{2+0 \choose 0} 1 - {2+1 \choose 1} 0 + {2+2 \choose 2} 0 - \cdots + 0 = 1

However, we are not yet done. How much does $w$ contribute to $M_1$? Its contribution should be 0, since $w \not\in B_1$. Let's look at what its contribution would be on the right-hand-side. As already stated, its contribution is 2 to $S_1$ and 1 to $S_2$ (and 0 to $S_k, \:k \geq 3$). So, its contribution to $M_1$ would be
{1+0 \choose 0} 2 - {1+1 \choose 1} 1 + {1 + 2 \choose 2} 0 - \cdots + 0 = 2 - 2 = 0
This is as it should be.

Try the simpler case $p=1$, then try $p=3$. After than you might see how to handle the general case.

 

[Dinheiro]

Great, Ray! I didn't know about this book, though. Thanks