Set Partition — Definition, Formula & Examples

A set partition is a way of splitting a set into non-empty groups (called blocks) where every element belongs to exactly one group and no element is left out.

A partition of a set $S$ is a collection $\{B_1, B_2, \ldots, B_k\}$ of non-empty subsets of $S$ such that $B_i \cap B_j = \emptyset$ for all $i \neq j$ and $B_1 \cup B_2 \cup \cdots \cup B_k = S$ . Each $B_i$ is called a block of the partition.

Key Formula

B_n = \sum_{k=0}^{n} S(n,k)

Where:

$B_n$ = Bell number: total number of partitions of an n-element set
$S(n,k)$ = Stirling number of the second kind: number of partitions of an n-element set into exactly k non-empty blocks
$n$ = Number of elements in the set

How It Works

To partition a set, you assign every element to exactly one block, with no block left empty. Two partitions are considered different if at least one element ends up in a different block. The total number of partitions of an

n

-element set is given by the Bell number

B_n

. For instance,

B_3 = 5

and

B_4 = 15

. The number of partitions of an

n

-element set into exactly

k

non-empty blocks is counted by the Stirling number of the second kind,

S(n, k)

Worked Example

Problem: List all partitions of the set

S = \{1, 2, 3\}

Step 1: Partitions into 1 block (the whole set in one group):

\{\{1, 2, 3\}\}

Step 2: Partitions into 2 blocks (split into two non-empty groups):

\{\{1\}, \{2, 3\}\}, \quad \{\{2\}, \{1, 3\}\}, \quad \{\{3\}, \{1, 2\}\}

Step 3: Partition into 3 blocks (each element alone):

\{\{1\}, \{2\}, \{3\}\}

Answer: There are 5 partitions total, confirming

B_3 = 5

Why It Matters

Set partitions appear in combinatorics proofs, equivalence relation counting, and algorithm design (e.g., clustering). In abstract algebra, partitions of a set correspond one-to-one with equivalence relations on that set, making them central to understanding quotient structures.

Common Mistakes

Mistake: Confusing set partitions with integer partitions. A partition of the integer 3 means writing 3 as a sum (like 2+1), while a partition of the set {1,2,3} means grouping its elements.

Correction: Remember that set partitions care about which specific elements go into each block, not just the sizes of the blocks.