The Inclusion-Exclusion Principle is a powerful tool for counting elements in multiple sets. It helps us avoid double-counting overlapping elements by alternating between adding and subtracting set sizes and their intersections.

This principle is crucial in combinatorics, allowing us to solve complex counting problems involving overlapping categories. It's especially useful for finding the number of elements in unions of sets and counting surjective functions.

Inclusion-Exclusion Principle

Concept and Formula

• The Inclusion-Exclusion Principle determines the number of elements in the union of multiple sets by accounting for overlaps between the sets
• Starts by adding the sizes of individual sets, then subtracts the sizes of all pairwise intersections, adds back the sizes of all triple intersections, and continues alternating between addition and subtraction
• The general formula for n sets A₁, A₂, ..., Aₙ is:

$|A₁ ∪ A₂ ∪ ... ∪ Aₙ| = ∑|Aᵢ| - ∑|Aᵢ ∩ Aⱼ| + ∑|Aᵢ ∩ Aⱼ ∩ Aₖ| - ... + (-1)ⁿ⁺¹|A₁ ∩ A₂ ∩ ... ∩ Aₙ|$

where ∑ denotes the sum over all distinct combinations of indices

Principle Basis and Overlaps

• Based on the idea that when counting elements in the union of sets, elements in the overlaps are counted multiple times
• Alternating between addition and subtraction accounts for the multiple counting of elements in overlaps
• Example: In a group of students, some play football (set A), some play basketball (set B), and some play both sports (overlap A ∩ B). To find the total number of students who play either sport, add |A| and |B|, then subtract |A ∩ B| to avoid double-counting students in the overlap
• Example: Three sets A (numbers divisible by 2), B (numbers divisible by 3), and C (numbers divisible by 5) in the range 1-30. To find the number of elements in A ∪ B ∪ C, use the Inclusion-Exclusion Principle to account for overlaps (numbers divisible by 6, 10, 15, and 30)

Applying the Inclusion-Exclusion Principle

Problem-Solving Steps

• Identify the sets involved in the problem and determine their sizes, as well as the sizes of their intersections
• Write out the Inclusion-Exclusion formula for the given number of sets, expanding the summations to include all relevant terms
• Substitute the sizes of the sets and their intersections into the formula, simplifying the expression as needed
• Evaluate the resulting expression to obtain the number of elements in the union of the sets
• Example: In a class of 30 students, 12 study Math, 15 study Science, and 8 study both. To find the number of students studying either Math or Science, use |Math ∪ Science| = |Math| + |Science| - |Math ∩ Science| = 12 + 15 - 8 = 19 students

Complement Sets

• When dealing with complement sets, use the Inclusion-Exclusion Principle to find the size of the union of the complement sets
• Subtract the size of the union of complement sets from the size of the universal set to obtain the desired result
• Example: In a group of 50 people, 28 speak English, 30 speak Spanish, and 20 speak both. To find the number of people who speak neither language, first find |(English ∪ Spanish)'| = 50 - (28 + 30 - 20) = 12. So, 12 people speak neither English nor Spanish

Union of Multiple Sets

Two and Three Sets

• For two sets A and B, the number of elements in their union is given by |A ∪ B| = |A| + |B| - |A ∩ B|, where |A ∩ B| represents the size of the intersection of A and B
• For three sets A, B, and C, the number of elements in their union is given by |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
• Example: In a survey of 100 people, 28 like apples, 30 like bananas, 25 like oranges, 12 like apples and bananas, 10 like apples and oranges, 14 like bananas and oranges, and 5 like all three fruits. To find the number of people who like at least one of the fruits, use the Inclusion-Exclusion Principle for three sets

Generalization to n Sets

• Generalize the Inclusion-Exclusion Principle to n sets using the formula mentioned in the first learning objective, expanding the summations and alternating between addition and subtraction of intersection terms
• When dealing with problems involving multiple sets, organize the information about set sizes and intersection sizes in a clear manner to facilitate the application of the Inclusion-Exclusion Principle
• Example: In a group of 200 students, 120 study Math, 100 study Science, 80 study History, 60 study Math and Science, 50 study Math and History, 40 study Science and History, and 30 study all three subjects. To find the number of students studying at least one of the subjects, use the Inclusion-Exclusion Principle for n sets (n = 3 in this case)

Surjective Functions and the Inclusion-Exclusion Principle

Surjective Functions

• A surjective function, also called an onto function, is a function f: A → B such that for every element b in the codomain B, there exists at least one element a in the domain A with f(a) = b
• To count the number of surjective functions from a set A with n elements to a set B with m elements (n ≥ m), use the Inclusion-Exclusion Principle
• Example: Determine the number of surjective functions from a set A = {1, 2, 3, 4} to a set B = {a, b, c}

Applying the Inclusion-Exclusion Principle

• Define sets Aᵢ as the set of functions where element i in the codomain B is not mapped to by any element in the domain A. The number of surjective functions is then the complement of the union of all Aᵢ sets
• Apply the Inclusion-Exclusion Principle to find the size of the union of the Aᵢ sets, using the formula:

$|A₁ ∪ A₂ ∪ ... ∪ Aₘ| = ∑|Aᵢ| - ∑|Aᵢ ∩ Aⱼ| + ∑|Aᵢ ∩ Aⱼ ∩ Aₖ| - ... + (-1)ᵐ|A₁ ∩ A₂ ∩ ... ∩ Aₘ|$

• The size of each Aᵢ is (m-1)ⁿ, as there are m-1 choices for each element in the domain
• The size of the intersection of k sets Aᵢ is (m-k)ⁿ, as there are m-k choices for each element in the domain
• Subtract the size of the union of the Aᵢ sets from the total number of functions mⁿ to obtain the number of surjective functions
• Example: For the sets A and B mentioned earlier, the number of surjective functions is 3⁴ - (3C1 × 2⁴ - 3C2 × 1⁴ + 3C3 × 0⁴) = 36