Xirius-PrincipleofInclusionExclusionPIE6-COS203.pdf
Xirius AI
This document, titled "Xirius-PrincipleofInclusionExclusionPIE6-COS203.pdf," is a comprehensive educational resource for the COS203 course, focusing on the Principle of Inclusion-Exclusion (PIE). It serves as a fundamental guide to a powerful combinatorial counting technique used to determine the size of the union of multiple sets, especially when these sets have overlapping elements. The "PIE6" in the filename likely indicates that this is the sixth module or lecture dedicated to this principle, suggesting a detailed and possibly advanced treatment of the topic within the course curriculum.
The document systematically introduces PIE, starting with its basic application for two and three sets, then generalizing it to an arbitrary number of sets. It emphasizes the core idea of correcting for overcounting by alternately adding and subtracting the sizes of intersections. Beyond the theoretical framework, the document delves into significant applications of PIE, such as calculating the number of derangements (permutations where no element remains in its original position) and counting the number of surjective functions between two finite sets. It also explores its utility in number theory problems, like determining the count of integers within a range that satisfy specific divisibility criteria. Through clear explanations, formulas, and illustrative examples, the document aims to equip students with a robust understanding and practical skills in applying this essential combinatorial principle.
MAIN TOPICS AND CONCEPTS
The document begins by introducing the most basic form of the Principle of Inclusion-Exclusion (PIE), which addresses the problem of counting elements in the union of two sets that may have common elements. When simply adding the sizes of two sets, elements present in both sets are counted twice. PIE corrects this by subtracting the size of their intersection.
* Detailed explanation with key points:
* When counting the total number of elements in two sets, $A$ and $B$, if we simply sum $|A|$ and $|B|$, any elements that belong to both $A$ and $B$ (i.e., elements in their intersection $A \cap B$) will be counted twice.
* To get the correct count for the union $A \cup B$, we must subtract the count of the intersection once to compensate for the double-counting.
* Important formulas/equations in LaTeX:
$$ |A \cup B| = |A| + |B| - |A \cap B| $$
* Examples if applicable:
* Example: In a class of 30 students, 18 students take Mathematics, 15 students take Physics, and 7 students take both Mathematics and Physics. How many students take at least one of these subjects?
* Let $M$ be the set of students taking Mathematics, and $P$ be the set of students taking Physics.
* $|M| = 18$, $|P| = 15$, $|M \cap P| = 7$.
* Using PIE: $|M \cup P| = |M| + |P| - |M \cap P| = 18 + 15 - 7 = 33 - 7 = 26$.
* So, 26 students take at least one of the subjects.
The Principle of Inclusion-Exclusion for Three SetsBuilding upon the two-set case, the document extends PIE to three sets, $A$, $B$, and $C$. This scenario introduces more complex overlaps, requiring a more elaborate correction mechanism.
* Detailed explanation with key points:
* When summing $|A| + |B| + |C|$, elements in pairwise intersections ($A \cap B$, $A \cap C$, $B \cap C$) are counted twice, and elements in the triple intersection ($A \cap B \cap C$) are counted three times.
* Subtracting the pairwise intersections corrects for elements counted twice, but it also inadvertently removes the triple intersection elements too many times (they were counted 3 times, then subtracted 3 times, resulting in 0 counts).
* Therefore, the size of the triple intersection must be added back to ensure elements common to all three sets are counted exactly once.
* Important formulas/equations in LaTeX:
$$ |A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C| $$
* Examples if applicable:
* Example: Out of 100 students, 50 take Math, 40 take Physics, 30 take Chemistry. 15 take Math and Physics, 10 take Math and Chemistry, 12 take Physics and Chemistry. 5 students take all three subjects. How many students take at least one subject?
* Let $M, P, C$ be the sets for Math, Physics, and Chemistry respectively.
* $|M|=50, |P|=40, |C|=30$.
* $|M \cap P|=15, |M \cap C|=10, |P \cap C|=12$.
* $|M \cap P \cap C|=5$.
* Using PIE:
$|M \cup P \cup C| = (50+40+30) - (15+10+12) + 5$
$= 120 - 37 + 5 = 88$.
* So, 88 students take at least one of the subjects.
General Principle of Inclusion-Exclusion (for $n$ Sets)The document then generalizes PIE to any finite number of sets, $A_1, A_2, \dots, A_n$. This general form is crucial for solving more complex combinatorial problems.
* Detailed explanation with key points:
* The general principle follows an alternating sum pattern:
1. Sum the sizes of all individual sets.
2. Subtract the sum of the sizes of all possible pairwise intersections.
3. Add the sum of the sizes of all possible triple intersections.
4. Continue this process, alternating between subtraction and addition, until the intersection of all $n$ sets is considered.
* The sign for each term depends on the number of sets in the intersection: positive for an odd number of sets, negative for an even number of sets.
* Important formulas/equations in LaTeX:
The number of elements in the union of $n$ sets $A_1, A_2, \dots, A_n$ is given by:
$$ \left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n |A_i| - \sum_{1 \le i < j \le n} |A_i \cap A_j| + \sum_{1 \le i < j < k \le n} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} |A_1 \cap A_2 \cap \dots \cap A_n| $$
This can be written more compactly as:
$$ \left| \bigcup_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \le i_1 < i_2 < \dots < i_k \le n} |A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k}| $$
An alternative and often more useful form of PIE is to count the number of elements in a universal set $S$ that have none of $n$ properties $P_1, P_2, \dots, P_n$. Let $A_i$ be the set of elements having property $P_i$. Then the number of elements having none of the properties is:
$$ \left| S \setminus \bigcup_{i=1}^n A_i \right| = |S| - \left| \bigcup_{i=1}^n A_i \right| $$
Substituting the general PIE formula for the union:
$$ \left| S \setminus \bigcup_{i=1}^n A_i \right| = |S| - \sum_{i} |A_i| + \sum_{i<j} |A_i \cap A_j| - \sum_{i<j<k} |A_i \cap A_j \cap A_k| + \dots + (-1)^n |A_1 \cap A_2 \cap \dots \cap A_n| $$
This is often denoted as $N(\overline{P_1}\overline{P_2}...\overline{P_n}) = N - \sum N(P_i) + \sum N(P_i P_j) - \dots + (-1)^n N(P_1 P_2 \dots P_n)$, where $N$ is the total number of elements, $N(P_i)$ is the number of elements with property $P_i$, $N(P_i P_j)$ is the number of elements with properties $P_i$ and $P_j$, and so on.
Applications of PIE: DerangementsA classic application of the Principle of Inclusion-Exclusion is to count derangements.
* Detailed explanation with key points:
* A derangement is a permutation of the elements of a set such that no element appears in its original position. For example, if we have letters $L_1, L_2, L_3$ and envelopes $E_1, E_2, E_3$, a derangement would be placing $L_1$ in $E_2$, $L_2$ in $E_3$, and $L_3$ in $E_1$.
* To calculate $D_n$, the number of derangements of $n$ objects, we consider the total number of permutations ($n!$) and subtract permutations where at least one element is in its original position.
* We define property $P_i$ as "the $i$-th element is in its original position." We want to count permutations where none of these properties hold.
* Important formulas/equations in LaTeX:
The number of derangements of $n$ objects, denoted $D_n$ or $!n$, is given by:
$$ D_n = n! \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right) $$
This formula can be approximated by $n!/e$ for large $n$.
A recurrence relation for derangements is:
$$ D_n = (n-1)(D_{n-1} + D_{n-2}) \quad \text{for } n \ge 2 $$
with base cases $D_0 = 1$ (empty set has one derangement, the empty permutation) and $D_1 = 0$.
* Examples if applicable:
* Example: Four friends (A, B, C, D) exchange gifts. In how many ways can the gifts be distributed so that no one receives their own gift?
* This is a derangement problem for $n=4$.
* $D_4 = 4! \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} \right)$
* $D_4 = 24 \left( 1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} \right)$
* $D_4 = 24 \left( \frac{12}{24} - \frac{4}{24} + \frac{1}{24} \right) = 24 \left( \frac{9}{24} \right) = 9$.
* There are 9 ways for the gifts to be deranged.
Applications of PIE: Counting Surjective FunctionsAnother significant application of PIE is in counting the number of surjective functions (surjections) between two finite sets.
* Detailed explanation with key points:
* A function $f: A \to B$ is surjective if every element in the codomain $B$ has at least one pre-image in the domain $A$. In simpler terms, every element in $B$ is "hit" by at least one element from $A$.
* Let $|A|=m$ and $|B|=n$. The total number of functions from $A$ to $B$ is $n^m$.
To find the number of surjections, we use PIE by considering the complement: functions that are not* surjective. A function is not surjective if at least one element in the codomain $B$ is not mapped to. Let $P_i$ be the property that the $i$-th element of $B$ is not* in the image of the function. We want to count functions where none of these properties hold.* Important formulas/equations in LaTeX:
The number of surjective functions from a set of size $m$ to a set of size $n$, denoted $S(m, n)$ or $n! S(m, n)$ where $S(m,n)$ is a Stirling number of the second kind, is given by:
$$ S(m, n) = \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k)^m $$
* Examples if applicable:
* Example: How many ways are there to distribute 5 distinct balls into 3 distinct bins such that no bin is empty? (This is equivalent to counting surjections from a set of 5 balls to a set of 3 bins).
* Here, $m=5$ (balls) and $n=3$ (bins).
* $S(5, 3) = \sum_{k=0}^3 (-1)^k \binom{3}{k} (3-k)^5$
* $S(5, 3) = (-1)^0 \binom{3}{0} (3-0)^5 + (-1)^1 \binom{3}{1} (3-1)^5 + (-1)^2 \binom{3}{2} (3-2)^5 + (-1)^3 \binom{3}{3} (3-3)^5$
* $S(5, 3) = (1)(1)(3^5) - (1)(3)(2^5) + (1)(3)(1^5) - (1)(1)(0^5)$
* $S(5, 3) = 243 - 3 \cdot 32 + 3 \cdot 1 - 0$
* $S(5, 3) = 243 - 96 + 3 = 150$.
* There are 150 ways to distribute the balls such that no bin is empty.
Applications of PIE: Counting Integers with Specific PropertiesPIE is also highly effective in number theory problems, particularly for counting integers within a given range that satisfy or do not satisfy certain divisibility conditions.
* Detailed explanation with key points:
* The problem typically involves finding the number of integers up to $N$ that are not divisible by any of a given set of prime numbers (or composite numbers).
* We define properties $P_i$ as "being divisible by $p_i$" (where $p_i$ are the given divisors). We then use the complementary form of PIE to count integers that have none of these properties.
* The number of integers up to $N$ divisible by $d$ is $\lfloor N/d \rfloor$.
* Examples if applicable:
* Example: How many integers from 1 to 100 are not divisible by 2, 3, or 5?
* Let $S = \{1, 2, \dots, 100\}$, so $|S|=100$.
* Let $A_2$ be the set of integers in $S$ divisible by 2.
* Let $A_3$ be the set of integers in $S$ divisible by 3.
* Let $A_5$ be the set of integers in $S$ divisible by 5.
* We want to find $|S| - |A_2 \cup A_3 \cup A_5|$.
* $|A_2| = \lfloor 100/2 \rfloor = 50$
* $|A_3| = \lfloor 100/3 \rfloor = 33$
* $|A_5| = \lfloor 100/5 \rfloor = 20$
* $|A_2 \cap A_3| = \lfloor 100/(2 \cdot 3) \rfloor = \lfloor 100/6 \rfloor = 16$
* $|A_2 \cap A_5| = \lfloor 100/(2 \cdot 5) \rfloor = \lfloor 100/10 \rfloor = 10$
* $|A_3 \cap A_5| = \lfloor 100/(3 \cdot 5) \rfloor = \lfloor 100/15 \rfloor = 6$
* $|A_2 \cap A_3 \cap A_5| = \lfloor 100/(2 \cdot 3 \cdot 5) \rfloor = \lfloor 100/30 \rfloor = 3$
* Using PIE for the union:
$|A_2 \cup A_3 \cup A_5| = (50+33+20) - (16+10+6) + 3 = 103 - 32 + 3 = 74$.
* The number of integers not divisible by 2, 3, or 5 is $|S| - |A_2 \cup A_3 \cup A_5| = 100 - 74 = 26$.
KEY DEFINITIONS AND TERMS
* Principle of Inclusion-Exclusion (PIE): A fundamental combinatorial counting technique used to determine the size of the union of multiple finite sets. It works by systematically adding the sizes of individual sets, then subtracting the sizes of all pairwise intersections, adding back the sizes of all triple intersections, and so on, to correct for elements that have been overcounted or undercounted in previous steps. Its core idea is to ensure each element in the union is counted exactly once.
* Derangement: A permutation of the elements of a set such that no element remains in its original position. For a set of $n$ distinct objects, a derangement is an arrangement where none of the objects are in their "correct" or initial place. The number of derangements of $n$ objects is denoted by $D_n$ or $!n$.
* Surjective Function (Surjection): A function $f: A \to B$ (from domain $A$ to codomain $B$) is surjective if for every element $y$ in the codomain $B$, there exists at least one element $x$ in the domain $A$ such that $f(x) = y$. In simpler terms, every element in the codomain is "hit" or "reached" by at least one element from the domain. It is also referred to as an "onto" function.
* Set Union ($\cup$): The union of two or more sets is a new set containing all the distinct elements that are present in at least one of the original sets. For sets $A$ and $B$, $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$.
* Set Intersection ($\cap$): The intersection of two or more sets is a new set containing only the elements that are common to all of the original sets. For sets $A$ and $B$, $A \cap B = \{x \mid x \in A \text{ and } x \in B\}$.
Universal Set ($S$): In the context of PIE, the universal set refers to the overarching set of all possible elements under consideration for a particular problem. Properties are defined for elements within this universal set, and PIE is often used to count elements in $S$ that do not* possess any of a given set of properties.IMPORTANT EXAMPLES AND APPLICATIONS
- Example 1: Students and Subjects (Basic PIE)
* Problem: In a group of 50 students, 30 like football, 25 like basketball, and 10 like both. How many students like at least one of the two sports?
* Explanation: Let $F$ be the set of students who like football and $B$ be the set of students who like basketball. We are given $|F|=30$, $|B|=25$, and $|F \cap B|=10$. We need to find $|F \cup B|$.
* Application of PIE: Using the formula for two sets, $|F \cup B| = |F| + |B| - |F \cap B|$.
* Solution: $|F \cup B| = 30 + 25 - 10 = 55 - 10 = 45$.
* Result: 45 students like at least one of the two sports.
- Example 2: Misplaced Letters (