# Partition **The separation of the elements of a [[set]] into non-empty [[Subset|subsets]] such that every element is in exactly one subset.** ![[ParitionSetOf4.svg]] *The 15 possible partitions of a set of 4 elements; all elements not shown in a set are in sets with themselves as the only element* > [!Partition] > A **partition** of a set $X$ is a set of non-empty subsets of $X$ such that every element $x$ in $X$ is in *exactly one* of the subsets. A partition of a set *does not* include the [[Set#^5f880b|empty set]]. The [[union]] of the sets of a partition $P$ of a set $X$ is equal to $X$, that is, $\bigcup_{S\in P} S=X$ The [[intersection]] of any two distinct sets of $P$ is *empty*. ## Enumeration The number of partitions of a set of $n$ elements is called the $n$th *Bell number* $B_{n}$. It can be calculated using the [[Binomial Theorem#Binomial coefficient|binomial coefficient]] in a recurrence relation. $B_{n+1}=\sum_{k=0}^{n}\binom{n}{k}B_{k}$