Dinheiro said:
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.
