ABSTRACT
This chapter studies combinatorial techniques that are related to the arithmetic operation of subtraction: involutions, inclusion-exclusion formulas, and Mo¨bius inversion. Involutions allow us to give bijective proofs of identities involving both positive and negative terms. The inclusion-exclusion formula extends the sum rule 1.2 to a rule for computing |A1∪A2∪ · · · ∪ Am| in the case where the sets Ai need not be pairwise disjoint. This formula turns out to be a special case of the general Mo¨bius inversion formula for posets, which has many applications in number theory and algebra as well as combinatorics.
