Principle of Inclusion and Exclusion

Understanding the Principle of Inclusion and Exclusion (PIE)

• The Principle of Inclusion and Exclusion provides a method to calculate the number of elements in a union of several sets.
• It is used when counting elements that are parts of multiple sets, with overlapping or repeating items.
• PIE corrects over-counting by alternating between adding and subtracting the counts of intersections between the sets.

Steps Involved in PIE

• Count the number of elements in each individual set.
• Subtract the number of elements common to every two sets (their intersection).
• Add back the number of elements common to every three sets.
• Continue alternating between adding and subtracting for intersections of higher numbers of sets until all intersections have been addressed.

Applying PIE

• PIE is applicable in problems involving more than two overlapping sets.
• In problems with three overlapping sets A, B, and C, the formula applies as:

  • A U B U C

    =

    A

    +

    B

    +

    C

    -

    A ∩ B

    -

    B ∩ C

    -

    C ∩ A

    +

    A ∩ B ∩ C

• The vertical bars represent cardinality, meaning “the number of elements in a set”.
• Each term within the vertical bars represents a count: the counts of individual sets; counts of intersections of two sets; and finally, the count of intersection of three sets.

Relation to Combinatorics

• PIE is a significant principle in combinatorics, a branch of mathematics concerned with counting and arranging objects.
• It provides a systemic method to handle the complexity of counting problems involving overlapping conditions.
• It is, in essence, an applied form of combining and arranging - fundamental to many mathematical, statistical, and scientific applications.