The Ultimate Discrete Mathematics Cheatsheet

# ── Inclusion-Exclusion: Worked Examples ──

# Example 1: How many integers from 1 to 100 are divisible by 3 or 5?
# Let A = divisible by 3, B = divisible by 5
|A| = 100 // 3 = 33     # {3, 6, 9, ..., 99}
|B| = 100 // 5 = 20     # {5, 10, 15, ..., 100}
|A ∩ B| = 100 // 15 = 6  # {15, 30, 45, 60, 75, 90}

|A ∪ B| = 33 + 20 - 6 = 47

# Example 2: Three sets
# In a class: 40 study Math, 50 study Physics, 45 study Chemistry
# 20 study Math & Physics, 15 study Math & Chemistry, 18 study Physics & Chemistry
# 8 study all three. How many study at least one?
# |M ∪ P ∪ C| = 40 + 50 + 45 - 20 - 15 - 18 + 8 = 90

# Example 3: Derangements (nothing in original position)
# Number of derangements of n items: D(n) = n! * Σ((-1)^k / k!) for k=0 to n
# D(4) = 24 * (1 - 1 + 1/2 - 1/6 + 1/24) = 24 * 9/24 = 9

# ── Warshall's Algorithm for Transitive Closure ──
# Time: O(n^3), Space: O(n^2)

def warshall(n, edges):
    """Compute transitive closure of a relation on {0, 1, ..., n-1}."""
    # Initialize adjacency matrix
    R = [[False] * n for _ in range(n)]
    for u, v in edges:
        R[u][v] = True

    # Warshall's algorithm
    for k in range(n):
        for i in range(n):
            if R[i][k]:  # Optimization: skip if no path i->k
                for j in range(n):
                    if R[k][j]:
                        R[i][j] = True

    return R

# Example: R = {(0,1), (1,2), (2,0)} on set {0,1,2}
edges = [(0,1), (1,2), (2,0)]
closure = warshall(3, edges)
# R* = {(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)}

# ── Composition of Relations ──
def compose(R, S):
    """Compute S ∘ R (S after R).
    R: set of (a, b) pairs, S: set of (b, c) pairs.
    Result: set of (a, c) pairs."""
    result = set()
    for a, b in R:
        for b2, c in S:
            if b == b2:
                result.add((a, c))
    return result

# Example:
R = {(1, 2), (2, 3), (3, 4)}  # relation on natural numbers
S = {(2, 5), (3, 6), (4, 7)}
print(compose(R, S))  # {(1, 5), (2, 6), (3, 7)}

# Matrix method: composition = boolean matrix product
# (S ∘ R)[i][j] = OR over k of (R[i][k] AND S[k][j])

# ── Pigeonhole Principle: Worked Examples ──

# Example 1 (Weak Form):
# In a group of 13 people, prove at least 2 share a birth month.
# Pigeons = 13 people, Holes = 12 months
# ceil(13/12) = 2, so at least 2 people share a month. ✓

# Example 2 (Strong Form):
# Among 100 people, how many have the same birthday (day of year)?
# Pigeons = 100, Holes = 365
# floor((100-1)/365) + 1 = 0 + 1 = 1 (trivially true)
# But floor(99/365) + 1 = 1. So at least 2 share? No.
# Actually: ceil(100/365) = 1. Need ceil.
# 100 > 365 is false, so weak form doesn't help.
# Correct: floor(99/365) + 1 = 1. So guaranteed 1 per day minimum.
# Actually: At least 1 person. Trivially true. Not useful.
# Real answer: we CAN'T guarantee 2 sharing among 100 people with 365 days.

# Example 3 (Strong Form - non-trivial):
# Among 400 people, prove at least 2 share the same birthday.
# Pigeons = 400, Holes = 365
# floor((400-1)/365) + 1 = 1 + 1 = 2. ✓ At least 2 people share.

# Example 4 (Interview Classic):
# Show that in any group of 6 people, there are either 3 mutual
# friends or 3 mutual strangers (Ramsey's theorem R(3,3) = 6).
# Consider person A and their 5 relationships with others.
# By PHP (5 people, 2 categories: friend/stranger),
# A has ≥ 3 friends OR ≥ 3 strangers (say 3 friends: B, C, D).
# If any 2 of {B,C,D} are friends, + A = 3 mutual friends.
# If no 2 of {B,C,D} are friends, then {B,C,D} are 3 mutual strangers.

# Example 5 (Counting):
# How many socks must you pull from a drawer with 4 colors
# to guarantee a matching pair?
# PHP: 5 socks (4 colors + 1). The 5th sock MUST match one of the 4.

# ── Stars and Bars: Worked Examples ──

# Example 1: How many solutions to x1 + x2 + x3 = 10 where xi >= 0?
# Stars (10 items) and Bars (2 dividers for 3 variables)
# C(10 + 3 - 1, 3 - 1) = C(12, 2) = 66

# Example 2: How many solutions to x1 + x2 + x3 = 10 where xi >= 1?
# Substitute yi = xi - 1: y1 + y2 + y3 = 7 where yi >= 0
# C(7 + 3 - 1, 3 - 1) = C(9, 2) = 36

# Example 3: Distribute 20 identical candies to 5 children, each gets >= 3.
# yi = xi - 3: y1 + ... + y5 = 20 - 15 = 5, yi >= 0
# C(5 + 5 - 1, 5 - 1) = C(9, 4) = 126

# Example 4: Number of non-decreasing sequences of length 4 from {1,2,...,6}
# Equivalent to combinations with repetition: C(6+4-1, 4) = C(9,4) = 126

# ── Solving Linear Recurrence Relations ──
# Step 1: Write characteristic equation
# Step 2: Find roots r1, r2, ...
# Step 3: General solution depends on roots

# Case 1: Distinct roots r1, r2, ..., rk
#   a_n = A1*r1^n + A2*r2^n + ... + Ak*rk^n
# Example: a_n = 5a_{n-1} - 6a_{n-2}, a_0=1, a_1=2
#   r^2 - 5r + 6 = 0 => r = 2, 3
#   a_n = A(2^n) + B(3^n)
#   a_0 = A + B = 1,  a_1 = 2A + 3B = 2
#   A = 1, B = 0  =>  a_n = 2^n

# Case 2: Repeated root r (multiplicity m)
#   (A1 + A2*n + A3*n^2 + ... + Am*n^{m-1}) * r^n

# Example: a_n = 6a_{n-1} - 9a_{n-2}, a_0=1, a_1=6
#   r^2 - 6r + 9 = 0 => (r-3)^2 = 0 => r = 3 (double root)
#   a_n = (A + Bn)(3^n)
#   a_0 = A = 1,  a_1 = (1+B)(3) = 6 => B = 1
#   a_n = (1 + n)(3^n)

# Case 3: Complex roots a ± bi
#   Use polar form: r^n = p^n(A*cos(nθ) + B*sin(nθ))
#   where p = sqrt(a^2 + b^2), θ = atan2(b, a)

# ── Kruskal's Algorithm (Greedy, edges sorted by weight) ──
def kruskal(n, edges):
    """edges: list of (weight, u, v). n: number of vertices."""
    parent = list(range(n))
    rank = [0] * n
    edges.sort()  # sort by weight

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x

    def union(x, y):
        px, py = find(x), find(y)
        if px == py: return False
        if rank[px] < rank[py]: px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]: rank[px] += 1
        return True

    mst = []
    for w, u, v in edges:
        if union(u, v):
            mst.append((w, u, v))
            if len(mst) == n - 1: break
    return mst  # total weight = sum of w

# ── Prim's Algorithm (Greedy, grow from a source) ──
import heapq
def prim(n, adj):
    """adj: adjacency list {u: [(v, weight), ...]}"""
    visited = [False] * n
    min_heap = [(0, 0, -1)]  # (weight, node, parent)
    mst = []

    while min_heap:
        w, u, parent = heapq.heappop(min_heap)
        if visited[u]: continue
        visited[u] = True
        if parent != -1:
            mst.append((w, parent, u))
        for v, weight in adj[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (weight, v, u))
    return mst

# Kruskal: O(E log E) — good for sparse graphs
# Prim: O(E log V) with heap — good for dense graphs

# ── Permutation Notation ──
# Two-line notation: σ = (1 2 3 4 5)
#                      (3 1 5 2 4)
# means: 1→3, 2→1, 3→5, 4→2, 5→4

# Cycle notation: σ = (1 3 5 4 2) — one 5-cycle
# σ = (1 3)(2 4)     — two disjoint 2-cycles (transpositions)

# ── Permutation Properties ──
# Order of a permutation = LCM of cycle lengths
# Example: σ = (1 2 3)(4 5) — order = LCM(3,2) = 6

# Even permutation: expressible as even number of transpositions
# Odd permutation: expressible as odd number of transpositions
# Sign of σ: (-1)^(number of transpositions)
# A_n (alternating group) = set of even permutations, |A_n| = n!/2

# ── Composition of permutations ──
# Apply right permutation first, then left
# σ = (1 2 3), τ = (1 3)
# σ ∘ τ: apply τ then σ
# τ: 1→3, 2→2, 3→1
# σ: 1→2, 2→3, 3→1
# (σ ∘ τ)(1) = σ(τ(1)) = σ(3) = 1
# (σ ∘ τ)(2) = σ(τ(2)) = σ(2) = 3
# (σ ∘ τ)(3) = σ(τ(3)) = σ(1) = 2
# σ ∘ τ = (2 3)

# ── Bayes' Theorem: Worked Examples ──

# Example 1: Medical Testing
# Disease affects 1% of population. Test is 99% accurate.
# P(D) = 0.01, P(~D) = 0.99
# P(+|D) = 0.99  (sensitivity / true positive rate)
# P(-|~D) = 0.99 => P(+|~D) = 0.01  (false positive rate)
#
# Question: Given a positive test, what's the probability
# you actually have the disease?
#
# P(D|+) = P(+|D) * P(D) / P(+)
# P(+) = P(+|D)*P(D) + P(+|~D)*P(~D)
#      = 0.99 * 0.01 + 0.01 * 0.99 = 0.0198
#
# P(D|+) = 0.0099 / 0.0198 = 0.5 = 50% !!
#
# Counterintuitive: Even with 99% accurate test,
# a positive result gives only 50% chance of disease!

# Example 2: Spam Filter
# P(Spam) = 0.3, P(Ham) = 0.7
# P("free" | Spam) = 0.8
# P("free" | Ham) = 0.1
#
# P(Spam | "free") = P("free"|Spam) * P(Spam) / P("free")
# P("free") = 0.8*0.3 + 0.1*0.7 = 0.24 + 0.07 = 0.31
# P(Spam | "free") = 0.24 / 0.31 ≈ 0.774 = 77.4%

# Example 3: Faulty Machine Parts
# Machine A produces 60% of parts, 2% defective
# Machine B produces 40% of parts, 1% defective
# P(A) = 0.6, P(B) = 0.4
# P(D|A) = 0.02, P(D|B) = 0.01
#
# P(A|D) = P(D|A)*P(A) / P(D)
# P(D) = 0.02*0.6 + 0.01*0.4 = 0.012 + 0.004 = 0.016
# P(A|D) = 0.012 / 0.016 = 0.75 = 75%

# ── Counting Grid Paths with Obstacles ──
def count_paths(m, n, obstacles=None):
    """Count paths in m×n grid with obstacles.
    obstacles: set of (row, col) cells that are blocked."""
    if obstacles is None:
        obstacles = set()
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1 if (0, 0) not in obstacles else 0

    for i in range(m):
        for j in range(n):
            if (i, j) in obstacles:
                dp[i][j] = 0
                continue
            if i > 0:
                dp[i][j] += dp[i-1][j]
            if j > 0:
                dp[i][j] += dp[i][j-1]

    return dp[m-1][n-1]

# Example: 3×4 grid, obstacle at (1,1)
print(count_paths(3, 4))                # 10 (no obstacles)
print(count_paths(3, 4, {(1, 1)}))      # fewer paths

# ── Using Combinatorics (no obstacles) ──
from math import comb
def grid_paths(m, n):
    """C(m+n-2, m-1) paths from top-left to bottom-right."""
    return comb(m + n - 2, m - 1)

print(grid_paths(3, 4))  # 10
print(grid_paths(20, 20))  # 137846528820