5. (A simple generalization of the principle of inclusion-exclusion)
Let A be a finite set, and s={P1,P2,⋯,Pm} be a finite set of m properties. Let Ai(1⩽i⩽m) be the subset of A consisting of all elements that have property Pi. Then the total number of elements in A that have exactly r properties, denoted by A(r), has the following formula (r⩾0): A(r)=(r1)∑1⩽i1<i2<⋯<ir⩽m∣Ai1∩Ai2∩⋯∩Air∣−(rr+1)∑1⩽j1<j2<⋯<jr+1⩽m∣Aj1∩Aj2∩⋯∩Ajr+1∣+−⋯+(−1)m−r(rm)∣A1∩A2∩⋯∩Am∣.
Solution
5. Proof: Let a be an element in A and a has exactly r properties among r properties. Then it is clear that it is counted exactly once on both the left and right sides of the given formula. If a is an element in A and a has fewer than r properties, then it is clear that it is not counted on either side of the formula. Finally, let a be an element in A that has t(t>r) properties among r properties, then it is counted in the sum \sum_{1 \leqslant i_{1}r+1)$.
For any $u, 0r\right) .
\end{aligned}
Note: In particular, when r=0, we obtain Theorem 1 of this chapter.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: NuminaMath-1.5,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.