Partially Ordered Sets
3.1 Basic Concepts
The theory of partially ordered sets (or posets) plays an important unifying role in enumerative combinatorics. In particular, the theory of Möbius inversion on a partially ordered set is a far-reaching generalization of the Principle of Inclusion-Exclusion, and the theory of binomial posets provides a unified setting for various classes of generating functions. These two topics will be among the highlights of this chapter, though many other interesting uses of partially ordered sets will also be given.
To get a glimpse of the potential scope of the theory of partially ordered sets as it relates to the Principle of Inclusion-Exclusion, consider the following example. Suppose we have four finite sets ...