Lecture06_counting.pdf

Basic Concepts of Counting

<aside> 💡 Cardinality of a Set:

• The number of elements in a set is called its cardinality.
• It's denoted by vertical bars, $|S|$.
• E.g., if $S = {a, b, c}$, then $|S| = 3$. </aside>

Basic Rules

<aside> 💡 Cartesian Product:

• Denoted as $S_1\times S_2$
• Refers to all possible ordered pairs (i.e., 1st element from $S_1$, 2nd element from $S_2$) </aside>

• Product Rule: $|S_1\times S_2|=|S_1|\times|S_2|$
• Sum Rule: $|S_1\cup S_2|=|S_1|+|S_2|, S_1\cap S_2=\emptyset$
• Subtraction Rule: $|S_1\cup S_2|=|S_1|+|S_2|-|S_1\cap S_2|$
• Division Rule: $n = \frac{|S|}{d}$
  • $n$: Number of disjoint subsets partitioning $S$.
  • $|S|$: Cardinality (or number of elements) of the set $S$.
  • $d$: Number of elements in each disjoint subset.

Inclusion-exclusion Principle

$$ \begin{aligned} |A_1 \cup A_2 \cup \ldots \cup A_n| &= \sum_{i} |A_i| \\ &- \sum_{i < j} |A_i \cap A_j| \\ &+ \sum_{i < j < k} |A_i \cap A_j \cap A_k| \\ &- \ldots \\ &+ (-1)^{n+1} |A_1 \cap A_2 \cap \ldots \cap A_n| \end{aligned}

$$

Tree diagram

• Tree diagram can be used to solve counting problems
• The number of leaf node is the count

Pigeonhole Principle

Generalized pigeonhole principle

• If $N$ objects are placed into $k$ boxes, there exists at least one box that contains at least $\left\lceil \frac{N}{k}\right\rceil$

Permutations & Combinations

Basics

Permutation: