Advanced Counting

Generating Functions

A generating function encodes a sequence of numbers as coefficients of a power series, turning counting problems into algebraic manipulations.

Ordinary Generating Functions (OGF)

For a sequence a₀, a₁, a₂, ..., the OGF is:

A(x) = Σₙ₌₀^∞ aₙ xⁿ = a₀ + a₁x + a₂x² + a₃x³ + ...

Example: The sequence 1, 1, 1, 1, ... has OGF:

A(x) = 1 + x + x² + x³ + ... = 1/(1-x)    (for |x| < 1)

Example: The sequence 1, 2, 3, 4, ... has OGF:

A(x) = 1 + 2x + 3x² + 4x³ + ... = 1/(1-x)²

| Operation on sequence | Effect on OGF | |---|---| | Right shift by k (prepend k zeros) | xᵏ · A(x) | | Multiply aₙ by cⁿ | A(cx) | | Prefix sum (bₙ = a₀ + a₁ + ... + aₙ) | A(x) / (1 - x) | | Convolution (cₙ = Σ aₖ bₙ₋ₖ) | A(x) · B(x) | | Differentiation (naₙ sequence) | x · A'(x) |

Using OGFs for Counting

Example: How many ways to make change for n cents using pennies (1¢), nickels (5¢), and dimes (10¢)?

Each coin contributes a factor:

Pennies: 1 + x + x² + x³ + ... = 1/(1-x)
Nickels: 1 + x⁵ + x¹⁰ + ... = 1/(1-x⁵)
Dimes:   1 + x¹⁰ + x²⁰ + ... = 1/(1-x¹⁰)

The generating function for the answer is:

A(x) = 1/((1-x)(1-x⁵)(1-x¹⁰))

The coefficient of xⁿ gives the number of ways to make n cents.

Exponential Generating Functions (EGF)

For labeled structures, use EGF:

A(x) = Σₙ₌₀^∞ aₙ xⁿ/n!

The product of EGFs corresponds to combining labeled structures (exponential formula).

Example: eˣ = Σ xⁿ/n! is the EGF for the sequence 1, 1, 1, 1, ...

Example: The EGF for derangements is e⁻ˣ/(1-x), since Dₙ/n! → 1/e.

Important Generating Functions

| Sequence | OGF | |---|---| | 1, 1, 1, ... | 1/(1-x) | | 1, c, c², c³, ... | 1/(1-cx) | | 1, 2, 3, 4, ... | 1/(1-x)² | | C(n+k-1, k), ... | 1/(1-x)ᵏ | | Fibonacci: 0, 1, 1, 2, 3, 5, ... | x/(1-x-x²) | | Catalan: 1, 1, 2, 5, 14, ... | (1-√(1-4x))/(2x) |

Recurrence Relations

A recurrence relation defines a sequence where each term is expressed in terms of previous terms.

Linear Recurrences

First-order linear: aₙ = c · aₙ₋₁ + f(n).

Homogeneous with constant coefficients:

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ

Solving Homogeneous Linear Recurrences

Method: Find the characteristic equation:

rᵏ - c₁rᵏ⁻¹ - c₂rᵏ⁻² - ... - cₖ = 0

Case 1: Distinct roots r₁, r₂, ..., rₖ:

aₙ = α₁r₁ⁿ + α₂r₂ⁿ + ... + αₖrₖⁿ

Case 2: Repeated root r with multiplicity m:

(α₁ + α₂n + α₃n² + ... + αₘnᵐ⁻¹) · rⁿ

Use initial conditions to solve for the αᵢ constants.

Example: Fibonacci numbers: Fₙ = Fₙ₋₁ + Fₙ₋₂, F₀ = 0, F₁ = 1.

Characteristic equation: r² - r - 1 = 0. Roots: r = (1 ± √5)/2. Let φ = (1+√5)/2, ψ = (1-√5)/2.

Fₙ = (φⁿ - ψⁿ) / √5

This is Binet's formula. Since |ψ| < 1, Fₙ ≈ φⁿ/√5 for large n, so Fibonacci grows exponentially with base φ ≈ 1.618 (the golden ratio).

Example: aₙ = 5aₙ₋₁ - 6aₙ₋₂, a₀ = 1, a₁ = 4.

Characteristic: r² - 5r + 6 = 0 → (r-2)(r-3) = 0 → r = 2, 3. General: aₙ = α·2ⁿ + β·3ⁿ. Using a₀ = 1: α + β = 1. Using a₁ = 4: 2α + 3β = 4. Solving: α = -1, β = 2. Answer: aₙ = -2ⁿ + 2·3ⁿ.

Non-Homogeneous Linear Recurrences

Form: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ + f(n).

Solution: aₙ = (homogeneous solution) + (particular solution).

For the particular solution, guess a form matching f(n):

| f(n) | Guess for particular solution | |---|---| | Constant d | A | | n | An + B | | n² | An² + Bn + C | | dⁿ | A·dⁿ (if d is not a root of characteristic eq.) | | dⁿ | A·n·dⁿ (if d is a root with multiplicity 1) |

Example: aₙ = 2aₙ₋₁ + 3, a₀ = 1.

Homogeneous solution: aₙ⁽ʰ⁾ = α·2ⁿ. Particular: try aₙ⁽ᵖ⁾ = A. Then A = 2A + 3, so A = -3. General: aₙ = α·2ⁿ - 3. Using a₀ = 1: α - 3 = 1, α = 4. Answer: aₙ = 4·2ⁿ - 3 = 2ⁿ⁺² - 3.

Solving Recurrences: Master Theorem

For divide-and-conquer recurrences of the form:

T(n) = aT(n/b) + f(n)

where a ≥ 1, b > 1.

Let c = log_b(a).

Case 1: If f(n) = O(nᶜ⁻ᵉ) for some ε > 0, then T(n) = Θ(nᶜ).

Case 2: If f(n) = Θ(nᶜ · logᵏ n) for some k ≥ 0, then T(n) = Θ(nᶜ · logᵏ⁺¹ n).

Case 3: If f(n) = Ω(nᶜ⁺ᵉ) for some ε > 0, and af(n/b) ≤ δf(n) for some δ < 1 (regularity), then T(n) = Θ(f(n)).

Examples:

| Recurrence | Case | Result | |---|---|---| | T(n) = 2T(n/2) + n | Case 2 (c=1, f=n) | Θ(n log n) | | T(n) = 2T(n/2) + 1 | Case 1 (c=1, f=1) | Θ(n) | | T(n) = 4T(n/2) + n³ | Case 3 (c=2, f=n³) | Θ(n³) | | T(n) = 2T(n/2) + n log n | Case 2 (k=1) | Θ(n log² n) | | T(n) = 7T(n/2) + n² | Case 1 (c≈2.807, f=n²) | Θ(n^2.807) |

The last one is Strassen's matrix multiplication.

Akra-Bazzi Method

A more general method for recurrences of the form:

T(n) = Σᵢ aᵢ T(n/bᵢ) + f(n)

where the bᵢ may differ.

Find p such that Σ aᵢ/bᵢᵖ = 1. Then:

T(n) = Θ(nᵖ (1 + ∫₁ⁿ f(u)/u^(p+1) du))

This handles cases the master theorem cannot, like T(n) = T(n/3) + T(2n/3) + n.

Important Sequences

Catalan Numbers

Cₙ = C(2n, n) / (n + 1) = (2n)! / ((n+1)! · n!)

First values: 1, 1, 2, 5, 14, 42, 132, 429, 1430, ...

Recurrence: C₀ = 1, Cₙ = Σₖ₌₀ⁿ⁻¹ Cₖ · Cₙ₋₁₋ₖ.

Catalan numbers count an astonishing variety of structures:

Balanced parenthesizations of n pairs: ()(()), (())(), ...
Full binary trees with n + 1 leaves
Triangulations of a convex (n + 2)-gon
Monotonic lattice paths from (0,0) to (n,n) not crossing the diagonal
Stack-sortable permutations of length n
Non-crossing partitions of {1, ..., n}

Generating function: C(x) = (1 - √(1 - 4x)) / (2x).

Asymptotic: Cₙ ~ 4ⁿ / (n^(3/2) · √π).

Stirling Numbers

Stirling numbers of the second kind S(n, k): The number of ways to partition a set of n elements into exactly k non-empty subsets.

Recurrence: S(n, k) = k · S(n-1, k) + S(n-1, k-1), with S(n, 1) = S(n, n) = 1.

| n\k | 1 | 2 | 3 | 4 | 5 | |---|---|---|---|---|---| | 1 | 1 | | | | | | 2 | 1 | 1 | | | | | 3 | 1 | 3 | 1 | | | | 4 | 1 | 7 | 6 | 1 | | | 5 | 1 | 15 | 25 | 10 | 1 |

Example: S(4, 2) = 7 ways to split {a,b,c,d} into 2 non-empty subsets: {a},{bcd}; {b},{acd}; {c},{abd}; {d},{abc}; {ab},{cd}; {ac},{bd}; {ad},{bc}.

Stirling numbers of the first kind s(n, k) (unsigned): Number of permutations of n elements with exactly k cycles.

Bell Numbers

Bₙ = total number of partitions of an n-element set = Σₖ S(n, k).

B₀ = 1, B₁ = 1, B₂ = 2, B₃ = 5, B₄ = 15, B₅ = 52

Recurrence: Bₙ₊₁ = Σₖ₌₀ⁿ C(n, k) · Bₖ.

EGF: Σ Bₙ xⁿ/n! = e^(eˣ - 1).

Partition Numbers

p(n) = number of ways to write n as a sum of positive integers (order doesn't matter).

p(1) = 1: {1}
p(2) = 2: {2}, {1+1}
p(3) = 3: {3}, {2+1}, {1+1+1}
p(4) = 5: {4}, {3+1}, {2+2}, {2+1+1}, {1+1+1+1}
p(5) = 7: {5}, {4+1}, {3+2}, {3+1+1}, {2+2+1}, {2+1+1+1}, {1+1+1+1+1}

Generating function: Π_{k≥1} 1/(1-xᵏ).

Asymptotic (Hardy-Ramanujan): p(n) ~ (1/(4n√3)) · e^(π√(2n/3)).

The partition function grows sub-exponentially but super-polynomially.

Euler's pentagonal theorem: Π_{k≥1} (1-xᵏ) = Σₖ₌₋∞^∞ (-1)ᵏ x^(k(3k-1)/2), giving an efficient recurrence for p(n).

Recurrence in Algorithm Analysis

Common Recurrences

| Algorithm | Recurrence | Solution | |---|---|---| | Binary search | T(n) = T(n/2) + O(1) | O(log n) | | Merge sort | T(n) = 2T(n/2) + O(n) | O(n log n) | | Quicksort (worst) | T(n) = T(n-1) + O(n) | O(n²) | | Quicksort (average) | T(n) = 2T(n/2) + O(n) | O(n log n) | | Strassen | T(n) = 7T(n/2) + O(n²) | O(n^2.807) | | Karatsuba | T(n) = 3T(n/2) + O(n) | O(n^1.585) | | Tower of Hanoi | T(n) = 2T(n-1) + 1 | 2ⁿ - 1 |

Real-World Applications

Algorithm complexity: Master theorem and recurrence solving are the primary tools for analyzing divide-and-conquer algorithms.
Data structure analysis: Catalan numbers count BST shapes, parenthesizations, and expression trees.
Combinatorial optimization: Generating functions help count feasible solutions.
Compiler design: Catalan numbers arise in counting parse trees and expression evaluations.
Statistical mechanics: Partition functions (related to integer partition numbers) model energy distributions.
Queueing theory: Catalan numbers appear in ballot problems and queue analysis.