Partition Functions

Combinatorics · Axiom Academy

Using generating functions to study integer partitions and derive fundamental identities 1. The Partition Generating Function To build partitions, we can choose how many 1's to include (0, 1, 2, 3, ...), how many 2's to include (0, 1, 2, 3, ...), and so on for each positive integer. Each choice is independent! The generating function for choosing k copies of the integer m contributes x^(m·k) to the sum. For a fixed m, we can choose 0, 1, 2, ... copies: Since the choices for different integers are independent, we multiply the generating functions together, giving us Euler's famous infinite product formula. 2. Euler's Infinite Product Formula By multiplying the geometric series for each positive integer, we obtain the remarkable infinite product representation of the partition generating function: This formula encodes all partition counts! The coefficient of x^n in this infinite product equals p(n), the number of partitions of n. 3. Fundamental Partition Identities Generating functions reveal beautiful partition identities. One classic result compares partitions into distinct parts versus partitions into odd parts. For distinct parts, we can use each integer 0 or 1 times. For odd parts, we can use each odd integer any number of times. Let's see how the generating functions match:

This is the written version of the interactive lesson above. See the full Combinatorics course.