Partitions of Integers — Mathematics Knowledge System

Overview

A partition of a positive integer n is a way of writing n as a sum of positive integers, where the order of the summands does not matter. The number of partitions of n is denoted p(n); for example p(4)=5 because 4 can be written as 4, 3+1, 2+2, 2+1+1, or 1+1+1+1. Unlike compositions (ordered sums), partitions are unordered, which makes p(n) grow much more slowly and gives it a famously irregular, hard-to-compute closed form — though generating functions provide an elegant way to encode and compute it.

Intuition

Each factor 1/(1-x^k) in Euler's product is the generating function for 'how many parts of size k to use' (0, 1, 2, … copies of k, contributing 0, k, 2k, … to the total). Multiplying all these factors together and looking at the coefficient of xⁿ automatically sums over every way of choosing how many parts of each size to use so that they add to n — exactly a partition. This is why partitions, unlike ordered compositions, connect so naturally to infinite products rather than simple binomial formulas.

Formal Definition

Definition

The partition function p(n) has no simple closed form, but has the classical generating function due to Euler:

\sum_{n=0}^{\infty} p(n)\, x^n = \prod_{k=1}^{\infty} \frac{1}{1-x^k}

Euler's generating function for p(n)

p(n) = p(n,1) + p(n,2) + \cdots + p(n,n)

Sum over partitions with largest part exactly k

Worked Examples

Enumerate every way to write 4 as an unordered sum of positive integers.
$4,\quad 3+1,\quad 2+2,\quad 2+1+1,\quad 1+1+1+1$

Answer: There are 5 partitions, so p(4)=5.

Practice Problems

Difficulty 2/10

What is p(3)? List them.

Difficulty 4/10

What is p(6)?

Difficulty 4/10

How many partitions of 4 have exactly 2 parts?

Quiz

Summary

A partition of n is an unordered way of writing n as a sum of positive integers; p(n) counts them.
Small values: p(1)=1, p(2)=2, p(3)=3, p(4)=5, p(5)=7, p(6)=11.
Euler's generating function ∏ 1/(1-x^k) encodes p(n) as coefficients, since each factor accounts for parts of one size.

References

WebsiteWikipedia — Partition (number theory)