Skip to main content

Chapter 7 Inclusion-Exclusion

In this chapter, we study an enumeration technique known as Inclusion-Exclusion. In its simplest case, it is absolutely intuitive. Its power rests in the fact that in many situations, we start with an exponentially large calculation and see it reduce to a manageable size. We focus on three applications that every student of combinatorics should know: (1) counting surjections, (2) derangements, and (3) the Euler \(\phi\)-function.