Inclusion-Exclusion Principle & Advanced Counting Techniques

1. Floor and Ceiling Functions

1.1 Definitions

• Floor function $\lfloor x\rfloor$: Largest integer ≤ $x$. Example: $\lfloor 3.7\rfloor =3$, $\lfloor -1.2\rfloor =-2$.
• Ceiling function $\lceil x\rceil$: Smallest integer ≥ $x$. Example: $\lceil 3.2\rceil =4$, $\lceil -1.7\rceil =-1$.

1.2 When $\lfloor x\rfloor =\lceil x\rceil$

This equality holds only if $x$ is an integer. Proof:

• If $x\in \mathbb{Z}$, both functions return $x$.
• If $x\notin \mathbb{Z}$, $\lfloor x\rfloor <x<\lceil x\rceil$.

1.3 Applications

• Discrete mathematics: Used in counting lattice points, algorithm analysis (e.g., time complexity).
• Computer science: Rounding in programming (e.g., math.floor() in Python).

---

2. Pigeonhole Principle (PP)

2.1 Statement

If $n$ items are placed into $m$ containers, with $n>m$, then at least one container holds ≥ 2 items.

2.2 Generalized Pigeonhole Principle (GPP)

For $n$ items and $m$ containers, the minimum number of items in the most crowded container is: $$\lceil \frac{n}{m}\rceil$$ Example: Among 11 integers, at least $\lceil 11/10\rceil =2$ share the same last digit (PP).

2.3 Proof of GPP

Assume the opposite: all containers have ≤ $k$ items. Then total items ≤ $m\times k$. If $n>m\times k$, contradiction arises.

2.4 Applications

• Collisions in hashing: Guarantees hash collisions if load factor > 1.
• Graph theory: Proves existence of edges/vertices with shared properties.
• Number theory: Shows non-unique representations (e.g., modulo operations).

---

3. Inclusion-Exclusion Principle (IEP)

3.1 Statement for Two Sets

For finite sets $A$ and $B$: $$|A\cup B|=|A|+|B|-|A\cap B|$$ Example: Count integers from 1 to 30 divisible by 2 or 3.

• $|A|=\lfloor 30/2\rfloor =15$ (multiples of 2).
• $|B|=\lfloor 30/3\rfloor =10$ (multiples of 3).
• $|A\cap B|=\lfloor 30/6\rfloor =5$ (multiples of 6).
• Result: $15+10-5=20$.

3.2 Generalized IEP for $n$ Sets

For $n$ sets $A_1,A_2,\dots ,A_n$: $$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _i|A_i|-\sum _{i<j}|A_i\cap A_j|+\sum _{i<j<k}|A_i\cap A_j\cap A_k|-\cdots +(-1{)}^{n+1}\left|\bigcap _{i=1}^n{A}_i\right|$$ Example: Count numbers ≤ 30 divisible by 2, 3, or 5.

• $|A|=15$, $|B|=10$, $|C|=6$.
• $|A\cap B|=5$, $|A\cap C|=3$, $|B\cap C|=2$.
• $|A\cap B\cap C|=1$.
• Result: $15+10+6-5-3-2+1=22$.

3.3 Why Use IEP?

• Avoids overcounting: Correctly accounts for overlaps in unions.
• Efficiency: Simplifies complex counting problems (e.g., derangements, lattice points).

3.4 Comparison: IEP vs. PP

---

4. Advanced Counting Techniques

4.1 Counting with Restrictions

Example: Count 3-digit numbers where digits are distinct and even.

• Digits: 2, 4, 6, 8 (4 choices for hundreds).
• Tens: 3 remaining even digits.
• Units: 2 remaining digits.
• Total: $4\times 3\times 2=24$.

4.2 Recurrence Relations (Link to Unit 4)

IEP is used to solve recurrences via generating functions or characteristic equations. Example: Solve $a_n=5a_{n-1}-6a_{n-2}$ with $a_0=1$, $a_1=3$.

• Characteristic equation: $r^2-5r+6=0$ → $r=2,3$.
• Solution: $a_n=A\cdot 2^n+B\cdot 3^n$.
• Initial conditions:
  • $a_0=A+B=1$.
  • $a_1=2A+3B=3$.
• Result: $A=0$, $B=1$ → $a_n=3^n$.

---

5. Applications in Computer Science

5.1 Hashing and Collisions

• PP guarantees collisions in hash tables if $n>m$.
• IEP refines collision counts for multiple hash functions.

5.2 Graph Theory

• Edge counting: IEP counts paths/edges in overlapping subgraphs.
• Ramsey Theory: PP proves monochromatic subgraphs.

5.3 Probability

• IEP calculates probabilities of union events: $$P(A\cup B)=P(A)+P(B)-P(A\cap B)$$

---

Exam Tip

Common Pitfalls

1. Misapplying IEP: Forgetting to alternate signs or missing intersections.
   • Fix: Write the formula explicitly for $n$ sets.
2. PP overuse: Assuming PP applies when $n\le m$.
   • Fix: Verify $n>m$ before concluding.
3. Floor/Ceiling errors: Confusing $\lfloor x\rfloor$ and $\lceil x\rceil$.
   • Fix: Test with non-integer values (e.g., $x=1.5$).

High-Score Strategies

• For IEP problems:
  • Draw Venn diagrams for $n\le 3$.
  • Use symmetry to simplify intersections (e.g., $|A\cap B|=|A\cap C|$).
• For PP problems:
  • State the generalized form if $n$ is not a multiple of $m$.
  • Link to real-world examples (e.g., "In a room of 367 people, at least two share a birthday").
• For floor/ceiling:
  • Always check if $x$ is integer for equality cases.
  • Relate to programming (e.g., array indexing).

Past Exam Patterns

• Definition-based (5 marks): Expect questions on PP/IEP statements.
• Application-based (10 marks): Solve counting problems using IEP or PP.
• Proof-based (5 marks): Prove PP or derive IEP for $n=2$.

---

Key Formula Summary