Kekkei - Advancing Financial Science For Everyone

Introduction

Generating functions excel at solving problems that seem intractable by direct counting. In this lesson, we apply GFs to integer partitions, coin change, and combinatorial sequences.

Learning Objectives:

Apply GFs to partition problems
Solve coin change using product of GFs
Use GFs for sequence generation

Integer Partitions

A partition of integer $n$ is a way to write $n$ as a sum of positive integers, where order doesn't matter.

Example: Partitions of 4: {4}, {3,1}, {2,2}, {2,1,1}, {1,1,1,1}

GF for partitions: Each part size $k$ can appear 0, 1, 2, ... times:

$P(x) = \prod_{k=1}^{\infty} \frac{1}{1-x^k}$

The coefficient $[x^n] P(x)$ gives the number of partitions of $n$ .

python

def count_partitions(n, max_k=None):
    """Count integer partitions of n using dynamic programming"""
    if max_k is None:
        max_k = n
    
    # dp[i] = number of partitions of i
    dp = [0] * (n + 1)
    dp[0] = 1  # empty partition
    
    # For each part size k
    for k in range(1, min(n, max_k) + 1):
        for i in range(k, n + 1):
            dp[i] += dp[i - k]
    
    return dp[n]

# Count partitions of 4 through 10
print("Integer partitions:")
for n in range(1, 11):
    count = count_partitions(n)
    print(f"  p({n}) = {count}")

Coin Change Problem

Example: Making Change

Using coins of denominations 1¢, 5¢, 10¢, how many ways to make n¢?

GF: Each coin type contributes a factor:

1¢: $1 + x + x^2 + ... = \frac{1}{1-x}$
5¢: $1 + x^5 + x^{10} + ... = \frac{1}{1-x^5}$
10¢: $1 + x^{10} + x^{20} + ... = \frac{1}{1-x^{10}}$

$G(x) = \frac{1}{(1-x)(1-x^5)(1-x^{10})}$

Coefficient of $x^n$ gives the answer.

python

def coin_change_ways(amount, coins):
    """Count ways to make change using dynamic programming"""
    dp = [0] * (amount + 1)
    dp[0] = 1  # one way to make 0
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    
    return dp[amount]

# Ways to make change for various amounts
coins = [1, 5, 10]
amounts = [10, 15, 20, 25, 50]

print(f"Coin change with denominations {coins}:")
for amount in amounts:
    ways = coin_change_ways(amount, coins)
    print(f"  {amount}¢: {ways} ways")

Key Takeaways

Partitions: $P(x) = \prod \frac{1}{1-x^k}$ generates partition numbers
Coin change: Product of GFs for each denomination
Convolution: Multiplication of GFs gives combined counts
DP verification: Dynamic programming confirms GF results

Next Lesson: Exponential Generating Functions for labeled structures!

IntroductionFocusStart Focus Mode

Integer PartitionsFocusStart Focus Mode

Coin Change ProblemFocusStart Focus Mode

Example: Making Change

Key TakeawaysFocusStart Focus Mode

Introduction

Integer Partitions

Coin Change Problem

Key Takeaways