ABSTRACT
The basic principles of counting the elements of a union of n nite and
pairwise disjoint sets (principle of addition) and of a subset of the Carte-
sian product of n nite sets (multiplication principle) were presented in
Chapter 1. The principle of inclusion and exclusion, or the sieve formula of
Eratosthenes, is also a powerful counting tool and this chapter is devoted
to its presentation. The number of elements in a union (and in the inter-
section of the complements) of any n subsets of a nite set is computed.
More generally, the numbers of elements that are contained in k and in at
least k among n subsets of a nite set are evaluated. Further, a series of
alternating inequalities for these numbers, due to Bonferroni, is derived. In
the case of ordered subsets of a set, the notion of the rank of an element is
introduced. Then, the elements of this set of a given rank are enumerated.
The important case of exchangeable sets, in which the number of elements
that are contained in the intersection of any r of them depends only on
r, is separately examined in all the preceding enumeration problems. The
Mobius inversion formula, which is also a useful counting tool, is presented
as a complement in the Exercises.
