- #1
Dinheiro
- 56
- 0
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
[itex] \sum_{k=0}^{n-p}(-1)^k\binom{p+k}{k}S_{p+k} [/itex]
in which
[itex]S_{0} = |\Omega| [/itex]
[itex]S_{1} = \sum_{i=1}^{n}|A_{i}| [/itex]
[itex]S_{2} = \sum_{1\leq i<j}^{n}|A_{i}\cap A_{j}| [/itex]
[itex]... [/itex]
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?
Last edited: