Combinatorics and Counting

🧩 Combinatorics and Counting

Combinatorics is the branch of mathematics dealing with the counting, arrangement, and combination of elements within sets. In computer science, this is crucial for Complexity Analysis, Probability, and Algorithm Design.

---

🟢 Part 1: Basic Counting Principles

Before diving into complex formulas, we must understand two fundamental rules.

1. Addition Rule (OR)

If task $A$ can be done in $m$ ways and task $B$ in $n$ ways, and $A$ and $B$ cannot occur simultaneously, then choosing $A$ or $B$ can be done in $m + n$ ways.

2. Multiplication Rule (AND)

If a task has two independent steps, where step 1 can be done in $m$ ways and step 2 in $n$ ways, then the total task can be done in $m \times n$ ways. Example: A password consists of 3 letters followed by 2 digits. Total combinations: $26^3 \times 10^2 = 1,757,600$.

---

🟡 Part 2: Permutations and Combinations

The difference between these two lies in one simple rule: Does order matter?

1. Permutations ($P$) - Order Matters

A permutation is an ordered arrangement of objects.

• Formula (No repetition): $P(n, r) = \frac{n!}{(n-r)!}$
• Formula (With repetition): $n^r$

Example: Arranging 3 people in a row of 3 chairs. Total ways: $3! = 6$.

2. Combinations ($C$) - Order Does Not Matter

A combination is a selection of objects where the order doesn’t change the outcome.

• Formula: $C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

Example: Selecting a team of 3 people from a group of 10. Total ways: $\binom{10}{3} = 120$.

---

🔴 Part 3: Advanced Principles

1. Inclusion-Exclusion Principle

Used to count the union of multiple sets while avoiding double-counting: $|A \cup B| = |A| + |B| - |A \cap B|$ Application: Counting users who performed action A OR action B in a database.

2. Pigeonhole Principle

If $n$ items are put into $m$ containers, with $n > m$, then at least one container must contain more than one item. CS Context: This is why Hash Collisions are mathematically guaranteed when the number of possible keys exceeds the size of the hash table.

Tip

Generating Subsets: The number of subsets of a set with $n$ elements is $2^n$. This is the mathematical reason why many brute-force algorithms (trying every possible combination) have $O(2^n)$ complexity.

---

💻 Programming Example: Calculating Combinations

import math

def combinations(n, r):
    """Calculates nCr (n choose r)"""
    return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))

# Example: Selecting 3 items from a menu of 10
print(f"Combinations: {combinations(10, 3)}") # 120

# Generating all combinations (Python standard library)
from itertools import combinations as c_list
items = ['A', 'B', 'C', 'D']
print(f"All pairs from {items}: {list(c_list(items, 2))}")

When to use which?

• Permutation: Creating a playlist (song order matters).
• Combination: Handing out 5 cards from a deck (hand value is the same regardless of deal order).
• Counting Principle: Estimating the size of a search space for an algorithm.