Ordinary Generating Functions

Learn to encode sequences as power series and solve counting problems algebraically.

24 min read
Intermediate

Introduction

Generating functions transform counting problems into algebra. Instead of counting directly, we encode sequences as power series, manipulate them algebraically, and extract answers by reading coefficients. It's a powerful technique that solves problems beyond basic combinatorics.

Learning Objectives:

  • Understand ordinary generating functions (OGFs)
  • Convert counting problems into power series
  • Extract coefficients to solve counting questions
  • Perform basic operations on generating functions

What Is a Generating Function?

For a sequence a0,a1,a2,a3,...a_0, a_1, a_2, a_3, ..., the ordinary generating function is the formal power series:

G(x)=โˆ‘n=0โˆžanxn=a0+a1x+a2x2+a3x3+โ‹ฏG(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots

The coefficient of xnx^n is ana_n, written as [xn]G(x)=an[x^n] G(x) = a_n.

Key insight: The GF "generates" the sequence by encoding it in polynomial form.

Example 1: Constant Sequence

Sequence: 1,1,1,1,...1, 1, 1, 1, ... (all terms equal 1)

G(x)=1+x+x2+x3+โ‹ฏ=โˆ‘n=0โˆžxnG(x) = 1 + x + x^2 + x^3 + \cdots = \sum_{n=0}^{\infty} x^n

Closed form (geometric series):

G(x)=11โˆ’xforย โˆฃxโˆฃ<1G(x) = \frac{1}{1-x} \quad \text{for } |x| < 1

Verification: Multiply both sides by (1โˆ’x)(1-x):

(1โˆ’x)โ‹…G(x)=(1โˆ’x)(1+x+x2+โ‹ฏโ€‰)=1(1-x) \cdot G(x) = (1-x)(1 + x + x^2 + \cdots) = 1

python
import numpy as np
import matplotlib.pyplot as plt

# Demonstrate geometric series approximation
def partial_sum_geometric(n_terms, x_val):
    """Compute partial sum of geometric series"""
    return sum(x_val**n for n in range(n_terms))

def closed_form(x_val):
    """Closed form: 1/(1-x)"""
    if abs(x_val) < 1:
        return 1 / (1 - x_val)
    else:
        return float('inf')

# Test for x = 0.5
x = 0.5
terms_list = [5, 10, 20, 50]

print(f"Geometric series for x = {x}:")
print(f"Closed form: 1/(1-x) = 1/(1-{x}) = {closed_form(x):.6f}")
print(f"\nPartial sums:")
for n in terms_list:
    partial = partial_sum_geometric(n, x)
    print(f"  {n} terms: {partial:.6f}  (error: {abs(partial - closed_form(x)):.6f})")

# Show coefficients
print(f"\nFirst 10 coefficients (all = 1):")
coefficients = [1] * 10
print(f"  {coefficients}")

Extracting Coefficients

The power of GFs: solve for G(x)G(x) algebraically, then extract the coefficient of xnx^n.

Example 2: Powers of 2

Sequence: 1,2,4,8,16,...1, 2, 4, 8, 16, ... (i.e., 2n2^n)

G(x)=1+2x+4x2+8x3+โ‹ฏ=โˆ‘n=0โˆž2nxnG(x) = 1 + 2x + 4x^2 + 8x^3 + \cdots = \sum_{n=0}^{\infty} 2^n x^n

Factor out powers of 2:

G(x)=โˆ‘n=0โˆž(2x)n=11โˆ’2xG(x) = \sum_{n=0}^{\infty} (2x)^n = \frac{1}{1-2x}

Check: [x3]11โˆ’2x=23=8[x^3] \frac{1}{1-2x} = 2^3 = 8 โœ“

python
# Verify coefficient extraction
def extract_coefficient_geometric(a, n):
    """
    For G(x) = 1/(1-ax), the coefficient of x^n is a^n
    """
    return a**n

# Test: G(x) = 1/(1-2x)
a = 2
test_n = [0, 1, 2, 3, 4, 5, 10]

print("G(x) = 1/(1-2x)")
print("\nCoefficient of x^n (equals 2^n):")
for n in test_n:
    coef = extract_coefficient_geometric(a, n)
    print(f"  [x^{n}]: {coef}")

# Verify with polynomial expansion (first few terms)
print("\nExpanded form (first 6 terms):")
expansion = [2**n for n in range(6)]
print(f"  {' + '.join(f'{c}x^{i}' if i > 0 else str(c) for i, c in enumerate(expansion))}")

Operations on Generating Functions

Addition

If F(x)=โˆ‘anxnF(x) = \sum a_n x^n and G(x)=โˆ‘bnxnG(x) = \sum b_n x^n, then:

F(x)+G(x)=โˆ‘(an+bn)xnF(x) + G(x) = \sum (a_n + b_n) x^n

Example: GF for an=1a_n = 1 and bn=nb_n = n:

F(x)=11โˆ’x,G(x)=x(1โˆ’x)2F(x) = \frac{1}{1-x}, \quad G(x) = \frac{x}{(1-x)^2}

F(x)+G(x)=11โˆ’x+x(1โˆ’x)2F(x) + G(x) = \frac{1}{1-x} + \frac{x}{(1-x)^2}

Multiplication (Convolution)

F(x)โ‹…G(x)=โˆ‘n=0โˆž(โˆ‘k=0nakbnโˆ’k)xnF(x) \cdot G(x) = \sum_{n=0}^{\infty} \left( \sum_{k=0}^{n} a_k b_{n-k} \right) x^n

The coefficient of xnx^n is the convolution: โˆ‘k=0nakbnโˆ’k\sum_{k=0}^{n} a_k b_{n-k}.

Binomial Series

The binomial series generalizes (1+x)n(1+x)^n to non-integer exponents:

(1+x)ฮฑ=โˆ‘k=0โˆž(ฮฑk)xk(1+x)^\alpha = \sum_{k=0}^{\infty} \binom{\alpha}{k} x^k

where (ฮฑk)=ฮฑ(ฮฑโˆ’1)โ‹ฏ(ฮฑโˆ’k+1)k!\binom{\alpha}{k} = \frac{\alpha (\alpha-1) \cdots (\alpha-k+1)}{k!} (generalized binomial coefficient).

Key cases:

  1. 11โˆ’x=(1โˆ’x)โˆ’1=โˆ‘n=0โˆžxn\frac{1}{1-x} = (1-x)^{-1} = \sum_{n=0}^{\infty} x^n (coefficients: all 1)

  2. 1(1โˆ’x)2=โˆ‘n=0โˆž(n+1)xn\frac{1}{(1-x)^2} = \sum_{n=0}^{\infty} (n+1) x^n (coefficients: 1,2,3,4,...1, 2, 3, 4, ...)

  3. 1(1โˆ’x)k=โˆ‘n=0โˆž(n+kโˆ’1kโˆ’1)xn\frac{1}{(1-x)^k} = \sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n

python
from scipy.special import comb

# Verify 1/(1-x)^2 = sum of (n+1)x^n
def verify_binomial_series(k, max_n):
    """
    Verify that coefficient of x^n in 1/(1-x)^k is C(n+k-1, k-1)
    """
    print(f"Coefficients of 1/(1-x)^{k}:")
    print(f"Formula: C(n+k-1, k-1) = C(n+{k-1}, {k-1})\n")

    for n in range(max_n):
        coef = int(comb(n + k - 1, k - 1, exact=True))
        print(f"  [x^{n}]: C({n + k - 1}, {k - 1}) = {coef}")

    return

# Test for k=2: 1/(1-x)^2
print("Case 1: 1/(1-x)^2")
verify_binomial_series(k=2, max_n=8)

print("\n" + "="*50)
print("\nCase 2: 1/(1-x)^3")
verify_binomial_series(k=3, max_n=8)

Solving a Counting Problem

Example 3: Number of Non-Negative Integer Solutions

How many solutions to x1+x2+x3=nx_1 + x_2 + x_3 = n where xiโ‰ฅ0x_i \geq 0?

GF approach: Each variable can be 0, 1, 2, 3, ..., so:

Gx1(x)=1+x+x2+x3+โ‹ฏ=11โˆ’xG_{x_1}(x) = 1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}

Same for x2x_2 and x3x_3. The product gives solutions:

G(x)=(11โˆ’x)3=1(1โˆ’x)3G(x) = \left( \frac{1}{1-x} \right)^3 = \frac{1}{(1-x)^3}

Coefficient of xnx^n:

[xn]1(1โˆ’x)3=(n+22)[x^n] \frac{1}{(1-x)^3} = \binom{n+2}{2}

For n=5n=5: (72)=21\binom{7}{2} = 21 โœ“ (matches stars and bars!)

python
from scipy.special import comb

def count_solutions_gf(n, k):
    """
    Count non-negative integer solutions to x1 + x2 + ... + xk = n
    using generating functions
    """
    # Coefficient of x^n in 1/(1-x)^k
    return int(comb(n + k - 1, k - 1, exact=True))

# Test: x1 + x2 + x3 = 5
n = 5
k = 3

result = count_solutions_gf(n, k)

print(f"Solutions to x1 + x2 + x3 = {n} (xi โ‰ฅ 0):")
print(f"\nGenerating function: (1/(1-x))^{k} = 1/(1-x)^{k}")
print(f"Coefficient of x^{n}: C({n}+{k}-1, {k}-1) = C({n+k-1}, {k-1}) = {result}")
print(f"\nVerification with stars and bars: {result}")

Key Takeaways

  1. OGF: Encodes sequence {an}\{a_n\} as G(x)=โˆ‘anxnG(x) = \sum a_n x^n
  2. Geometric series: 11โˆ’ax=โˆ‘anxn\frac{1}{1-ax} = \sum a^n x^n
  3. Extraction: [xn]G(x)[x^n] G(x) gives the nn-th coefficient
  4. Operations: Add GFs (term-wise), multiply (convolution)
  5. Binomial series: 1(1โˆ’x)k=โˆ‘(n+kโˆ’1kโˆ’1)xn\frac{1}{(1-x)^k} = \sum \binom{n+k-1}{k-1} x^n

Next Lesson: Applications to integer partitions, coin change, and more!

GF
Sequence
Closed Form
$\sum x^n$$1, 1, 1, ...$$\frac{1}{1-x}$
$\sum 2^n x^n$$1, 2, 4, 8, ...$$\frac{1}{1-2x}$
$\sum (n+1) x^n$$1, 2, 3, 4, ...$$\frac{1}{(1-x)^2}$
$\sum \binom{n+k-1}{k-1} x^n$Stars & bars$\frac{1}{(1-x)^k}$
๐ŸŽฒ

Combinatorics and Probability: From Counting to Inference

Master the mathematical foundations of counting, probability, and randomness. This comprehensive course bridges pure combinatorics with computational probability, covering everything from basic counting principles to advanced probabilistic methods, limit theorems, and real-world applications in algorithms, finance, and data science.