Combinatorics & Counting

Intuition: If you can choose a meal from either a menu of 4 pasta dishes or a menu of 5 salads (but not both at once), you have 4 + 5 = 9 total choices. The key word is or, and the key condition is that the two sets of choices are disjoint — you cannot pick something that appears on both menus simultaneously.

Formal statement: If task A can be done in m ways and task B can be done in n ways, and no way of doing A is the same as any way of doing B, then the task "do A or B" can be done in m + n ways.

In set language: if A and B are disjoint finite sets, then |A ∪ B| = |A| + |B|. More generally, for pairwise disjoint sets A₁, A₂, …, Aₖ:

|A₁ ∪ A₂ ∪ … ∪ Aₖ| = |A₁| + |A₂| + … + |Aₖ|

Why the disjointness condition matters: If the menus overlap (say, a Caesar salad appears on both), adding naively double-counts that item. Fixing that overcounting is exactly what inclusion-exclusion (later in this module) handles.

CS example: How many valid C identifiers of length exactly 1 are there? An identifier is a letter (52 choices: a–z, A–Z) or an underscore (1 choice). These are disjoint, so the answer is 52 + 1 = 53. (Digits are excluded from the first character.)

Common pitfall: Students forget to verify disjointness. Always ask: "Can something belong to both groups?" If yes, you need inclusion-exclusion.

# Count 1-character valid C identifiers
letters = set('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ')
underscores = {'_'}
# Disjoint? Yes. Apply sum rule.
print(len(letters) + len(underscores))  # 53

# Verify by brute force
import string
valid = [c for c in string.ascii_letters + '_']
print(len(valid))  # 53

Intuition: If you are getting dressed and you have 3 shirts and 4 pairs of pants, you have 3 × 4 = 12 distinct outfits. The key word is and — you choose a shirt and a pants independently. The choice of shirt does not change the number of pants available.

Formal statement: If task A can be done in m ways and task B can be done in n ways, and the two choices are independent (every combination of choices is possible and distinct), then doing A and then B can be done in m × n ways.

In set language: if A and B are finite sets, then |A × B| = |A| · |B|, where A × B is the Cartesian product (the set of all ordered pairs).

Multi-step generalization: For k independent tasks with n₁, n₂, …, nₖ choices respectively:

Total = n₁ × n₂ × … × nₖ

CS example — counting binary strings: How many binary strings of length n exist? Each position independently is 0 or 1 (2 choices), and there are n positions. By the product rule: 2 × 2 × … × 2 (n times) = 2ⁿ. This is why n-bit integers span a space of size 2ⁿ, and why a 256-bit cryptographic key has 2²⁵⁶ ≈ 10⁷⁷ possible values.

CS example — counting functions: How many functions f: {1,…,n} → {1,…,m} exist? For each of the n elements in the domain, f can independently map it to any of m values. Product rule: mⁿ total functions.

Subtle point: The product rule requires that every combination is valid and distinct. If some combinations are forbidden (e.g., no repeated elements), you must be more careful — that is the setting of permutations.

# Count all binary strings of length n
n = 8
total = 2 ** n
print(f"Binary strings of length {n}: {total}")  # 256

# Verify by direct enumeration
count = sum(1 for _ in range(total))
print(count)  # 256 -- product rule is exact

# Count functions f: {0..n-1} -> {0..m-1}
m = 5
print(f"Functions from {n}-set to {m}-set: {m**n}")  # 390625

Intuition: You want to arrange 3 books on a shelf. The first slot has 3 choices, the second has 2 remaining, the third has 1. Total: 3 × 2 × 1 = 6. The crucial feature is order matters — {A, B, C} and {B, A, C} are different arrangements.

Definition: A permutation of n distinct objects is an ordered arrangement of all n objects. The number of permutations is:

P(n) = n! = n × (n−1) × (n−2) × … × 2 × 1

This follows directly from the product rule: n choices for position 1, then n−1 for position 2, etc.

Partial permutations (k-permutations): If you only want to arrange k objects chosen from n (k ≤ n), the count is:

P(n, k) = n × (n−1) × … × (n−k+1) = n! / (n−k)!

Why n! grows so fast: 20! ≈ 2.4 × 10¹⁸. This is why brute-force over all arrangements of even 20 items is infeasible — the foundation of combinatorial hardness.

CS example — anagram detection: Checking if two strings are anagrams can be done by sorting (O(n log n)), but counting distinct anagrams of a word like "MISSISSIPPI" requires adjusting for repeated letters. If n objects have groups of identical elements of sizes n₁, n₂, …, nₖ (where n₁ + … + nₖ = n), the number of distinct permutations is n! / (n₁! × n₂! × … × nₖ!). For MISSISSIPPI (1 M, 4 I, 4 S, 2 P): 11! / (1! 4! 4! 2!) = 34,650.

Permutations with repetition: If you may reuse elements, arranging k items chosen from n gives nᵏ (just the product rule — each position independently has n choices). This is exactly the count of passwords of length k over an alphabet of size n.

import math
from itertools import permutations

# P(n, k): k-permutations of n distinct items
def P(n, k):
    return math.factorial(n) // math.factorial(n - k)

print(P(5, 3))   # 60: arrange 3 of 5 books
print(P(26, 4))  # 358800: 4-letter sequences from alphabet

# Multinomial: permutations of MISSISSIPPI
n = 11
counts = [1, 4, 4, 2]  # M I S P
multi = math.factorial(n) // math.prod(math.factorial(c) for c in counts)
print(multi)  # 34650

# Verify P(4, 2) by brute force
result = list(permutations([1,2,3,4], 2))
print(len(result))  # 12 == P(4,2)

Intuition: You want to choose a committee of 3 people from 5 candidates. Unlike arranging books, the committee {Alice, Bob, Carol} is the same committee as {Carol, Alice, Bob}. Order does not matter — only who is in the set.

Definition: A combination (or k-subset) is an unordered selection of k items from n distinct items. The count is written C(n, k), nCk, or "n choose k":

C(n, k) = n! / (k! × (n−k)!)

Derivation: We first count ordered selections: P(n, k) = n!/(n−k)!. But each k-element set has been counted k! times (once for each ordering of its elements). Dividing by k! corrects this:

C(n, k) = P(n, k) / k! = n! / (k! (n−k)!)

Key identities:

• C(n, 0) = C(n, n) = 1 (empty set and full set)
• C(n, k) = C(n, n−k) (symmetry: choosing k is the same as choosing which n−k to leave out)
• C(n, k) = C(n−1, k−1) + C(n−1, k) (Pascal's rule)

Pascal's rule explained: To form a k-subset of {1, …, n}, either include element n (then choose k−1 from the remaining n−1: C(n−1, k−1) ways) or exclude it (choose k from n−1: C(n−1, k) ways). This is the recursion that generates Pascal's triangle.

CS applications:

• Number of distinct k-element subsets of a set: C(n, k)
• Number of ways to place k rooks on an n×n chessboard with no two in the same row or column: C(n, k) × k!
• Number of bit strings of length n with exactly k ones: C(n, k)
• Number of paths on a grid from (0,0) to (m, n) moving only right or up: C(m+n, m)

The last one is beautiful: every such path consists of exactly m right-steps and n up-steps in some order, so it's the number of ways to choose which m of the m+n steps are rightward.

import math
from itertools import combinations

def C(n, k):
    if k < 0 or k > n:
        return 0
    return math.comb(n, k)  # built-in since Python 3.8

print(C(5, 3))    # 10: committees of 3 from 5
print(C(52, 5))   # 2598960: poker hands
print(C(10, 3))   # 120

# Grid paths from (0,0) to (m,n)
m, n = 3, 4
print(C(m + n, m))   # 35: paths on 3x4 grid

# Verify C(5,3) by brute force
result = list(combinations([1,2,3,4,5], 3))
print(len(result))   # 10

# Pascal's rule: C(n,k) == C(n-1,k-1) + C(n-1,k)
print(C(9, 4) == C(8, 3) + C(8, 4))  # True

Setup: What is (x + y)ⁿ expanded as a polynomial? For small n you can multiply out by hand, but the pattern is universal:

(x + y)ⁿ = Σₖ₌₀ⁿ C(n, k) xᵏ yⁿ⁻ᵏ

Combinatorial proof (the right way to understand it): (x + y)ⁿ is a product of n identical factors (x + y). When you expand it, you choose either x or y from each factor. A term xᵏ yⁿ⁻ᵏ arises whenever you chose x from exactly k of the n factors and y from the remaining n−k. The number of ways to choose which k factors contribute x is C(n, k). That is the coefficient.

Special cases that recur constantly:

• Setting x = y = 1: (1+1)ⁿ = Σ C(n,k) = 2ⁿ. This proves that a set of n elements has exactly 2ⁿ subsets (each element is either in or out).
• Setting x = 1, y = −1: (1−1)ⁿ = 0 = Σ (−1)ᵏ C(n,k). This means the number of even-sized subsets equals the number of odd-sized subsets (for n ≥ 1).
• Setting x = 1, y = 1/m for large m: gives approximations useful in probability.

Multinomial theorem: Generalizes to (x₁ + x₂ + … + xₘ)ⁿ = Σ [n!/(k₁! k₂! … kₘ!)] x₁ᵏ¹ x₂ᵏ² … xₘᵏᵐ, summed over all non-negative integer tuples (k₁, …, kₘ) with k₁ + … + kₘ = n. The coefficient n!/(k₁! … kₘ!) is called the multinomial coefficient.

CS connection: The binomial theorem underlies the analysis of Bernoulli trials (n independent coin flips with probability p of heads). The probability of exactly k heads is C(n,k) pᵏ (1−p)ⁿ⁻ᵏ — a direct application. This is the binomial distribution, central to randomized algorithm analysis.

from math import comb

def binomial_expand(n):
    """Returns coefficients of (x+y)^n from k=0 to k=n."""
    return [comb(n, k) for k in range(n + 1)]

print(binomial_expand(4))  # [1, 4, 6, 4, 1]  => (x+y)^4
print(binomial_expand(5))  # [1, 5, 10, 10, 5, 1]

# Identity: sum of row = 2^n
n = 10
coeffs = binomial_expand(n)
print(sum(coeffs) == 2**n)   # True -- total subsets

# Alternating sum = 0 for n >= 1
alt = sum((-1)**k * comb(n, k) for k in range(n+1))
print(alt)  # 0

# Binomial probability: P(exactly k heads in n flips, p=0.5)
p = 0.5
prob = lambda n, k, p: comb(n, k) * (p**k) * ((1-p)**(n-k))
print(sum(prob(10, k, 0.5) for k in range(11)))  # 1.0

Pascal's triangle arranges the binomial coefficients C(n, k) in a triangular array where row n contains C(n,0), C(n,1), …, C(n,n). Each interior entry is the sum of the two entries above it (Pascal's rule: C(n,k) = C(n−1,k−1) + C(n−1,k)).

Row 0:          1
Row 1:        1   1
Row 2:      1   2   1
Row 3:    1   3   3   1
Row 4:  1   4   6   4   1

Why it matters beyond memorization: Pascal's triangle is a compact way to compute all binomial coefficients efficiently using dynamic programming — the same recurrence that makes memoized DP possible in combinatorics problems.

Key identities visible in the triangle:

1. Hockey stick identity: Σᵢ₌ᵣⁿ C(i, r) = C(n+1, r+1). Sum the r-th column from row r to row n, and you get the entry one below and one to the right. Named for the hockey-stick shape traced in the triangle.

2. Vandermonde's identity: C(m+n, r) = Σₖ₌₀ʳ C(m, k) C(n, r−k). Combinatorial proof: choose r items from m+n by splitting the pool into two groups of m and n; choose k from the first group and r−k from the second.

3. Sum of squares: Σₖ₌₀ⁿ C(n,k)² = C(2n, n). Choose n items from a set of 2n by picking k from the first half and n−k from the second.

Algorithmic use: Many DP problems secretly count combinations. Counting the number of paths in a grid, the number of ways to partition a string, or the number of balanced parenthesizations all reduce to computing entries of Pascal's triangle via bottom-up DP.

def pascal_triangle(rows):
    """Generate first `rows` rows of Pascal's triangle."""
    tri = [[1]]
    for n in range(1, rows):
        prev = tri[-1]
        row = [1] + [prev[k-1] + prev[k] for k in range(1, n)] + [1]
        tri.append(row)
    return tri

for row in pascal_triangle(6):
    print(row)
# [1]
# [1, 1]
# [1, 2, 1]
# [1, 3, 3, 1]
# [1, 4, 6, 4, 1]
# [1, 5, 10, 10, 5, 1]

# Hockey stick: sum C(i,2) for i=2..5 == C(6,3)
from math import comb
hockey = sum(comb(i, 2) for i in range(2, 6))
print(hockey, comb(6, 3))  # 10 20 -- wait, r=2, n=5 => C(6,3)=20
hockey = sum(comb(i, 2) for i in range(2, 6))  # i=2,3,4,5 -> 1+3+6+10=20
print(hockey == comb(6, 3))  # True

Intuition: If you have 10 pigeons and 9 holes, and every pigeon must go into a hole, then at least one hole contains at least two pigeons. This is trivially obvious but profoundly powerful.

Formal statement (basic): If n+1 or more objects are placed into n categories, then at least one category contains at least 2 objects.

Generalized pigeonhole principle: If N objects are distributed into k categories, then at least one category contains at least ⌈N/k⌉ objects (ceiling of N/k).

Proof: By contradiction. If every category had at most ⌈N/k⌉ − 1 objects, the total would be at most k(⌈N/k⌉ − 1) < k(N/k) = N, contradicting that there are N objects.

Classic applications:

1. Birthday paradox setup: In a group of 367 people, two must share a birthday (366 possible birthdays including Feb 29, 367 people → pigeonhole). (The probabilistic birthday paradox asks how many people are needed for a 50% chance — that is ≈23, a different question.)

2. Repeated decimal digits: Any rational p/q has a repeating decimal with period at most q−1 (the remainders modulo q can only take q values; by pigeonhole, after at most q divisions, a remainder repeats).

3. Monotone subsequences (Erdős–Szekeres): Any sequence of more than n² distinct real numbers has either an increasing subsequence of length > n or a decreasing subsequence of length > n. Proof: label each element with the length of the longest increasing subsequence ending there; if all are ≤ n, then by pigeonhole two elements share the same label, which leads to a contradiction constructing a decreasing subsequence.

4. Hash collision guarantee: A hash function mapping N > m keys into m buckets must collide. This is unavoidable — no hash function can be collision-free when N > m.

5. File compression: No lossless compression algorithm can compress every n-bit file. There are 2ⁿ files of length n but only 2ⁿ − 1 shorter files (of length < n); pigeonhole means some file must not get shorter.

The art: The pigeonhole principle only tells you existence, not where. The skill is identifying the right objects and the right categories.

# Pigeonhole: find two people who share a birth month
import random

def find_shared_month(people_birthdays):
    """Guaranteed to find a collision if len > 12."""
    seen = {}
    for person, month in people_birthdays:
        if month in seen:
            return (seen[month], person, month)
        seen[month] = person
    return None  # only possible if len <= 12

# 13 people, 12 months => guaranteed collision
bdays = [(f"P{i}", random.randint(1,12)) for i in range(13)]
result = find_shared_month(bdays)
print(result)  # always prints a collision

# Generalized: with N items in k bins, max bin >= ceil(N/k)
import math
N, k = 23, 7
guaranteed_max = math.ceil(N / k)
print(f"At least one bin has >= {guaranteed_max} items")  # 4

The problem: The sum rule requires disjoint sets. What if your sets overlap? Naively adding their sizes double-counts elements in the intersection. Inclusion-exclusion is the precise fix.

For two sets: |A ∪ B| = |A| + |B| − |A ∩ B|

Intuition: Include both sets, then exclude the intersection once (it was counted twice).

For three sets: |A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|

Add individual sets, subtract pairwise intersections (they were counted twice, so subtract once), add back the triple intersection (it was added 3 times, subtracted 3 times — net 0 — so add once).

General formula: For sets A₁, A₂, …, Aₙ:

|A₁ ∪ … ∪ Aₙ| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| − … + (−1)ⁿ⁺¹|A₁∩…∩Aₙ|

Why it works (formal proof sketch): Consider an element x that belongs to exactly m of the n sets. Its contribution to the right side is C(m,1) − C(m,2) + C(m,3) − … = 1 (by the binomial identity with x=1, y=−1 applied to (1−1)ᵐ, adjusted for the k=0 term). So every element in the union is counted exactly once.

Classic applications:

1. Derangements: How many permutations of {1,…,n} have no fixed point (no i such that π(i) = i)? Let Aᵢ = {permutations where i is fixed}. By inclusion-exclusion: D(n) = n! Σₖ₌₀ⁿ (−1)ᵏ/k! ≈ n!/e This is the probability that a random shuffle leaves no card in its original position ≈ 1/e ≈ 36.8%, independent of n for large n. Remarkable.

2. Euler's totient function: φ(n) = n ∏_{p|n} (1 − 1/p), where the product is over distinct prime divisors. This is inclusion-exclusion over the sets of multiples of each prime factor.

3. Counting surjections: The number of surjective (onto) functions f: {1,…,n} → {1,…,k} is Σⱼ₌₀ᵏ (−1)ʲ C(k,j) (k−j)ⁿ. (Subtract the functions missing at least one output value.)

Practical advice: When you need to count things satisfying at least one of several properties, complement: count the total minus those satisfying none, which equals the union of "bad" sets. Inclusion-exclusion handles the union.

from math import factorial, comb

# Derangements: permutations with no fixed point
def derangements(n):
    return round(factorial(n) / 2.71828182845904523536)

# Exact formula
def D(n):
    return sum((-1)**k * factorial(n) // factorial(k) for k in range(n+1))

for n in range(1, 9):
    print(f"D({n}) = {D(n)}")
# D(1)=0, D(2)=1, D(3)=2, D(4)=9, D(5)=44 ...

# Surjections from n-set to k-set
def surjections(n, k):
    return sum((-1)**j * comb(k, j) * (k-j)**n for j in range(k+1))

print(surjections(4, 3))  # 36

# Inclusion-exclusion for |A ∪ B ∪ C|
A, B, C = {1,2,3,4}, {3,4,5,6}, {5,6,7,8}
IE = len(A)+len(B)+len(C) - len(A&B) - len(A&C) - len(B&C) + len(A&B&C)
print(IE, len(A|B|C))  # both 8

Problem: How many ways can you distribute 10 identical cookies among 4 children, if each child can get any number (including zero)?

The stars-and-bars insight: Represent cookies as stars (★) and use 3 dividers (|) to separate the 4 children's shares. For example:

★★★ | ★★ | ★★★★ | ★

means children get 3, 2, 4, 1 cookies. Any arrangement of 10 stars and 3 bars is a valid distribution. How many arrangements? We have 13 symbols, choose which 3 are bars: C(13, 3) = 286.

General formula: The number of ways to distribute n identical items among k groups (each getting ≥ 0) is:

C(n + k − 1, k − 1)

Equivalent formulation: The number of non-negative integer solutions to x₁ + x₂ + … + xₖ = n is C(n + k − 1, k − 1).

With a lower bound (each ≥ 1): If each group must get at least 1 item, first give 1 to each group (uses k items), then distribute the remaining n−k items freely: C((n−k) + k − 1, k − 1) = C(n−1, k−1).

CS applications:

• Counting multisets of size k drawn from an alphabet of n symbols
• Counting polynomials of degree ≤ d in k variables
• Counting cache line allocations, memory partitioning schemes
• In combinatorics proofs about integer compositions and partitions

Warning: This is for identical items. If items are distinct, use the product rule (each item independently goes to one of k groups: kⁿ total).

from math import comb

# Non-negative integer solutions to x1+x2+x3+x4 = 10
n, k = 10, 4
print(comb(n + k - 1, k - 1))  # C(13,3) = 286

# Verify by brute force (slow but correct for small n)
count = 0
for x1 in range(n+1):
    for x2 in range(n+1-x1):
        for x3 in range(n+1-x1-x2):
            x4 = n - x1 - x2 - x3
            count += 1
print(count)  # 286

# Multisets: choose k items from alphabet of n WITH repetition
# e.g., choose 3 letters from {a,b,c,d,e} with repetition
n_alpha, k_choose = 5, 3
print(comb(n_alpha + k_choose - 1, k_choose))  # C(7,3) = 35

Combinatorics problems require strategy, not just formulas. Here is a disciplined decision tree used by experienced problem solvers and taught at MIT/Stanford:

Step 1 — Define the sample space precisely. What exactly is one "outcome"? Is it an ordered tuple, a set, a function, a permutation? Being vague here is the root cause of most errors.

Step 2 — Identify the structure:

• Does order matter? Yes → permutations or product rule. No → combinations or stars-and-bars.
• Can items repeat? Yes + order matters → nᵏ. Yes + order doesn't matter → stars-and-bars. No + order matters → P(n,k). No + order doesn't matter → C(n,k).

Step 3 — Choose a technique:

• Direct count: Apply sum/product rule directly.
• Complement: Count the total and subtract what you don't want. Often easier when the "bad" cases are simpler.
• Bijection: Show a one-to-one correspondence with a set you already know how to count. (e.g., bit strings of length n with k ones ↔ k-element subsets of {1,…,n})
• Recursion/DP: Break into smaller subproblems. Useful when inclusion-exclusion or direct formulas are hard to apply.
• Inclusion-exclusion: When you need to count union of overlapping sets.

Step 4 — Verify with small cases. Plug in n=2 or n=3 and check by hand. If the formula gives the wrong answer for n=2, find the error before going further.

Bijective proofs deserve special mention: they establish that two sets have the same size by exhibiting an explicit bijection. They are often the most elegant and insightful proofs in combinatorics because they reveal why two counts are equal, not just that they are.

The complement trick: Counting "at least one" is usually harder than counting "none". If A is the event of interest: |A| = |Total| − |Aᶜ|. This is the first tool to reach for when the complement has a clean structure.

Double counting: Prove an identity by counting the same thing two ways. For example, C(n, k) · k = n · C(n−1, k−1) because both sides count pairs (committee of k, designated leader) from n people.

# Demonstration of complement counting
# Q: How many 8-bit strings have AT LEAST one '1' bit?
# Direct: tedious (sum over k=1 to 8 of C(8,k))
# Complement: Total - strings with NO ones = 2^8 - 1

n = 8
total = 2 ** n
no_ones = 1  # only '00000000'
at_least_one = total - no_ones
print(at_least_one)  # 255

# Verify by direct enumeration
count = sum(1 for x in range(256) if x > 0)
print(count)  # 255

# Bijection example:
# k-element subsets of {1..n}  <->  n-bit strings with exactly k ones
# Both counted by C(n, k)
from math import comb
from itertools import combinations

n, k = 6, 3
# Via formula
print(comb(n, k))  # 20
# Via bit strings
bit_strings = [x for x in range(2**n) if bin(x).count('1') == k]
print(len(bit_strings))  # 20