The inclusion-exclusion principle
The inclusion-exclusion principle. If a first task can be done in n ways
and a second task can be done in m ways, among which r ways are
usable for both tasks, then there are n+m-r ways to do either task.
The sum rule is a special case of this principle with r=0.
Example. The department should send, as a representative to a
university committee, either a faculty member (first task), or a student
There are 47 students and 13 faculty members, of which 2 are, at the
same time, students. How many ways are there to select a representative?
The inclusion-exclusion principle in terms of sets:
|A1?A2 | = |A1|+|A2|-|A1?A2|