Partitions Into Distinct Parts

Summary: A partition of $n$ into distinct (unequal) parts uses each positive integer at most once. The generating function is $\prod_{k \geq 1} (1 + x^{k} z)$ , with $z$ tracking the number of parts. Chapter 16 derives closed-form recurrent series for the number of partitions with exactly $m$ distinct parts (numerator $x^{m (m + 1) /2}$ , denominator $\prod_{k = 1}^{m} (1 - x^{k})$ ) and proves the staircase bijection $q_{m} (n) = p_{m} (n - m (m - 1) /2)$ between distinct and unrestricted partitions.

Sources: chapter16

Last updated: 2026-05-11

Definition

A partition of $n$ into distinct parts is an unordered tuple $a_{1} > a_{2} > \dots > a_{m} \geq 1$ with $\sum a_{i} = n$ . Write $q_{m} (n)$ for the number of such partitions with exactly $m$ parts and $q (n) = \sum_{m} q_{m} (n)$ for the total.

Enumerations (Chapter 16)

For $n = 8$ (source: chapter16, §301), $q (8) = 6$ :

$8 = 8 = 7 + 1 = 6 + 2 = 5 + 3 = 5 + 2 + 1 = 4 + 3 + 1.$

For $n = 9$ (§325), $q (9) = 8$ :

$9 = 9 = 6 + 2 + 1 = 8 + 1 = 5 + 4 = 7 + 2 = 5 + 3 + 1 = 6 + 3 = 4 + 3 + 2.$

For $n = 35$ with exactly $m = 7$ distinct parts (§300), $q_{7} (35) = 15$ .

Generating function (§297, §301)

$\prod_{k \geq 1} (1 + x^{k} z) = \sum_{n, m \geq 0} q_{m} (n) x^{n} z^{m} .$

At $z = 1$ :

$\prod_{k \geq 1} (1 + x^{k}) = \sum_{n} q (n) x^{n} = 1 + x + x^{2} + 2 x^{3} + 2 x^{4} + 3 x^{5} + 4 x^{6} + 5 x^{7} + 6 x^{8} + 8 x^{9} + 10 x^{10} + 12 x^{11} + \dots .$

Closed-form recurrent series for each $q_{m}$ (§307–§312)

Let $Z = \prod_{k \geq 1} (1 + x^{k} z) = 1 + P z + Q z^{2} + R z^{3} + S z^{4} + T z^{5} + \dots$ . Substituting $x z$ for $z$ removes the $k = 1$ factor:

$Z (x, x z) = \frac{Z ( x , z )}{1 + x z} .$

Expanding and matching coefficients of $z^{m}$ yields the recursion $P_{m} (1 - x^{m}) = x^{m} P_{m - 1}$ , hence

$P = \frac{x}{1 - x}, Q = \frac{x ^{3}}{( 1 - x ) ( 1 - x ^{2} )}, R = \frac{x ^{6}}{( 1 - x ) ( 1 - x ^{2} ) ( 1 - x ^{3} )},$

$S = \frac{x ^{10}}{( 1 - x ) ( 1 - x ^{2} ) ( 1 - x ^{3} ) ( 1 - x ^{4} )}, T = \frac{x ^{15}}{( 1 - x ) ( 1 - x ^{2} ) ( 1 - x ^{3} ) ( 1 - x ^{4} ) ( 1 - x ^{5} )} .$

The numerator exponents $1, 3, 6, 10, 15, 21, \dots$ are the triangular numbers $m (m + 1) /2$ (§312). In general

$P_{m} = \frac{x ^{m (m + 1) /2}}{\prod _{k = 1}^{m} ( 1 - x ^{k} )} .$

Each is a recurrent series with scale given by $\prod_{k = 1}^{m} (1 - x^{k})$ .

The staircase bijection (§312, §315)

Two equivalent forms appear:

Form A (Euler §312, by inspection of the recurrent series): The denominator $1/ \prod_{k = 1}^{m} (1 - x^{k})$ is the generating function for partitions of any integer into parts $\leq m$ . The numerator $x^{m (m + 1) /2}$ shifts the indexing, so

$q_{m} (N) = # {partitions of N - m (m + 1) /2 into parts \leq m} .$

Equivalently: $q_{m} (n + m (m + 1) /2) = p_{m} (n)$ .

Form B (Euler §315, derived from the unrestricted closed form): rephrased in terms of partitions of $n$ into exactly $m$ parts,

$q_{m} (n) = p_{m} (n - \frac{m ( m - 1 )}{2}) .$

Bijective interpretation: from a distinct partition $a_{1} > a_{2} > \dots > a_{m} \geq 1$ , subtract the staircase $0, 1, 2, \dots, (m - 1)$ to obtain $b_{i} = a_{i} - (m - i)$ :

$b_{1} \geq b_{2} \geq \dots \geq b_{m} \geq 1, \sum b_{i} = n - (2 m) .$

The map is invertible (add the staircase back), so it is a bijection between $m$ -distinct partitions of $n$ and $m$ -unrestricted partitions of $n - m (m - 1) /2$ . Euler does not give the bijection — he proves the identity algebraically — but the algebraic identity is the modern bijection in disguise.

Worked numerical examples (§318)

$q_{7} (50)$ = number of partitions of $50$ into $7$ unequal numbers = (using the table) $p_{7} (50 - 28) = p_{7} (22) = 522$ .
Equivalently, by Form A: $q_{7} (50) = p_{\leq 7} (50 - 28) = p_{\leq 7} (22) = 522$ .

Connection to $q (n)$ via the pentagonal theorem (§327)

Summing $q_{m}$ over all $m$ gives $q (n) = \sum_{m} q_{m} (n)$ . Euler computes the values of $q (n)$ directly from

$Q = \prod (1 + x^{k}) = \frac{\prod ( 1 - x ^{2 k} )}{\prod ( 1 - x ^{k} )} = \frac{1}{P} \cdot \prod_{k \geq 1} (1 - x^{2 k}),$

where $1/ P = \sum p (n) x^{n}$ and the second factor is the pentagonal-number expansion at $x^{2}$ : $\prod (1 - x^{2 k}) = 1 - x^{2} - x^{4} + x^{10} + x^{14} - x^{24} - x^{30} + \dots$ . The product of these two known series gives

$Q = 1 + x + x^{2} + 2 x^{3} + 2 x^{4} + 3 x^{5} + 4 x^{6} + 5 x^{7} + 6 x^{8} + 8 x^{9} + \dots .$

See eulers-pentagonal-number-theorem for the expansion of $\prod (1 - x^{k})$ used here.

Quartz 4

Explorer

partitions-into-distinct-parts

Partitions Into Distinct Parts

Definition

Enumerations (Chapter 16)

Generating function (§297, §301)

Closed-form recurrent series for each $q_{m}$ (§307–§312)

The staircase bijection (§312, §315)

Worked numerical examples (§318)

Connection to $q (n)$ via the pentagonal theorem (§327)

Graph View

Table of Contents

Backlinks

Quartz 4

Explorer

partitions-into-distinct-parts

Partitions Into Distinct Parts

Definition

Enumerations (Chapter 16)

Generating function (§297, §301)

Closed-form recurrent series for each qm​ (§307–§312)

The staircase bijection (§312, §315)

Worked numerical examples (§318)

Connection to q(n) via the pentagonal theorem (§327)

Related pages

Graph View

Table of Contents

Backlinks

Closed-form recurrent series for each $q_{m}$ (§307–§312)

Connection to $q (n)$ via the pentagonal theorem (§327)